1202.1229 (Christopher Portmann)

Key recycling in authentication    [PDF]

Christopher Portmann

In their seminal work on authentication, Wegman and Carter propose that to
authenticate multiple messages, it is sufficient to reuse the same hash
function as long as each tag is encrypted with a one-time pad. They argue that
because the one-time pad is perfectly hiding, the hash function used remains
completely unknown to the adversary.
Since their proof is not composable, we revisit it using a universally
composable framework. It turns out that the above argument is insufficient:
information about the hash function is in fact leaked in every round to the
adversary, and after a bounded finite amount of rounds it is completely known.
We show however that this leak is very small, and Wegman and Carter's protocol
is still \epsilon-secure, if \epsilon-almost strongly universal hash functions
are used.
This implies that the secret key corresponding to the choice of hash function
can be recycled for any task without any additional error than this \epsilon.
For example, if all the messages from many rounds of quantum key distribution
are authenticated in this way, the error increases linearly in the number of
rounds.

View original: http://arxiv.org/abs/1202.1229