Paper 2020/266

Quantum Indistinguishability for Public Key Encryption

Tommaso Gagliardoni, Juliane Krämer, and Patrick Struck


In this work we study the quantum security of public key encryption schemes (PKE). Boneh and Zhandry (CRYPTO'13) initiated this research area for PKE and symmetric key encryption (SKE), albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO'16) advanced the study of quantum security by giving, for SKE, the first definition with a quantum indistinguishability phase. For PKE, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. Our main result is a novel quantum security notion (qIND-qCPA) for PKE with a quantum indistinguishability phase, which closes the aforementioned gap. We show a distinguishing attack against code-based schemes and against LWE-based schemes with certain parameters. We also show that the canonical hybrid PKE-SKE encryption construction is qIND-qCPA-secure, even if the underlying PKE scheme by itself is not. Finally, we classify quantum-resistant PKE schemes based on the applicability of our security notion. 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 PKE, as the canonical way of building them requires both the secret and the public key. However, we identify a class of PKE schemes - which we call recoverable - and show that for this class 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 PKE schemes, including most NIST PQC candidates and the canonical hybrid construction, are indeed recoverable.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.The Twelfth International Conference on Post-Quantum Cryptography (PQCrypto 2021)
quantum securitypost-quantum cryptographyquantum indistinguishabilitysuperposition attacksQ2QS2NISTquantum-resistantqIND-qCPAtype-2 operators
Contact author(s)
tommaso gagliardoni @ kudelskisecurity com
juliane @ qpc tu-darmstadt de
patrick @ qpc tu-darmstadt de
2021-06-13: last of 5 revisions
2020-03-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tommaso Gagliardoni and Juliane Krämer and Patrick Struck},
      title = {Quantum Indistinguishability for Public Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/266},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.