Céline Chevalier

Indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) is usually considered the most desirable security notion for classical encryption. In this work, we investigate its adaptation in the quantum world, when an adversary can perform superposition queries. The security of quantum-secure classical encryption has first been studied by Boneh and Zhandry (CRYPTO'13), but they restricted the adversary to classical challenge queries, which makes the indistinguishability only hold for classical messages (IND-qCCA2). In this work, we give the first security notions for fully quantum indistinguishability under quantum adaptive chosen-ciphertext attacks, where the indistinguishability holds for superposition of plaintexts (qIND-qCCA2). This resolves an open problem asked by Gagliardoni et al. (CRYPTO'16). The qCCA2 security is defined in Boneh-Zhandry's paper using string copying and comparison, which is inherent in the classical setting. Quantumly, it is unclear what it means for a ciphertext to be different from the challenge ciphertext, and how the challenger can check the equality. The classical approach would either violate the no-cloning theorem or lead to perturbing the adversary's state, which may be detectable. To remedy these problems, from the recent groundbreaking compressed oracle technique introduced by Zhandry (CRYPTO'19), we develop a generic framework that allows to record quantum queries for probabilistic functions. We then give definitions for fully quantum real-or-random indistinguishability under adaptive chosen-ciphertext attacks (qIND-qCCA2). In the symmetric setting, we show that various classical modes of encryption are trivially broken in our security notions. We then provide the first formal proof for quantum security of the Encrypt-then-MAC paradigm, which also answers an open problem posed by Boneh and Zhandry. In the public-key setting, we show how to achieve these stronger security notions (qIND-qCCA2) from any encryption scheme secure in the sense of Boneh-Zhandry (IND-qCCA2). Along the way, we also give the first definitions of non-malleability for classical encryption in the quantum world and show that the picture of the relations between these notions is essentially the same as in the classical setting.

Properties of quantum mechanics have enabled the emergence of quantum cryptographic protocols achieving important goals which are proven to be impossible classically. Unfortunately, this usually comes at the cost of needing quantum power from every party in the protocol, while arguably a more realistic scenario would be a network of classical clients, classically interacting with a quantum server. In this paper, we focus on copy-protection, which is a quantum primitive that allows a program to be evaluated, but not copied, and has shown interest especially due to its links to other unclonable cryptographic primitives. Our main contribution is to show how to dequantize existing quantum copy-protection from hidden coset states, by giving a construction for classically-instructed remote state preparation for coset states. We also present the first secure copy-protection scheme for point-functions in the plain model, to which our dequantizer can be applied.

With the emergence of quantum communication, it is of folkloric belief that allowing an Adversary to perform superposition queries to otherwise classical cryptographic protocols and forcing the honest players to perform actions coherently on quantum states automatically breaks the schemes' security. Another intuition is that enforcing measurements on the exchanged messages is enough to protect protocols from these attacks. However, the reality is much more complex. The security models dealing with superposition attacks only consider unconditional security. The first seminal papers date back to 1997 and prove the impossibility of unconditionally-secure bit-commitment schemes. Follow-up works heavily rely on this assumption of unconditional security to prove strong impossibility results and their proof techniques cannot be applied to the computational setting. They essentially indicate that ideal primitives should in fact measure the input state. On the opposite, security models considering computational security assume that all supposedly classical messages are measured, which forbids by construction the analysis of superposition attacks. To fill in the gap between those models, Boneh and Zhandry have started to study the quantum computational security for classical primitives in their seminal work at Crypto'13, but only in the single-party setting. To the best of our knowledge, an equivalent model in the multiparty setting is still missing. In this work, we propose the first computational security model considering superposition attacks for multiparty protocols. We show that our new security model is satisfiable by proving the security of the well-known One-Time-Pad protocol and show an attack on a variant of the equally reputable Yao Protocol for Secure Two-Party Computations. The post-mortem of this attack reveals the precise points of failure, yielding highly counter-intuitive results: The attack vector consists of a (classically) seemingly inoffensive message and a measurement performed by the honest player. This example shows that adding extra classical communication, which is harmless for classical security, can make the protocol become subject to superposition attacks. Our results show that intuitions can be misleading when reasoning about cryptographic protocols in a quantum world, and that there is no evident answer to provide for either the vulnerabilities of classical protocols to superposition attacks or the adapted countermeasures.