Paper 2018/1150

Quantum-secure message authentication via blind-unforgeability

Gorjan Alagic, University of Maryland, College Park
Christian Majenz, Technical University of Denmark
Alexander Russell, University of Connecticut
Fang Song, Portland State University
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 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: Erratum added. We removed a result that had an error in its proof.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
DOI
10.1007/978-3-030-45727-3_27
Keywords
quantumquantum access modelunforgeabilityMAC
Contact author(s)
galagic @ gmail com
chmaj @ dtu dk
alexander russell @ uconn edu
crissong @ gmail com
History
2023-04-20: last of 2 revisions
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1150,
      author = {Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song},
      title = {Quantum-secure message authentication via blind-unforgeability},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1150},
      year = {2018},
      doi = {10.1007/978-3-030-45727-3_27},
      note = {\url{https://eprint.iacr.org/2018/1150}},
      url = {https://eprint.iacr.org/2018/1150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.