Engineering / Mathematics — Discrete Probability
Message Authentication with Hash Functions
Unconditionally secure message authentication from universal hash families, and how forgery probability is bounded.
Executive summary
A message authentication code lets a receiver verify that a message came from a party holding a shared key. Built from a universal hash family, the forgery probability is bounded unconditionally rather than by a computational assumption.
The construction is simple and the security argument is a direct application of the family's collision bound.
Learning objectives
- Describe the construction of a MAC from a hash family.
- Bound the forgery probability.
- Explain the one-time restriction and its remedy.
01The construction
Share a key
Sender and receiver agree on a key k selecting h_k from a universal family, kept secret.
Authenticate
The sender transmits the message m together with the tag t = h_k(m).
Verify
The receiver recomputes h_k(m) and accepts only if it matches the received tag.
An adversary who does not know k must guess the tag for a message of their choosing. The family's collision property bounds the chance of guessing correctly.
02Forgery probability
Forgery bound
Against an adversary who has seen no valid tag, the probability of producing a valid tag for a chosen message is at most 1/|R| where R is the tag space.
With a pairwise independent family the guarantee extends to an adversary who has seen exactly one valid message-tag pair: the tag on any different message remains uniformly distributed from their view, so the forgery probability is still 1/|R|.
03Beyond one use
Two standard routes extend the construction to many messages, and they make different trade-offs.
| Approach | Security basis | Cost |
|---|---|---|
| Fresh key per message | Unconditional | Key material grows with message count |
| Universal hash then encrypt tag | Unconditional hash, computational cipher | One nonce and one block cipher call per message |
| Keyed cryptographic hash | Computational | Reusable key; no per-message key material |
The middle row is the design used by widely deployed constructions: a fast universal hash compresses the message, and a block cipher masks the resulting tag under a nonce. The unconditional collision bound carries the message-length-dependent security while the cipher supplies key reuse.
04Frequently asked questions
Why is unconditional security possible here but not for encryption?
Because the adversary must produce a specific correct value rather than distinguish, and the tag space can be made small relative to the key. It is the same reason one-time pads achieve unconditional secrecy: the guarantee holds only while key material is not reused.
Is a MAC the same as a digital signature?
No. A MAC uses a shared key, so either party could have produced the tag and it gives no non-repudiation. A signature uses a private key and can be verified by anyone holding the public key.
Does message length affect security?
Yes for polynomial-evaluation families, where the forgery bound degrades linearly in the number of message blocks, since a difference polynomial of higher degree has more roots. Tag size must be chosen with the maximum message length in mind.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 128-130.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.