Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography /

Date: received 27 Feb 2020, last revised 26 May 2020

Contact author: paper qpke2020 at gagliardoni net, juliane@qpc tu-darmstadt de, patrick@qpc tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20200526:224531 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]