### 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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2018/1150

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.