Paper 2012/058

Key recycling in authentication

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$. We illustrate this by applying it to quantum key distribution (QKD): if the same hash function is recycled to authenticate the classical communication in every round of a QKD protocol, and used $\ell$ times per round, the total error after $r$ rounds is upper bounded by $r(\ell\epsilon+\epsilon')$, where $\epsilon'$ is the error of one round of QKD given an authentic channel.

Note: Corrected typos, updated introduction and references.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
chportma @ gmail com
2012-05-31: revised
2012-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christopher Portmann},
      title = {Key recycling in authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2012/058},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.