Authors:
(1) Samuel Bouaziz–Ermann, Sorbonne Université, CNRS, LIP6, France;
(2) Alex B. Grilo, Sorbonne Université, CNRS, LIP6, France;
(3) Damien Vergnaud, Sorbonne Université, CNRS, LIP6, France;
(4) Quoc-Huy Vu, Léonard de Vinci Pôle Universitaire, Research Center, 92 916 Paris La Défense, France. Authors: Authors: (1) Samuel Bouaziz–Ermann, Sorbonne Université, CNRS, LIP6, France; (2) Alex B. Grilo, Sorbonne Université, CNRS, LIP6, France; (3) Damien Vergnaud, Sorbonne Université, CNRS, LIP6, France; (4) Quoc-Huy Vu, Léonard de Vinci Pôle Universitaire, Research Center, 92 916 Paris La Défense, France. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 1.1 Technical Overview 1.1 Technical Overview 1.2 Related Works, Discussion and Open Problems 1.2 Related Works, Discussion and Open Problems Preliminaries
2.1 Notation
2.2 Quantum Computation
2.3 Quantum-Heavy Queries Learner
2.4 Polynomial Compatibility Conjecture
2.5 Useful Lemmas


Attack on the Key Agreement Protocols and 3.1 Definitions
3.2 The Attack on Key Agreements Protocols
3.3 Impossibility of quantum public-key encryption with classical keys Preliminaries
2.1 Notation
2.2 Quantum Computation
2.3 Quantum-Heavy Queries Learner
2.4 Polynomial Compatibility Conjecture
2.5 Useful Lemmas Preliminaries 2.1 Notation 2.1 Notation 2.2 Quantum Computation 2.2 Quantum Computation 2.3 Quantum-Heavy Queries Learner 2.3 Quantum-Heavy Queries Learner 2.4 Polynomial Compatibility Conjecture 2.4 Polynomial Compatibility Conjecture 2.5 Useful Lemmas 2.5 Useful Lemmas Attack on the Key Agreement Protocols and 3.1 Definitions
3.2 The Attack on Key Agreements Protocols
3.3 Impossibility of quantum public-key encryption with classical keys Attack on the Key Agreement Protocols and 3.1 Definitions Attack on the Key Agreement Protocols and 3.1 Definitions 3.2 The Attack on Key Agreements Protocols 3.2 The Attack on Key Agreements Protocols 3.3 Impossibility of quantum public-key encryption with classical keys 3.3 Impossibility of quantum public-key encryption with classical keys Acknowledgments and References Acknowledgments and References Abstract. There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC’89). Abstract However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al.(CRYPTO’22) of quantum enhanced key-agreement (KA) with classical communication. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state. 1 Introduction After decades of focusing on the possibility of information-theoretically secure quantum protocols, initiated by the land-marking results on money schemes [Wie83] and key-agreement [BB84], there has been recent progress in understanding how quantum resources can be used to implement cryptographic primitives under weaker computational assumptions. More concretely, it has been shown in [GLSV21, BCKM21] that Oblivious Transfer (OT) and Multi-party computation (MPC), two central primitives in cryptography can be constructed from one-way functions (OWF), the weakest classical cryptographic assumption. Such a result has been extended to show OT and MPC can be constructed from pseudo-random quantum states [AQY22], which is expected to be a weaker computational assumption than OWF [Kre21, KQST23]. This is in stark contrast with the classical case since we do not expect OT and MPC to be built from one-way functions [IR89]. More recently, it has been asked if quantum protocols are possible for public-key encryption from OWF (or weaker assumptions). While the conditional impossibility result for key-agreement of [ACC+22] implies that public-key encryption (PKE) from OWF with classical communication is impossible even if the honest parties are quantum,[3] it has been recently shown that PKE can be constructed from OWF if we have a quantum public-key [Col23, BGHD+23, KMNY23]. However, having a quantum public key is not ideal, given the issues that appear with public-key distribution, authentication, and reusability. These results leave then as an open question if quantum PKE from OWF is possible with a classical public key and quantum ciphertext. In this work, we extend the result of [ACC+22] and we show that key agreement is impossible when Alice and Bob exchange classical messages and at the very last round, Bob sends a quantum message to Alice. Our result holds under the same conjecture as [ACC+22] but is limited to the setting where Alice does not query the random oracle in the last round of the protocol. More concretely, we achieve the following result. With this result in hand, we show that quantum PKE is impossible with a classical public key in the Quantum Random Oracle Model (QROM), when the decryption algorithm does not query the random oracle. Corollary 1.2 (Informal). Assume (Gen, Enc, Dec) is a Public-Key Encryption scheme, where the public key is classical and the ciphertext is a quantum state. Assuming the algorithms Gen and Enc makes at most n quantum queries to a random oracle O, then there exists an algorithm Eve that can decipher by making O(poly(n)) classical queries to O. Corollary 1.2 (Informal). Assume (Gen, Enc, Dec) is a Public-Key Encryption scheme, where the public key is classical and the ciphertext is a quantum state. Assuming the algorithms Gen and Enc makes at most n quantum queries to a random oracle O, then there exists an algorithm Eve that can decipher by making O(poly(n)) classical queries to O. Using known techniques from black-box separation, our results can easily be translated to give separations of qPKE from black-box OWF. We also note that our result (Corollary 1.2) marks an initial step towards proving the conjecture of [MY22] on the possibility of black-box constructions of qPKE with classical public keys from quantum symmetric key encryption. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv [3] Such a result is actually conditioned on a conjecture that we state in Conjecture 2.16 and discuss in Section 1.2.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Quant

Oracle

Comparing SCP and OCA in Transaction Fee Mechanisms: Core Differences and Results

EScholar Technologies

Too Long; Didn't Read

Download free Tech Leaders Productivity Report!

Black‑Box Separation for Quantum PKE from OWF with Classical Public Keys

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

15 Common Types of Unethical Behavior Found in Open-Source Projects

The Noonification: Bitcoin Is The ONLY Digital Scarcity That Matters — Heres Why (5/5/2023)

63 Stories To Learn About Quantum Computing

Quantum Cryptography For Beginners: From Basics To Blockchain

A Detailed Guide on Quantum Cryptography with Pros and Cons

15 Common Types of Unethical Behavior Found in Open-Source Projects

The Noonification: Bitcoin Is The ONLY Digital Scarcity That Matters — Heres Why (5/5/2023)

63 Stories To Learn About Quantum Computing

Quantum Cryptography For Beginners: From Basics To Blockchain

A Detailed Guide on Quantum Cryptography with Pros and Cons

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps

Black‑Box Separation for Quantum PKE from OWF with Classical Public Keys