Quantum indistinguishability for public key encryption
From MaRDI portal
Publication:2118562
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- A note on quantum related-key attacks
- Breaking symmetric cryptosystems using quantum period finding
- On lattices, learning with errors, random linear codes, and cryptography
- Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation
- Quantum chosen-ciphertext attacks against Feistel ciphers
- Quantum computation and quantum information. 10th anniversary edition
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- Quantum-access-secure message authentication via blind-unforgeability
- Random oracles in a quantum world
- Secure signatures and chosen ciphertext security in a quantum computing world
- Semantic security and indistinguishability in the quantum world
- Superposition attacks on cryptographic protocols
- The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
- Unforgeable quantum encryption
Cited in
(11)- Post-quantum Security of Plain OAEP Transform
- Post-quantum plaintext-awareness
- Sponge-based authenticated encryption: security against quantum attackers
- On quantum ciphertext indistinguishability, recoverability, and OAEP
- Bit-oriented quantum public key probabilistic encryption schemes
- Anonymous, robust post-quantum public key encryption
- Tighter security proofs for GPV-IBE in the quantum random oracle model
- Semantic security and indistinguishability in the quantum world
- Computational indistinguishability between quantum states and its cryptographic application
- Characterizing the qIND-qCPA (In)security of the CBC, CFB, OFB and CTR Modes of Operation
- Relationships between quantum IND-CPA notions
This page was built for publication: Quantum indistinguishability for public key encryption
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118562)
