



@article {2308,
	title = {Quantum-secure message authentication via blind-unforgeability},
	year = {2018},
	abstract = {<p><span style="color: rgb(51, 51, 51); font-family: \&quot;Open Sans\&quot;, \&quot;Lucida Grande\&quot;, \&quot;Helvetica Neue\&quot;, Helvetica, Arial, sans-serif; font-size: 14px;">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 \&quot;predicting an unqueried value\&quot; 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 \&quot;blind-unforgeability\&quot; (or BU.) This notion matches \&quot;intuitive unpredictability\&quot; in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use \&quot;partially blinded\&quot; 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 \&quot;Bernoulli-preserving\&quot; 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.\&nbsp;</span></p>},
	url = {https://arxiv.org/abs/1803.03761},
	author = {Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song}
}
