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

Table of Links

Abstract and 1 Introduction

1.1 Technical Overview

1.2 Related Works, Discussion and Open Problems

2. Preliminaries

   2.1 Notation

   2.2 Quantum Computation

   2.3 Quantum-Heavy Queries Learner

   2.4 Polynomial Compatibility Conjecture

   2.5 Useful Lemmas

3. 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

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).

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.

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.

[3] Such a result is actually conditioned on a conjecture that we state in Conjecture 2.16 and discuss in Section 1.2.