betaFeedback

WorksPhysics and Astronomy

Quantum Cryptomania with Classical Communication without One-Way Functions

Abstract

In classical cryptography, one-way functions are necessary for most of cryptography. In the quantum world, however, Kretschmer at {TQC'21} and subsequent works have demonstrated that quantum versions of various primitives in minicrypt, such as signatures and private-key encryption, do not require quantum-computable one-way functions (\textsf{qOWF}s). However, the question of the necessity of \textsf{qOWF}s for primitives in Cryptomania like public-key encryption with classical public keys and ciphertexts (\textsf{qPKE}) has remained open. We provide a comprehensive picture of the relationship between \textsf{qPKE} and \textsf{qOWF}. First, our main result is a black-box separation between \textsf{qOWF}s and \textsf{qPKE}. In particular, we show that relative to a unitary, real, and self-inverse oracle, there exists a \textsf{qPKE} scheme (with classical keys and ciphertexts), but \textsf{qOWF}s do not exist. Further, our oracles admit a point-function obfuscation construction, thus ruling out black-box construction of \textsf{qOWF} from point function obfuscations. On the positive side, we construct \textsf{qPKE} from quantum indistinguishability obfuscation for quantum circuits with classical obfuscated descriptions and efficiently verifiable one-way puzzles, which is known to be a potentially weaker assumption than \textsf{qOWF}s, due to an existing black-box separation. Our construction is the quantum analog of the classical construction of \textsf{PKE} from one-way functions and indistinguishability obfuscation in the quantum computation with classical communication (QCCC) setting.

Introduction

One-way functions (OWFs) form the foundation of classical computational cryptography [30]. They are necessary for most non-trivial primitives, including signatures, many-time encryption, and bit commitments. This is reflected in Impagliazzo’s five worlds [31], where OWFs form the basis of Minicrypt, the world that supports basic computational cryptography. Furthermore, they are implied by more powerful cryptographic primitives, like public-key encryption (PKE), a central primitive of Cryptomania{^1}. PKE is one of the most fundamental primitives in cryptography, enabling secure communication without shared keys. Hence, understanding how PKE relates to other assumptions has been extensively studied in classical cryptography. In particular, it is known that classical public-key encryption (PKE) implies private-key encryption, which in turn is equivalent to OWFs [30, 28]. In the other direction, OWFs may not be sufficient for PKE, as Impagliazzo and Rudich ruled out fully black-box constructions of classical PKE from OWFs [32]. This gives a familiar view of the two primitives: one-wayness is necessary for public-key encryption, but may not be sufficient.

Quantum computation changes the relationships between cryptographic primitives. Classical proofs often rely on fixing random coins, copying internal states, or rewinding a computation, and these steps do not automatically extend to quantum algorithms. Indeed, prior constructions and oracle separations show that, unlike in the classical setting, commitments, one-time symmetric encryption, and one-time signatures can exist relative to a quantum oracle even when quantum computable one-way functions (qOWFs) do not [39 AQY22, 46, 10]. It may appear that the source of these anomalies is that the quantum versions of these minicrypt primitives allow for quantum communication. However, even when restricted to entirely classical communication, the relationships remain different. Indeed, commitments, symmetric encryption, and digital signatures with classical communication do not imply qOWF in a black-box manner [19, 10, 8, 13], unlike their classical counterparts. Much of the recent work has focused on the relationships of qOWF with the quantum versions of Minicrypt primitives [10, 19, 8, 13], but its corresponding relationship with quantum Cryptomania, particularly public-key encryption with classical communication (denoted as qPKE), is somewhat less understood. Previous work has shown that known classical black-box barriers to constructing qPKE from OWFs can be adapted to the quantum setting [LLL25a, LLL25b]. Nevertheless, in the reverse direction, the more basic question of whether qOWFs are necessary for qPKE has remained open.

Allowing quantum public keys changes the picture. Encryption with quantum public keys and classical ciphertexts can be constructed from post-quantum OWFs [36], and even from potentially weaker assumptions, such as pseudorandom function-like states with proofs of destruction [BGH+23] and short pseudorandom states (PRSs) [10]. Thus, the black-box barrier for classical public keys does not extend to quantum public keys in general [LLL25a]. However, quantum public keys do not provide the same form of public availability as classical keys. A classical public key can be published once and freely copied by anyone, whereas quantum public keys generally require distributing quantum states to each recipient [BGH+23]. This distinction motivates studying whether the assumptions needed for public-key encryption can also be weakened while retaining classical public keys and entirely classical communication. This leads us to ask the following natural question.

Open Problem 1. Does public-key encryption still require quantum-computable one-way functions in the quantum setting, even if the keys and communication remain classical?

Our results

In this work, we answer Open Problem 1 in the negative. Our main result is a separation of qOWF from qPKE.

Theorem 1.1 (Informal: oracle separations). There exists a quantum real and self-inverse unitary oracle relative to which perfectly correct, IND-CPA-secure qPKE exists but qOWFs do not.

Our separation also rules out quantum-computable pseudorandom generators (qPRG) and quantum-computable pseudorandom functions (qPRFs), since both imply qOWFs. In fact, we even rule out a weaker notion of these functions that allow quantum input sampling, as explored in [19], as long as they are deterministic on every input except with negligible probability.

Interestingly, our oracles (via a similar proof to that for our qPKE construction) also admit the construction of point-function obfuscation, which is a quantum algorithm that takes a classical encoding of a point function and outputs a classical encoding of the obfuscation that satisfies single-program virtual black-box (VBB) security without correlated auxiliary inputs (see Definition 7). Therefore, we also separate qOWFs from point-function obfuscation.

Finally, since our oracles are real, self-inverse, and unitary, our result rules out black-box constructions that use unitary, inverse, controlled, transpose, and complex-conjugate operations.

Our result gives a very interesting relationship between qOWFs and qPKE. Recall that Li, Li, Li, and Liu rule out black-box constructions of perfectly correct qPKE from qOWFs [41]. Together with theorem 1.1, this gives a two-way black-box separation between perfectly correct qPKE and qOWFs. This highlights the complexity of the quantum landscape as opposed to the hierarchical structure in the classical setting.

Public-key encryption from EV-OWPuzz and qiO. qOWF is not the only one-way primitive in quantum cryptography. There are several one-way notions believed to be weaker due to black-box separations, such as one-way state generators [46] and efficiently verifiable one-way puzzles (EV-OWPuzz) [20]. Given that our separation result (Theorem 1.1) shows that qOWFs may not be necessary for qPKE, it is therefore natural to ask if qPKE can be built from weaker forms of one-way primitives that exist in the quantum world.

Note that classically, a well-known construction shows that OWFs together with indistinguishability obfuscation (iO) give PKE [50]. EV-OWPuzz are a natural candidate to replace OWFs as a weaker quantum one-way primitive in a quantum analog of this construction, since they are already implied by, and hence necessary for, qPKE [20]. An EV-OWPuzz consists of two QPT algorithms: a sampler SS, which outputs a classical puzzle and answer (p,a)(p,a), and a verifier VV, which accepts honestly sampled pairs except with negligible probability. One-wayness requires that, for every QPT algorithm AA,

Pr⁡(p,a)←S(1λ)[V(p,A(p))=1]≤negl⁡(λ).\Pr_{(p,a)\leftarrow S(1^\lambda)}[V(p,A(p))=1]\leq\operatorname{negl}(\lambda).

Chung, Goldin, and Gray [20 Section 3] asked whether EV-OWPuzz suffice to construct secret-key encryption with quantum computation and classical communication. We study a related question for public-key encryption: do EV-OWPuzz suffice when combined with indistinguishability obfuscation?

For our second result, we show that EV-OWPuzz suffices to construct qPKE when combined with quantum indistinguishability obfuscation (qiO), for pseudodeterministic quantum circuits with classical obfuscated descriptions, under Definition 8. Obfuscation of this class of circuits is studied in [15].

Theorem 1.2 (Informal: construction). EV-OWPuzzEV\text{-}OWPuzz and qiOqiO imply IND-CPA-secure qPKEqPKE with classical communication and keys.

Framework for different notions of generalized qOWF Next, we take a closer look at the very definition of qOWF. The definition most commonly used in the literature [3, 21, 24, 25, 29, 33, 34, 35, 38, 47, 48] requires that determinism holds for every input, except with negligible probability, and that the one-wayness game is with respect to the uniform distribution on the input space. However, there are natural generalizations to relax the above definition with respect to the determinism requirement and the security requirement through the distribution of inputs considered in the one-wayness game. For instance, should evaluation be near-deterministic on every input or only on average, or should inversion hardness be measured on uniform inputs or on inputs produced by a specified quantum sampler? Indeed, Barhoush, Nishimaki, and Yamakawa studied the role of quantum input sampling, i.e., where the input of the function in the security experiment can be sampled by an arbitrary efficient quantum algorithm [19]. They showed that allowing quantum samplers can yield a potentially weaker assumption. Thus, one may suspect that our separation result (Theorem 1.1) is due to similar differences in the definition of qOWF, and not a fundamental barrier towards qOWF being necessary for qPKE. Therefore, to better understand the role of these different potential generalizations of qOWF in our separation result (Theorem 1.1), we provide a general framework for different generalizations of qOWF. In our framework, a qOWF consists of a pair of QPT algorithms (S,E)(S, E), where SS is the input sampler, and EE is the evaluator. Let ff be the function that maps xx to the most likely output of E(x)E(x). In each notion, one-wayness requires that, for every QPT inverter AA,

Pr⁡X←S(1λ)Y←E(X)[E(A(Y))=Y]≤negl⁡(λ).\Pr_{\substack{X\gets S(1^\lambda)\\Y\gets E(X)}}\left[E(A(Y))=Y\right]\leq\operatorname{negl}(\lambda).

In this framework, we discuss two natural generalizations of the existing qOWF definition and finally consider an even weaker definition that combines the relaxations of the two generalizations.

  1. Generalized-qOWF1_1. The sampler SS is an efficient quantum algorithm, and

∀x∈{0,1}m(λ),Pr⁡[E(x)≠f(x)]≤negl⁡(λ).\forall x\in\{0,1\}^{m(\lambda)},\qquad\Pr[E(x)\ne f(x)]\leq\operatorname{negl}(\lambda).

In other words, this definition generalizes the qOWF definition by replacing the uniform distribution with arbitrary and potentially quantum sampling distributions for the one-wayness experiment. Thus, it is a quantum analog of the general classical OWFs whose one-wayness is with respect to arbitrary efficiently classically samplable distributions; see [49 ABH^{+}26]. Classically, they are equivalent to traditional OWFs, since the randomness can be pulled out from any classical sampler, but this argument does not extend to quantum samplers. Barhoush, Nishimaki, and Yamakawa [19] give black-box separations demonstrating this distinction for pseudorandom generators.

  1. Generalized-qOWF2_2. The sampler SS is uniform, and

Pr⁡X←{0,1}m(λ)[E(X)≠f(X)]≤negl⁡(λ).\Pr_{X\gets\{0,1\}^{m(\lambda)}}[E(X)\ne f(X)]\leq\operatorname{negl}(\lambda).

This definition generalizes the existing qOWF definition by allowing determinism to hold on average over uniform inputs, though the one-wayness game remains in terms of the uniform inputs. For instance, this notion allows the evaluator to be completely non-deterministic on a negligible fraction of inputs. However, on an overwhelming fraction of the inputs, the function is deterministic up to negligible error. This notion of determinism has been used to define quantum-computable pseudorandom generators; see [8, 13].

  1. Generalized-qOWF3\mathrm{qOWF}_3. The sampler SS is arbitrary, and

Pr⁡X←S(1λ)[E(X)≠f(X)]≤negl⁡(λ).\Pr_{X\leftarrow S(1^\lambda)}[E(X) \ne f(X)] \le\operatorname{negl}(\lambda).

This definition is naturally obtained by combining the two somewhat incomparable relaxations allowed in the first two definitions. Unlike the above two definitions, this notion may allow the evaluator to behave non-deterministically on a majority of inputs, raising the question of whether this definition should even be called a function. Nevertheless, we study this notion as a natural generalization of the first two definitions for the theoretical exploration of the limits of our separation result.

For brevity, we will just use qOWF1\mathrm{qOWF}_1, qOWF2\mathrm{qOWF}_2 and qOWF3\mathrm{qOWF}_3 to refer to generalized-qOWF1\mathrm{qOWF}_1, generalized-qOWF2\mathrm{qOWF}_2 and generalized-qOWF3\mathrm{qOWF}_3, respectively, from now on.

The distinction between these notions of qOWF\mathrm{qOWF} suggests a more nuanced question: how does the relationship between qOWF\mathrm{qOWF} and qPKE\mathrm{qPKE} change across the different notions of qOWF\mathrm{qOWF}?

We provide a clear picture of this question. Firstly, we note that our separation result is even stronger than the version stated in Theorem 1.1, and in particular we show the following fine-grained version of it.

Theorem 1.3 (Informal: fine-grained version of oracle separations). There exists a quantum real and self-inverse unitary oracle relative to which perfectly correct, IND-CPA-secure qPKE\mathrm{qPKE} exists but neither qOWF1\mathrm{qOWF}_1's nor qOWF2\mathrm{qOWF}_2's exist.

Thus, this gives black-box separations between qPKE\mathrm{qPKE} and the two notions qOWF1\mathrm{qOWF}_1 and qOWF2\mathrm{qOWF}_2, but what about the last and weakest notion, qOWF3\mathrm{qOWF}_3? Interestingly, we find that qOWF3\mathrm{qOWF}_3 has a different relation with qPKE\mathrm{qPKE} and EV-OWPuzz. Our third result presents this relationship.

Theorem 1.4 (Informal: equivalence with puzzles). qOWF3\mathrm{qOWF}_3's exist if and only if EV-OWPuzz exist. Since qPKE\mathrm{qPKE} implies EV-OWPuzz [20], we conclude that qPKE\mathrm{qPKE} implies qOWF3\mathrm{qOWF}_3's.

This equivalence may seem surprising since qOWF3\mathrm{qOWF}_3 still requires nearly deterministic evaluation on sampled inputs, whereas in an EV-OWPuzz, there is no such determinism requirement. Nevertheless, we show that since qOWF3\mathrm{qOWF}_3 allows average-input determinism for an arbitrary quantum sampleable distribution, we can build it from EV-OWPuzz. We note that for a relativizing equivalence, it is necessary that we allow both average-input correctness and security relative to quantum input sampling. Indeed, if we remove even one of these two relaxations, we get either qOWF1\mathrm{qOWF}_1 or qOWF2\mathrm{qOWF}_2, which by Theorem 1.3 are separated from qPKE\mathrm{qPKE} and, hence, are also separated from EV-OWPuzz.

We summarize all our results in Figure 1.

Implications and separations among qOWF, qPKE, EV-OWPuzz, and related notions

Figure 1. Solid arrows denote implications, the double arrow denotes equivalence, and crossed dashed arrows denote black-box impossibilities. Blue arrows denote reductions proved in this work. Dark red separations are ours; the light red separation is from prior work. The qOWF-to-qPKE impossibility assumes perfect correctness of qPKE [41].

Related works

In the classical setting, PKE can be constructed from indistinguishability obfuscation and OWFs [50]. Whether OWFs alone suffice remains open, but we know that classical black-box constructions are ruled out by [32]. An optimal quadratic-query attack on classical key agreement in the random oracle model was later given in [BMG09].

Extending this impossibility to the quantum setting has required a separate line of work. Earlier results were conditional or applied to restricted constructions [ACC+22, BEGVV23, LLLL24, LLLL25b]. Li, Li, Li, and Liu subsequently gave a polynomial-query attack on every perfectly correct public-key encryption scheme with classical keys in the quantum random oracle model, even when ciphertexts are quantum [41]. Their later work extends this to perfectly correct key agreement with arbitrarily many rounds of classical communication [43]. These attacks allow unbounded computation between queries and give black-box barriers to constructing public-key encryption or key agreement from OWFs. They do not rule out constructions with negligible correctness error in full generality. Our separation addresses the reverse question: whether qPKE implies qOWFs when the algorithms may be quantum.

Two earlier oracle separations are particularly relevant to this reverse direction. Kretschmer, Qian, and Tal construct a classical oracle relative to which P = NP, but trapdoor qOWFs, qPKE with classical keys and ciphertexts, and signatures with classical keys and signatures exist [38]. Their oracle rules out classically computable OWFs, while retaining quantum-computable ones. Goldin, Morimae, Mutreja, and Yamakawa construct a unitary oracle relative to which BQP = QCMA but non-interactive key exchange with classical communication exists. This rules out qOWFs, but the parties in their key-exchange construction retain quantum private states [26]. Our qPKE separation has classical public keys, secret keys, and ciphertexts, and rules out both qOWF1_1s and qOWF2_2s: every-input determinism with arbitrary quantum input sampling, and average determinism with uniform input sampling.

Our proof is also related to separations involving short PRSs and determinism. Barhoush rules out black-box constructions of qPRGs from short PRSs and from L\mathsf{L}-qPRGs, allowing unitary and inverse access. His black-box formulation requires the correctness of the target primitive to follow from the correctness of the source [8]. Bouaziz–Ermann, Hhan, Muguruza, and Vu give a unitary oracle relative to which logarithmic-output pseudorandom function-like states exist, but qPRGs with negligible correctness error do not. Their proof uses a barrier theorem for products of Haar-distributed states [13]. We use the same broad strategy of forcing a candidate to fail correctness or become simulatable. To apply this strategy to qPKE, we continuously change the OsampO_{\mathrm{samp}}, OencO_{\mathrm{enc}}, and OdecO_{\mathrm{dec}} operations and show that a nearly deterministic evaluator computes the same function for many choices of the oracle. We then show that an oracle can be chosen for which encryption remains secure.

Quantum input sampling was studied by Barhoush, Nishimaki, and Yamakawa [19]. They separate qPRGs with uniform seeds from qPRFs with quantum key sampling, using unitary oracles with inverse access.

Kretschmer [39] showed that there is a quantum oracle relative to which long PRSs exist but BQP = QMA, ruling out qOWFs. Black-box constructions of many-time signatures with classical secret keys and signatures from PRSs with at least linearly many output qubits are also ruled out [22], even allowing quantum public keys; this separation does not allow inverse queries. Together with the signature construction from short PRSs, this rules out the corresponding black-box shortening of PRSs [22, 10]. A separate oracle separation between linear-output PRSs and clog⁡λc \log\lambda-qubit PRSs, for sufficiently large cc, is given in [16].

Technical Overview

We will give a brief overview of our separation and the construction of qPKE from puzzles and obfuscation.

Oracle Separation

In this section, we discuss the main ideas behind our oracle separation result. For simplicity, we focus only on the separation of qOWF1_1s and qOWF2_2s from qPKE.

Our separation exploits a key distinction between qPKE and qOWFs: determinism. Key generation and encryption may produce different outputs each time they are run. Meanwhile, an qOWF evaluator must produce one fixed output on a given or at least an overwhelming fraction of the inputs. qOWF1_1 requires this on every input, while qOWF2_2 allows exceptions on a negligible fraction of uniformly distributed inputs. This suggests designing oracles whose random outputs don’t affect encryption, but since they can’t be derandomized, any nearly deterministic evaluator can’t use them non-trivially to construct an qOWF.

First attempt for the Oracles We begin with a natural construction of oracles that admits a qPKE construction. At each length nn, sample a random table, where each row indexed by j∈{0,1}nj \in\{0,1\}^n contains a uniformly random string sj∈{0,1}8ns_j \in\{0,1\}^{8n}, and two random disjoint sets of ciphertext strings, one for each message bit. Each set has 22n2^{2^n} elements from {0,1}12n\{0,1\}^{12n}. We call jj a p-key and sjs_j an s-key, reserving public key and secret key for the encryption scheme constructed from the oracle. The contents of each row are sampled independently of those of other rows. Based on such a random table, we consider three oracles:

  • Key sampling oracle OsampO_{\mathrm{samp}}. Prepare a uniform superposition over pairs (j,sj)(j, s_j). Measuring this state samples a uniform p-key and its s-key. To make it unitary, we implement it as a

swapping oracle that swaps the uniform superposition state with a dummy state, as used in previous works of [18, 27].

  • Ciphertext sampling oracle OencO_{\mathrm{enc}}. Given a p-key jj and a message bit bb, prepare a uniform superposition over the ciphertext set for (j,b)(j,b). Measuring this state samples a ciphertext string cc.

  • Decryption oracle OdecO_{\mathrm{dec}}. Given (j,sj,c)(j,s_j,c) for an honestly sampled ciphertext string cc, return its message bit. With an incorrect s-key, the measurement returns an unbiased bit.

Note that the three oracle operations are real, unitary, and self-inverse. These oracles naturally give a secure qPKE construction as follows. Key generation samples (j,sj)(j,s_j) using OsampO_{\mathrm{samp}}, publishes jj, and keeps (j,sj)(j,s_j) as the secret key. Encryption samples cc using Oenc(j,b)O_{\mathrm{enc}}(j,b) and outputs (j,c)(j,c); decryption uses Odec(j,sj,c)O_{\mathrm{dec}}(j,s_j,c). Correctness is immediate, and all keys and ciphertexts are classical. Security follows by standard quantum query hybrids. Let JJ be the challenge public key. First, remove (J,sJ)(J,s_J) from the key-sampling state. Next, replace decryption at JJ with the unbiased response. Finally, replace the challenge ciphertext in the ciphertext-sampling state with a fresh string, keeping the ciphertext given to the adversary unchanged. The exponentially large p-key and s-key spaces and ciphertext sets make these replacements indistinguishable to polynomial-query adversaries. In the final hybrid, the joint distribution of the challenge ciphertext and the oracle is independent of the message bit, thus completing the security proof. Next, to rule out qOWF, we also add a PSPACE oracle, i.e., an oracle for a fixed PSPACE-complete language, which has no access to the random tables, in order to preserve the security of our qPKE scheme.

The qPKE construction also provides an qOWF. The construction above gives a secure qPKE, but unfortunately it already yields a qOWF1_1. In particular, the oracle above allows us to efficiently verify if a given s-key, p-key pair is indeed a valid honestly sampled pair. This is because encrypting message one with the p-key and then decrypting the ciphertext with the s-key returns one with probability exactly 1 if they are a sampled key pair and 1/21/2 for every other pair. Hence, repeating this process sufficiently many times (say, λ\lambda times) allows us to distinguish sampled key pairs from other pairs, which lets us evaluate the following qOWF1_1: f(j,s)={(0,j),s=sj,⊥,s≠sj.f(j,s)=\begin{cases}(0,j), & s=s_j,\\ \bot, & s\ne s_j.\end{cases} It is easy to check that the above verification process leads to deterministic evaluation (up to negligible error) for every input. In fact, the determinism holds even if we change the distribution on the oracle tables. For one-wayness, we consider the quantum input sampler that samples (j,sj)(j,s_j) according to the qPKE scheme’s key-generation algorithm. By the correctness of the qPKE scheme, the image of a typical (j,sj)(j,s_j) under ff is (0,j)(0,j). This implies that any inverter against ff with respect to this quantum input sampler essentially computes the secret key (j,sj)(j,s_j) given a sample public key jj for the qPKE scheme, thus breaking the qPKE security. Moreover, this correspondence holds even if we change the oracle distribution! Thus, for our separation, we must tweak the oracle operations themselves, not just the distribution over the oracle parameters (such as the random tables).

Oracles with two tables. We tweak the oracle operation by introducing a second table, so that the above-mentioned evaluator for ff can fail fixed-input determinism while the qPKE construction remains correct and secure. In particular, at each length nn, sample two independent tables A,BA,B with the same p-key indices, each assigning its own s-key and ciphertext sets to every p-key. Independently sample uniform i∈{1,2,3}i\in\{1,2,3\} and t∈[0,1]t\in[0,1], and set τ=(i−1+t)/3\tau=(i-1+t)/3, which is uniform in [0,1][0,1]. Informally, the oracle operations use an interpolation of the two tables determined by τ\tau. choices are made once, independently at each length, and remain fixed throughout every execution. At τ=0\tau= 0, the oracle operations use only AA; at τ=1\tau= 1, they use only BB. For intermediate values, sampling can use weighted superpositions of the states specified by AA and BB. For example, at τ=1/2\tau= 1/2, conditioned on obtaining p-key jj, the s-key register is in the state (∣sjA⟩+∣sjB⟩)/2(|s_j^A\rangle+ |s_j^B\rangle)/\sqrt{2} assuming sjA,sjBs_j^A,s_j^B are distinct. The precise dependence of all three operations on τ\tau is given in § 5.3.1. The qPKE security argument above also applies to this two-table construction using similar arguments as above2; see Lemma 5.11. Crucially, fix a p-key jj with distinct s-keys and disjoint ciphertext sets across the two tables. For τ∈[0,1/3]\tau\in[0,1/3], both sampling operations use AA, and honestly sampled keys decrypt correctly. Yet, decrypting an AA-encryption of one with sjBs_j^B returns one with a probability p(τ)p(\tau) that varies continuously from 1/21/2 to 113. Thus, decrypting a message under a p-key using a given s-key can no longer separate the sampled s-key from the s-key from the other table BB. As a result, for any polynomial number of repetitions, there is an inverse-polynomial fraction of values of τ\tau for which the above evaluator outputs (0,j)(0,j) and ⊥\perp each with probability at least 1/31/3 on the fixed input (j,sjB)(j,s_j^B); hence, the above evaluation algorithm for ff fails fixed-input determinism.

References

  1. [2]Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão, and Or Sattath. The pursuit of uniqueness: Extending Valiant–Vazirani theorem to the probabilistic and quantum settings. Quantum, 6:668, 2022. Full version: https://arxiv.org/abs/0810.4840v3.
  2. [3]Mark Adcock and Richard Cleve. A quantum Goldreich–Levin theorem with cryptographic applications. In STACS 2002, volume 2285 of Lecture Notes in Computer Science, pages 323–334. Springer, 2002.
  3. [5]Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC ’06, pages 427–436. ACM, 2006.
  4. [6]Noga Alon and Shachar Lovett. Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions. Theory of Computing, 9(15):559–577, 2013.DOI
  5. [8]Mohammed Barhoush. Separating pseudorandom generators from logarithmic pseudorandom states. arXiv:2510.20131v3, 2025. https://arxiv.org/abs/2510.20131v3.
  6. [9]Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. Full version: https://arxiv.org/abs/quant-ph/9701001.
  7. [10]Mohammed Barhoush, Amit Behera, Lior Ozer, Louis Salvail, and Or Sattath. Signatures from pseudorandom states via ⊥-prfs, 2024.arxiv.org/abs/2311.00847
  8. [11]Elette Boyle, Kai-Min Chung, and Rafael Pass. On extractability (a.k.a. differing-inputs) obfuscation. In TCC 2014, 2014. Full version: Cryptology ePrint Archive, Paper 2013/650. https://eprint.iacr.org/2013/650.
  9. [13]Samuel Bouaziz-Ermann, Minki Hhan, Garazi Muguruza, and Quoc-Huy Vu. On limits on the provable consequences of quantum pseudorandomness. arXiv:2510.05393, version 4, 2026. https://arxiv.org/abs/2510.05393v4.
  10. [15]James Bartusek, Aparna Gupte, Saachi Mutreja, and Omri Shmueli. Classical obfuscation of quantum circuits via publicly-verifiable QFHE. arXiv:2510.08400, version 2, 2026. Originally posted in 2025.arxiv.org/abs/2510.08400
  11. [16]Samuel Bouaziz-Ermann and Garazi Muguruza. Quantum pseudorandomness cannot be shrunk in a black-box way, 2024.
  12. [18]Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. A new world in the depths of microcrypt: Separating owsgs and quantum money from qefid. arXiv preprint arXiv:2410.03453, 2024.DOI
  13. [19]Mohammed Barhoush, Ryo Nishimaki, and Takashi Yamakawa. Microcrypt assumptions with quantum input sampling and pseudodeterminism: Constructions and separations. In International Conference on the Theory and Application of Cryptology and Information Security, pages 516–548. Springer, 2025. Full version: https://arxiv.org/abs/2505.14461v1.
  14. [20]Kai-Min Chung, Eli Goldin, and Matthew Gray. On central primitives for quantum cryptography with classical communication. In Annual International Cryptology Conference, pages 215–248. Springer, 2024. Full version: https://arxiv.org/abs/2402.17715v2.
  15. [21]Claude Crépeau, Frédéric Légaré, and Louis Salvail. How to convert the flavor of a quantum bit commitment. In Advances in Cryptology – EUROCRYPT 2001, volume 2045 of Lecture Notes in Computer Science, pages 60–77. Springer, 2001.DOI
  16. [22]Andrea Coladangelo and Saachi Mutreja. On black-box separations of quantum digital signatures from pseudorandom states. In Theory of Cryptography Conference, pages 289–317. Springer, 2024.arxiv.org/abs/2402.08194
  17. [23]Kai-Min Chung and Rafael Pass. Tight parallel repetition theorems for public-coin arguments using KL-divergence. Cryptology ePrint Archive, Paper 2015/031, 2015. https://eprint.iacr.org/2015/031.DOI
  18. [24]Paul Dumais, Dominic Mayers, and Louis Salvail. Perfectly concealing quantum bit commitment from any quantum one-way permutation. In Advances in Cryptology – EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 300–315. Springer, 2000.DOI
  19. [25]Aditya Gulati, Dakshita Khurana, and Kabir Tomer. How to build pseudorandom unitaries in microcrypt, 2026.arxiv.org/abs/2610.03711
  20. [26]Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa. Countcrypt: Quantum cryptography between qcma and pp. arXiv preprint arXiv:2410.14792, 2024.arxiv.org/abs/2410.14792
  21. [27]Eli Goldin and Mark Zhandry. Translating between the common haar random state model and the unitary model, 2025.arxiv.org/abs/2503.11634
  22. [28]Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, 1999.DOI
  23. [29]Akinori Hosoyamada and Takashi Yamakawa. Finding collisions in a quantum world: Quantum black-box separation of collision-resistance and one-wayness. In Advances in Cryptology – ASIACRYPT 2020, Part I, volume 12491 of Lecture Notes in Computer Science, pages 3–32. Springer, 2020.
  24. [30]Russell Impagliazzo and Michael Luby. One-way functions are essential for complexity based cryptography. In 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), pages 230–235. IEEE Computer Society, 1989.DOI
  25. [31]R. Impagliazzo. A personal view of average-case complexity. In Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pages 134–147, 1995.
  26. [32]Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pages 44–61. ACM, 1989.
  27. [33]Toshiyuki Isshiki and Keisuke Tanaka. Improved constructions of quantum bit-commitment based on quantum one-way permutations. Technical Report C-172, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, February 2003.
  28. [34]Toshiyuki Isshiki and Keisuke Tanaka. Quantum bit-commitment for small storage based on quantum one-way permutations. RIMS Kōkyūroku, 1325:27–32, 2003.
  29. [35]Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, and Rudy Raymond H. Putra. Universal test for quantum one-way permutations. Theoretical Computer Science, 345(2–3):370–385, 2005.
  30. [36]Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Quantum public-key encryption with tamper-resilient public keys from one-way functions, 2023.arxiv.org/abs/2304.01800
  31. [37]Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113–133, 2009.
  32. [38]William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 189–200. Association for Computing Machinery, 2025.DOI
  33. [39]William Kretschmer. Quantum pseudorandomness and classical complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPICs), pages 2:1–2:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. Revised full version: arXiv:2103.09320v5, 2024.DOI
  34. [41]Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Cryptomania vs minicrypt in a quantum world. arXiv preprint arXiv:2504.05710, 2025.arxiv.org/abs/2504.05710
  35. [43]Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Impossibility of perfectly complete many-round key agreement in the QROM. arXiv:2608.03824v1, 2026. https://arxiv.org/abs/2608.03824v1.
  36. [44]John Lott and Cédric Villani. Weak curvature conditions and functional inequalities. Journal of Functional Analysis, 245(1):311–333, 2007. https://doi.org/10.1016/j.jfa.2006.10.018.
  37. [45]Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. From worst-case hardness of NP to quantum cryptography via quantum indistinguishability obfuscation. In ICALP 2026, volume 374 of Leibniz International Proceedings in Informatics (LIPIcs), 2026. Article 143. https://doi.org/10.4230/LIPIcs.ICALP.2026.143. Full version: https://arxiv.org/abs/2506.19542.
  38. [46]Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Advances in Cryptology – CRYPTO 2022, Part I, volume 13507 of Lecture Notes in Computer Science, pages 269–295. Springer, 2022.DOI
  39. [47]Tomoyuki Morimae and Takashi Yamakawa. Quantum advantage from one-way functions. Cryptology ePrint Archive, Paper 2023/161, 2023.arxiv.org/abs/2302.04749
  40. [48]Tatsuaki Okamoto, Keisuke Tanaka, and Shigenori Uchiyama. Quantum public-key cryptosystems. In Advances in Cryptology – CRYPTO 2000, volume 1880 of Lecture Notes in Computer Science, pages 147–165. Springer, 2000.
  41. [49]Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. SIAM Journal on Computing, 40(6):1803–1844, 2011.
  42. [50]Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: Deniable encryption, and more. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. ACM, 2014. Full version: https://eprint.iacr.org/2013/454.
  43. [51]John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences, 59(2):281–326, 1999.DOI
  44. [52]John Watrous. The theory of quantum information. Cambridge university press, 2018.DOI
  45. [53]Mark Zhandry. How to construct quantum random functions. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 679–687. IEEE, 2012.

Paper details

vlnc:W_78f3emj4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents