Cryptology ePrint Archive: Report 2018/1150

Quantum-secure message authentication via blind-unforgeability

Gorjan Alagic and Christian Majenz and 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.

Category / Keywords: foundations / quantum, quantum access model, unforgeability, MAC

Original Publication (with minor differences): IACR-EUROCRYPT-2020

Date: received 25 Nov 2018, last revised 3 Jul 2020

Contact author: christian majenz at cwi nl

Available format(s): PDF | BibTeX Citation

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

Version: 20200703:073023 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]