Paper 2020/266

Quantum Indistinguishability for Public Key Encryption

Tommaso Gagliardoni and Juliane Krämer and Patrick Struck

Abstract

In this work we study the quantum security of public key encryption schemes. Boneh and Zhandry (CRYPTO'13) initiated this research area for symmetric and public key encryption, albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO'16) advanced the study of quantum security by giving, for symmetric key encryption schemes, the first definition with a quantum indistinguishability phase. For public key encryption schemes, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. Our main result is a novel quantum security notion (qINDqCPA) for public key encryption with a quantum indistinguishability phase, which closes the aforementioned gap. Furthermore, we show that the canonical LWE-based encryption scheme achieves our quantum security notion, show that our notion is strictly stronger than existing security notions, and study the general classification of quantum-resistant public key encryption schemes. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. At first glance, type-2 operators appear unnatural for public key encryption schemes, as the canonical way of building them requires both the secret and the public key. However, we identify a class of encryption schemes - which we call recoverable - and show that for this class of schemes, type-2 operators require merely the public key. Moreover, recoverable schemes allow to realise type-2 operators even if they suffer from decryption failures, which in general thwarts the reversibility mandated by type-2 operators. Our work reveals that many real-world quantum-resistant schemes, including most round 2 NIST PQC candidates, are indeed recoverable.