Paper 2018/1150

Quantum-secure message authentication via blind-unforgeability

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


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

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
quantumquantum access modelunforgeabilityMAC
Contact author(s)
christian majenz @ cwi nl
2020-07-03: revised
2018-12-03: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.