## CryptoDB

### Paper: Quantum-access-secure message authentication via blind-unforgeability

Authors: Gorjan Alagic , QuICS, University of Maryland, NIST Christian Majenz , QuSoft and Centrum Wiskunde & Informatica, Amsterdam, The Netherlands Alexander Russell , Department of Computer Science and Engineering, University of Connecticut Fang Song , Department of Computer Science and Engineering, University of Connecticut DOI: 10.1007/978-3-030-45727-3_27 (login may be required) Search ePrint Search Google Slides EUROCRYPT 2020 Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a 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. In this setting, 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.
##### BibTeX
@inproceedings{eurocrypt-2020-30239,
title={Quantum-access-secure message authentication via blind-unforgeability},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={Quantum access;quantum-secure;message authentication;query complexity},
volume={12105},
doi={10.1007/978-3-030-45727-3_27},
author={Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song},
year=2020
}