Date Added: Oct 2012
The authors 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. They 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, they show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, they present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but they prove that a four-wise independent family is sufficient for one-time security.