@article {2628, title = {Quantum-Access-Secure Message Authentication via Blind-Unforgeability}, journal = {In: Canteaut A., Ishai Y. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham}, volume = {12-17}, year = {2020}, month = {5/1/2020}, pages = {788-817 }, type = {inproceedings}, abstract = {

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 strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT \’13, CRYPTO \’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.

}, doi = {https://doi.org/10.1007/978-3-030-45727-3_27}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song} }