Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Quantum computing, MAC, chosen message attacks, post-quantum security

Original Publication (with major differences): IACR-EUROCRYPT-2013

Date: received 26 Oct 2012, last revised 11 Sep 2013

Contact author: mzhandry at stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20130911:155107 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]