ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR12-136 | 11th September 2013 17:52

Quantum-Secure Message Authentication Codes

RSS-Feed




Revision #2
Authors: Dan Boneh, Mark Zhandry
Accepted on: 11th September 2013 17:52
Downloads: 200
Keywords: 


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.


Revision #1 to TR12-136 | 11th March 2013 02:01

Quantum-Secure Message Authentication Codes





Revision #1
Authors: Dan Boneh, Mark Zhandry
Accepted on: 11th March 2013 02:01
Downloads: 235
Keywords: 


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.


Paper:

TR12-136 | 26th October 2012 17:40

Quantum-Secure Message Authentication Codes





TR12-136
Authors: Dan Boneh, Mark Zhandry
Publication: 26th October 2012 18:17
Downloads: 653
Keywords: 


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.



ISSN 1433-8092 | Imprint