Ehsan Ebrahimi

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.

In this paper, we study the post-quantum security of various threshold symmetric schemes. In a threshold scheme, the secret-key is split among multiple parties in order to protect the key. Our first observation is a security analysis in the superposition-access model might be needed for a multi-party threshold scheme in the post-quantum setting since a corrupt party may deliver its secret key to a quantum adversary. Consequently, the adversary can implement a partial evaluation of the multi-party threshold scheme on his quantum device and this can enforce a superposition access to the underlying primitive. In other words, if the underlying primitive is vulnerable to a superposition attack, then the security of the multi-party threshold scheme might break. For instance, under a reasonable assumption we show that the NPR's threshold pseudorandom function (Naor et al. Eurocrypt 99) is not post-quantum secure if the underlying pseudorandom function family is not secure in the superposition-access model.