Paper 2020/291

Unforgeability in the quantum world

Myrto Arapinis, Mahshid Delavar, Mina Doosti, and Elham Kashefi

Abstract

Defining unforgeability and designing cryptographic primitives that provide unforgeability in the quantum setting, i.e. where the adversary has quantum capabilities including quantum oracle access to the primitive, has proven to be a hard challenge. The classical notions and techniques do not transpose directly to the quantum setting. In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries specifically for Message Authentication Codes and Digital Signatures schemes. We develop a general and parameterized quantum game-based security framework for both classical and quantum primitives modelled by unitary transformations. We provide general possibility and impossibility results for such primitives. In particular, we show that no unitary primitive can provide existential unforgeability against quantum adversaries. Our main impossibility result relies on a new and generic quantum attack. We demonstrate this attack both on classical and quantum primitives to show its applicability as well as the completeness of our definitions of security. On the other hand, we show that selective unforgeability is satisfied by a specific class of unitaries that we term unknown unitaries.