Paper 2020/266

Make Quantum Indistinguishability Great Again

Tommaso Gagliardoni and Juliane Krämer and Patrick Struck

Abstract

In this work we study the (superposition-based, or QS2) quantum security of public key encryption schemes. Boneh and Zhandry (CRYPTO 2013) initiated this research area for symmetric and public key encryption, albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO 2016) advanced the study of quantum security, for symmetric key encryption schemes, by giving the first definition where the indistinguishability phase is quantum. For public key encryption schemes, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. In this work we close this gap by defining strong QS2 security notions for the public key case. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. Extending this idea to the public key case brings non-trivial obstacles: On the one hand, public key encryption schemes typically cannot recover the randomness when decrypting ciphertexts. On the other hand, many real-world schemes (including most quantum-resistant NIST candidates) suffer from a small probability of decryption failures. These two problems make it difficult to enforce the reversibility of the encryption operation needed by type-2 operators. Nevertheless, we identify a class of encryption schemes, which we call recoverable, that allow to avoid decryption failures given knowledge of the original encryption randomness, and we show that many real-world quantum-resistant schemes, including many NIST candidates, are of this type. Then we show how to define and construct type-2 encryption operators for schemes that are fully correct or recoverable. Moreover, we show that for recoverable schemes, the type-2 operator can be efficiently implemented even without knowledge of the secret key. This means that, for the public key case, type-2 operators are actually very natural, and already included in the traditional "post-quantum" (QS1) definition of security. Equipped with these results, we (1) give the first quantum security notion (qINDqCPA) for public key encryption with a quantum indistinguishability phase, (2) prove that the canonical LWE-based encryption scheme achieves our security notion, (3) show that our notion is strictly stronger than existing security notions, and (4) study the general classification of quantum-resistant public key encryption schemes.