Quantum-Access-Secure Message Authentication via Blind-Unforgeability

Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of "predicting an unqueried value" when the adversary can query in quantum superposition.

We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the "hash-and-MAC" paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving.

Finally, we demonstrate that blind unforgeability is stronger than a previous definition of Boneh and Zhandry [EUROCRYPT '13, CRYPTO '13] in the sense that we can construct an explicit function family which is forgeable by an attack that is recognized by blind-unforgeability, yet satisfies the definition by Boneh and Zhandry.

Note: An earlier version of this article contained a theorem that the new security notion "blindunforgeability" (BU) we introduce implies the notion of "plus-one" unforgeability (PO) that was hitherto the only proposed generalization of EUF-CMA to > 1 quantum chosen-message queries. Unfortunately the proof contained an error. We thank Shih-Han Hung for discovering the error. We have now removed the claim and the question whether the implication holds is currently open. We would like to emphasize that the example presented in Section 8 disqualifies PO as a quantum-access generalization of EUF-CMA, so currently there are two reasonable possible definitions of "quantum-access EUF-CMA": the notion of blind-unforgeability proposed in this article, and its conjunction with plus-one unforgeability.