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

Date: received 25 Nov 2018

Contact author: c majenz at uva nl

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2018/1150

[ Cryptology ePrint archive ]