A tag has a different job from encryption
An authentication tag lets a receiver test whether a message is consistent with a shared secret key. It does not necessarily hide the message. We study an intentionally small one-time experiment, prove its exact substitution probability and see why its assumptions matter.
Definition 11.1.1
(One-time affine tag scheme)
Let be prime, and use for messages, tags and key components. The sender and receiver share a uniformly random secret pair , independently of the fixed message . For this one use, the sender publishes and
The receiver accepts a purported pair exactly when . All operations are in . Both key components range over the whole field, including zero.
The attack model provides the adversary with one authentic pair and then one verification attempt for a different message; there are no earlier observations or verification feedback under this key.
The exact one-attempt bound
Theorem 11.1.2
(Substituting a different message)
After observing , an adversary chooses any and a tag , possibly as functions of the observation and of private randomness independent of the key. The probability that the receiver accepts is exactly .
Proof
(Conditioning on the observed tag)
Fix the observed value . For each of the choices of , exactly one produces that observation. Since the original key pairs were uniform, all these remaining keys are equally likely. For a fixed choice of ,
The difference is nonzero and hence invertible, so as runs over the field this expression takes every tag value exactly once. Conditional on the observation, the correct tag for is uniform. Thus any proposed succeeds with probability . The argument holds for every observation and every different selected from it; averaging also covers the adversary's independent random choices.
The proof has two ingredients, and it is worth separating them before using the result.
Proof X-ray
What is random after the observation?
Uniformity of and its independence from are used once: they make the keys consistent with the observation equally likely, parametrized by alone. The public tag removes one degree of freedom of the key and leaves the other untouched.
The key move is the rewriting , which expresses the unknown target tag through the one remaining unknown. The hypothesis is used exactly here, together with the primality of : a nonzero element of a field is invertible, so is a bijection of and pushes the uniform to a uniform tag. Over with , the values are only and , each with probability , so a forger would succeed with probability instead of .
The argument closes pointwise: the bound holds for each observation and each chosen from it, so it survives any adaptive or randomized choice of by averaging, provided the adversary's randomness is independent of the key.
Worked example 11.1.3
(A small field and an observed tag)
Take , and suppose the key is , . For , the authentic tag is . An observer who sees only cannot determine : for each , the key is consistent. For a substituted message , its valid tag is ; as ranges over the field, this takes all seven values. A single guessed tag succeeds with probability . The displayed key is revealed here solely to check arithmetic; a real key is secret.
Worked example 11.1.4
(Copying the observed tag)
Keep and the observation . A forger might submit the new message with the old tag . The correct tag for is when , and
because is invertible modulo seven. Among the seven equally likely consistent keys , only accepts the copied tag, so the success probability is , as the theorem predicts. The edge case is the key under which the tag ignores the message; it is allowed, and it is exactly what this strategy bets on.
The definition lets take the value zero. Excluding it looks like a harmless way to make every tag depend on the message, but it changes the exact bound.
Worked example 11.1.5
(Forbidding the zero key component)
Suppose instead that is uniform on and is uniform on , independently, so there are keys. After observing , each still has exactly one consistent , so is uniform on the nonzero values. For , the target tag then takes every value except , each with probability . A forger who submits any succeeds with probability , which is larger than ; with it is . Copying the tag now never works, but the best attack has improved.
Reuse breaks the experiment
Counterexample mode
Two pairs reveal this key
Suppose the same key authenticates distinct messages with tags , and both pairs are observed. Then
The denominator is invertible because the messages differ. For the example, a second authentic pair gives and modulo seven. The observer can then compute the tag for every field message, such as for message . The one-observation theorem does not apply to this two-observation experiment.
Common mistake
(Reading the bound as a guarantee against replay or repeated guessing)
The theorem concerns one attempt on a message . Replaying the authentic pair is accepted with probability , so the scheme supplies no freshness guarantee. Repeated verification attempts are also outside the statement: each rejection tells the adversary which keys are excluded, and a separate analysis is needed.
The message is public and is not encrypted. A real system needs secure key establishment, replay protection, appropriate key handling and a reviewed authentication scheme; this tiny example is not an implementation recommendation.
Exercises
Quick check
(With , , , find the tags of messages and .)
Compute and reduce modulo seven.
Solution · Answer
and , so the tags are and modulo seven.
Quick check
(Given one observed pair , how many keys remain possible, and what is for each possible ?)
Solve for .
Solution · Answer
There are equally likely keys: for each the observation forces .
Quick check
(Why does the proof require ?)
Look at the factor multiplying in the target tag.
Solution · Answer
Then is nonzero and invertible, so the target tag is uniform as varies. For the target tag is the observed , already known to the adversary.
Quick check
(What changes if two distinct message-tag pairs made with the same key become public?)
Subtract the two tag equations.
Solution · Answer
The difference gives , which determines because is invertible; either pair then determines , and the adversary can compute the tag of every message.
Further reading
MIT lecture notes on universal hashing discuss pairwise-independent affine maps. UC Berkeley notes on message authentication discuss broader authentication constructions.