Paper 2012/606

Quantum-Secure Message Authentication Codes

Dan Boneh and Mark Zhandry

Abstract

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2013
Keywords
Quantum computingMACchosen message attackspost-quantum security
Contact author(s)
mzhandry @ stanford edu
History
2013-09-11: last of 4 revisions
2012-10-29: received
See all versions
Short URL
https://ia.cr/2012/606
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/606,
      author = {Dan Boneh and Mark Zhandry},
      title = {Quantum-Secure Message Authentication Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2012/606},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/606}},
      url = {https://eprint.iacr.org/2012/606}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.