Paper 2018/1150

Quantum-secure message authentication via blind-unforgeability

Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song

Abstract

Formulating and designing unforgeable authentication of classical messages in the presence of quantum adversaries 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. In this work, we uncover serious shortcomings in existing approaches, and propose a new definition. We then support its viability by a number of constructions and characterizations. Specifically, we demonstrate a function which is secure according to the existing definition by Boneh and Zhandry, but is clearly vulnerable to a quantum forgery attack, whereby a query supported only on inputs that start with $0$ divulges the value of the function on an input that starts with $1$. We then propose a new definition, which we call ``blind-unforgeability'' (or BU.) This notion matches ``intuitive unpredictability'' in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use ``partially blinded'' oracle access to predict values in the blinded region. Our definition (BU) coincides with standard unpredictability (EUF-CMA) in the classical-query setting. We show that quantum-secure pseudorandom functions are BU-secure MACs. In addition, we show that BU satisfies a composition property (Hash-and-MAC) using ``Bernoulli-preserving'' hash functions, a new notion which may be of independent interest. Finally, we show that BU is amenable to security reductions by giving a precise bound on the extent to which quantum algorithms can deviate from their usual behavior due to the blinding in the BU security experiment.

Note: Published version, with one correction in the summary of results

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)
christian majenz @ cwi nl
History
2020-07-03: revised
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.