Quantum indistinguishability for public key encryption

DOI10.1007/978-3-030-81293-5_24zbMATH Open1485.94085arXiv2003.00578OpenAlexW3013361954MaRDI QIDQ2118562FDOQ2118562

Authors: Tommaso Gagliardoni, Juliane Krämer, Patrick Struck 

Publication date: 22 March 2022

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.

Full work available at URL: https://arxiv.org/abs/2003.00578

Recommendations

• On quantum ciphertext indistinguishability, recoverability, and OAEP
• Semantic security and indistinguishability in the quantum world
• Anonymous, robust post-quantum public key encryption
• Relationships between quantum IND-CPA notions
• A practical post-quantum public-key cryptosystem based on spLWE

zbMATH Keywords

quantum security of public key encryption schemes

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cites Work

• On lattices, learning with errors, random linear codes, and cryptography
• Title not available (Why is that?)
• Secure signatures and chosen ciphertext security in a quantum computing world
• Superposition attacks on cryptographic protocols
• Quantum computation and quantum information. 10th anniversary edition
• The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
• Random oracles in a quantum world
• A note on quantum related-key attacks
• Quantum-access-secure message authentication via blind-unforgeability
• Breaking symmetric cryptosystems using quantum period finding
• Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
• Quantum chosen-ciphertext attacks against Feistel ciphers
• Unforgeable quantum encryption
• Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation
• Semantic security and indistinguishability in the quantum world

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)