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 S S S , which outputs a classical puzzle and answer ( p , a ) (p,a) ( p , a ) , and a verifier V V V , which accepts honestly sampled pairs except with negligible probability. One-wayness requires that, for every QPT algorithm A A A ,
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). ( p , a ) ← S ( 1 λ ) Pr [ V ( p , A ( p )) = 1 ] ≤ negl ( λ ) .
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). E V - O W P u z z EV\text{-}OWPuzz E V - O W P u z z and q i O qiO q i O imply IND-CPA-secure q P K E qPKE q P K E 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) ( S , E ) , where S S S is the input sampler, and E E E is the evaluator. Let f f f be the function that maps x x x to the most likely output of E ( x ) E(x) E ( x ) . In each notion, one-wayness requires that, for every QPT inverter A A A ,
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). X ← S ( 1 λ ) Y ← E ( X ) Pr [ E ( A ( Y )) = Y ] ≤ negl ( λ ) .
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.
Generalized-qOWF1 _1 1 . The sampler S S S 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). ∀ x ∈ { 0 , 1 } m ( λ ) , Pr [ E ( x ) = f ( x )] ≤ negl ( λ ) .
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.
Generalized-qOWF2 _2 2 . The sampler S S S 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). X ← { 0 , 1 } m ( λ ) Pr [ E ( X ) = f ( X )] ≤ negl ( λ ) .
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 ] .
Generalized-q O W F 3 \mathrm{qOWF}_3 qOWF 3 . The sampler S S S 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). X ← S ( 1 λ ) Pr [ E ( X ) = f ( X )] ≤ negl ( λ ) .
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 q O W F 1 \mathrm{qOWF}_1 qOWF 1 , q O W F 2 \mathrm{qOWF}_2 qOWF 2 and q O W F 3 \mathrm{qOWF}_3 qOWF 3 to refer to generalized-q O W F 1 \mathrm{qOWF}_1 qOWF 1 , generalized-q O W F 2 \mathrm{qOWF}_2 qOWF 2 and generalized-q O W F 3 \mathrm{qOWF}_3 qOWF 3 , respectively, from now on.
The distinction between these notions of q O W F \mathrm{qOWF} qOWF suggests a more nuanced question: how does the relationship between q O W F \mathrm{qOWF} qOWF and q P K E \mathrm{qPKE} qPKE change across the different notions of q O W F \mathrm{qOWF} 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 q P K E \mathrm{qPKE} qPKE exists but neither q O W F 1 \mathrm{qOWF}_1 qOWF 1 's nor q O W F 2 \mathrm{qOWF}_2 qOWF 2 's exist.
Thus, this gives black-box separations between q P K E \mathrm{qPKE} qPKE and the two notions q O W F 1 \mathrm{qOWF}_1 qOWF 1 and q O W F 2 \mathrm{qOWF}_2 qOWF 2 , but what about the last and weakest notion, q O W F 3 \mathrm{qOWF}_3 qOWF 3 ? Interestingly, we find that q O W F 3 \mathrm{qOWF}_3 qOWF 3 has a different relation with q P K E \mathrm{qPKE} qPKE and EV-OWPuzz. Our third result presents this relationship.
Theorem 1.4 (Informal: equivalence with puzzles). q O W F 3 \mathrm{qOWF}_3 qOWF 3 's exist if and only if EV-OWPuzz exist. Since q P K E \mathrm{qPKE} qPKE implies EV-OWPuzz [20 ] , we conclude that q P K E \mathrm{qPKE} qPKE implies q O W F 3 \mathrm{qOWF}_3 qOWF 3 's.
This equivalence may seem surprising since q O W F 3 \mathrm{qOWF}_3 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 q O W F 3 \mathrm{qOWF}_3 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 q O W F 1 \mathrm{qOWF}_1 qOWF 1 or q O W F 2 \mathrm{qOWF}_2 qOWF 2 , which by Theorem 1.3 are separated from q P K E \mathrm{qPKE} qPKE and, hence, are also separated from EV-OWPuzz.
We summarize all our results in Figure 1 .
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 _1 1 s and qOWF2 _2 2 s: 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} 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 O s a m p O_{\mathrm{samp}} O samp , O e n c O_{\mathrm{enc}} O enc , and O d e c O_{\mathrm{dec}} O 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 c log λ c \log\lambda c log λ -qubit PRSs, for sufficiently large c c c , 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 _1 1 s and qOWF2 _2 2 s 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 1 requires this on every input, while qOWF2 _2 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 n n n , sample a random table, where each row indexed by j ∈ { 0 , 1 } n j \in\{0,1\}^n j ∈ { 0 , 1 } n contains a uniformly random string s j ∈ { 0 , 1 } 8 n s_j \in\{0,1\}^{8n} s j ∈ { 0 , 1 } 8 n , and two random disjoint sets of ciphertext strings, one for each message bit. Each set has 2 2 n 2^{2^n} 2 2 n elements from { 0 , 1 } 12 n \{0,1\}^{12n} { 0 , 1 } 12 n . We call j j j a p-key and s j s_j s 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 O s a m p O_{\mathrm{samp}} O samp . Prepare a uniform superposition over pairs ( j , s j ) (j, s_j) ( 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 O e n c O_{\mathrm{enc}} O enc . Given a p-key j j j and a message bit b b b , prepare a uniform superposition over the ciphertext set for ( j , b ) (j,b) ( j , b ) . Measuring this state samples a ciphertext string c c c .
Decryption oracle O d e c O_{\mathrm{dec}} O dec . Given ( j , s j , c ) (j,s_j,c) ( j , s j , c ) for an honestly sampled ciphertext string c c c , 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 , s j ) (j,s_j) ( j , s j ) using O s a m p O_{\mathrm{samp}} O samp , publishes j j j , and keeps ( j , s j ) (j,s_j) ( j , s j ) as the secret key. Encryption samples c c c using O e n c ( j , b ) O_{\mathrm{enc}}(j,b) O enc ( j , b ) and outputs ( j , c ) (j,c) ( j , c ) ; decryption uses O d e c ( j , s j , c ) O_{\mathrm{dec}}(j,s_j,c) O dec ( j , s j , c ) . Correctness is immediate, and all keys and ciphertexts are classical. Security follows by standard quantum query hybrids. Let J J J be the challenge public key. First, remove ( J , s J ) (J,s_J) ( J , s J ) from the key-sampling state. Next, replace decryption at J J J 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 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 / 2 1/2 1/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 1 : f ( j , s ) = { ( 0 , j ) , s = s j , ⊥ , s ≠ s j . f(j,s)=\begin{cases}(0,j), & s=s_j,\\ \bot, & s\ne s_j.\end{cases} f ( j , s ) = { ( 0 , j ) , ⊥ , s = s j , s = s j . 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 , s j ) (j,s_j) ( 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 , s j ) (j,s_j) ( j , s j ) under f f f is ( 0 , j ) (0,j) ( 0 , j ) . This implies that any inverter against f f f with respect to this quantum input sampler essentially computes the secret key ( j , s j ) (j,s_j) ( j , s j ) given a sample public key j j j 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 f f f can fail fixed-input determinism while the qPKE construction remains correct and secure. In particular, at each length n n n , sample two independent tables A , B A,B A , 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\} i ∈ { 1 , 2 , 3 } and t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , and set τ = ( i − 1 + t ) / 3 \tau=(i-1+t)/3 τ = ( i − 1 + t ) /3 , which is uniform in [ 0 , 1 ] [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 τ = 0 , the oracle operations use only A A A ; at τ = 1 \tau= 1 τ = 1 , they use only B B B . For intermediate values, sampling can use weighted superpositions of the states specified by A A A and B B B . For example, at τ = 1 / 2 \tau= 1/2 τ = 1/2 , conditioned on obtaining p-key j j j , the s-key register is in the state ( ∣ s j A ⟩ + ∣ s j B ⟩ ) / 2 (|s_j^A\rangle+ |s_j^B\rangle)/\sqrt{2} ( ∣ s j A ⟩ + ∣ s j B ⟩) / 2 assuming s j A , s j B s_j^A,s_j^B s 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 j j j with distinct s-keys and disjoint ciphertext sets across the two tables. For τ ∈ [ 0 , 1 / 3 ] \tau\in[0,1/3] τ ∈ [ 0 , 1/3 ] , both sampling operations use A A A , and honestly sampled keys decrypt correctly. Yet, decrypting an A A A -encryption of one with s j B s_j^B s j B returns one with a probability p ( τ ) p(\tau) p ( τ ) that varies continuously from 1 / 2 1/2 1/2 to 1 1 1 3 . 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 B B B . 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) ( 0 , j ) and ⊥ \perp ⊥ each with probability at least 1 / 3 1/3 1/3 on the fixed input ( j , s j B ) (j,s_j^B) ( j , s j B ) ; hence, the above evaluation algorithm for f f f fails fixed-input determinism.
Ruling out all qOWFs by conditioning the oracle distribution. However, only ruling out the particular q O W F 1 \mathrm{qOWF}_1 qOWF 1 f f f is not enough; we need to rule out every q O W F 1 \mathrm{qOWF}_1 qOWF 1 and every q O W F 2 \mathrm{qOWF}_2 qOWF 2 . We construct it by conditioning : sample only oracles conditioned on satisfying some event, such that no q O W F 1 \mathrm{qOWF}_1 qOWF 1 or q O W F 2 \mathrm{qOWF}_2 qOWF 2 exists conditioned on this event.4 Bouaziz–Ermann et al. [13 Section 5.2] use this approach to rule out candidate quantum-evaluable pseudorandom generators, considering each candidate infinitely often and ensuring either a correctness failure or a successful attack. However, we need to be careful, since if we condition on an event with too small a weight, then after conditioning on such an event, the qPKE security may not hold. For example, conditioning on every s-key in both tables being the all-zero string makes every honestly generated secret key publicly known. Applying this restriction at infinitely many lengths destroys qPKE security.
There are two ways to rule out a candidate evaluator: either we condition on those oracle parameters for which it is not deterministic enough to satisfy the correctness condition of q O W F 1 \mathrm{qOWF}_1 qOWF 1 or q O W F 2 \mathrm{qOWF}_2 qOWF 2 and we condition on that event, or we show somehow that the evaluator can be inverted using the PSPACE oracle. Thus one option is that we categorize each evaluator into two categories, according to the determinism requirement with respect to both q O W F 1 \mathrm{qOWF}_1 qOWF 1 and q O W F 2 \mathrm{qOWF}_2 qOWF 2 , averaged over the oracle randomness:
the first category where the failure probability of determinism, i.e., the probability over the oracles that the determinism does not hold, is at least a threshold t t t , in which case we condition on the event that they are not deterministic.5
the second category where this failure probability is smaller than t t t with respect to either q O W F 1 \mathrm{qOWF}_1 qOWF 1 or q O W F 2 \mathrm{qOWF}_2 qOWF 2 .
If we can prove that, using a PSPACE oracle, we can invert all qOWFs corresponding to the evaluators in the second category, then we can rule out all q O W F 1 \mathrm{qOWF}_1 qOWF 1 s and q O W F 2 \mathrm{qOWF}_2 qOWF 2 s. However, the PSPACE oracle does not have access to the oracle data, namely ( A , B , τ ) (A,B,\tau) ( A , B , τ ) . So it seems like the only way we can rule out evaluators in the second category is to show that these evaluators do not the tables in a non-trivial way! Our intuition here is that since any such evaluator in the second category is deterministic according to the requirements of either qOWF1 _1 1 or qOWF2 _2 2 , it agrees on a function for an overwhelming fraction of the inputs. Hence, since the three oracles O s a m p , O e n c , O d e c O_{\mathrm{samp}}, O_{\mathrm{enc}}, O_{\mathrm{dec}} O samp , O enc , O dec are randomized, any such evaluator satisfying such an agreement should not depend on the oracles too strongly, i.e., the evaluator computes the same function under a large fraction of the oracles. We formalize this intuition and prove a general result which can be seen next. This can be seen as a generalization of the barrier theorem proven by Bouaziz–Ermann et al. [13 Theorem 5.3 and Lemma 5.8] , who obtain a similar agreement albeit on output bits in the common Haar random model. Hence we call it the general barrier theorem.
The Generalized Barrier Result. Consider a distribution on some space of tables T \mathcal{T} T , and say we consider a map encoding a given table A A A to an oracle O ( A ) ∈ X O(A) \in\mathcal{X} O ( A ) ∈ X , where X \mathcal{X} X is a space of oracles. Finally, suppose there is a way to get interpolation between two tables A , B ∈ T A, B \in\mathcal{T} A , B ∈ T to get an interpolated oracle, using an interpolation parameter τ ∈ [ 0 , 1 ] \tau\in[0,1] τ ∈ [ 0 , 1 ] represented as Interp ( A , B , τ ) \operatorname{Interp}(A, B, \tau) Interp ( A , B , τ ) such that Interp ( A , B , 0 ) = O ( A ) \operatorname{Interp}(A, B, 0) = O(A) Interp ( A , B , 0 ) = O ( A ) and Interp ( A , B , 1 ) = O ( B ) \operatorname{Interp}(A, B, 1) = O(B) Interp ( A , B , 1 ) = O ( B ) . Moreover, suppose changing τ \tau τ changes the interpolated oracle Interp ( A , B , τ ) \operatorname{Interp}(A, B, \tau) Interp ( A , B , τ ) at a bounded speed v 0 v_0 v 0 , i.e., for any s , t ∈ [ 0 , 1 ] s,t \in[0,1] s , t ∈ [ 0 , 1 ] the distance (as per operator norm) between the oracles is bounded by ∣ Interp ( A , B , s ) − Interp ( A , B , t ) ∣ ≤ v 0 ∣ s − t ∣ \lvert\operatorname{Interp}(A, B, s) - \operatorname{Interp}(A, B, t) \rvert\leq v_0\lvert s-t\rvert ∣ Interp ( A , B , s ) − Interp ( A , B , t )∣ ≤ v 0 ∣ s − t ∣ . (Later, we show that our oracles also change in a bounded fashion as we vary τ \tau τ ; see Lemma 5.7 .) Then, we show:
Theorem 2.1 (Formalized in Corollary 5.3). Let ν \nu ν be a distribution on the set of tables T \mathcal{T} T and draw A , B A,B A , B independently from ν \nu ν , and independently sample τ \tau τ from [ 0 , 1 ] [0,1] [ 0 , 1 ] uniformly. Let μ \mu μ be the resulting distribution Interp ( A , B , τ ) \operatorname{Interp}(A,B,\tau) Interp ( A , B , τ ) obtained on the oracles. Suppose
S 1 , … , S r S_1,\ldots,S_r S 1 , … , S r are sets of oracles that are pairwise separated by distance at least δ > 0 \delta> 0 δ > 0 ,
a sample O O O drawn from μ \mu μ lies outside their union with probability ε b a d ≤ 1 / 2 \varepsilon_{\mathrm{bad}} \leq1/2 ε bad ≤ 1/2 ,
then there exists a set S i S_i S i , such that the probability that a sample from μ \mu μ falls in S i S_i S i is at least 1 − ( 1 + 6 v 0 δ ) ε b a d 1 - \left(1+\frac{6v_0}{\delta}\right)\varepsilon_{\mathrm{bad}} 1 − ( 1 + δ 6 v 0 ) ε bad .
In our case, we apply the barrier theorem to rule out each evaluator from the second category (see Item 2) according to each of the two definitions. The sets of oracles S 1 , … , S r S_1,\ldots,S_r S 1 , … , S r are defined (separately for each of the two definitions, as we describe in the next paragraph). In the case of qOWF1 _1 1 , each set S i S_i S i consists of all the oracles that yield the same function under the evaluator. Hence, for our application, it is going to be doubly exponential in the input length of the functions. Fortunately, the bound in the theorem is independent of the number of sets, and thus does not become meaningless even for such a large number of sets. This is one of two axes of generalization compared to the barrier theorem in [13 ] , which we need for our separation. The second axis of generalization is that our result holds for an arbitrary metric space X \mathcal{X} X , space T \mathcal{T} T , and functions O \mathcal{O} O , Interp \operatorname{Interp} Interp satisfying the conditions above, and with respect to any distribution ν \nu ν , without needing the specific properties of the Haar random distribution.
Invoking the barrier theorem. Next, we complete the separation proof, assuming the generalized barrier theorem. To apply the above generalized barrier theorem, we define the sets of oracles S 1 , … , S r S_1,\ldots,S_r S 1 , … , S r for the two definitions separately. For qOWF1 _1 1 , fix an evaluator E E E and the security parameter, keeping the operations at short lengths fixed. Let S f S_f S f contain the oracles for which E E E outputs f ( x ) f(x) f ( x ) with probability at least 5 / 6 5/6 5/6 on every input x x x . Since different functions force an output-probability gap of at least 2 / 3 2/3 2/3 at some input x x x , these sets are separated by 1 / ( 3 q ) 1/(3q) 1/ ( 3 q ) in the maximum operator-norm distance between corresponding oracle operations, where q q q denotes the number of queries that the evaluator makes. In the second category (see Item 2) with respect to qOWF1 _1 1 , their union has probability at least 1 − t 1-t 1 − t , so Theorem 2.1 gives a set S g S_g S g of oracles with probability weight at least 1 − O ( q t ) 1-O(qt) 1 − O ( q t ) (Lemma 5.16) such that the evaluator computes the same function on all inputs under any oracle in S g S_g S g .
Next, after estimating the fixed short operations, and then if the sampled oracle lies in the corresponding large set S g S_g S g (which happens with probability at least 1 − O ( q t ) 1-O(qt) 1 − O ( q t ) ), the PSPACE oracle can find a preimage (Lemmas 5.17 and 5.18 ) by averaging over oracles from the base distribution on the oracles, without needing the real oracles. Thus, at each step of our conditioning, which corresponds to a particular evaluator, either the evaluator is of the first category (see Item 1) and we condition on an event that forces a correctness failure, or we show that the evaluator can be inverted except with a small probability O ( q t ) O(qt) O ( q t ) (and we do not condition). With an appropriate choice of the parameters, these small probabilities indicating the potential failure to invert at each of the countably many steps have a finite sum. Thus, after conditioning over all countably many steps, we get a distribution that, by the Borel-Cantelli theorem, satisfies that with probability one, no qOWF1 _1 1 exists (Theorem 5.20 ).
For qOWF2 _2 2 , instead fix an input x x x and let S x , y S_{x,y} S x , y contain the oracles for which Pr [ E O ( x ) = y ] ≥ 5 / 6 \Pr[E^O(x)=y]\ge5/6 Pr [ E O ( x ) = y ] ≥ 5/6 ; it is easy to see that these sets also satisfy the hypothesis for the generalized barrier theorem. This lets us invoke Theorem 2.1 separately for each reliable input, yielding an agreement guarantee with one function for most oracles, on most inputs. For each evaluator E E E , we choose sufficiently spaced security parameters 1 ≤ λ 1 < λ 2 < ⋯ 1\le\lambda_1<\lambda_2<\cdots 1 ≤ λ 1 < λ 2 < ⋯ : at λ 1 \lambda_1 λ 1 , we sample the new oracle data that E ( 1 λ 1 ) E(1^{\lambda_1}) E ( 1 λ 1 ) may query, after potential conditioning with respect to Definition 1; at λ 2 \lambda_2 λ 2 , we do the same with respect to Definition 2, keeping previously sampled data unchanged; and we continue alternating. This way, after countably many such steps, we obtain a distribution under which, with probability one, each evaluator is either invertible at infinitely many security parameters or fails the required determinism at infinitely many security parameters, for each definition separately; see Theorem 5.20 .6
qPKE security after conditioning. It remains to show that conditioning the oracle distribution as above preserves qPKE security. We measure the accumulated effect of the conditioning using relative entropy between the conditioned distributions and the base distribution, and choose the parameters so that this quantity stays polynomially bounded on all oracle lengths an efficient adversary can query; in particular, we show that the relative entropy of the conditioned distribution with respect to the base distribution, restricted to oracle lengths at most m m m , is bounded by 2 m 2m 2 m . Next, we show that using Pinsker’s inequality, this bound allows us to replace the data at a hidden random subset of p-keys containing the challenge p-key by fresh samples from the base distribution, with negligible effect on the adversary’s success probability7 ; see Lemmas 5.8 and 5.12 . Note that the secret data at the challenge public key are now independent of the remaining oracle data, hence the earlier qPKE security argument (shown in Lemma 5.11 ) applies (see Lemma 5.12 ). Using Borel–Cantelli, this gives security with probability one under the conditioned distribution. Moreover, with some positive probability, the two tables’ ciphertext sets are disjoint at every p-key and length. Therefore, we conclude that there must exist a fixed oracle with perfectly correct, secure qPKE but neither qOWF1 _1 1 nor qOWF2 _2 2 exist (Corollary 5.21 ).
Proving the barrier theorem. We prove the general barrier theorem using a path-based framework ; we show that for any independently sampled oracles O 1 O_1 O 1 , O 2 O_2 O 2 from μ \mu μ , we can connect them using a random path of oracles such that each oracle in the path has marginal distribution μ \mu μ ; the detailed path construction is given in the proof of Lemma 5.5. Then we show the contrapositive of the above theorem by proving that if no single set S i S_i S i has probability weight large enough under μ \mu μ , then since the sets are mutually separated, the path must spend a sufficient amount of time, i.e., contain a large number of oracles outside the union of the sets S 1 , … , S r S_1,\ldots,S_r S 1 , … , S r . However, we know that each oracle in the path is marginally distributed according to μ \mu μ , and that most of the probability weight of μ \mu μ lies in the union of the sets; the expected number of oracles in the path, or the expected amount of time spent outside the union of the sets, must be small, thus arriving at a contradiction. The formal argument is a bit more delicate as the random path is continuous, but the same intuition holds by considering the path to be indexed by continuous time, and then concluding the contradiction on the amount of time spent outside the union of the sets; see Section 5.1.1 for more details.
Public-key encryption from puzzles and qiO
Our starting point is the classical construction of OWFs together with iO implying public-key encryption [50 ] . The goal is to replace the role of the OWF assumption with EV-OWPuzz.
The qPKE construction. We first describe the construction with classical iO. Given such an obfuscation, the idea behind the PKE scheme is to publish an obfuscation of P u P_u P u for a uniformly random u u u as the public key and keep u u u as the secret key. Here P u P_u P u denotes a function which outputs 1 if the input is u u u and 0 elsewhere. The encryption of a message bit b b b is to simply output an obfuscated program as the ciphertext, where the circuit to be obfuscated returns the message bit when the public-key program accepts its input and zero otherwise, so evaluating it at the secret key u u u recovers the message. Hence, decryption is just evaluating the cipher-text program at the secret key. It is easy to see that correctness follows from the correctness of the obfuscation scheme. Further it is easy to see that for security, we only need the additional point-hiding property from the iO scheme that the obfuscation of random point function P u P_u P u for a uniformly random u u u is indistinguishable from the obfuscation of the zero circuit Z Z Z . However, to prove such a property for a iO scheme, we would need an additional hardness assumption like one-way functions, since this cannot follow from iO security unconditionally as iO can even exist when P=NP. A recent work of [45 ] provides such a construction of PKE based on iO using the complexity theoretic assumption in the proof. Note that the same template would work to give qPKE even if we can get such a point-hiding guarantee for qiO. Our approach is to prove such a guarantee for qiO but by only relying on the requirement of EV-OWPuzz instead of one-way functions.8
The obstacle and the suppression lemma. In the classical case, the starting point of the proof is that iO is a single-point differing-inputs obfuscation (diO), i.e., a non-negligible distinguisher between obfuscations of two circuits differing on one input allows that input to be recovered from the circuit descriptions [11 Section 6.1] . In the proof, we can combine this property with an injective keyed one-way function (which can be built from iO and one-way functions) due to the deterministic and injective property, to ensure that finding a distinguishing input for two 1-point differing inputs, would lead to inverting the keyed one-way function to the unique answer. However, an EV-OWPuzz verifier may accept many answers with intermediate acceptance probabilities so there is no unique answer, which would violate the condition of requiring the circuits to differ at a single point. Thus we need a way to take an EV-OWPuzz verifier and suppress all but a unique accepting answer for it.
In this work, we show that such a suppression lemma indeed holds.
Lemma 2.2 (Informal suppression lemma; formalized in Lemma 6.1 ). For any EV-OWPuzz scheme, given a puzzle p p p with an answer that the verifier accepts with probability at least 2 / 3 2/3 2/3 , an efficient randomized procedure constructs a quantum circuit W W W based on the puzzle p p p such that, with inverse-polynomial probability, there is an answer a ⋆ a^{\star} a ⋆ satisfying Pr [ W ( a ⋆ ) = 1 ] ≥ 1 − negl ( λ ) \Pr[W(a^{\star})=1] \ge1-\operatorname{negl}(\lambda) Pr [ W ( a ⋆ ) = 1 ] ≥ 1 − negl ( λ ) , for every a ≠ a ⋆ a \ne a^{\star} a = a ⋆ , Pr [ W ( a ) = 1 ] ≤ negl ( λ ) \Pr[W(a)=1] \le\operatorname{negl}(\lambda) Pr [ W ( a ) = 1 ] ≤ negl ( λ ) and the EV-OWPuzz verifier still accepts a ⋆ a^{\star} a ⋆ for p p p with probability greater than 1 / 3 1/3 1/3 .
To prove the point-hiding property for qiO based on the suppression lemma, note that on a successful trial, the circuit produced by suppression implements a point function at an answer a ⋆ a^{\star} a ⋆ . Masking its input by a uniform r r r makes the accepting point u = a ⋆ ⊕ r u=a^{\star}\oplus r u = a ⋆ ⊕ r uniform. Finally, an extension of the extraction argument from [11 Section 6.1] turns a distinguisher between obfuscations of a random point and zero circuits, with a non-negligible advantage, into a procedure recovering a ⋆ = u ⊕ r a^{\star}=u\oplus r a ⋆ = u ⊕ r with inverse-polynomial probability. This contradicts the EV-OWPuzz security since a ⋆ a^{\star} a ⋆ is still accepted by the EV-OWPuzz verifier with probability at least 1 / 3 1/3 1/3 , proving the point hiding guarantee of qiO (see Lemma 6.2).
Proving the suppression lemma. To prove the suppression, we first amplify the verifier by standard independent repetition so that answers originally accepted with probability at least 2 / 3 2/3 2/3 are accepted with overwhelming probability, while those accepted with probability at most 1 / 3 1/3 1/3 are accepted with negligible probability. Next, we guess a hash output length, sample a random hash function, and retain only answers hashing to zero. With inverse-polynomial probability, this hash bucket contains one answer whose acceptance probability exceeds that of every other retained answer by an inverse-polynomial amount. Next, conditioned on this event, we utilize this inverse-polynomial gap to amplify the acceptance probability of the unique answer to 1 − 1- 1 − negligible while on all other inputs, the accepting probability plunges to negligible, via independent repetitions and a suitable choice of threshold on the number of accepting trials for acceptance. For more details on how to choose random hash function and the threshold efficiently, see the proof of Lemma 6.1 .
Definitions
We collect the conventions and primitive definitions.
Conventions
We use a lowercase prefix q for the quantum-computable variant of a classical primitive, as in qOWF and qPKE.
All algorithms and adversaries in the work are uniform quantum polynomial time (QPT). Their classical input and output lengths have fixed polynomial bounds on the security parameter. A function η : N → [ 0 , 1 ] \eta:\mathbb{N}\to[0,1] η : N → [ 0 , 1 ] is negligible if, for every positive integer c c c , η ( λ ) ≤ λ − c \eta(\lambda)\le\lambda^{-c} η ( λ ) ≤ λ − c for all sufficiently large λ \lambda λ . We write negl ( λ ) \operatorname{negl}(\lambda) negl ( λ ) for such a bound. We use [ d ] = { 1 , … , d } [d]=\{1,\ldots,d\} [ d ] = { 1 , … , d } , identify [ 2 n ] [2^n] [ 2 n ] with { 0 , 1 } n \{0,1\}^n { 0 , 1 } n , and write U m U_m U m for the uniform distribution on { 0 , 1 } m \{0,1\}^m { 0 , 1 } m .
We use P, NP, and PSPACE for deterministic polynomial time, nondeterministic polynomial time, and deterministic polynomial space, respectively. We also use bounded-error quantum polynomial time (BQP), quantum Merlin–Arthur (QMA), and quantum classical Merlin–Arthur (QCMA).
Oracle access and gate conventions. Algorithms with oracle access in this work may query the oracle in superposition, and have forward, inverse, transpose, conjugate, and controlled access.
Probability distances. For distributions Q , P Q, P Q , P , define their relative entropy by D ( Q ∥ P ) = ∫ log ( d Q / d P ) d Q D(Q\|P) = \int\log(dQ/dP)\,dQ D ( Q ∥ P ) = ∫ log ( d Q / d P ) d Q when Q Q Q has a density relative to P P P , and set it to infinity otherwise. Here log \log log denotes the natural logarithm function. The statistical distance, or equivalently, the total variation distance, is SD ( Q , P ) = sup A ∣ Q ( A ) − P ( A ) ∣ \operatorname{SD}(Q,P) = \sup_A |Q(A)-P(A)| SD ( Q , P ) = sup A ∣ Q ( A ) − P ( A ) ∣ , where the supremum is over measurable events. We use the chain rule for relative entropy, its nonnegativity, and Pinsker’s inequality, as recalled below. First, we recall the chain rule for relative entropy, expressed in terms of conditional distributions.
Lemma 3.1 (Chain rule for relative entropy [23 Section 2.2, Lemma 3] ). For joint distributions R U V \mathcal{R}_{UV} R U V and S U V \mathcal{S}_{UV} S U V with finite relative entropy,
D ( R U V ∥ S U V ) = D ( R U ∥ S U ) + E u ← R U D ( R V ∣ U = u ∥ S V ∣ U = u ) . D(\mathcal{R}_{UV}\|\mathcal{S}_{UV}) = D(\mathcal{R}_{U}\|\mathcal{S}_{U}) + \underset{u\leftarrow\mathcal{R}_{U}}{\mathbb{E}} D(\mathcal{R}_{V\mid U=u}\|\mathcal{S}_{V\mid U=u}). D ( R U V ∥ S U V ) = D ( R U ∥ S U ) + u ← R U E D ( R V ∣ U = u ∥ S V ∣ U = u ) .
Next we note the following standard fact about the relative entropy. Note that no independence is required under R \mathcal{R} R .
Lemma 3.2 (Relative entropy to a product distribution [23 Section 2.2, Lemma 5] ). Let R \mathcal{R} R be a joint distribution on X 1 , … , X m X_1,\ldots,X_m X 1 , … , X m , with marginals R 1 , … , R m \mathcal{R}_1,\ldots,\mathcal{R}_m R 1 , … , R m . For any product distribution S = ∏ j = 1 m S j \mathcal{S} = \prod_{j=1}^{m}\mathcal{S}_j S = ∏ j = 1 m S j ,
∑ j = 1 m D ( R j ∥ S j ) ≤ D ( R ∥ ∏ j = 1 m S j ) . \sum_{j=1}^{m}D(\mathcal{R}_j\|\mathcal{S}_j) \le D\left(\mathcal{R}\middle\|\prod_{j=1}^{m}\mathcal{S}_j\right). j = 1 ∑ m D ( R j ∥ S j ) ≤ D ( R j = 1 ∏ m S j ) .
Finally, we recall Pinsker’s inequality.
Lemma 3.3 (Pinsker’s inequality [52 Theorem 5.15] ). For distributions R , S \mathcal{R},\mathcal{S} R , S , it holds that
SD ( R , S ) ≤ D ( R ∥ S ) 2 . \operatorname{SD}(\mathcal{R},\mathcal{S}) \le\sqrt{\frac{D(\mathcal{R}\|\mathcal{S})}{2}}. SD ( R , S ) ≤ 2 D ( R ∥ S ) .
One-way functions
A quantum computable one-way function or qOWF is given by a QPT evaluator E ( x ) E(x) E ( x ) with m ( λ ) m(\lambda) m ( λ ) -bit inputs and ℓ ( λ ) \ell(\lambda) ℓ ( λ ) -bit classical outputs. Define f ( x ) f(x) f ( x ) to be the most likely output of E ( x ) E(x) E ( x ) , with ties broken lexicographically, and let
e ( x ) = Pr [ E ( x ) ≠ f ( x ) ] . e(x)=\Pr[E(x)\ne f(x)]. e ( x ) = Pr [ E ( x ) = f ( x )] .
Definition 1 (qOWF1 _1 1 : Every-input determinism). A qOWF1 _1 1 E E E is associated with a QPT input sampler S S S such that it satisfies one-wayness as defined below with respect to S S S . Moreover, it satisfies that there is a negligible function η ( λ ) \eta(\lambda) η ( λ ) such that
∀ x ∈ { 0 , 1 } m ( λ ) , e ( x ) ≤ η ( λ ) . \forall x\in\{0,1\}^{m(\lambda)},\ e(x)\le\eta(\lambda). ∀ x ∈ { 0 , 1 } m ( λ ) , e ( x ) ≤ η ( λ ) .
Setting the sampler S S S to be the uniform random distribution recovers the standard definition of qOWF, as considered in past works; see Refs. [3 , 21 , 24 , 25 , 29 , 33 , 34 , 35 , 38 , 47 , 48 ] .
Definition 2 (qOWF2 _2 2 : Average determinism on uniform inputs). A q O W F 2 qOWF_2 q O W F 2 E E E satisfies the one-wayness property as defined below with respect to S = U m ( λ ) S = U_m(\lambda) S = U m ( λ ) , and also satisfies
E X ← U m ( λ ) e ( X ) ≤ η ( λ ) \mathbb{E}_{X \leftarrow U_m(\lambda)} e(X) \leq\eta(\lambda) E X ← U m ( λ ) e ( X ) ≤ η ( λ ) for some negligible function η ( λ ) \eta(\lambda) η ( λ ) .
We introduce the following new notion for this paper, which is implied by the previous two notions. It permits arbitrary quantum input sampling while requiring determinism only on average over that sampler. We refer to it explicitly as qOWF3 _3 3 to distinguish it from the stronger notions above.
Definition 3 (qOWF3 _3 3 : Average determinism with arbitrary sampling). A q O W F 3 qOWF_3 q O W F 3 E E E is associated with a Q P T QPT QP T sampler S S S , such that it satisfies the one-wayness as defined below with respect to S S S . Moreover, it satisfies
E X ← S ( 1 λ ) e ( X ) ≤ η ( λ ) \mathbb{E}_{X \leftarrow S(1^\lambda)} e(X) \leq\eta(\lambda) E X ← S ( 1 λ ) e ( X ) ≤ η ( λ ) for one negligible η \eta η .
One-wayness. Given a Q P T QPT QP T sampler S S S of classical inputs, we say one-wayness holds if, for every uniform Q P T QPT QP T inverter I I I ,
Pr X ← S ( 1 λ ) Y ← E ( X ) X ′ ← I ( Y , 1 λ ) [ E ( X ′ ) = Y ] ≤ negl ( λ ) . \Pr_{\substack{X \leftarrow S(1^\lambda)\\Y\leftarrow E(X)\\X' \leftarrow I(Y,1^\lambda)}}\left[E(X') = Y\right] \leq\operatorname{negl}(\lambda). X ← S ( 1 λ ) Y ← E ( X ) X ′ ← I ( Y , 1 λ ) Pr [ E ( X ′ ) = Y ] ≤ negl ( λ ) .
Here we assume that all malformed inputs are mapped to ⊥ \perp ⊥ by E E E .
Pseudorandom Generators
We recall the notion of quantum pseudorandom generators with uniform input sampling.
Definition 4 (Quantum pseudorandom generator). A q P R G qPRG q P R G is a Q P T QPT QP T algorithm G G G with classical seeds of length r ( λ ) r(\lambda) r ( λ ) and classical outputs of polynomial length s ( λ ) ≥ r ( λ ) + 1 s(\lambda) \geq r(\lambda) + 1 s ( λ ) ≥ r ( λ ) + 1 , satisfying:
Correctness. There exist deterministic functions g λ : { 0 , 1 } r ( λ ) → { 0 , 1 } s ( λ ) g_\lambda: \{0,1\}^{r(\lambda)} \to\{0,1\}^{s(\lambda)} g λ : { 0 , 1 } r ( λ ) → { 0 , 1 } s ( λ ) such that
Pr X ← { 0 , 1 } r ( λ ) [ G ( X ) ≠ g λ ( X ) ] ≤ negl ( λ ) . \Pr_{X \leftarrow\{0,1\}^{r(\lambda)}}\left[G(X) \ne g_\lambda(X)\right] \leq\operatorname{negl}(\lambda). X ← { 0 , 1 } r ( λ ) Pr [ G ( X ) = g λ ( X ) ] ≤ negl ( λ ) . Pseudorandomness. For every Q P T QPT QP T distinguisher D D D ,
∣ Pr X ← { 0 , 1 } r ( λ ) [ D ( G ( X ) ) = 1 ] − Pr Y ← { 0 , 1 } s ( λ ) [ D ( Y ) = 1 ] ∣ ≤ negl ( λ ) . \left|\Pr_{X \leftarrow\{0,1\}^{r(\lambda)}}[D(G(X)) = 1] - \Pr_{Y \leftarrow\{0,1\}^{s(\lambda)}}[D(Y) = 1]\right| \leq\operatorname{negl}(\lambda). X ← { 0 , 1 } r ( λ ) Pr [ D ( G ( X )) = 1 ] − Y ← { 0 , 1 } s ( λ ) Pr [ D ( Y ) = 1 ] ≤ negl ( λ ) .
Efficiently verifiable one-way puzzles
We recall a microcrypt primitive known as EV-OWPuzz, which was introduced in [20 ] .
Definition 5 (Efficiently verifiable one-way puzzle). An efficiently verifiable one-way puzzle (E V - O W P p u z z \mathsf{EV\text{-}OWP}_{\mathrm{puzz}} EV - OWP puzz ) consists of two QPT algorithms: a sampler S a m p \mathsf{Samp} Samp and a verifier V V V . The sampler outputs a classical puzzle and answer ( p , a ) ← S a m p ( 1 λ ) (p,a) \leftarrow\mathsf{Samp}(1^\lambda) ( p , a ) ← Samp ( 1 λ ) , and the verifier b ← V ( p , a ) b \leftarrow V(p,a) b ← V ( p , a ) outputs a bit. Write v p ( a ) = Pr [ V ( p , a ) = 1 ] v_p(a) = \Pr[V(p,a)=1] v p ( a ) = Pr [ V ( p , a ) = 1 ] . Then,
E ( p , a ) ← S a m p ( 1 λ ) [ 1 − v p ( a ) ] ≤ negl ( λ ) . \mathop{\mathbb{E}}_{(p,a)\leftarrow\mathsf{Samp}(1^\lambda)} [1-v_p(a)] \leq\operatorname{negl}(\lambda). E ( p , a ) ← Samp ( 1 λ ) [ 1 − v p ( a )] ≤ negl ( λ ) .
And, for every QPT algorithm A A A ,
Pr ( p , a ) ← S a m p ( 1 λ ) [ V ( p , A ( p ) ) = 1 ] ≤ negl ( λ ) . \Pr_{(p,a)\leftarrow\mathsf{Samp}(1^\lambda)}[V(p,A(p))=1] \leq\operatorname{negl}(\lambda). ( p , a ) ← Samp ( 1 λ ) Pr [ V ( p , A ( p )) = 1 ] ≤ negl ( λ ) .
Public-key encryption
We recall the notions of public-key encryption with quantum computation and classical communication.
Definition 6 (Public-key encryption). A public-key encryption scheme with quantum computation and classical communication (q P K E \mathsf{qPKE} qPKE ) consists of three QPT algorithms with classical inputs and outputs:
Gen ( 1 λ ) \operatorname{Gen}(1^\lambda) Gen ( 1 λ ) outputs a public key p k \mathsf{pk} pk and a secret key s k \mathsf{sk} sk .
Enc ( p k , m ) \operatorname{Enc}(\mathsf{pk},m) Enc ( pk , m ) takes a message m ∈ M λ m \in\mathcal{M}_\lambda m ∈ M λ and outputs a ciphertext c c c .
Dec ( s k , c ) \operatorname{Dec}(\mathsf{sk},c) Dec ( sk , c ) outputs a message in M λ \mathcal{M}_\lambda M λ or ⊥ \perp ⊥ .
Here M λ \mathcal{M}_\lambda M λ is the message space, whose elements have polynomially bounded length.
Correctness. For every m ∈ M λ m \in\mathcal{M}_\lambda m ∈ M λ ,
Pr ( p k , s k ) ← Gen ( 1 λ ) c ← Enc ( p k , m ) [ Dec ( s k , c ) = m ] ≥ 1 − negl ( λ ) . \Pr_{\substack{(\mathsf{pk},\mathsf{sk})\leftarrow\operatorname{Gen}(1^\lambda)\\ c\leftarrow\operatorname{Enc}(\mathsf{pk},m)}}[\operatorname{Dec}(\mathsf{sk},c)=m] \geq1-\operatorname{negl}(\lambda). ( pk , sk ) ← Gen ( 1 λ ) c ← Enc ( pk , m ) Pr [ Dec ( sk , c ) = m ] ≥ 1 − negl ( λ ) .
Security (indistinguishability under chosen-plaintext attacks, IND-CPA). For every QPT adversary A = ( A 1 , A 2 ) A=(A_1,A_2) A = ( A 1 , A 2 ) ,
Pr [ ( p k , s k ) ← Gen ( 1 λ ) ( m 0 , m 1 , ρ ) ← A 1 ( p k ) b ← { 0 , 1 } c ← Enc ( p k , m b ) b ′ ← A 2 ( p k , c , ρ ) ∣ b ′ = b ] − 1 2 ≤ negl ( λ ) . \Pr\left[
\left.
\begin{gathered}
(\mathsf{pk},\mathsf{sk})\leftarrow\operatorname{Gen}(1^\lambda)\\
(m_0,m_1,\rho)\leftarrow A_1(\mathsf{pk})\\
b\leftarrow\{0,1\}\\
c\leftarrow\operatorname{Enc}(\mathsf{pk},m_b)\\
b'\leftarrow A_2(\mathsf{pk},c,\rho)
\end{gathered}
\ \right|\ b'=b
\right]-\frac{1}{2}\leq\operatorname{negl}(\lambda). Pr ( pk , sk ) ← Gen ( 1 λ ) ( m 0 , m 1 , ρ ) ← A 1 ( pk ) b ← { 0 , 1 } c ← Enc ( pk , m b ) b ′ ← A 2 ( pk , c , ρ ) b ′ = b − 2 1 ≤ negl ( λ ) .
The adversary chooses equal-length messages m 0 , m 1 ∈ M λ m_0,m_1 \in\mathcal{M}_\lambda m 0 , m 1 ∈ M λ and may retain a quantum state ρ \rho ρ between its two stages.
Point-function obfuscation
For a point a ∈ { 0 , 1 } λ a \in\{0,1\}^\lambda a ∈ { 0 , 1 } λ , write P a ( x ) = 1 { x = a } P_a(x)=\mathbf{1}\{x=a\} P a ( x ) = 1 { x = a } , the function that maps every input to 0 except for a a a which is mapped to 1. Also, let O a ∣ x , z = ∣ x , z ⊕ P a ( x ) ⟩ O_{a|x,z}=|x,z\oplus P_a(x)\rangle O a ∣ x , z = ∣ x , z ⊕ P a ( x )⟩ . We now define a point-function obfuscator using virtual black-box guarantee.
Definition 7 (Point-function obfuscation). A point-function obfuscator consists of two uniform QPT algorithms with classical inputs and outputs:
Obf ( 1 λ , a ) \operatorname{Obf}(1^\lambda,a) Obf ( 1 λ , a ) takes a point a ∈ { 0 , 1 } λ a \in\{0,1\}^\lambda a ∈ { 0 , 1 } λ and outputs a classical program p p p .
Eval ( p , x ) \operatorname{Eval}(p,x) Eval ( p , x ) takes a program p p p and an input x ∈ { 0 , 1 } λ x \in\{0,1\}^\lambda x ∈ { 0 , 1 } λ , and outputs a bit.
Correctness. There is a negligible function η \eta η such that, for every λ \lambda λ ,
max a ∈ { 0 , 1 } λ E p ← Obf ( 1 λ , a ) max x ∈ { 0 , 1 } λ Pr [ Eval ( p , x ) ≠ P a ( x ) ] ≤ η ( λ ) . \max_{a\in\{0,1\}^{\lambda}} \mathop{\mathbb{E}}_{p\leftarrow\operatorname{Obf}(1^\lambda,a)} \max_{x\in\{0,1\}^{\lambda}} \Pr[\operatorname{Eval}(p,x)\ne P_a(x)] \le\eta(\lambda). a ∈ { 0 , 1 } λ max E p ← Obf ( 1 λ , a ) x ∈ { 0 , 1 } λ max Pr [ Eval ( p , x ) = P a ( x )] ≤ η ( λ ) .
The maximum over evaluation inputs is taken before averaging over programs.
Security (single-program virtual black-box). For every uniform QPT adversary A \mathcal{A} A with a one-bit output, there exist a uniform QPT simulator S \mathcal{S} S and a negligible function ε \varepsilon ε such that, for every λ \lambda λ and every point a ∈ { 0 , 1 } λ a \in\{0,1\}^{\lambda} a ∈ { 0 , 1 } λ ,
∣ Pr [ A ( Obf ( 1 λ , a ) ) = 1 ] − Pr [ S O a ( 1 λ ) = 1 ] ∣ ≤ ε ( λ ) . \left|\Pr[\mathcal{A}(\operatorname{Obf}(1^\lambda,a))=1]-\Pr[\mathcal{S}^{O_a}(1^\lambda)=1]\right|\le\varepsilon(\lambda). Pr [ A ( Obf ( 1 λ , a )) = 1 ] − Pr [ S O a ( 1 λ ) = 1 ] ≤ ε ( λ ) .
The same simulator works for all points and accesses the hidden point only through quantum queries to O a O_a O a .
Quantum indistinguishability obfuscation
We consider quantum indistinguishability obfuscation (qiO) for quantum circuits that have an efficient classical encoding and with classical input/outputs.
Definition 8 (Quantum Indistinguishability Obfuscation). A qiO obfuscator consists of QPT algorithms ( O , E ) (O,E) ( O , E ) with the following syntax:
O ( 1 λ , Q ) O(1^\lambda,Q) O ( 1 λ , Q ) takes a classical description of a quantum circuit Q Q Q and returns a classical string c c c .
E ( c , x ) E(c,x) E ( c , x ) takes the obfuscated program c c c and a classical input x x x of the corresponding circuit’s input length, and outputs a classical string.
A family Q Q Q is an admissible implementation of a total classical function f f f if
sup x Pr [ Q ( x ) ≠ f ( x ) ] ≤ ϵ ( λ ) \sup_x \Pr[Q(x)\ne f(x)]\le\epsilon(\lambda) x sup Pr [ Q ( x ) = f ( x )] ≤ ϵ ( λ )
for a negligible function ϵ \epsilon ϵ . The obfuscator has the following properties.
Correctness. For every admissible family, the error Pr c ← O ( 1 λ , Q ) , E [ E ( c , x ) ≠ f ( x ) ] \Pr_{c\leftarrow O(1^\lambda,Q),E}[E(c,x)\ne f(x)] Pr c ← O ( 1 λ , Q ) , E [ E ( c , x ) = f ( x )] is negligible, uniformly over all inputs x x x .
Security. If two equal-size circuit families with the same input and output lengths admissibly implement the same total classical function, their obfuscations are computationally indistinguishable, even in the presence of arbitrary polynomial-length classical auxiliary information.
Remark 3.4 (Simultaneous correctness). Any obfuscator satisfying Definition 8 can be amplified to satisfy the following stronger correctness guarantee: for every admissible family Q Q Q implementing f f f and all sufficiently large λ \lambda λ ,
Pr c ← O ( Q ) [ max x Pr E [ E ( c , x ) ≠ f ( x ) ] > 2 − λ ] ≤ 2 − λ . \Pr_{c\leftarrow O(Q)}\left[\max_x\Pr_E[E(c,x)\ne f(x)]>2^{-\lambda}\right]\le2^{-\lambda}. c ← O ( Q ) Pr [ x max E Pr [ E ( c , x ) = f ( x )] > 2 − λ ] ≤ 2 − λ .
To obtain this guarantee, start with an obfuscator ( O 0 , E 0 ) (O_0,E_0) ( O 0 , E 0 ) satisfying Definition 8, and compile a program with n n n input bits and ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 output bits independently an odd number L = O ( n + λ + L=O(n+\lambda+ L = O ( n + λ + log ( ℓ + 1 ) \log(\ell+1) log ( ℓ + 1 ) of times. Regard the tuple as one classical encoding, and evaluate by taking the majority separately at each output bit, using independent workspace for each evaluation. For each fixed input and output bit, the joint compilation-and-evaluation error is at most 1 / 10 1/10 1/10 for all sufficiently large λ \lambda λ . A Chernoff bound makes the error of its majority at most e − c 0 L e^{-c_0L} e − c 0 L for an absolute constant c 0 > 0 c_0>0 c 0 > 0 . Taking a union bound over output bits, applying Markov’s inequality over the compiled tuple, and then taking a union bound over inputs gives
Pr c [ max x Pr E [ E ( c , x ) ≠ f ( x ) ] > 2 − λ ] ≤ 2 n + λ ℓ e − c 0 L ≤ 2 − λ . \Pr_{\mathbf{c}}\left[\max_x\Pr_E[E(\mathbf{c},x)\ne f(x)]>2^{-\lambda}\right]\le2^{n+\lambda}\ell e^{-c_0L}\le2^{-\lambda}. c Pr [ x max E Pr [ E ( c , x ) = f ( x )] > 2 − λ ] ≤ 2 n + λ ℓ e − c 0 L ≤ 2 − λ .
where the last inequality holds for a sufficiently large constant in L L L . A polynomial hybrid preserves obfuscation security, and the new algorithms remain polynomial time on all syntactically valid inputs. Thus we may assume the stronger correctness without loss of generality.
Relations among qOWF definitions and related primitives
We study the relationships among the three qOWF definitions and the related primitives. In summary, we show that qOWF1 _1 1 s and qOWF2 _2 2 s both imply qOWF3 _3 3 , qPRG imply qOWF2 _2 2 , and qOWF3 _3 3 is equivalent to EV-OWPuzz. We also explain the implications from encryption and point-function obfuscation to puzzles.
Relation among qOWF notions.
We show the following straightforward result.
Proposition 4.1. Every qOWF 1 _1 1 or qOWF 2 _2 2 is also a qOWF 3 _3 3 .
Proof. qOWF1 _1 1 has the same security requirement as qOWF3 _3 3 and has a stricter correctness requirement. Furthermore, a uniform sampler is one of the samplers permitted for qOWF3 _3 3 , giving the implication from qOWF2 _2 2 .
qPRG and qOWF-2.
Proposition 4.2. Suppose a QPT generator G G G takes a uniform r ( λ ) r(\lambda) r ( λ ) -bit seed and has classical output length s ( λ ) ≥ r ( λ ) + 1 s(\lambda)\ge r(\lambda)+1 s ( λ ) ≥ r ( λ ) + 1 . Suppose its output is computationally indistinguishable from U s ( λ ) U_{s(\lambda)} U s ( λ ) , and its determinism error averaged over uniform seeds is negligible. Then a qOWF 2 _2 2 exists.
Proof. Take t = λ t=\lambda t = λ independent seed blocks and define H ( x 1 , … , x t ) = ( G ( x 1 ) , … , G ( x t ) ) H(x_1,\ldots,x_t)=(G(x_1),\ldots,G(x_t)) H ( x 1 , … , x t ) = ( G ( x 1 ) , … , G ( x t )) using fresh invocations. The average error is at most t t t times that of G G G , hence negligible. A polynomial hybrid replacing one block at a time shows that H ( U t r ) H(U_{tr}) H ( U t r ) is indistinguishable from U t s U_{ts} U t s .
If I I I inverts H H H , distinguish a string y y y by running I ( y ) I(y) I ( y ) , evaluating H H H on its output, and returning one exactly when the result equals y y y . On H ( U t r ) H(U_{tr}) H ( U t r ) , this is exactly its inversion probability. On a uniform string it is at most
2 − t s ∑ y , x Pr [ I ( y ) = x ] Pr [ H ( x ) = y ] ≤ 2 − t s ∑ x ∑ y Pr [ H ( x ) = y ] = 2 t r − t s ≤ 2 − λ . 2^{-ts}\sum_{y,x}\Pr[I(y)=x]\Pr[H(x)=y]\le2^{-ts}\sum_x\sum_y\Pr[H(x)=y]=2^{tr-ts}\le2^{-\lambda}. 2 − t s y , x ∑ Pr [ I ( y ) = x ] Pr [ H ( x ) = y ] ≤ 2 − t s x ∑ y ∑ Pr [ H ( x ) = y ] = 2 t r − t s ≤ 2 − λ .
Verification is independent of the inverter conditional on its classical output. A nonnegligible inversion probability would therefore distinguish the two output distributions.
The negligible average-correctness convention is used in the qPRG definitions of Bouaziz–Ermann et al. [13 Definition 3.8] and Barhoush [8 Section 3.2, Definition 2] . Consequently, Theorem 5.1 rules out these qPRGs as well. The every-input convention in Barhoush, Nishimaki, and Yamakawa [19 Section 2.1] is stronger.
qOWF-3 and EV-OWPuzz.
q O W F 3 qOWF_3 q O W F 3 captures exactly the existence of efficiently verifiable one-way puzzles.
Proposition 4.3 (q O W F 3 qOWF_3 q O W F 3 and efficiently verifiable puzzles). EV-OWPuzz s exist if and only if q O W F 3 qOWF_3 q O W F 3 s exist.
Proof. Assume there exists a q O W F 3 qOWF_3 q O W F 3 ( S , E ) (S,E) ( S , E ) and let f ( x ) f(x) f ( x ) be its most likely output. Write η = Pr x ← S [ E ( x ) ≠ f ( x ) ] \eta= \Pr_{x\leftarrow S}[E(x) \ne f(x)] η = Pr x ← S [ E ( x ) = f ( x )] . We will show the existence of a EV-OWPuzz.
We let the sampling algorithm of the puzzle sample x ← S x \leftarrow S x ← S and y ← E ( x ) y \leftarrow E(x) y ← E ( x ) , and output ( y , x ) (y,x) ( y , x ) as the puzzle and answer. On a proposed answer x ′ x' x ′ , the verifier of the puzzle runs E ( x ′ ) E(x') E ( x ′ ) and accepts exactly when the result is y y y . Two independent evaluations at the same honestly sampled input disagree with probability at most 2 η 2\eta 2 η , by comparing both with f ( x ) f(x) f ( x ) . The puzzle therefore has negligible correctness error. Its solving probability is exactly the inversion probability.
For the converse, take a puzzle ( Samp , V ) (\operatorname{Samp},V) ( Samp , V ) with correctness error η \eta η . We build a q O W F 3 qOWF_3 q O W F 3 ( S , E ) (S,E) ( S , E ) as follows. Let S S S sample ( p , a ) ← Samp ( 1 λ ) (p,a) \leftarrow\operatorname{Samp}(1^\lambda) ( p , a ) ← Samp ( 1 λ ) and output ( p , a ) (p,a) ( p , a ) . The evaluator E ( p , a ) E(p,a) E ( p , a ) runs t = λ t=\lambda t = λ verifications V ( p , a ) V(p,a) V ( p , a ) and outputs p p p if every verification accepts; otherwise it outputs ⊥ \perp ⊥ . Put u ( p , a ) = v p ( a ) t u(p,a)=v_p(a)^t u ( p , a ) = v p ( a ) t , where v p ( a ) = Pr [ V ( p , a ) = 1 ] v_p(a)=\Pr[V(p,a)=1] v p ( a ) = Pr [ V ( p , a ) = 1 ] . The union bound gives
E ( p , a ) ← Samp ( 1 λ ) [ 1 − u ( p , a ) ] ≤ t η . \mathop{\mathbb{E}}_{(p,a)\leftarrow\operatorname{Samp}(1^\lambda)}[1-u(p,a)] \le t\eta. E ( p , a ) ← Samp ( 1 λ ) [ 1 − u ( p , a )] ≤ t η . The most-likely-output function satisfies f ( p , a ) = p f(p,a)=p f ( p , a ) = p when u ( p , a ) > 1 / 2 u(p,a)>1/2 u ( p , a ) > 1/2 , and f ( p , a ) = ⊥ f(p,a)=\perp f ( p , a ) =⊥ when u ( p , a ) < 1 / 2 u(p,a)<1/2 u ( p , a ) < 1/2 , with ties broken lexicographically. It is easy to check that
E x ← S ( 1 λ ) Pr [ E ( x ) ≠ f ( x ) ] ≤ t η \mathop{\mathbb{E}}_{x\leftarrow S(1^\lambda)}\Pr[E(x)\ne f(x)] \le t\eta E x ← S ( 1 λ ) Pr [ E ( x ) = f ( x )] ≤ t η as required for q O W F 3 qOWF_3 q O W F 3 .
Given an inverter against this q O W F 3 qOWF_3 q O W F 3 , solve a puzzle p p p by invoking the inverter on p p p , parsing its proposed input as ( p ′ , a ′ ) (p',a') ( p ′ , a ′ ) , and returning a ′ a' a ′ only when p ′ = p p'=p p ′ = p . Let σ A \sigma_A σ A denote the resulting solver’s verification probability. In the experiment, a challenge equals ⊥ \perp ⊥ with probability at most t η t\eta t η . When the challenge is a puzzle, the inversion check accepts with probability u ( p , a ′ ) ≤ v p ( a ′ ) u(p,a')\le v_p(a') u ( p , a ′ ) ≤ v p ( a ′ ) . Hence the inversion probability is at most t η + σ A t\eta+\sigma_A t η + σ A . This bound is negligible by puzzle security, which completes the proof of the converse direction.
Point-function obfuscation implies EV-OWPuzz.
q P K E qPKE q P K E with classical communication implies EV-OWPuzz: use q P K E qPKE q P K E as secret-key encryption and apply Chung, Goldin, and Gray [20 Section 2.5, Theorem 8] . Point-function obfuscation also suffices for EV-OWPuzz, as the following lemma shows.
Lemma 4.4. Point-function obfuscation implies EV-OWPuzz.
Proof. Assume there exists a point-function obfuscation ( Obf , Eval ) (\operatorname{Obf},\operatorname{Eval}) ( Obf , Eval ) . Write P a ( x ) = 1 { x = a } P_a(x)=1\{x=a\} P a ( x ) = 1 { x = a } . Choose a uniform point a ∈ { 0 , 1 } λ a\in\{0,1\}^\lambda a ∈ { 0 , 1 } λ , with λ ≥ 1 \lambda\ge1 λ ≥ 1 , and sample p ← Obf ( 1 λ , a ) p\leftarrow\operatorname{Obf}(1^\lambda,a) p ← Obf ( 1 λ , a ) . We build a EV-OWPuzz as follows. The puzzle is p p p , its answer is a a a , and verification runs Eval ( p , a ′ ) \operatorname{Eval}(p,a') Eval ( p , a ′ ) . Correctness follows from the correctness of obfuscation. We now show security.
Fix a proposed puzzle solver B B B . We use the solver to distinguish whether the first bit of a solution to the puzzle is b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } . For each b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } , consider the one-bit adversary A b A_b A b that runs a ′ ← B ( p ) a' \leftarrow B(p) a ′ ← B ( p ) and accepts exactly when a ′ a' a ′ has its first bit b b b , and verification accepts. Definition 7 bounds the verification error even when the input is chosen after seeing p p p , because it takes the maximum over inputs before averaging over programs.
Let S b S_b S b be the simulator for A b A_b A b , which works for every hidden point. For a point chosen uniformly from either first-bit half of { 0 , 1 } λ \{0,1\}^{\lambda} { 0 , 1 } λ , replacing the simulator’s point oracle by the all-zero oracle changes its average acceptance probability by at most O ( q b 2 − ( λ − 1 ) / 2 ) O(q_b2^{-(\lambda-1)/2}) O ( q b 2 − ( λ − 1 ) /2 ) , where q b q_b q b bounds its queries. To see this, replace queries one at a time, using the query states with the all-zero oracle: their expected squared weight on the hidden point is at most 2 − ( λ − 1 ) 2^{-(\lambda-1)} 2 − ( λ − 1 ) . This is the standard quantum query comparison of [9 ] . The simulator therefore has negligibly different average acceptance probabilities on the two halves. By the security of point-function obfuscation, the same is true of A b A_b A b . Its acceptance is negligible on the half with first bit 1 − b 1-b 1 − b , so it is also negligible on the half with first bit b b b . Summing over b = 0 , 1 b=0,1 b = 0 , 1 gives exactly the solver’s verification success, which is therefore negligible.
Separating qOWFs from qPKE and Point-function Obfuscation
In this part, we present a quantum black-box separation between qOWFs and both qPKE and point-function obfuscation. More precisely, we will prove the following theorem:
Theorem 5.1 (qPKE and point-function obfuscation without qOWFs). There exists a self-inverse and real quantum unitary oracle relative to which a perfectly correct qPKE scheme with classical keys and ciphertexts (Definition 6) and a point-function obfuscator with classical obfuscated programs (Definition 7) exist, but neither q O W F 1 s \mathrm{qOWF}_{1s} qOWF 1 s (Definition 1) nor q O W F 2 s \mathrm{qOWF}_{2s} qOWF 2 s (Definition 2) exist.
We first prove the general barrier theorem in Section 5.1, and then in Section 5.2 construct the oracle supporting qPKE and point-function obfuscation, define a base distribution P \mathcal{P} P on it, and provide the constructions of qPKE and point-function obfuscations in that oracle world, together with their correctness bounds. Section 5.3 proves security of the two constructions in the oracle world, with respect to a general class of distributions close enough to P \mathcal{P} P . Section 5.4 then utilizes the generalized barrier theorem from Section 5.1 and defines a conditioning procedure on the base oracle P \mathcal{P} P to construct a selected distribution Q \mathcal{Q} Q , such that no qOWFs exist with respect to Q \mathcal{Q} Q with probability 1, and the relative entropy of Q \mathcal{Q} Q from the original distribution P \mathcal{P} P is bounded, thus by the security guarantees of the qPKE and point-function obfuscation construction in Section 5.3, we also conclude that the same constructions are secure even in Q \mathcal{Q} Q with probability 1, which implies the existence of a fixed oracle with this separation, and hence completes the proof.
General barrier theorem
Let ( X , d ) (\mathcal{X},d) ( X , d ) be a metric space, let D \mathcal{D} D be a measurable space, and let ν \nu ν be a distribution on D \mathcal{D} D . Measurable sets are events to which probabilities are assigned; a map is measurable if the inputs sent into any measurable set also form a measurable set. No distance on D \mathcal{D} D is required.
Let V : D → X V:\mathcal{D}\to\mathcal{X} V : D → X assign a point V ( a ) V(a) V ( a ) to each a ∈ D a\in\mathcal{D} a ∈ D . A fixed measurable map F : D × D × [ 0 , 1 ] → X F:\mathcal{D}\times\mathcal{D}\times[0,1]\to\mathcal{X} F : D × D × [ 0 , 1 ] → X specifies how to interpolate from V ( a ) V(a) V ( a ) to V ( b ) V(b) V ( b ) . It takes two inputs a , b ∈ D a,b\in\mathcal{D} a , b ∈ D and a parameter t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , and returns the point F ( a , b , t ) ∈ X F(a,b,t)\in\mathcal{X} F ( a , b , t ) ∈ X , with F ( a , b , 0 ) = V ( a ) F(a,b,0)=V(a) F ( a , b , 0 ) = V ( a ) and F ( a , b , 1 ) = V ( b ) F(a,b,1)=V(b) F ( a , b , 1 ) = V ( b ) . Once $a,b,t are fixed, the resulting point is fixed; randomness comes from sampling these inputs. For subsets S , T ⊆ X S,T \subseteq\mathcal{X} S , T ⊆ X , write d ( S , T ) = inf x ∈ S , y ∈ T d ( x , y ) d(S,T)=\inf_{x\in S,y\in T}d(x,y) d ( S , T ) = inf x ∈ S , y ∈ T d ( x , y ) . For a collection of sets, we call the region outside their union the gap .
Theorem 5.2 (Barrier for distributions obtained by interpolation). Let A , B A,B A , B be independent samples from ν \nu ν , let U U U be an independently sampled uniform random variable in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and let μ \mu μ be the distribution of F ( A , B , U ) F(A,B,U) F ( A , B , U ) where F F F is a map defined above. Suppose there exists v 0 > 0 v_0>0 v 0 > 0 such that d ( F ( a , b , s ) , F ( a , b , t ) ) ≤ v 0 ∣ s − t ∣ d(F(a,b,s),F(a,b,t))\le v_0\lvert s-t\rvert d ( F ( a , b , s ) , F ( a , b , t )) ≤ v 0 ∣ s − t ∣ for all a , b ∈ D a,b\in D a , b ∈ D , s , t ∈ [ 0 , 1 ] s,t\in[0,1] s , t ∈ [ 0 , 1 ] , and suppose S 1 , … , S r ⊆ X S_1,\ldots,S_r\subseteq\mathcal{X} S 1 , … , S r ⊆ X are measurable sets with d ( S i , S j ) ≥ δ d(S_i,S_j)\ge\delta d ( S i , S j ) ≥ δ for i ≠ j i\ne j i = j , for some r ≥ 1 r\ge1 r ≥ 1 and δ > 0 \delta>0 δ > 0 . Then
μ ( X ∖ ⋃ i = 1 r S i ) ≥ δ 3 v 0 ( g 2 − ∑ i p i 2 ) , \mu\left(\mathcal{X}\setminus\bigcup_{i=1}^{r}S_i\right)\ge\frac{\delta}{3v_0}\left(g^2-\sum_i p_i^2\right), μ ( X ∖ i = 1 ⋃ r S i ) ≥ 3 v 0 δ ( g 2 − i ∑ p i 2 ) , where p i = μ ( S i ) p_i=\mu(S_i) p i = μ ( S i ) and g = ∑ i = 1 r p i g=\sum_{i=1}^{r}p_i g = ∑ i = 1 r p i .
For example, take D = { 0 , 1 } D=\{0,1\} D = { 0 , 1 } , X = [ 0 , 1 ] \mathcal{X}=[0,1] X = [ 0 , 1 ] with the usual distance, uniform ν \nu ν , V ( a ) = a V(a)=a V ( a ) = a , and F ( a , b , t ) = ( 1 − t ) a + t b F(a,b,t)=(1-t)a+tb F ( a , b , t ) = ( 1 − t ) a + t b . Then μ \mu μ assigns probability 1 / 4 1/4 1/4 to each endpoint and its remaining probability 1 / 2 1/2 1/2 uniformly over the interval.
In the proof of our main separation result (Theorem 5.1 ), we will use the following corollary of Theorem 5.2 .
Corollary 5.3 (A set of large probability). Under the hypotheses of Theorem 5.2 , let ε b a d = μ ( X ∖ ⋃ i = 1 r S i ) < 1 \varepsilon_{\mathrm{bad}}=\mu(\mathcal{X}\setminus\bigcup_{i=1}^{r}S_i)<1 ε bad = μ ( X ∖ ⋃ i = 1 r S i ) < 1 be the probability that a sample lies outside every S i S_i S i . Then there is an index j j j such that
μ ( S j ) ≥ 1 − ε b a d − 3 v 0 δ ε b a d 1 − ε b a d . \mu(S_j)\ge1-\varepsilon_{\mathrm{bad}}-\frac{3v_0}{\delta}\frac{\varepsilon_{\mathrm{bad}}}{1-\varepsilon_{\mathrm{bad}}}. μ ( S j ) ≥ 1 − ε bad − δ 3 v 0 1 − ε bad ε bad .
If δ / v 0 \delta/v_0 δ / v 0 is fixed and the probability outside all the sets is small, then one of the sets has probability close to one.
Proof. Put p i = μ ( S i ) p_i=\mu(S_i) p i = μ ( S i ) , g = 1 − ε b a d > 0 g=1-\varepsilon_{\mathrm{bad}}>0 g = 1 − ε bad > 0 , and p max = max i p i p_{\max}=\max_i p_i p m a x = max i p i . Since ∑ i p i 2 ≤ g p max \sum_i p_i^2\le gp_{\max} ∑ i p i 2 ≤ g p m a x , Theorem 5.2 gives ε b a d ≥ ( δ / ( 3 v 0 ) ) g ( g − p max ) \varepsilon_{\mathrm{bad}}\ge(\delta/(3v_0))g(g-p_{\max}) ε bad ≥ ( δ / ( 3 v 0 )) g ( g − p m a x ) . Rearranging gives p max ≥ g − ( 3 v 0 / δ ) ε b a d / g p_{\max}\ge g-(3v_0/\delta)\varepsilon_{\mathrm{bad}}/g p m a x ≥ g − ( 3 v 0 / δ ) ε bad / g . Substitute g = 1 − ε b a d g=1-\varepsilon_{\mathrm{bad}} g = 1 − ε bad and choose j j j with p j = p max p_j=p_{\max} p j = p m a x .
To prove the theorem, we construct random paths whose endpoints are independent samples from μ \mu μ and whose position at every fixed time also has distribution μ \mu μ . Proposition 5.4 derives a barrier bound from these properties and a bound on how quickly the position changes. Lemma 5.5 constructs the required paths from the interpolation map F F F in Theorem 5.2 .
Paths between independent samples
We now consider an arbitrary probability distribution μ \mu μ on a metric space ( X , d ) (\mathcal{X},d) ( X , d ) .
Imagine moving continuously from a point x s t a r t x_{\mathrm{start}} x start to a point x e n d x_{\mathrm{end}} x end . Write X t X_t X t for the position at t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , so that X 0 = x s t a r t X_0=x_{\mathrm{start}} X 0 = x start and X 1 = x e n d X_1=x_{\mathrm{end}} X 1 = x end . We call t t t the time parameter of the path. It parametrizes this mathematical interpolation; it is not the running time of an algorithm. A random path is an entire path chosen according to a probability distribution Π \Pi Π . Thus Π \Pi Π is a distribution on paths, while μ \mu μ is a distribution on points. Once a path is chosen, all its positions X t X_t X t are fixed.
We require the endpoints to be independent samples from μ \mu μ , and every fixed intermediate point X t X_t X t to have distribution μ \mu μ as well. We also require movement to be bounded: there is a number v > 0 v>0 v > 0 such that an interval of parameter length h h h changes the position by distance at most v h vh v h . We call v v v a speed bound , or equivalently a change bound . The following definition makes these requirements precise without assuming that the path has a derivative.
Definition 9 (Paths with unchanged distributions). The space ( X , d ) (\mathcal{X},d) ( X , d ) with probability distribution μ \mu μ admits paths with change bound v > 0 v>0 v > 0 if there exists a probability distribution Π \Pi Π on continuous paths X : [ 0 , 1 ] → X X:[0,1]\to\mathcal{X} X : [ 0 , 1 ] → X with the following properties. We sample X ∼ Π X\sim\Pi X ∼ Π and write X t = X ( t ) X_t=X(t) X t = X ( t ) .
Independent endpoints. Under X ∼ Π X\sim\Pi X ∼ Π , the initial point X 0 X_0 X 0 and final point X 1 X_1 X 1 are independent, and each has distribution μ \mu μ .
Marginal intermediate distributions. For every fixed t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] and every measurable set A ⊆ X A\subseteq\mathcal{X} A ⊆ X ,
Pr X ∼ Π [ X t ∈ A ] = μ ( A ) . \Pr_{X\sim\Pi}[X_t\in A]=\mu(A). X ∼ Π Pr [ X t ∈ A ] = μ ( A ) . Bounded change. With probability one over X ∼ Π X\sim\Pi X ∼ Π ,
d ( X s , X t ) ≤ v ∣ s − t ∣ for all s , t ∈ [ 0 , 1 ] . d(X_s,X_t)\leq v|s-t|\qquad\text{for all }s,t\in[0,1]. d ( X s , X t ) ≤ v ∣ s − t ∣ for all s , t ∈ [ 0 , 1 ] . We require the evaluation map ( X , t ) ↦ X t (X,t)\mapsto X_t ( X , t ) ↦ X t to be jointly measurable, so that sampling X ∼ Π X\sim\Pi X ∼ Π and an independent time gives well-defined probabilities and expectations. The first two requirements are exact conditions on Π \Pi Π ; the third holds with Π \Pi Π -probability one.
The second property is also called having the same marginal distribution at every time. It concerns each predetermined time separately; it does not assert independence between intermediate times. Neighboring points on a continuous path are strongly related. The third property says, in particular, that traveling a distance of at least δ \delta δ requires at least δ / v \delta/v δ / v units of parameter time.
The first ingredient towards proving Theorem 5.2 is the following proposition that converts the existence of suitable random paths into a barrier bound. In particular, the proposition bounds the probability outside finitely many separated sets. Its many-set form will also bound how much probability can lie outside the largest of these sets.
Proposition 5.4 (Barrier from paths). Suppose ( X , d , μ ) (\mathcal{X},d,\mu) ( X , d , μ ) admits paths with change bound v v v . Let S 1 , … , S r S_1,\ldots,S_r S 1 , … , S r be finitely many measurable sets separated by distance at least δ > 0 \delta>0 δ > 0 . Write
p i = μ ( S i ) , g = ∑ i p i , B = X ∖ ⋃ i S i , b = μ ( B ) = 1 − g . p_i=\mu(S_i),\qquad g=\sum_i p_i,\qquad B=\mathcal{X}\setminus\bigcup_i S_i,\qquad b=\mu(B)=1-g. p i = μ ( S i ) , g = i ∑ p i , B = X ∖ i ⋃ S i , b = μ ( B ) = 1 − g . Then
b ≥ δ v ( g 2 − ∑ i p i 2 ) . b\geq\frac{\delta}{v}\left(g^2-\sum_i p_i^2\right). b ≥ v δ ( g 2 − i ∑ p i 2 ) .
Proof template. We sample a path from Π \Pi Π and an independent uniform time along it. Independent endpoints determine how often the path must cross between different sets. The speed bound makes every such crossing occupy an interval of length at least δ / v \delta/v δ / v , while the unchanged intermediate distributions convert the probability of sampling this interval into a lower bound on the gap probability. Definition 9 packages these properties into a reusable criterion. The method has precedents: Barhoush [8 Section 4, Lemma 2] interpolates between fixed oracle pairs, and Lott–Villani [44 Definitions 1.2 and 1.6, and Theorem 2.5] use random paths with independent endpoints and bounds on the distributions encountered along them. Here we require the distribution at each fixed time to remain unchanged and allow general paths with bounded change. The barrier follows directly from these properties, without invoking the geometric inequalities used for Haar distributions in [13 Section 5.1] .
Proof. Fix a distribution Π \Pi Π on paths satisfying Definition 9. Sample X ∼ Π X \sim\Pi X ∼ Π , and independently choose T T T uniformly from [ 0 , 1 ] [0,1] [ 0 , 1 ] . For each fixed path X X X , define
L B ( X ) = Pr T [ X T ∈ B ] , L_B(X) = \Pr_T[X_T \in B], L B ( X ) = T Pr [ X T ∈ B ] ,
L B ( X ) L_B(X) L B ( X ) is the probability that at a uniformly sampled time on this fixed path, the point lies in the gap B B B . Equivalently, it is the fraction of parameter time spent in B B B .
Probability of sampling the gap. Next we can write the average value of L B ( X ) L_B(X) L B ( X ) over X ∼ Π X \sim\Pi X ∼ Π as the overall probability over random X ∼ Π X \sim\Pi X ∼ Π and independently uniform T ∈ [ 0 , 1 ] T \in[0,1] T ∈ [ 0 , 1 ] that X T ∈ B X_T \in B X T ∈ B . Since T T T is chosen independently, the same probability can be written as an expectation over T T T , of the probability that X T ∈ B X_T \in B X T ∈ B for random X ∼ Π X \sim\Pi X ∼ Π . This last probability term is b b b , because T T T is sampled independently of X X X , and at every fixed time t t t , the marginal-intermediate-distribution condition (Item 2) guarantees that Pr X ∼ Π [ X t ∈ B ] = b \Pr_{X\sim\Pi}[X_t \in B] = b Pr X ∼ Π [ X t ∈ B ] = b . Combining these, we get
E X ∼ Π [ L B ( X ) ] = Pr X ∼ Π , T [ X T ∈ B ] = E T [ Pr X ∼ Π [ X T ∈ B ] ] = E T [ Pr Y ∼ μ [ Y ∈ B ] ] = E T [ b ] = b . \mathbb{E}_{X\sim\Pi}[L_B(X)] = \Pr_{X\sim\Pi,T}[X_T \in B] = \mathbb{E}_T\left[\Pr_{X\sim\Pi}[X_T \in B]\right] = \mathbb{E}_T\left[\Pr_{Y\sim\mu}[Y \in B]\right] = \mathbb{E}_T[b] = b. E X ∼ Π [ L B ( X )] = X ∼ Π , T Pr [ X T ∈ B ] = E T [ X ∼ Π Pr [ X T ∈ B ] ] = E T [ Y ∼ μ Pr [ Y ∈ B ] ] = E T [ b ] = b .
Hence, in order to complete the proof of Proposition 5.4, it is enough to show that
E X ∼ Π [ L B ( X ) ] ≥ δ v ( g 2 − ∑ i p i 2 ) . (1) \mathbb{E}_{X\sim\Pi}[L_B(X)] \ge\frac{\delta}{v}\left(g^2-\sum_i p_i^2\right). \tag*{(1)} E X ∼ Π [ L B ( X )] ≥ v δ ( g 2 − i ∑ p i 2 ) . (1)
Time required for a crossing. Fix a path X X X in the support of Π \Pi Π satisfying Item 3, such that X 0 ∈ S i X_0 \in S_i X 0 ∈ S i and X 1 ∈ S j X_1 \in S_j X 1 ∈ S j for some i ≠ j i \ne j i = j . We identify one interval during which this path crosses the gap. Let S k ‾ \overline{S_k} S k denote the closure of S k S_k S k , obtained by including all limits of sequences of points in S k S_k S k . The closures remain separated by at least δ \delta δ , because distance is continuous.
Let τ \tau τ be the first time the path reaches any S k ‾ \overline{S_k} S k with k ≠ i k \ne i k = i , and let σ \sigma σ be the last time at or before τ \tau τ that it belongs to S i ‾ \overline{S_i} S i . These times exist, because the path begins in S i S_i S i and ends in another set, and continuity makes the relevant sets of hitting times closed subsets of [ 0 , 1 ] [0,1] [ 0 , 1 ] . A nonempty closed subset of a closed bounded interval contains its smallest and largest elements, so these first and last times are attained. We use closures only to justify the boundary times; we do not assume that adding boundary points preserves the probabilities of the sets.
For every t ∈ ( σ , τ ) t \in(\sigma,\tau) t ∈ ( σ , τ ) , the path is outside S i ‾ \overline{S_i} S i by the definition of σ \sigma σ , and outside every other closure by the definition of τ \tau τ . Thus it is in B B B throughout this interval. Its endpoints lie in different closures, so the separation and change bounds give
δ ≤ d ( X σ , X τ ) ≤ v ( τ − σ ) . \delta\le d(X_\sigma,X_\tau) \le v(\tau-\sigma). δ ≤ d ( X σ , X τ ) ≤ v ( τ − σ ) .
On this fixed path, the uniform time T T T lies in ( σ , τ ) (\sigma,\tau) ( σ , τ ) with probability τ − σ \tau-\sigma τ − σ . Consequently L B ( X ) ≥ τ − σ ≥ δ / v L_B(X) \ge\tau-\sigma\ge\delta/v L B ( X ) ≥ τ − σ ≥ δ / v . The first inequality is because a path may cross the gap more than once; but we only count the one crossing in the interval ( σ , τ ) (\sigma,\tau) ( σ , τ ) , which gives the required lower bound.
Probability of crossing under Π \Pi Π Let E \mathcal{E} E be the event, over X ∼ Π X \sim\Pi X ∼ Π , that the initial point X 0 X_0 X 0 and final point X 1 X_1 X 1 belong to different sets among S 1 , … , S r S_1,\ldots,S_r S 1 , … , S r . By Definition 9, X 0 , X 1 X_0,X_1 X 0 , X 1 are distributed as independent samples from μ \mu μ . Their independence under Π \Pi Π gives
Pr X ∼ Π [ E ] = Pr X 0 ∼ μ , X 1 ∼ μ [ ∃ i ≠ j , X 0 ∈ S i , X 1 ∈ S j ] = ∑ i ≠ j p i p j = ( ∑ i p i ) 2 − ∑ i p i 2 = g 2 − ∑ i p i 2 . \Pr_{X\sim\Pi}[\mathcal{E}] = \Pr_{X_0\sim\mu,X_1\sim\mu}[\exists i \ne j,X_0 \in S_i,X_1 \in S_j] = \sum_{i\ne j}p_i p_j = \left(\sum_i p_i\right)^2-\sum_i p_i^2 = g^2-\sum_i p_i^2. X ∼ Π Pr [ E ] = X 0 ∼ μ , X 1 ∼ μ Pr [ ∃ i = j , X 0 ∈ S i , X 1 ∈ S j ] = i = j ∑ p i p j = ( i ∑ p i ) 2 − i ∑ p i 2 = g 2 − i ∑ p i 2 .
We already showed that every path in E \mathcal{E} E has L B ( X ) ≥ δ / v L_B(X) \ge\delta/v L B ( X ) ≥ δ / v . On every other path, L B ( X ) ≥ 0 L_B(X) \ge0 L B ( X ) ≥ 0 . Therefore, we get
E X ∼ Π [ L B ( X ) ] ≥ δ v Pr X ∼ Π [ E ] = δ v ( g 2 − ∑ i p i 2 ) , \mathbb{E}_{X \sim\Pi}[L_B(X)] \ge\frac{\delta}{v} \Pr_{X \sim\Pi}[\mathcal{E}] = \frac{\delta}{v}\left(g^2 - \sum_i p_i^2\right), E X ∼ Π [ L B ( X )] ≥ v δ X ∼ Π Pr [ E ] = v δ ( g 2 − i ∑ p i 2 ) ,
which completes the proof of Equation (1) and hence the proposition.
To apply Proposition 5.4 , we must specify a distribution Π \Pi Π on paths satisfying Definition 9 . The next lemma constructs this distribution from the hypotheses of Theorem 5.2 . We join several transitions in succession, then choose a random starting position and a random amount of progress along them.
Lemma 5.5 (Constructing the path distribution). Under the hypotheses of Theorem 5.2 , there is an explicit distribution Π \Pi Π on continuous paths X : [ 0 , 1 ] → X X : [0,1] \to\mathcal{X} X : [ 0 , 1 ] → X satisfying Definition 9 with change bound v = 3 v 0 v = 3v_0 v = 3 v 0 . Thus the distribution μ \mu μ in that theorem satisfies the path hypothesis of Proposition 5.4 . For a finite product of such distributions, independent choices of paths give change bound 3 max i v 0 , i 3\max_i v_{0,i} 3 max i v 0 , i when distance is the maximum of the coordinate distances. Coordinates fixed at prescribed values may be included.
Proof. Fix ν \nu ν , V V V , F F F , μ \mu μ , and v 0 v_0 v 0 as in Theorem 5.2 . We first specify how to sample an entire path from Π \Pi Π , then verify the three properties in Definition 9 .
Sampling a path from Π \Pi Π . Let A 0 , … , A 4 A_0, \ldots, A_4 A 0 , … , A 4 be five independent samples from ν \nu ν . Independently sample U U U uniformly in [ 0 , 1 ) [0,1) [ 0 , 1 ) and T T T uniformly in [ 2 , 3 ) [2,3) [ 2 , 3 ) . For every s ∈ [ 0 , 1 ] s \in[0,1] s ∈ [ 0 , 1 ] , set
k s = ⌊ U + s T ⌋ , u s = U + s T − k s , X s = F ( A k s , A k s + 1 , u s ) . k_s = \lfloor U + sT \rfloor,\qquad u_s = U + sT - k_s,\qquad X_s = F(A_{k_s}, A_{k_s+1}, u_s). k s = ⌊ U + s T ⌋ , u s = U + s T − k s , X s = F ( A k s , A k s + 1 , u s ) .
These choices determine the entire function s ↦ X s s \mapsto X_s s ↦ X s . Define Π \Pi Π to be the distribution of this function. Since 0 ≤ U + s T < 4 0 \le U + sT < 4 0 ≤ U + s T < 4 , we have k s ∈ { 0 , 1 , 2 , 3 } k_s \in\{0,1,2,3\} k s ∈ { 0 , 1 , 2 , 3 } , so the five samples suffice. Half-open sampling intervals give the same uniform distributions as the corresponding closed intervals and avoid endpoint conventions.
To interpret the construction, join the four transitions from V ( A 0 ) V(A_0) V ( A 0 ) to V ( A 1 ) V(A_1) V ( A 1 ) , from V ( A 1 ) V(A_1) V ( A 1 ) to V ( A 2 ) V(A_2) V ( A 2 ) , and so on, assigning one unit of progress to each transition. At time s s s , the total progress is U + s T U + sT U + s T : the integer k s k_s k s selects the current transition, and u s ∈ [ 0 , 1 ) u_s \in[0,1) u s ∈ [ 0 , 1 ) gives the position within it. Thus U U U is the starting position and T T T is the total amount of progress during the time interval [ 0 , 1 ] [0,1] [ 0 , 1 ] . At a boundary between transitions, the endpoint identities for F F F make both formulas agree at the common point V ( A k ) V(A_k) V ( A k ) . Hence every sampled path is continuous. The formula is jointly measurable in the sampled data and s s s , since F F F is measurable and k s k_s k s has only four possible values. This supplies the measurability required in Definition 9 .
Bounded change. Within a single transition, a progress change of size h h h changes the point by at most v 0 h v_0h v 0 h . If an interval crosses a transition boundary, divide it at that boundary and use the triangle inequality. The changes add to at most v 0 v_0 v 0 times the total progress. Since progress increases at rate T ≤ 3 T \le3 T ≤ 3 , we obtain
d ( X s , X t ) ≤ v 0 T ∣ s − t ∣ ≤ 3 v 0 ∣ s − t ∣ . d(X_s, X_t) \le v_0T|s-t| \le3v_0|s-t|. d ( X s , X t ) ≤ v 0 T ∣ s − t ∣ ≤ 3 v 0 ∣ s − t ∣.
Marginal intermediate distributions. Fix a time s s s and first condition on T T T . The fractional part u s = ( U + s T ) mod 1 u_s = (U + sT) \mathbin{\operatorname{mod}} 1 u s = ( U + s T ) mod 1 is uniform in [ 0 , 1 ) [0,1) [ 0 , 1 ) : adding a fixed number to a uniform position and reducing modulo one preserves uniformity. The index k s k_s k s depends only on U , T U,T U , T , which are independent of all the samples. Conditional on any choice of U , T U,T U , T , the selected pair ( A k s , A k s + 1 ) (A_{k_s}, A_{k_s+1}) ( A k s , A k s + 1 ) consists of independent ν \nu ν -samples. Consequently the pair is independent of the position u s u_s u s , and X s X_s X s has exactly the distribution μ \mu μ .
Independent endpoints. The initial point is X 0 = F ( A 0 , A 1 , U ) X_0 = F(A_0, A_1, U) X 0 = F ( A 0 , A 1 , U ) . Since T ≥ 2 T \ge2 T ≥ 2 , the final transition index satisfies k 1 ≥ 2 k_1 \ge2 k 1 ≥ 2 , so the final transition uses neither sampled variable A 0 A_0 A 0 nor A 1 A_1 A 1 . Moreover, conditional on any initial position U U U , the fractional part u 1 = ( U + T ) mod 1 u_1 = (U + T) \mathbin{\operatorname{mod}} 1 u 1 = ( U + T ) mod 1 is uniform, because T T T is uniform on an interval of length one. Hence u 1 u_1 u 1 is independent of U U U . Conditional on U , T U,T U , T , the final pair of samples has distribution ν × ν \nu\times\nu ν × ν , independently of the initial pair. It follows that the final triple ( A k 1 , A k 1 + 1 , u 1 ) (A_{k_1}, A_{k_1+1}, u_1) ( A k 1 , A k 1 + 1 , u 1 ) is independent of ( A 0 , A 1 , U ) (A_0, A_1, U) ( A 0 , A 1 , U ) and has distribution ν × ν × U [ 0 , 1 ) \nu\times\nu\times U_{[0,1)} ν × ν × U [ 0 , 1 ) , where U [ 0 , 1 ) U_{[0,1)} U [ 0 , 1 ) denotes the uniform distribution on [ 0 , 1 ) [0,1) [ 0 , 1 ) . Thus X 0 X_0 X 0 and X 1 X_1 X 1 are independent samples from μ \mu μ . Both choices in the construction matter: advancing by at least two transitions ensures that the initial and final transitions use disjoint sampled variables, and randomizing the fractional progress avoids sharing the initial position.
We have therefore constructed the required distribution Π \Pi Π : its endpoints are independent μ \mu μ -samples, every fixed-time marginal is μ \mu μ , and its change bound is 3 v 0 3v_0 3 v 0 . For a finite product, perform this construction independently in each coordinate and use the same time interval [ 0 , 1 ] [0,1] [ 0 , 1 ] . At every fixed time the coordinate distributions remain independent, and the two entire endpoints are independent. Taking the maximum of the coordinate change bounds gives 3 max i v 0 , i 3\max_i v_{0,i} 3 max i v 0 , i . A coordinate fixed at a prescribed value contributes zero change.
Proof of Theorem 5.2. Under the theorem’s hypotheses, Lemma 5.5 constructs a distribution Π \Pi Π satisfying Definition 9 with v = 3 v 0 v = 3v_0 v = 3 v 0 . Apply Proposition 5.4 to this distribution of paths to obtain the stated bound.
For finite products of these distributions, Theorem 5.2 and Corollary 5.3 hold with v 0 = max i v 0 , i v_0 = \max_i v_{0,i} v 0 = max i v 0 , i , using the maximum coordinate distance.
Relation to the Haar barrier theorem of [BEHMV26]
Bouaziz–Ermann et al. [13 Section 5.1, Theorems 2.1 and 5.3, and Appendix A.1] assume a specific metric probability space: a product of spheres with product Haar measure. They obtain their barrier bound from this geometry by enlarging one set through neighborhoods of increasing radius. They lower-bound the rate at which its probability grows using a Cheeger bound, which controls the size of the boundary relative to the probabilities on its two sides. Their proof obtains that bound from Lichnerowicz’s theorem and Buser’s inequality. The radius measures the width of a neighborhood; it is not the time parameter of a random path between independently sampled endpoints.
The path condition in Proposition 5.4 is an intermediate proof tool. Combining it with Lemma 5.5 gives Theorem 5.2, whose hypotheses directly describe how the distribution is generated. This gives a formulation parallel to the Haar result: the distribution belongs to a specified class, and the required path properties are proved from that description.
The Haar setting satisfies the path condition as well. In each sphere, connect independent Haar samples by the shortest great-circle arc, the shortest route along the sphere, traversed at a constant rate over [ 0 , 1 ] [0,1] [ 0 , 1 ] . Except on an event of probability zero, this arc is uniquely defined. Applying a unitary to the endpoints applies the same unitary to every intermediate point, so every fixed intermediate point is Haar distributed. Independent choices in each coordinate preserve the product distribution. Each arc has length at most π \pi π . Since Euclidean distance is at most arc length, these paths satisfy Definition 9 with v = π v=\pi v = π for the maximum coordinate Euclidean distance used in [13 ] .
To obtain the two-set bound, let S 0 , S 1 S_0,S_1 S 0 , S 1 be measurable sets separated by distance at least δ > 0 \delta>0 δ > 0 . Write p i = μ ( S i ) p_i=\mu(S_i) p i = μ ( S i ) for i ∈ { 0 , 1 } i\in\{0,1\} i ∈ { 0 , 1 } , m = min { p 0 , p 1 } m=\min\{p_0,p_1\} m = min { p 0 , p 1 } , and ϵ = 1 − p 0 − p 1 \epsilon=1-p_0-p_1 ϵ = 1 − p 0 − p 1 for the probability outside both sets. Proposition 5.4 gives
ϵ ≥ 2 δ π p 0 p 1 ≥ δ π m ( 1 − ϵ ) . \epsilon\ge\frac{2\delta}{\pi}p_0p_1 \ge\frac{\delta}{\pi}m(1-\epsilon). ϵ ≥ π 2 δ p 0 p 1 ≥ π δ m ( 1 − ϵ ) .
where the second inequality uses 2 max { p 0 , p 1 } ≥ p 0 + p 1 = 1 − ϵ 2\max\{p_0,p_1\}\ge p_0+p_1=1-\epsilon 2 max { p 0 , p 1 } ≥ p 0 + p 1 = 1 − ϵ . If m = 0 m=0 m = 0 , the desired bound is immediate. Otherwise δ ≤ 2 < π \delta\le2<\pi δ ≤ 2 < π , since the Euclidean distance between unit vectors is at most two. Rearranging and using m ≤ 1 m\le1 m ≤ 1 yields
μ ( X ∖ ( S 0 ∪ S 1 ) ) = ϵ ≥ δ m π + δ m ≥ δ 2 π min { μ ( S 0 ) , μ ( S 1 ) } . \mu(\mathcal{X}\setminus(S_0\cup S_1))=\epsilon\ge\frac{\delta m}{\pi+\delta m}\ge\frac{\delta}{2\pi}\min\{\mu(S_0),\mu(S_1)\}. μ ( X ∖ ( S 0 ∪ S 1 )) = ϵ ≥ π + δ m δ m ≥ 2 π δ min { μ ( S 0 ) , μ ( S 1 )} .
This recovers the dependence on the distance and the smaller set’s probability in [13 Theorem 5.3] , with a different constant that is independent of the dimensions and the number of spheres. For the interpolation distributions considered here, Lemma 5.5 instead constructs paths with v = 3 v 0 v=3v_0 v = 3 v 0 , yielding Theorem 5.2 .
Base Oracle Distribution and Constructions of qPKE and Point-function Obfuscation
We first define a base distribution P \mathcal{P} P of oracles with respect to which we show a secure qPKE and Point-function Obfuscation, up to negligible probability over the distribution. Then in § 5.8 , we condition on favorable events to obtain a new distribution Q \mathcal{Q} Q , where qOWFs do not exist, while the qPKE and Point-function Obfuscation constructions remain secure, up to some small probability.
Base Oracle distribution
At each length, the oracle provides three operations: O s a m p O_{\mathrm{samp}} O samp , O e n c O_{\mathrm{enc}} O enc , and O d e c O_{\mathrm{dec}} O dec . We first describe the classical data used by the oracles, mainly consisting of three objects: a row , tables and an interpolation parameter . We then specify the quantum states and oracle operations determined by these data. After the oracles are described, § 5.5 gives the qPKE and point-function obfuscation constructions using these operations.
Classical data and their distribution. Fix a length n ≥ 1 n\ge1 n ≥ 1 , and set N = 2 n N=2^n N = 2 n , Y = 2 8 n Y=2^{8n} Y = 2 8 n , M = 2 2 n M=2^{2n} M = 2 2 n , Z = 2 12 n Z=2^{12n} Z = 2 12 n . There are N N N p-keys, Y Y Y possible s-keys, and Z Z Z possible c-texts, where a row corresponding to a p-key j ∈ [ N ] j\in[N] j ∈ [ N ] is a classical tuple ( s , L 0 , L 1 ) (s,L_0,L_1) ( s , L 0 , L 1 ) , s ∈ [ Y ] s\in[Y] s ∈ [ Y ] , L 0 , L 1 ⊆ [ Z ] L_0,L_1\subseteq[Z] L 0 , L 1 ⊆ [ Z ] , ∣ L 0 ∣ = ∣ L 1 ∣ = M |L_0|=|L_1|=M ∣ L 0 ∣ = ∣ L 1 ∣ = M , L 0 ∩ L 1 = ∅ L_0\cap L_1=\varnothing L 0 ∩ L 1 = ∅ . We call s s s the s-key, and L 0 L_0 L 0 and L 1 L_1 L 1 are two sets of c-texts, where for each bit b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } , L b L_b L b is the set of c-texts hiding bit b b b . For each j ∈ [ N ] j\in[N] j ∈ [ N ] , we sample a row ( s , L 0 , L 1 ) (s,L_0,L_1) ( s , L 0 , L 1 ) by independently sampling s ← $ [ Y ] s\overset{\$}{\leftarrow}[Y] s ← $ [ Y ] , L 0 ← $ ( [ Z ] M ) L_0\overset{\$}{\leftarrow}\binom{[Z]}{M} L 0 ← $ ( M [ Z ] ) , L 1 ← $ ( [ Z ] ∖ L 0 M ) L_1\overset{\$}{\leftarrow}\binom{[Z]\setminus L_0}{M} L 1 ← $ ( M [ Z ] ∖ L 0 ) . The two c-text sets are sampled as a uniform ordered pair of disjoint sets; they are not independent of each other.
Sampling the two tables and the interpolation parameter. For each j ∈ [ N ] j\in[N] j ∈ [ N ] , independently sample two rows from the distribution above, named ( s j A , A j , 0 , A j , 1 ) (s_j^A,A_{j,0},A_{j,1}) ( s j A , A j , 0 , A j , 1 ) and ( s j B , B j , 0 , B j , 1 ) (s_j^B,B_{j,0},B_{j,1}) ( s j B , B j , 0 , B j , 1 ) . Collect the first rows into table A A A and the second rows into table B B B , i.e., A = ( ( s j A , A j , 0 , A j , 1 ) ) j ∈ [ N ] A=((s_j^A,A_{j,0},A_{j,1}))_{j\in[N]} A = (( s j A , A j , 0 , A j , 1 ) ) j ∈ [ N ] and B = ( ( s j B , B j , 0 , B j , 1 ) ) j ∈ [ N ] B = ((s^{B}_{j}, B_{j,0}, B_{j,1}))_{j \in[N]} B = (( s j B , B j , 0 , B j , 1 ) ) j ∈ [ N ] . All row draws are independent across p-keys and between tables. We call their pair at p-key j j j the pair of rows . Within each table, the two c-text sets are disjoint; across tables, c-text sets may intersect and the s-keys s j A , s j B s^{A}_{j}, s^{B}_{j} s j A , s j B may coincide.
Let A j = A j , 0 ∪ A j , 1 A_j = A_{j,0} \cup A_{j,1} A j = A j , 0 ∪ A j , 1 and B j = B j , 0 ∪ B j , 1 B_j = B_{j,0} \cup B_{j,1} B j = B j , 0 ∪ B j , 1 . A pair of rows is good if A j ∩ B j = ∅ A_j \cap B_j = \varnothing A j ∩ B j = ∅ , and is bad with probability at most 4 M 2 / Z 4M^2/Z 4 M 2 / Z . Independently of the tables A n , B n A_n, B_n A n , B n , sample independent uniform i n ∈ { 1 , 2 , 3 } i_n \in\{1,2,3\} i n ∈ { 1 , 2 , 3 } and t n ∈ [ 0 , 1 ] t_n \in[0,1] t n ∈ [ 0 , 1 ] , and set τ n = ( i n − 1 + t n ) / 3 \tau_n = (i_n - 1 + t_n)/3 τ n = ( i n − 1 + t n ) /3 . Then τ n \tau_n τ n is uniform in [ 0 , 1 ] [0,1] [ 0 , 1 ] . The base distribution P \mathcal{P} P is the resulting distribution of ( A n , B n , τ n ) n ≥ 1 (A_n,B_n,\tau_n)_{n \ge1} ( A n , B n , τ n ) n ≥ 1 , independent across lengths, with A n , B n , τ n A_n, B_n, \tau_n A n , B n , τ n independent within each length. All three operations and all rows at length n n n use the same τ n \tau_n τ n ; algorithms query the resulting operations without supplying this parameter. Below we suppress the length subscript and write A , B , τ A, B, \tau A , B , τ .
States and response angles. Each table specifies uniform c-text states and response angles:
∣ ϕ j , b A ⟩ = 1 M ∑ c ∈ A j , b ∣ c ⟩ , ∣ ϕ j , b B ⟩ = 1 M ∑ c ∈ B j , b ∣ c ⟩ . \lvert\phi^{A}_{j,b} \rangle= \frac{1}{\sqrt{M}} \sum_{c \in A_{j,b}} \lvert c \rangle,\qquad\lvert\phi^{B}_{j,b} \rangle= \frac{1}{\sqrt{M}} \sum_{c \in B_{j,b}} \lvert c \rangle. ∣ ϕ j , b A ⟩ = M 1 c ∈ A j , b ∑ ∣ c ⟩ , ∣ ϕ j , b B ⟩ = M 1 c ∈ B j , b ∑ ∣ c ⟩ .
α j A ( c ) = { 0 c ∈ A j , 0 , π / 2 c ∈ A j , 1 , π / 4 c ∉ A j , α j B ( c ) = { 0 c ∈ B j , 0 , π / 2 c ∈ B j , 1 , π / 4 c ∉ B j . \alpha^{A}_{j}(c) =
\begin{cases}
0 & c \in A_{j,0},\\
\pi/2 & c \in A_{j,1},\\
\pi/4 & c \notin A_j,
\end{cases}
\qquad
\alpha^{B}_{j}(c) =
\begin{cases}
0 & c \in B_{j,0},\\
\pi/2 & c \in B_{j,1},\\
\pi/4 & c \notin B_j.
\end{cases} α j A ( c ) = ⎩ ⎨ ⎧ 0 π /2 π /4 c ∈ A j , 0 , c ∈ A j , 1 , c ∈ / A j , α j B ( c ) = ⎩ ⎨ ⎧ 0 π /2 π /4 c ∈ B j , 0 , c ∈ B j , 1 , c ∈ / B j .
O d e c O_{\mathrm{dec}} O dec uses angles 0 , π / 2 , π / 4 0, \pi/2, \pi/4 0 , π /2 , π /4 to return zero, one, or an unbiased bit when its response qubit starts in ∣ 0 ⟩ \lvert0 \rangle ∣ 0 ⟩ . To accommodate c-texts from both tables, define the shared angle
γ j ( c ) = { α j A ( c ) c ∈ A j ∖ B j , α j B ( c ) c ∈ B j ∖ A j , π / 4 otherwise . \gamma_j(c) =
\begin{cases}
\alpha^{A}_{j}(c) & c \in A_j \setminus B_j,\\
\alpha^{B}_{j}(c) & c \in B_j \setminus A_j,\\
\pi/4 & \text{otherwise}.
\end{cases} γ j ( c ) = ⎩ ⎨ ⎧ α j A ( c ) α j B ( c ) π /4 c ∈ A j ∖ B j , c ∈ B j ∖ A j , otherwise .
Thus a c-text c c c in exactly one table uses that table’s angle, while a c-text in both tables or neither uses the default π / 4 \pi/4 π /4 . For 1 / 3 ≤ τ ≤ 2 / 3 1/3 \le\tau\le2/3 1/3 ≤ τ ≤ 2/3 , define
∣ g j ( τ ) ⟩ = { cos ( π ( 3 τ − 1 ) 2 ) ∣ s j A ⟩ + sin ( π ( 3 τ − 1 ) 2 ) ∣ s j B ⟩ s j A ≠ s j B , ∣ s j A ⟩ s j A = s j B . \lvert g_j(\tau) \rangle=
\begin{cases}
\cos\left(\frac{\pi(3\tau-1)}{2}\right)\lvert s^{A}_{j}\rangle+ \sin\left(\frac{\pi(3\tau-1)}{2}\right)\lvert s^{B}_{j}\rangle& s^{A}_{j} \ne s^{B}_{j},\\
\lvert s^{A}_{j}\rangle& s^{A}_{j} = s^{B}_{j}.
\end{cases} ∣ g j ( τ )⟩ = { cos ( 2 π ( 3 τ − 1 ) ) ∣ s j A ⟩ + sin ( 2 π ( 3 τ − 1 ) ) ∣ s j B ⟩ ∣ s j A ⟩ s j A = s j B , s j A = s j B .
∣ ϕ j , b ( τ ) ⟩ = cos ( π ( 3 τ − 1 ) 2 ) ∣ ϕ j , b A ⟩ + sin ( π ( 3 τ − 1 ) 2 ) ∣ ϕ j , b B ⟩ 1 + 2 sin ( π ( 3 τ − 1 ) 2 ) cos ( π ( 3 τ − 1 ) 2 ) ⟨ ϕ j , b A ∣ ϕ j , b B ⟩ . \lvert\phi_{j,b}(\tau) \rangle=
\frac{\cos\left(\frac{\pi(3\tau-1)}{2}\right)\lvert\phi^{A}_{j,b}\rangle+ \sin\left(\frac{\pi(3\tau-1)}{2}\right)\lvert\phi^{B}_{j,b}\rangle}
{\sqrt{1 + 2\sin\left(\frac{\pi(3\tau-1)}{2}\right)\cos\left(\frac{\pi(3\tau-1)}{2}\right)\langle\phi^{A}_{j,b} \mid\phi^{B}_{j,b}\rangle}}. ∣ ϕ j , b ( τ )⟩ = 1 + 2 sin ( 2 π ( 3 τ − 1 ) ) cos ( 2 π ( 3 τ − 1 ) ) ⟨ ϕ j , b A ∣ ϕ j , b B ⟩ cos ( 2 π ( 3 τ − 1 ) ) ∣ ϕ j , b A ⟩ + sin ( 2 π ( 3 τ − 1 ) ) ∣ ϕ j , b B ⟩ .
The O s a m p O_{\mathrm{samp}} O samp state is ∣ Ψ ⟩ = N − 1 / 2 ∑ j ∈ [ N ] ∣ j ⟩ ∣ ψ j ⟩ \lvert\Psi\rangle= N^{-1/2} \sum_{j \in[N]} \lvert j \rangle\lvert\psi_j \rangle ∣ Ψ ⟩ = N − 1/2 ∑ j ∈ [ N ] ∣ j ⟩ ∣ ψ j ⟩ . The parameter τ \tau τ determines its components ∣ ψ j ⟩ \lvert\psi_j \rangle ∣ ψ j ⟩ , the O e n c O_{\mathrm{enc}} O enc states ∣ ϕ j , b ⟩ \lvert\phi_{j,b} \rangle ∣ ϕ j , b ⟩ , and the O d e c O_{\mathrm{dec}} O dec angles β j , y ( c ) \beta_{j,y}(c) β j , y ( c ) . For y ∉ { s j A , s j B } y \notin\{s^{A}_{j},s^{B}_{j}\} y ∈ / { s j A , s j B } , always set β j , y ( c ) = π / 4 \beta_{j,y}(c) = \pi/4 β j , y ( c ) = π /4 . For distinct s-keys s j A , s j B s^{A}_{j},s^{B}_{j} s j A , s j B , use the following formulas.
0 ≤ τ ≤ 1 / 3 0 \le\tau\le1/3 0 ≤ τ ≤ 1/3 : sample from A and interpolate to the shared response rule. Set ∣ ψ j ⟩ = ∣ s j A ⟩ \lvert\psi_j \rangle= \lvert s^{A}_{j}\rangle ∣ ψ j ⟩ = ∣ s j A ⟩ , ∣ ϕ j , b ⟩ = ∣ ϕ j , b A ⟩ \lvert\phi_{j,b} \rangle= \lvert\phi^{A}_{j,b}\rangle ∣ ϕ j , b ⟩ = ∣ ϕ j , b A ⟩ , β j , s j A ( c ) = ( 1 − 3 τ ) α j A ( c ) + 3 τ γ j ( c ) \beta_{j,s^{A}_{j}}(c) = (1-3\tau)\alpha^{A}_{j}(c) + 3\tau\gamma_j(c) β j , s j A ( c ) = ( 1 − 3 τ ) α j A ( c ) + 3 τ γ j ( c ) , β j , s j B ( c ) = ( 1 − 3 τ ) π / 4 + 3 τ γ j ( c ) \beta_{j,s^{B}_{j}}(c) = (1-3\tau)\pi/4 + 3\tau\gamma_j(c) β j , s j B ( c ) = ( 1 − 3 τ ) π /4 + 3 τ γ j ( c ) .
1 / 3 ≤ τ ≤ 2 / 3 1/3 \le\tau\le2/3 1/3 ≤ τ ≤ 2/3 : interpolate both states and use the shared response rule. Set ∣ ψ j ⟩ = ∣ g j ( τ ) ⟩ \lvert\psi_j \rangle= \lvert g_j(\tau) \rangle ∣ ψ j ⟩ = ∣ g j ( τ )⟩ , ∣ ϕ j , b ⟩ = ∣ ϕ j , b ( τ ) ⟩ \lvert\phi_{j,b} \rangle= \lvert\phi_{j,b}(\tau) \rangle ∣ ϕ j , b ⟩ = ∣ ϕ j , b ( τ )⟩ , and β j , s j A ( c ) = β j , s j B ( c ) = γ j ( c ) \beta_{j,s^{A}_{j}}(c) = \beta_{j,s^{B}_{j}}(c) = \gamma_j(c) β j , s j A ( c ) = β j , s j B ( c ) = γ j ( c ) .
2 / 3 ≤ τ ≤ 1 2/3 \le\tau\le1 2/3 ≤ τ ≤ 1 : sample from B and interpolate to its response rule. Set ∣ ψ j ⟩ = ∣ s j B ⟩ \lvert\psi_j \rangle= \lvert s^{B}_{j}\rangle ∣ ψ j ⟩ = ∣ s j B ⟩ , ∣ ϕ j , b ⟩ = ∣ ϕ j , b B ⟩ \lvert\phi_{j,b} \rangle= \lvert\phi^{B}_{j,b}\rangle ∣ ϕ j , b ⟩ = ∣ ϕ j , b B ⟩ , β j , s j A ( c ) = ( 3 − 3 τ ) γ j ( c ) + ( 3 τ − 2 ) π / 4 \beta_{j,s^{A}_{j}}(c) = (3-3\tau)\gamma_j(c) + (3\tau-2)\pi/4 β j , s j A ( c ) = ( 3 − 3 τ ) γ j ( c ) + ( 3 τ − 2 ) π /4 , β j , s j B ( c ) = ( 3 − 3 τ ) γ j ( c ) + ( 3 τ − 2 ) α j B ( c ) \beta_{j,s^{B}_{j}}(c) = (3-3\tau)\gamma_j(c) + (3\tau-2)\alpha^{B}_{j}(c) β j , s j B ( c ) = ( 3 − 3 τ ) γ j ( c ) + ( 3 τ − 2 ) α j B ( c ) .
If s j A = s j B s_j^A=s_j^B s j A = s j B , keep the same states and assign their common s-key the single angle ( 1 − 3 τ ) α j A ( c ) + 3 τ γ j ( c ) (1-3\tau)\alpha_j^A(c)+3\tau\gamma_j(c) ( 1 − 3 τ ) α j A ( c ) + 3 τ γ j ( c ) for 0 ≤ τ ≤ 1 / 3 0\leq\tau\leq1/3 0 ≤ τ ≤ 1/3 , γ j ( c ) \gamma_j(c) γ j ( c ) for 1 / 3 ≤ τ ≤ 2 / 3 1/3\leq\tau\leq2/3 1/3 ≤ τ ≤ 2/3 , and ( 3 − 3 τ ) γ j ( c ) + ( 3 τ − 2 ) α j B ( c ) (3-3\tau)\gamma_j(c)+(3\tau-2)\alpha_j^B(c) ( 3 − 3 τ ) γ j ( c ) + ( 3 τ − 2 ) α j B ( c ) for 2 / 3 ≤ τ ≤ 1 2/3\leq\tau\leq1 2/3 ≤ τ ≤ 1 . The formulas agree at τ = 1 / 3 \tau=1/3 τ = 1/3 and τ = 2 / 3 \tau=2/3 τ = 2/3 .
Oracle operations. Each answer register for O s a m p O_{\mathrm{samp}} O samp or O e n c O_{\mathrm{enc}} O enc also has a distinguished basis state ∣ □ ⟩ |\square\rangle ∣ □ ⟩ orthogonal to all valid answers. The following unitaries are defined on arbitrary inputs, act as the identity on unused encodings, and extend linearly to superpositions. O e n c O_{\mathrm{enc}} O enc and O d e c O_{\mathrm{dec}} O dec preserve their control registers.
O s a m p O_{\mathrm{samp}} O samp . On the joint answer register for ( j , y ) (j,y) ( j , y ) , define
O s a m p , n = I − ( ∣ □ ⟩ − ∣ Ψ ⟩ ) ( ⟨ □ ∣ − ⟨ Ψ ∣ ) . O_{\mathrm{samp},n}=I-\left(|\square\rangle-|\Psi\rangle\right)\left(\langle\square|-\langle\Psi|\right). O samp , n = I − ( ∣ □ ⟩ − ∣Ψ ⟩ ) ( ⟨ □ ∣ − ⟨ Ψ∣ ) .
It swaps ∣ □ ⟩ |\square\rangle ∣ □ ⟩ with ∣ Ψ ⟩ |\Psi\rangle ∣Ψ ⟩ and fixes their orthogonal complement. Measuring the prepared state ∣ Ψ ⟩ |\Psi\rangle ∣Ψ ⟩ gives a uniform p-key j j j and an s-key distributed as the measurement of ∣ ψ j ⟩ |\psi_j\rangle ∣ ψ j ⟩ .
O e n c O_{\mathrm{enc}} O enc . On control registers ( j , b ) (j,b) ( j , b ) and an answer register for the c-text c c c , define
O e n c , n = ∑ j ∈ [ N ] , b ∈ { 0 , 1 } ∣ j , b ⟩ ⟨ j , b ∣ ⊗ [ I − ( ∣ □ ⟩ − ∣ ϕ j , b ⟩ ) ( ⟨ □ ∣ − ⟨ ϕ j , b ∣ ) ] + Π b a d ⊗ I . O_{\mathrm{enc},n}=
\sum_{j\in[N],\,b\in\{0,1\}}|j,b\rangle\langle j,b|\otimes\left[I-\left(|\square\rangle-|\phi_{j,b}\rangle\right)\left(\langle\square|-\langle\phi_{j,b}|\right)\right]+\Pi_{\mathrm{bad}}\otimes I. O enc , n = j ∈ [ N ] , b ∈ { 0 , 1 } ∑ ∣ j , b ⟩ ⟨ j , b ∣ ⊗ [ I − ( ∣ □ ⟩ − ∣ ϕ j , b ⟩ ) ( ⟨ □ ∣ − ⟨ ϕ j , b ∣ ) ] + Π bad ⊗ I .
where Π b a d \Pi_{\mathrm{bad}} Π bad projects onto malformed controls. At each valid ( j , b ) (j,b) ( j , b ) , the answer operation swaps ∣ □ ⟩ |\square\rangle ∣ □ ⟩ with ∣ ϕ j , b ⟩ |\phi_{j,b}\rangle ∣ ϕ j , b ⟩ and fixes their orthogonal complement. Measuring the prepared answer gives a c-text c c c associated with bit b b b at p-key j j j .
O d e c O_{\mathrm{dec}} O dec . On controls ( j , y , c ) ∈ [ N ] × [ Y ] × [ Z ] (j,y,c)\in[N]\times[Y]\times[Z] ( j , y , c ) ∈ [ N ] × [ Y ] × [ Z ] and one response qubit, define
O d e c , n ∣ j , y , c , 0 ⟩ = cos ( β j , y ( c ) ) ∣ j , y , c , 0 ⟩ + sin ( β j , y ( c ) ) ∣ j , y , c , 1 ⟩ , O d e c , n ∣ j , y , c , 1 ⟩ = sin ( β j , y ( c ) ) ∣ j , y , c , 0 ⟩ − cos ( β j , y ( c ) ) ∣ j , y , c , 1 ⟩ . \begin{aligned}
O_{\mathrm{dec},n}|j,y,c,0\rangle&=\cos(\beta_{j,y}(c))|j,y,c,0\rangle+\sin(\beta_{j,y}(c))|j,y,c,1\rangle,\\
O_{\mathrm{dec},n}|j,y,c,1\rangle&=\sin(\beta_{j,y}(c))|j,y,c,0\rangle-\cos(\beta_{j,y}(c))|j,y,c,1\rangle.
\end{aligned} O dec , n ∣ j , y , c , 0 ⟩ O dec , n ∣ j , y , c , 1 ⟩ = cos ( β j , y ( c )) ∣ j , y , c , 0 ⟩ + sin ( β j , y ( c )) ∣ j , y , c , 1 ⟩ , = sin ( β j , y ( c )) ∣ j , y , c , 0 ⟩ − cos ( β j , y ( c )) ∣ j , y , c , 1 ⟩ .
Malformed controls are unchanged. Starting with response ∣ 0 ⟩ |0\rangle ∣0 ⟩ , measurement returns one with probability sin 2 ( β j , y ( c ) ) \sin^2(\beta_{j,y}(c)) sin 2 ( β j , y ( c )) . Every other s-key uses the default angle π / 4 \pi/4 π /4 for all c-texts c c c .
These three operations use O ( n ) O(n) O ( n ) qubits and form the oracle block at length n n n . In addition, fix a PSPACE-complete language L P S P A C E L_{\mathrm{PSPACE}} L PSPACE independently of all sampled data and provide its reversible membership oracle U P S P A C E ∣ z , v ⟩ = ∣ z , v ⊕ 1 { z ∈ L P S P A C E } ⟩ U_{\mathrm{PSPACE}}|z,v\rangle=|z,v\oplus1_{\{z\in L_{\mathrm{PSPACE}}\}}\rangle U PSPACE ∣ z , v ⟩ = ∣ z , v ⊕ 1 { z ∈ L PSPACE } ⟩ , for v ∈ { 0 , 1 } v\in\{0,1\} v ∈ { 0 , 1 } . This oracle has no access to the other oracles.
For the following norm estimates, abbreviate the reflections used above by
H ψ = I − ( ∣ □ ⟩ − ∣ ψ ⟩ ) ( ⟨ □ ∣ − ⟨ ψ ∣ ) , Q ( θ ) = ( cos θ sin θ sin θ − cos θ ) . (2) H_\psi=I-\left(|\square\rangle-|\psi\rangle\right)\left(\langle\square|-\langle\psi|\right),\qquad Q(\theta)=\begin{pmatrix}\cos\theta&\sin\theta\\\sin\theta&-\cos\theta\end{pmatrix}. \tag*{(2)} H ψ = I − ( ∣ □ ⟩ − ∣ ψ ⟩ ) ( ⟨ □ ∣ − ⟨ ψ ∣ ) , Q ( θ ) = ( cos θ sin θ sin θ − cos θ ) . (2)
where ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ is a normalized real state orthogonal to ∣ □ ⟩ |\square\rangle ∣ □ ⟩ . Thus O s a m p O_{\mathrm{samp}} O samp is H Ψ H_\Psi H Ψ , the answer operation of O e n c O_{\mathrm{enc}} O enc at ( j , b ) (j,b) ( j , b ) is H ϕ j , b H_{\phi_{j,b}} H ϕ j , b , and the response operation of O d e c O_{\mathrm{dec}} O dec at ( j , y , c ) (j,y,c) ( j , y , c ) is Q ( β j , y ( c ) ) Q(\beta_{j,y}(c)) Q ( β j , y ( c )) .
Properties of the Oracle and the base distribution on it
Next, we state the following immediate properties of the oracle distribution.
Observation 5.6 (Immediate properties of the oracle). The definitions give the following properties.
Matching endpoints. For any three tables A , B , C A, B, C A , B , C at the same length, the transition A → B A \to B A → B at τ = 1 \tau= 1 τ = 1 gives exactly the same oracle operations as the transition B → C B \to C B → C at τ = 0 \tau= 0 τ = 0 , because both endpoints depend only on B B B . Thus the transitions A → B → C A \to B \to C A → B → C join continuously, allowing us to concatenate transitions in the path construction of § 5.1 .
Uniform p p p -key. For every τ \tau τ , O s a m p O_{\mathrm{samp}} O samp yields a uniform p p p -key j j j , since each normalized ∣ ψ j ⟩ \lvert\psi_j\rangle ∣ ψ j ⟩ has coefficient 1 / N 1/\sqrt{N} 1/ N in ∣ Ψ ⟩ \lvert\Psi\rangle ∣ Ψ ⟩ .
Default response. By definition, β j , y ( c ) = π / 4 \beta_{j,y}(c) = \pi/4 β j , y ( c ) = π /4 whenever y ∉ { s j A , s j B } y \notin\{s_j^A, s_j^B\} y ∈ / { s j A , s j B } .
Correctness. At every good pair of rows at j j j , the formulas give β j , y ( c ) = π b / 2 \beta_{j,y}(c) = \pi b/2 β j , y ( c ) = π b /2 for honestly sampled y , c y, c y , c , so O d e c O_{\mathrm{dec}} O dec recovers b b b with certainty, including when s j A = s j B s_j^A = s_j^B s j A = s j B .
Next, we establish that the unitaries U ( τ ) U(\tau) U ( τ ) are in fact Lipschitz in τ \tau τ with the Lipschitz constant independent of the length n n n and the choice of tables A , B A, B A , B .
Lemma 5.7 (Bounded change of the interpolation). There is a constant v 0 v_0 v 0 , independent of the length n n n and the choice of tables A , B A, B A , B , such that ∥ U ( τ ) − U ( τ ′ ) ∥ ≤ v 0 ∣ τ − τ ′ ∣ \lVert U(\tau) - U(\tau')\rVert\le v_0\lvert\tau- \tau'\rvert ∥ U ( τ ) − U ( τ ′ )∥ ≤ v 0 ∣ τ − τ ′ ∣ for every oracle operation U U U along the transition from A A A to B B B and all τ , τ ′ ∈ [ 0 , 1 ] \tau, \tau' \in[0,1] τ , τ ′ ∈ [ 0 , 1 ] .
Proof. For the response and state-preparation reflections,
∥ Q ( θ ) − Q ( θ ′ ) ∥ ≤ ∣ θ − θ ′ ∣ , ∥ H ψ − H ϕ ∥ ≤ 2 2 ∥ ∣ ψ ⟩ − ∣ ϕ ⟩ ∥ . \lVert Q(\theta) - Q(\theta')\rVert\le\lvert\theta- \theta'\rvert,\qquad\lVert H_{\psi} - H_{\phi}\rVert\le2\sqrt{2}\lVert\lvert\psi\rangle- \lvert\phi\rangle\rVert. ∥ Q ( θ ) − Q ( θ ′ )∥ ≤ ∣ θ − θ ′ ∣ , ∥ H ψ − H ϕ ∥ ≤ 2 2 ∥∣ ψ ⟩ − ∣ ϕ ⟩∥ .
Within each of the intervals [ 0 , 1 / 3 ] [0,1/3] [ 0 , 1/3 ] , [ 1 / 3 , 2 / 3 ] [1/3,2/3] [ 1/3 , 2/3 ] , and [ 2 / 3 , 1 ] [2/3,1] [ 2/3 , 1 ] , the response angles β j , y ( c ) \beta_{j,y}(c) β j , y ( c ) and s-key states ∣ ψ j ⟩ \lvert\psi_j\rangle ∣ ψ j ⟩ have derivatives in τ \tau τ bounded by absolute constants. Orthogonality of the terms with distinct p p p -keys gives the same bound for ∣ Ψ ⟩ \lvert\Psi\rangle ∣ Ψ ⟩ . On [ 1 / 3 , 2 / 3 ] [1/3,2/3] [ 1/3 , 2/3 ] , the numerator defining ∣ ϕ j , b ( τ ) ⟩ \lvert\phi_{j,b}(\tau)\rangle ∣ ϕ j , b ( τ )⟩ has a bounded derivative and a norm of at least one, so its normalized state also has a bounded derivative; outside this interval, the c-text states are constant. Direct sums take the maximum of component norms, and the formulas agree at the joins, so the triangle inequality extends the bound across the entire transition. □
Next, we state the following lemma regarding the replacement of a random coordinate of an oracle distribution with independently sampled variables for each p-key, such as our base distribution P \mathcal{P} P .
Lemma 5.8 (Replacing a random coordinate). Let P = P W ∏ j = 1 N P j \mathcal{P} = \mathcal{P}_W \prod_{j=1}^{N} \mathcal{P}_j P = P W ∏ j = 1 N P j and D ( R ∥ P ) ≤ L D(\mathcal{R}\mathbin{\|}\mathcal{P}) \le L D ( R ∥ P ) ≤ L . Sample ( W , X 1 , … , X N ) (W, X_1, \ldots, X_N) ( W , X 1 , … , X N ) from R \mathcal{R} R , independently choose a uniform h h h -subset H ⊆ [ N ] H \subseteq[N] H ⊆ [ N ] , and choose a uniform J ∈ H J \in H J ∈ H , where 1 ≤ h ≤ N 1 \le h \le N 1 ≤ h ≤ N .
Let μ \mu μ be the distribution of ( W , X − H , H , J , X J ) (W, X_{-H}, H, J, X_J) ( W , X − H , H , J , X J ) , where X − H = ( X j ) j ∉ H X_{-H} = (X_j)_{j\notin H} X − H = ( X j ) j ∈ / H . Let μ ′ \mu' μ ′ be obtained by replacing X J X_J X J with an independent sample from P J \mathcal{P}_J P J . Then
D ( μ ∥ μ ′ ) ≤ L h , (3) D(\mu\mathbin{\|}\mu') \le\frac{L}{h}, \tag*{(3)} D ( μ ∥ μ ′ ) ≤ h L , (3) and consequently,
SD ( μ , μ ′ ) ≤ L 2 h . (4) \operatorname{SD}(\mu,\mu') \le\sqrt{\frac{L}{2h}}. \tag*{(4)} SD ( μ , μ ′ ) ≤ 2 h L . (4)
Proof. Fix H H H . Under P \mathcal{P} P , the coordinates X H X_H X H are independent of ( W , X − H ) (W,X_{-H}) ( W , X − H ) and have distribution ∏ j ∈ H P j \prod_{j\in H}P_j ∏ j ∈ H P j . The chain rule in Lemma 3.1, together with nonnegativity of relative entropy, therefore gives
E W , X − H D ( R X H ∣ W , X − H ∥ ∏ j ∈ H P j ) ≤ D ( R ∥ P ) ≤ L . \mathbb{E}_{W,X_{-H}} D\left(\mathcal{R}_{X_H\mid W,X_{-H}} \,\middle\|\, \prod_{j\in H}P_j\right) \le D(\mathcal{R}\|\mathcal{P}) \le L. E W , X − H D R X H ∣ W , X − H j ∈ H ∏ P j ≤ D ( R ∥ P ) ≤ L .
Apply Lemma 3.2 to each conditional distribution of X H X_H X H , and average over the conditioning variables. This yields
∑ j ∈ H E W , X − H D ( R X j ∣ W , X − H ∥ P j ) ≤ L . \sum_{j\in H}\mathbb{E}_{W,X_{-H}}D\left(\mathcal{R}_{X_j\mid W,X_{-H}}\|P_j\right)\le L. j ∈ H ∑ E W , X − H D ( R X j ∣ W , X − H ∥ P j ) ≤ L .
Since J J J is uniform in H H H , averaging over J J J divides this sum by h h h . Averaging also over H H H proves (3) . By construction, μ \mu μ and μ ′ \mu' μ ′ have the same marginal on ( W , X − H , H , J ) (W,X_{-H},H,J) ( W , X − H , H , J ) . Applying the chain rule once more gives
D ( μ ∥ μ ′ ) = E H , J , W , X − H D ( R X J ∣ W , X − H ∥ P J ) ≤ L h . D(\mu\|\mu')=\mathbb{E}_{H,J,W,X_{-H}}D\left(\mathcal{R}_{X_J\mid W,X_{-H}}\|P_J\right)\le\frac{L}{h}. D ( μ ∥ μ ′ ) = E H , J , W , X − H D ( R X J ∣ W , X − H ∥ P J ) ≤ h L .
Finally, combining this with Pinsker’s inequality (Lemma 3.3) yields the desired Eq. (4) . Adjoining independent samples preserves this distance, and applying the same classical or quantum experiment cannot increase the difference between its output probabilities.
Construction of qPKE and Point-function Obfuscation
We now define the two primitives supported by the oracle. Keys, ciphertexts, and obfuscated programs are classical strings, and the quantum algorithms use the quantum oracles O s a m p O_{\mathrm{samp}} O samp , O e n c O_{\mathrm{enc}} O enc and O d e c O_{\mathrm{dec}} O dec defined above.
The Public Key Encryption Scheme. At security parameter λ \lambda λ , use the operations at length n = λ n=\lambda n = λ :
KeyGen ( 1 λ ) \operatorname{KeyGen}(1^\lambda) KeyGen ( 1 λ ) applies O s a m p , λ O_{\mathrm{samp},\lambda} O samp , λ to blank and measures ( j , y ) (j,y) ( j , y ) . It outputs p k = j \mathrm{pk}=j pk = j and s k = ( j , y ) \mathrm{sk}=(j,y) sk = ( j , y ) .
Enc ( j , b ) \operatorname{Enc}(j,b) Enc ( j , b ) applies O e n c , λ O_{\mathrm{enc},\lambda} O enc , λ to ∣ j , b , □ ⟩ \lvert j,b,\square\rangle ∣ j , b , □ ⟩ , measures the c-text c c c , and outputs the ciphertext ( j , c ) (j,c) ( j , c ) .
Dec ( ( j , y ) , ( j , c ) ) \operatorname{Dec}((j,y),(j,c)) Dec (( j , y ) , ( j , c )) applies O d e c , λ O_{\mathrm{dec},\lambda} O dec , λ to ∣ j , y , c , 0 ⟩ \lvert j,y,c,0\rangle ∣ j , y , c , 0 ⟩ and measures the response bit.
Define encryption on malformed inputs to return a fixed ciphertext, and decryption to return zero if an input is malformed or the p-keys in the secret key and ciphertext differ.
Lemma 5.9 (qPKE correctness under a relative-entropy bound). Let P n P_n P n be the base distribution of oracle descriptions at length n = λ n=\lambda n = λ . For any potentially different distribution R \mathcal{R} R on these descriptions satisfying D ( R ∥ P n ) ≤ L D(\mathcal{R}\|P_n)\le L D ( R ∥ P n ) ≤ L , it holds that for every b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } , the expected honest decryption error of the qPKE construction, averaged over R \mathcal{R} R satisfies
E O ← R [ Pr ( p k , s k ) ← KeyGen O ( 1 λ ) c t ← Enc O ( p k , b ) [ Dec O ( s k , c t ) ≠ b ] ] ≤ 4 M 2 Z + L 2 N . \mathbb{E}_{\mathcal{O}\leftarrow\mathcal{R}}\left[\Pr_{\substack{(\mathrm{pk},\mathrm{sk})\leftarrow\operatorname{KeyGen}^{\mathcal{O}}(1^\lambda)\\ \mathrm{ct}\leftarrow\operatorname{Enc}^{\mathcal{O}}(\mathrm{pk},b)}}\left[\operatorname{Dec}^{\mathcal{O}}(\mathrm{sk},\mathrm{ct})\ne b\right]\right]\le\frac{4M^2}{Z}+\sqrt{\frac{L}{2N}}. E O ← R ( pk , sk ) ← KeyGen O ( 1 λ ) ct ← Enc O ( pk , b ) Pr [ Dec O ( sk , ct ) = b ] ≤ Z 4 M 2 + 2 N L . Proof. Observation 5.6 gives exact honest decryption whenever the sampled pair of rows is good. Since key generation chooses the p-key uniformly for every oracle description, the decryption error for either message bit is at most the fraction of bad pairs of rows. Apply Lemma 5.8 with h = N h=N h = N ,
taking the coordinates to be the N N N pairs of rows and W = τ W = \tau W = τ to be the interpolation parameter. Replacing a uniformly chosen pair by an independent base sample changes its probability of being bad by at most L / ( 2 N ) \sqrt{L/(2N)} L / ( 2 N ) . Under the base distribution, a union bound over the four cross-table pairs of c-text sets gives probability at most 4 M 2 / Z 4M^2/Z 4 M 2 / Z that A J ∩ B J ≠ ∅ A_J \cap B_J \ne\varnothing A J ∩ B J = ∅ . Thus the expected fraction of bad pairs under R R R , and hence the expected decryption error, is at most the stated bound.
Point-function obfuscation. At security parameter λ \lambda λ , use the oracle block at length n = 2 λ n = 2\lambda n = 2 λ . Write each p-key as j = ( j 1 , j 2 ) j = (j_1,j_2) j = ( j 1 , j 2 ) , where j 1 , j 2 ∈ { 0 , 1 } λ j_1,j_2 \in\{0,1\}^{\lambda} j 1 , j 2 ∈ { 0 , 1 } λ are its prefix and suffix, respectively. The algorithms are as follows.
Obf ( 1 λ , a ) \operatorname{Obf}(1^\lambda,a) Obf ( 1 λ , a ) : run KeyGen ( 1 2 λ ) \operatorname{KeyGen}(1^{2\lambda}) KeyGen ( 1 2 λ ) to obtain p-key j = ( j 1 , j 2 ) j = (j_1,j_2) j = ( j 1 , j 2 ) and secret key ( j , s ) (j,s) ( j , s ) , then run Enc ( j , 1 ) \operatorname{Enc}(j,1) Enc ( j , 1 ) to obtain ciphertext ( j , c ) (j,c) ( j , c ) . Output p = ( j 1 , d , s , c ) p = (j_1,d,s,c) p = ( j 1 , d , s , c ) , where d = j 2 ⊕ a d = j_2 \oplus a d = j 2 ⊕ a .
Eval ( p , x ) \operatorname{Eval}(p,x) Eval ( p , x ) : for p = ( j 1 , d , s , c ) p = (j_1,d,s,c) p = ( j 1 , d , s , c ) , set j x = ( j 1 , x ⊕ d ) j_x = (j_1,x \oplus d) j x = ( j 1 , x ⊕ d ) . Apply O d e c , 2 λ O_{\mathrm{dec},2\lambda} O dec , 2 λ at controls ( j x , s , c ) (j_x,s,c) ( j x , s , c ) to each of λ \lambda λ response qubits initialized to zero. Output one exactly when all measured responses are one. Reject malformed programs or inputs.
For x = a x = a x = a , evaluation uses the original p-key j j j . The suffix j 2 j_2 j 2 appears in p p p only through d d d .
Oracle data for p-keys with a common prefix. There are G = 2 λ G = 2^\lambda G = 2 λ possible values of j 1 j_1 j 1 and, for each j 1 j_1 j 1 , there are C = 2 λ C = 2^\lambda C = 2 λ possible values of j 2 j_2 j 2 , giving N = G C = 2 2 λ N = GC = 2^{2\lambda} N = GC = 2 2 λ p-keys. Identifying { 0 , 1 } λ \{0,1\}^{\lambda} { 0 , 1 } λ with [ 2 λ ] [2^\lambda] [ 2 λ ] , we write j 1 ∈ [ G ] j_1 \in[G] j 1 ∈ [ G ] and j 2 ∈ [ C ] j_2 \in[C] j 2 ∈ [ C ] . At this length, an s-key lies in [ Y ] [Y] [ Y ] , where Y = 2 16 λ Y = 2^{16\lambda} Y = 2 16 λ , and each c-text set contains M = 2 4 λ M = 2^{4\lambda} M = 2 4 λ elements of [ Z ] [Z] [ Z ] , where Z = 2 24 λ Z = 2^{24\lambda} Z = 2 24 λ . For each j 1 ∈ [ G ] j_1 \in[G] j 1 ∈ [ G ] , collect the C C C pairs of rows corresponding to p-keys with that prefix into the tuple
X j 1 = ( ( s ( j 1 , j 2 ) A , A ( j 1 , j 2 ) , 0 , A ( j 1 , j 2 ) , 1 ) , ( s ( j 1 , j 2 ) B , B ( j 1 , j 2 ) , 0 , B ( j 1 , j 2 ) , 1 ) ) j 2 ∈ [ C ] . X_{j_1} = \left(\left(s^{A}_{(j_1,j_2)},A_{(j_1,j_2),0},A_{(j_1,j_2),1}\right),\left(s^{B}_{(j_1,j_2)},B_{(j_1,j_2),0},B_{(j_1,j_2),1}\right)\right)_{j_2\in[C]}. X j 1 = ( ( s ( j 1 , j 2 ) A , A ( j 1 , j 2 ) , 0 , A ( j 1 , j 2 ) , 1 ) , ( s ( j 1 , j 2 ) B , B ( j 1 , j 2 ) , 0 , B ( j 1 , j 2 ) , 1 ) ) j 2 ∈ [ C ] .
For a fixed program p = ( j 1 , d , s , c ) p = (j_1,d,s,c) p = ( j 1 , d , s , c ) , varying the input x x x changes only the suffix of j x j_x j x , so every evaluation uses decryption data from X j 1 X_{j_1} X j 1 . Under P \mathcal{P} P , the tuples X 1 , … , X G X_1,\ldots,X_G X 1 , … , X G are independent and identically distributed, and independent of τ \tau τ and the other oracle blocks.
Call X j 1 X_{j_1} X j 1 good if its 2 C 2C 2 C s-key values are all distinct and A ( j 1 , j 2 ) ∩ B ( j 1 , j 2 ) = ∅ A_{(j_1,j_2)} \cap B_{(j_1,j_2)} = \varnothing A ( j 1 , j 2 ) ∩ B ( j 1 , j 2 ) = ∅ for every j 2 ∈ [ C ] j_2 \in[C] j 2 ∈ [ C ] ; otherwise call it bad. Define the fraction of bad tuples by
ρ λ = 1 G ∑ j 1 ∈ [ G ] 1 { X j 1 is bad } . \rho_\lambda= \frac{1}{G}\sum_{j_1\in[G]} 1\{X_{j_1}\text{ is bad}\}. ρ λ = G 1 j 1 ∈ [ G ] ∑ 1 { X j 1 is bad } .
Lemma 5.10 (Point-function obfuscation correctness under a relative-entropy bound). Let P n \mathcal{P}_n P n be the base distribution of oracle descriptions at length n = 2 λ n = 2\lambda n = 2 λ , and let R \mathcal{R} R be a distribution on these descriptions satisfying D ( R ∥ P n ) ≤ L D(\mathcal{R}\Vert\mathcal{P}_n) \le L D ( R ∥ P n ) ≤ L . Define
ϵ V B B ( O ) = max a ∈ { 0 , 1 } E p ← Obf O ( 1 λ , a ) max x ∈ { 0 , 1 } Pr [ Eval O ( p , x ) ≠ P a ( x ) ] . \epsilon^{VBB}(\mathcal{O}) = \max_{a\in\{0,1\}} \mathop{\mathbb{E}}_{p\leftarrow\operatorname{Obf}^{\mathcal{O}}(1^\lambda,a)}\max_{x\in\{0,1\}}\Pr[\operatorname{Eval}^{\mathcal{O}}(p,x)\ne P_a(x)]. ϵ V B B ( O ) = a ∈ { 0 , 1 } max E p ← Obf O ( 1 λ , a ) x ∈ { 0 , 1 } max Pr [ Eval O ( p , x ) = P a ( x )] . Then
E O ← R ϵ V B B ( O ) ≤ O ( C 2 Y + C M 2 Z + L G ) + 2 − λ . \mathop{\mathbb{E}}_{\mathcal{O}\leftarrow\mathcal{R}}\epsilon^{VBB}(\mathcal{O}) \le O\left(\frac{C^2}{Y}+\frac{CM^2}{Z}+\sqrt{\frac{L}{G}}\right)+2^{-\lambda}. E O ← R ϵ V B B ( O ) ≤ O ( Y C 2 + Z C M 2 + G L ) + 2 − λ . For every fixed oracle, ϵ V B B ( O ) ≤ ρ λ + 2 − λ \epsilon^{VBB}(\mathcal{O}) \le\rho_\lambda+2^{-\lambda} ϵ V B B ( O ) ≤ ρ λ + 2 − λ .
Proof. A program p = ( j 1 , d , s , c ) p=(j_1,d,s,c) p = ( j 1 , d , s , c ) with good X j 1 X_{j_1} X j 1 accepts its point a a a with certainty: at the original p-key j = ( j 1 , j 2 ) j=(j_1,j_2) j = ( j 1 , j 2 ) , Observation 5.6 makes O d e c O_{\mathrm{dec}} O dec return one on the published s-key s s s and c-text c c c , so all repetitions accept. At an input x ≠ a x \ne a x = a , the evaluator uses j x = ( j 1 , x ⊕ d ) ≠ j j_x=(j_1,x\oplus d)\ne j j x = ( j 1 , x ⊕ d ) = j . The published s-key differs from both s-keys at j x j_x j x , so β j x , s ( c ) = π / 4 \beta_{j_x,s}(c)=\pi/4 β j x , s ( c ) = π /4 and the acceptance probability is 2 − λ 2^{-\lambda} 2 − λ . This holds for every input to the program. Since O s a m p O_{\mathrm{samp}} O samp chooses j 1 j_1 j 1 uniformly for every oracle description, the maximum over points of the average program error is at most ρ λ + 2 − λ \rho_\lambda+2^{-\lambda} ρ λ + 2 − λ .
Apply Lemma 5.8 to X 1 , … , X G X_1,\ldots,X_G X 1 , … , X G , with h = G h=G h = G and W = τ W=\tau W = τ . For a uniform j 1 ∈ [ G ] j_1\in[G] j 1 ∈ [ G ] , replacing X j 1 X_{j_1} X j 1 by an independent sample from P X j 1 \mathcal{P}_{X_{j_1}} P X j 1 changes its probability of being bad by at most L / ( 2 G ) \sqrt{L}/(2G) L / ( 2 G ) .
Under P \mathcal{P} P , a union bound over s-key collisions and bad pairs of rows gives
E R ρ λ ≤ ( 2 C 2 ) Y + 4 C M 2 Z + L 2 G . \mathbb{E}_{\mathcal{R}}\rho_\lambda\le\frac{\binom{2C}{2}}{Y}+\frac{4CM^2}{Z}+\sqrt{\frac{L}{2G}}. E R ρ λ ≤ Y ( 2 2 C ) + Z 4 C M 2 + 2 G L .
Combining the two bounds completes the proof of the lemma.
The correctness requirement in Definition 7 also suffices for coherent adaptive evaluation of the same honestly generated program. For a fixed program with maximum error ϵ p \epsilon_p ϵ p , keep the input register containing x x x , compute and copy the answer, and uncompute. The resulting operation approximates the point oracle within norm 2 ϵ p 2\sqrt{\epsilon_p} 2 ϵ p . Since the input register containing x x x is retained, the same bound holds on superpositions, including inputs entangled with other registers. Jensen’s inequality and a polynomial query hybrid give negligible average error for polynomially many adaptive evaluations of one program.
Correctness averages over honestly generated programs; it need not hold for every program string.
Sections 5.3.1 and 5.3.2 prove security for these constructions under distributions with bounded relative entropy from the base law.
Security of qPKE and Point-function Obfuscation
We prove security for the constructions of § 5.5 under a general class of distributions including the distribution P \mathcal{P} P . For each primitive, we first prove security with respect to P \mathcal{P} P , and then transfer the bound to any distribution R \mathcal{R} R with bounded relative entropy from P \mathcal{P} P .
qPKE
At length n n n , the two table rows at p-key j j j from § 5.3 form the pair of rows
X j = ( ( s j A , A j , 0 , A j , 1 ) , ( s j B , B j , 0 , B j , 1 ) ) . X_j=\left((s_j^A,A_{j,0},A_{j,1}),(s_j^B,B_{j,0},B_{j,1})\right). X j = ( ( s j A , A j , 0 , A j , 1 ) , ( s j B , B j , 0 , B j , 1 ) ) .
Let W W W contain the interpolation parameter τ \tau τ and the accessible oracle data at other lengths. The reference distribution is P W ∏ j P X j \mathcal{P}_W\prod_j\mathcal{P}_{X_j} P W ∏ j P X j ; operations at other lengths may be arbitrary functions of W W W .
For an adversary A \mathcal{A} A , define
p A , b O ( j ) = Pr [ A O ( j , Enc O ( j , b ) ) = 1 ] , p^{\mathcal{O}}_{\mathcal{A},b}(j)=\Pr\left[\mathcal{A}^{\mathcal{O}}(j,\operatorname{Enc}^{\mathcal{O}}(j,b))=1\right], p A , b O ( j ) = Pr [ A O ( j , Enc O ( j , b )) = 1 ] ,
a A ( O ) = 1 N ∑ j = 1 N ( p A , 0 O ( j ) − p A , 1 O ( j ) ) . a_{\mathcal{A}}(\mathcal{O})=\frac{1}{N}\sum_{j=1}^{N}\left(p^{\mathcal{O}}_{\mathcal{A},0}(j)-p^{\mathcal{O}}_{\mathcal{A},1}(j)\right). a A ( O ) = N 1 j = 1 ∑ N ( p A , 0 O ( j ) − p A , 1 O ( j ) ) .
Here A O ( j , c t ) \mathcal{A}^{\mathcal{O}}(j,\mathrm{ct}) A O ( j , ct ) denotes the full adversarial execution, including preprocessing, with the public key j j j and ciphertext c t \mathrm{ct} ct delivered at their prescribed times. Thus a A ( O ) a_{\mathcal{A}}(\mathcal{O}) a A ( O ) is the difference between the probabilities that the adversary outputs one in the two challenge experiments.
Lemma 5.11 (qPKE with independently sampled oracle data for the challenge p-key). Fix the interpolation parameter τ \tau τ as defined in § 5.3.1 , the challenge p-key J J J , and arbitrary external data, including all oracle data outside X J X_J X J . If X J X_J X J is sampled independently according to the base distribution P P P , then every adversary making at most q q q queries, including preprocessing, satisfies
∣ E X J ← P X J [ p A , 0 O ( J ) − p A , 1 O ( J ) ] ∣ ≤ O ( q N + q Y + q M + M 2 Z ) . \left|\mathop{\mathbb{E}}_{X_J \leftarrow P_{X_J}}\left[p^{\mathcal{O}}_{A,0}(J)-p^{\mathcal{O}}_{A,1}(J)\right]\right| \le O\left(\frac{q}{\sqrt{N}}+\frac{q}{\sqrt{Y}}+\frac{q}{\sqrt{M}}+\frac{M^2}{Z}\right). E X J ← P X J [ p A , 0 O ( J ) − p A , 1 O ( J ) ] ≤ O ( N q + Y q + M q + Z M 2 ) .
Proof. For each b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } , define hybrids H b ( 0 ) , … , H b ( 4 ) H_b^{(0)},\ldots,H_b^{(4)} H b ( 0 ) , … , H b ( 4 ) , each outputting the adversary’s bit, and write π b ( k ) = Pr [ H b ( k ) = 1 ] \pi_b^{(k)}=\Pr[H_b^{(k)}=1] π b ( k ) = Pr [ H b ( k ) = 1 ] . These probabilities average over X J X_J X J and the experiment’s randomness; J J J and the external data remain fixed. All oracle changes apply throughout the execution, including preprocessing.
Hybrid H b ( 0 ) H_b^{(0)} H b ( 0 ) : the real experiment. Sample X J ← P X J X_J \leftarrow P_{X_J} X J ← P X J and give the adversary public key J J J and a ciphertext encrypting b b b . Thus π b ( 0 ) = E X J p A , b O ( J ) \pi_b^{(0)}=\mathbb{E}_{X_J}p^{\mathcal{O}}_{A,b}(J) π b ( 0 ) = E X J p A , b O ( J ) .
Hybrid H b ( 1 ) H_b^{(1)} H b ( 1 ) : remove J J J from O s a m p O_{\mathrm{samp}} O samp . Modify H b ( 0 ) H_b^{(0)} H b ( 0 ) so that every adversarial O s a m p O_{\mathrm{samp}} O samp query uses the state obtained by removing N − 1 / 2 ∣ J ⟩ ∣ ψ J ⟩ N^{-1/2}|J\rangle|\psi_J\rangle N − 1/2 ∣ J ⟩ ∣ ψ J ⟩ from ∣ Ψ ⟩ |\Psi\rangle ∣Ψ ⟩ and normalizing the remainder. The removed squared norm is 1 / N 1/N 1/ N , so the state and its reflection change by O ( N − 1 / 2 ) O(N^{-1/2}) O ( N − 1/2 ) . Comparing the queries one at a time gives ∣ π b ( 1 ) − π b ( 0 ) ∣ ≤ O ( q / N ) |\pi_b^{(1)}-\pi_b^{(0)}|\le O(q/\sqrt{N}) ∣ π b ( 1 ) − π b ( 0 ) ∣ ≤ O ( q / N ) .
Hybrid H b ( 2 ) H_b^{(2)} H b ( 2 ) : use default O d e c O_{\mathrm{dec}} O dec responses at J J J . Modify H b ( 1 ) H_b^{(1)} H b ( 1 ) by setting every angle β J , y ( c ) \beta_{J,y}(c) β J , y ( c ) to π / 4 \pi/4 π /4 . Only controls with y ∈ { s J A , s J B } y\in\{s^A_J,s^B_J\} y ∈ { s J A , s J B } change. The query states in H b ( 2 ) H_b^{(2)} H b ( 2 ) are independent of these two uniform s-keys, so their expected squared weight on the changed controls is at most 2 / Y 2/Y 2/ Y . Comparing queries using these states and applying Cauchy–Schwarz gives ∣ π b ( 2 ) − π b ( 1 ) ∣ ≤ O ( q / Y ) |\pi_b^{(2)}-\pi_b^{(1)}|\le O(q/\sqrt{Y}) ∣ π b ( 2 ) − π b ( 1 ) ∣ ≤ O ( q / Y ) . O s a m p O_{\mathrm{samp}} O samp and O d e c O_{\mathrm{dec}} O dec now use no data from X J X_J X J .
Hybrid H b ( 3 ) H_b^{(3)} H b ( 3 ) : condition on disjoint c-text sets. Run H b ( 2 ) H_b^{(2)} H b ( 2 ) conditioned on the four sets A J , 0 , A J , 1 , B J , 0 , B J , 1 A_{J,0},A_{J,1},B_{J,0},B_{J,1} A J , 0 , A J , 1 , B J , 0 , B J , 1 being pairwise disjoint. This event fails with probability at most 4 M 2 / Z 4M^2/Z 4 M 2 / Z , giving ∣ π b ( 3 ) − π b ( 2 ) ∣ ≤ 4 M 2 / Z |\pi_b^{(3)}-\pi_b^{(2)}|\le4M^2/Z ∣ π b ( 3 ) − π b ( 2 ) ∣ ≤ 4 M 2 / Z . The sets are now uniform ordered disjoint M M M -subsets of [ Z ] [Z] [ Z ] . For 1 / 3 ≤ τ ≤ 2 / 3 1/3\le\tau\le2/3 1/3 ≤ τ ≤ 2/3 , measuring ∣ ϕ J , b ( τ ) ⟩ |\phi_{J,b}(\tau)\rangle ∣ ϕ J , b ( τ )⟩ chooses table A A A or B B B with probabilities cos 2 ( π ( 3 τ − 1 ) / 2 ) \cos^2(\pi(3\tau-1)/2) cos 2 ( π ( 3 τ − 1 ) /2 ) and sin 2 ( π ( 3 τ − 1 ) / 2 ) \sin^2(\pi(3\tau-1)/2) sin 2 ( π ( 3 τ − 1 ) /2 ) , followed by a uniform c-text from A J , b A_{J,b} A J , b or B J , b B_{J,b} B J , b . For τ ≤ 1 / 3 \tau\le1/3 τ ≤ 1/3 , only A A A is used; for τ ≥ 2 / 3 \tau\ge2/3 τ ≥ 2/3 , only B B B is used. The table choice is independent of b b b .
An equivalent way to sample H b ( 3 ) H_b^{(3)} H b ( 3 ) is to choose a uniform c-text C ∈ [ Z ] C\in[Z] C ∈ [ Z ] and four uniform disjoint helper sets of size M M M in [ Z ] ∖ { C } [Z]\setminus\{C\} [ Z ] ∖ { C } . In the set selected by the table choice and message b b b , replace a uniform c-text D D D by C C C , and use ( J , C ) (J,C) ( J , C ) as the challenge ciphertext. For each resulting tuple and selected C C C , the removed c-text D D D can be any of the Z − 4 M Z-4M Z − 4 M c-texts outside the four resulting sets, with equal probability. Hence this sampling description leaves the distribution unchanged.
Hybrid H b ( 4 ) H_b^{(4)} H b ( 4 ) : keep the helper sets unchanged. Use the preceding sampling description, but omit the replacement of D D D by C C C ; the challenge ciphertext is still ( J , C ) (J,C) ( J , C ) . The selected c-text state ∣ ϕ J , b A ⟩ |\phi^A_{J,b}\rangle ∣ ϕ J , b A ⟩ or ∣ ϕ J , b B ⟩ |\phi^B_{J,b}\rangle ∣ ϕ J , b B ⟩ changes by 2 / M \sqrt{2/M} 2/ M . For 1 / 3 ≤ τ ≤ 2 / 3 1/3\le\tau\le2/3 1/3 ≤ τ ≤ 2/3 , the normalization denominator is one because the sets remain disjoint, so the same bound holds for ∣ ϕ J , b ( τ ) ⟩ |\phi_{J,b}(\tau)\rangle ∣ ϕ J , b ( τ )⟩ . The O e n c O_{\mathrm{enc}} O enc reflections change by O ( M − 1 / 2 ) O(M^{-1/2}) O ( M − 1/2 ) , giving ∣ π b ( 4 ) − π b ( 3 ) ∣ ≤ O ( q / M ) |\pi_b^{(4)}-\pi_b^{(3)}|\le O(q/\sqrt{M}) ∣ π b ( 4 ) − π b ( 3 ) ∣ ≤ O ( q / M ) .
The distribution of H b ( 4 ) H_b^{(4)} H b ( 4 ) is independent of b b b : the challenge is ( J , C ) (J,C) ( J , C ) , the helper sets were sampled independently of b b b , and O s a m p O_{\mathrm{samp}} O samp and O d e c O_{\mathrm{dec}} O dec do not use X J X_J X J . Thus π 0 ( 4 ) = π 1 ( 4 ) \pi_0^{(4)}=\pi_1^{(4)} π 0 ( 4 ) = π 1 ( 4 ) , and the triangle inequality gives
∣ π 0 ( 0 ) − π 1 ( 0 ) ∣ ≤ ∑ b ∈ { 0 , 1 } ∑ k = 1 4 ∣ π b ( k ) − π b ( k − 1 ) ∣ ≤ O ( q N + q Y + q M + M 2 Z ) . \begin{aligned}
\left|\pi_0^{(0)}-\pi_1^{(0)}\right|
\le\sum_{b\in\{0,1\}}\sum_{k=1}^{4}\left|\pi_b^{(k)}-\pi_b^{(k-1)}\right| \\
&\le O\left(\frac{q}{\sqrt{N}}+\frac{q}{\sqrt{Y}}+\frac{q}{\sqrt{M}}+\frac{M^2}{Z}\right).
\end{aligned} π 0 ( 0 ) − π 1 ( 0 ) ≤ b ∈ { 0 , 1 } ∑ k = 1 ∑ 4 π b ( k ) − π b ( k − 1 ) ≤ O ( N q + Y q + M q + Z M 2 ) .
This is the claimed bound.
Lemma 5.12 (qPKE under a relative-entropy bound). Suppose R \mathcal{R} R has relative entropy at most L L L from P W ∏ j P X j \mathcal{P}_W\prod_j P_{X_j} P W ∏ j P X j , and let q ≥ 1 q \ge1 q ≥ 1 bound the adversary’s queries and honest preparation calls. For every integer 1 ≤ h ≤ N 1 \le h \le N 1 ≤ h ≤ N ,
∣ E O ← R a A ( O ) ∣ ≤ O ( q h N + L h + M 2 Z ) . (5) \left|\mathbb{E}_{\mathcal{O}\leftarrow\mathcal{R}} a_A(\mathcal{O})\right|
\le O\left(q\sqrt{\frac{h}{N}}+\sqrt{\frac{L}{h}}+\frac{M^2}{Z}\right). \tag*{(5)} ∣ E O ← R a A ( O ) ∣ ≤ O ( q N h + h L + Z M 2 ) . (5) Moreover, the same bound with L + ln 2 L+\ln2 L + ln 2 in place of L L L , holds for E O ← R ∣ a A ( O ) ∣ \mathbb{E}_{\mathcal{O}\leftarrow\mathcal{R}}|a_A(\mathcal{O})| E O ← R ∣ a A ( O ) ∣ .
Proof. For each b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } , define hybrids H b ( 0 ) , H b ( 1 ) , H b ( 2 ) \mathrm{H}_b^{(0)},\mathrm{H}_b^{(1)},\mathrm{H}_b^{(2)} H b ( 0 ) , H b ( 1 ) , H b ( 2 ) , each outputting the adversary’s bit. Write π b ( k ) = Pr [ H b ( k ) = 1 ] \pi_b^{(k)}=\Pr[\mathrm{H}_b^{(k)}=1] π b ( k ) = Pr [ H b ( k ) = 1 ] . All replacements below apply throughout the execution, including preprocessing.
Hybrid H b ( 0 ) \mathrm{H}_b^{(0)} H b ( 0 ) : the real experiment under R \mathcal{R} R . Draw the oracle description from R \mathcal{R} R and choose J J J uniformly, independently of it. Privately choose a uniform h h h -subset H ⊆ [ N ] H\subseteq[N] H ⊆ [ N ] containing J J J . Give the adversary the public key J J J and an encryption of b b b . This is the real experiment: O s a m p O_{\mathrm{samp}} O samp gives every p-key probability 1 / N 1/N 1/ N , the secret key is not otherwise used, and H H H has no effect. In particular, π 0 ( 0 ) − π 1 ( 0 ) = E R a A ( O ) \pi_0^{(0)}-\pi_1^{(0)}=\mathbb{E}_{\mathcal{R}}a_A(\mathcal{O}) π 0 ( 0 ) − π 1 ( 0 ) = E R a A ( O ) . Comparing messages 0 and 1 suffices, since equal messages give no difference and reversing them can be absorbed into the adversary’s output rule.
Hybrid H b ( 1 ) \mathrm{H}_b^{(1)} H b ( 1 ) : replace the other pairs of rows in H H H . Next, we want to use the guarantees of Lemma 5.8 to move to a hybrid where we replace the variables for the challenge p-key J J J with independently sampled variables from P \mathcal{P} P in order to invoke Lemma 5.11. However, note that Lemma 5.8 only ensures negligible statistical distance for records in the absence of the variables X H ∖ { J } = ( X j ) j ∈ H ∖ { J } X_{H\setminus\{J\}}=(X_j)_{j\in H\setminus\{J\}} X H ∖ { J } = ( X j ) j ∈ H ∖ { J } . Thus, we first need to replace the variables with independent samples, which is what we do next. Specifically, we sample them independently from the base distribution P \mathcal{P} P .
In particular, modify H b ( 0 ) \mathrm{H}_b^{(0)} H b ( 0 ) by replacing X j X_j X j , for j ∈ H ∖ { J } j\in H\setminus\{J\} j ∈ H ∖ { J } , by independent samples according to the base distribution P \mathcal{P} P . The variable H H H remains hidden from the adversaries. Each p-key contributes squared mass 1 / N 1/N 1/ N to ∣ Ψ ⟩ |\Psi\rangle ∣Ψ ⟩ , so its state and O s a m p O_{\mathrm{samp}} O samp reflection change by O ( h / N ) O(\sqrt{h/N}) O ( h / N ) . O e n c O_{\mathrm{enc}} O enc and O d e c O_{\mathrm{dec}} O dec change only at p-keys in H ∖ { J } H\setminus\{J\} H ∖ { J } . Conditional on J J J , the original query states are independent of H H H , and their expected squared weight on these p-keys is at most ( h − 1 ) / ( N − 1 ) (h-1)/(N-1) ( h − 1 ) / ( N − 1 ) . Comparing queries using these states gives ∣ π b ( 1 ) − π b ( 0 ) ∣ ≤ O ( q h / N ) |\pi_b^{(1)}-\pi_b^{(0)}|\le O(q\sqrt{h/N}) ∣ π b ( 1 ) − π b ( 0 ) ∣ ≤ O ( q h / N ) , including superpositions over operation names and lengths. For h = 1 h=1 h = 1 , no pair of rows changes and the cost is zero.
Hybrid H b ( 2 ) \mathrm{H}_b^{(2)} H b ( 2 ) : replace the challenge pair of rows. Modify H b ( 1 ) \mathrm{H}_b^{(1)} H b ( 1 ) by replacing X J X_J X J with an independent base sample. Both the oracle and the challenge ciphertext use this new pair of rows. To compare the hybrids, condition on W W W , the outside pairs of rows X − H X_{-H} X − H , and the independent replacement data. The original pairs of rows in H ∖ { J } H\setminus\{J\} H ∖ { J } no longer occur in H b ( 1 ) \mathrm{H}_b^{(1)} H b ( 1 ) . Equivalently, H H H was sampled uniformly first and J J J uniformly within H H H . Lemma 5.8 bounds the change in their joint distribution, averaged over the conditioning data, and gives
∣ π b ( 2 ) − π b ( 1 ) ∣ ≤ L 2 h . \left|\pi_b^{(2)}-\pi_b^{(1)}\right|\le\sqrt{\frac{L}{2h}}. π b ( 2 ) − π b ( 1 ) ≤ 2 h L .
The conditioning is used only for this comparison, after the preceding query bound; the conditioned data are not given to the adversary.
In H b ( 2 ) H_b^{(2)} H b ( 2 ) , the challenge pair of rows is independent of all remaining data. Lemma 5.11 therefore gives
∣ π 0 ( 2 ) − π 1 ( 2 ) ∣ ≤ O ( q N + q Y + q M + M 2 Z ) . \left|\pi_0^{(2)}-\pi_1^{(2)}\right|\le O\left(\frac{q}{\sqrt{N}}+\frac{q}{\sqrt{Y}}+\frac{q}{\sqrt{M}}+\frac{M^2}{Z}\right). π 0 ( 2 ) − π 1 ( 2 ) ≤ O ( N q + Y q + M q + Z M 2 ) .
Consequently,
∣ π 0 ( 0 ) − π 1 ( 0 ) ∣ ≤ ∑ b ∈ { 0 , 1 } ∑ k = 1 2 ∣ π b ( k ) − π b ( k − 1 ) ∣ + ∣ π 0 ( 2 ) − π 1 ( 2 ) ∣ . \left|\pi_0^{(0)}-\pi_1^{(0)}\right|\le\sum_{b\in\{0,1\}}\sum_{k=1}^{2}\left|\pi_b^{(k)}-\pi_b^{(k-1)}\right|+\left|\pi_0^{(2)}-\pi_1^{(2)}\right|. π 0 ( 0 ) − π 1 ( 0 ) ≤ b ∈ { 0 , 1 } ∑ k = 1 ∑ 2 π b ( k ) − π b ( k − 1 ) + π 0 ( 2 ) − π 1 ( 2 ) .
Substituting the bounds and using Y , M ≥ N Y,M\ge N Y , M ≥ N proves (5.5).
Expected absolute difference. Append σ = 1 [ a A ( O ) < 0 ] \sigma=1[a_{\mathcal{A}}(O)<0] σ = 1 [ a A ( O ) < 0 ] to W W W , using an independent uniform bit in the reference distribution. This increases the relative entropy by at most ln 2 \ln2 ln 2 . Give σ \sigma σ to an adversary A ′ \mathcal{A}' A ′ that runs A \mathcal{A} A and flips its output when σ = 1 \sigma=1 σ = 1 . Then
a A ′ ( O ) = ( − 1 ) σ a A ( O ) = ∣ a A ( O ) ∣ . a_{\mathcal{A}'}(O)=(-1)^\sigma a_{\mathcal{A}}(O)=\left|a_{\mathcal{A}}(O)\right|. a A ′ ( O ) = ( − 1 ) σ a A ( O ) = ∣ a A ( O ) ∣ .
The bit σ \sigma σ need not be computable; it is used only for this comparison. The hidden subset remains independent of the original query states, and in H b ( 2 ) H_b^{(2)} H b ( 2 ) the X J X_J X J is independent of σ \sigma σ as well. Applying the same hybrids with budget L + ln 2 L+\ln2 L + ln 2 bounds E R ∣ a A ( O ) ∣ \mathbb{E}_{R}\left|a_{\mathcal{A}}(O)\right| E R ∣ a A ( O ) ∣ .
Point-function Obfuscation
We use X j 1 , G , C , N X_{j_1},G,C,N X j 1 , G , C , N from Section 5.2.3. Let W W W contain the interpolation parameter τ \tau τ and the accessible oracle data at other lengths. The base distribution is P W ∏ k ∈ [ G ] P X k \mathcal{P}_W\prod_{k\in[G]}\mathcal{P}_{X_k} P W ∏ k ∈ [ G ] P X k .
The simulator. For an adversary A \mathcal{A} A , the simulator S \mathcal{S} S has quantum access to the common oracle O O O and the point oracle O a O_a O a . It uses O s a m p , 2 λ O_{\mathrm{samp},2\lambda} O samp , 2 λ to sample a key ( j 1 , j 2 ′ , s ) (j_1,j'_2,s) ( j 1 , j 2 ′ , s ) , then uses O e n c , 2 λ O_{\mathrm{enc},2\lambda} O enc , 2 λ to sample a c-text c c c encrypting one at p-key ( j 1 , j 2 ′ ) (j_1,j'_2) ( j 1 , j 2 ′ ) . It independently chooses uniform d ∈ { 0 , 1 } λ d\in\{0,1\}^{\lambda} d ∈ { 0 , 1 } λ and sets p = ( j 1 , d , s , c ) p=(j_1,d,s,c) p = ( j 1 , d , s , c ) . It then runs A \mathcal{A} A internally, provides p p p as the input program to the adversary, and answers its oracle queries as follows. All queries are forwarded unchanged to the corresponding operation of O O O , except encryption and decryption queries at length 2 λ 2\lambda 2 λ whose p-key prefix is j 1 j_1 j 1 , which are handled as follows. These rules are applied coherently to each basis component of a query.
O e n c O_{\mathrm{enc}} O enc queries at 2 λ 2\lambda 2 λ . For an O e n c , 2 λ O_{\mathrm{enc},2\lambda} O enc , 2 λ query with p-key ( j 1 , u ) (j_1,u) ( j 1 , u ) and message bit b b b , the simulator uses O a O_a O a to test whether u ⊕ d = a u\mathbin{\oplus}d=a u ⊕ d = a . In particular, it coherently computes u ⊕ d u\mathbin{\oplus}d u ⊕ d and runs it through O a O_a O a coherently. Conditioned on accept, it applies O e n c O_{\mathrm{enc}} O enc at p-key ( j 1 , j 2 ′ ) (j_1,j'_2) ( j 1 , j 2 ′ ) and the same bit b b b , and if the test rejects, it applies the original operation at ( j 1 , u ) (j_1,u) ( j 1 , u ) , coherently.
O d e c O_{\mathrm{dec}} O dec queries at 2 λ 2\lambda 2 λ . For an O d e c , 2 λ O_{\mathrm{dec},2\lambda} O dec , 2 λ query with p-key ( j 1 , u ) (j_1,u) ( j 1 , u ) , s-key y y y , and c-text c ′ c' c ′ , the simulator performs the same test with O a O_a O a to check if u ⊕ d = a u\mathbin{\oplus}d=a u ⊕ d = a . If it accepts, it applies the decryption response operation of O O O at ( j 1 , j 2 ′ , y , c ′ ) (j_1,j'_2,y,c') ( j 1 , j 2 ′ , y , c ′ ) . If it rejects, it applies the original operation at ( j 1 , u , y , c ′ ) (j_1,u,y,c') ( j 1 , u , y , c ′ ) .
Remark 5.13 (Universality of the simulator). The simulator is a uniform procedure that, given the code of A \mathcal{A} A and an explicit polynomial running-time bound, runs A \mathcal{A} A with polynomial overhead and returns its output bit. For each fixed uniform QPT adversary, this gives a uniform QPT simulator as required by Definition 7.
The proof template for the simulation security is the same as that in the case of qPKE in § 5.6.1 . We start with showing simulation security (as in Definition 7) when the p-key prefix corresponding to the challenge obfuscation has independently sampled oracle data, see Lemma 5.14 . Next, as done for qPKE in Lemma 5.12 , we reduce the security game in the bounded relative-entropy distribution case to the independently sampled oracle data case, that establishes security in the bounded relative-entropy case, see Lemma 5.15 . We note that the proof of Lemma 5.15 is very similar to that Lemma 5.12 with the main difference that instead of working over N N N p-keys, we need to work with G G G p-key prefixes, which results in similar bounds as in Lemma 5.12 but with N N N replaced with G G G .
For a fixed oracle O \mathcal{O} O and point a a a , let p A , a O ( j 1 ) p^{\mathcal{O}}_{A,a}(j_1) p A , a O ( j 1 ) and p S , a O ( j 1 ) p^{\mathcal{O}}_{S,a}(j_1) p S , a O ( j 1 ) be the probabilities that the real and simulated experiments output one, respectively, conditioned on the prefix of the sampled p-key being j 1 j_1 j 1 . This prefix is uniform in [ G ] [G] [ G ] in both experiments. Thus, their overall difference is
d a ( O ) = Pr [ A O ( Obf O ( 1 λ , a ) ) = 1 ] − Pr [ S O , O a ( 1 λ ) = 1 ] = 1 G ∑ j 1 ∈ [ G ] ( p A , a O ( j 1 ) − p S , a O ( j 1 ) ) . d_a(\mathcal{O}) = \Pr[\mathcal{A}^{\mathcal{O}}(\operatorname{Obf}^{\mathcal{O}}(1^\lambda,a)) = 1] - \Pr[\mathcal{S}^{\mathcal{O},O_a}(1^\lambda) = 1]
= \frac{1}{G}\sum_{j_1\in[G]}\left(p^{\mathcal{O}}_{A,a}(j_1)-p^{\mathcal{O}}_{S,a}(j_1)\right). d a ( O ) = Pr [ A O ( Obf O ( 1 λ , a )) = 1 ] − Pr [ S O , O a ( 1 λ ) = 1 ] = G 1 j 1 ∈ [ G ] ∑ ( p A , a O ( j 1 ) − p S , a O ( j 1 ) ) .
Lemma 5.14 (Point-function obfuscation with independently sampled oracle data for the challenge p-key prefix). Fix the interpolation parameter τ \tau τ , a value j 1 ∈ [ G ] j_1 \in[G] j 1 ∈ [ G ] for the prefix of the p-key, a point a ∈ { 0 , 1 } λ a \in\{0,1\}^{\lambda} a ∈ { 0 , 1 } λ , and arbitrary external data, including all oracle data outside X j 1 X_{j_1} X j 1 . If X j 1 X_{j_1} X j 1 is sampled independently from P X j 1 P_{X_{j_1}} P X j 1 , then every adversary satisfies
∣ E X j 1 ← P X j 1 [ p A , a O ( j 1 ) − p S , a O ( j 1 ) ] ∣ ≤ O ( q C + q N ) . \left|\mathop{\mathbb{E}}_{X_{j_1}\leftarrow P_{X_{j_1}}}\left[p^{\mathcal{O}}_{A,a}(j_1)-p^{\mathcal{O}}_{S,a}(j_1)\right]\right|
\le O\left(\frac{q}{\sqrt{C}}+\frac{q}{\sqrt{N}}\right). E X j 1 ← P X j 1 [ p A , a O ( j 1 ) − p S , a O ( j 1 ) ] ≤ O ( C q + N q ) . where q q q bounds all oracle calls in the real and simulated experiments, including preparation and preprocessing.
Proof. The proof template is similar to that of the proof of Lemma 5.11 . The proof begins as in the proof of Lemma 5.11 by modifying the sampling oracle. However, in this case, the obfuscated program reveals the s-key, so the same argument for replacing decryption by default responses does not apply. Instead, we modify encryption and decryption at a p-key with the same prefix and an independently sampled suffix. Exchanging the corresponding pairs of rows then lets us identify the final hybrid with the simulated experiment.
Fix d ∈ { 0 , 1 } λ d \in\{0,1\}^{\lambda} d ∈ { 0 , 1 } λ , put J = ( j 1 , a ⊕ d ) J=(j_1,a\oplus d) J = ( j 1 , a ⊕ d ) , and write T = ( A , B ) \mathcal{T}=(A,B) T = ( A , B ) for the tables at length 2 λ 2\lambda 2 λ . Using (2) , write
U e n c T ( k , b ) = H ϕ k , b T , U d e c T ( k , y , z ) = Q ( β k , y T ( z ) ) . U^{\mathcal{T}}_{\mathrm{enc}}(k,b)=H_{\phi^{\mathcal{T}}_{k,b}},\qquad
U^{\mathcal{T}}_{\mathrm{dec}}(k,y,z)=Q(\beta^{\mathcal{T}}_{k,y}(z)). U enc T ( k , b ) = H ϕ k , b T , U dec T ( k , y , z ) = Q ( β k , y T ( z )) .
Define hybrids H ( 0 ) , … , H ( 3 ) H^{(0)},\ldots,H^{(3)} H ( 0 ) , … , H ( 3 ) , and write π ( r ) = Pr [ H ( r ) = 1 ] \pi^{(r)}=\Pr[H^{(r)}=1] π ( r ) = Pr [ H ( r ) = 1 ] . Each hybrid changes only the specified operations. All replacements affect the adversary’s queries throughout its execution, including preprocessing, at length 2 λ 2\lambda 2 λ .
Hybrid H ( 0 ) H^{(0)} H ( 0 ) : the real experiment. Sample X j 1 ← P X j 1 X_{j_1}\leftarrow P_{X_{j_1}} X j 1 ← P X j 1 , independently choose uniform j 2 ′ ∈ [ C ] j'_2\in[C] j 2 ′ ∈ [ C ] , and put J ′ = ( j 1 , j 2 ′ ) J'=(j_1,j'_2) J ′ = ( j 1 , j 2 ′ ) . Measure ∣ ψ J ⟩ |\psi_J\rangle ∣ ψ J ⟩ and ∣ ϕ J ′ ⟩ |\phi_{J'}\rangle ∣ ϕ J ′ ⟩ separately to obtain s , c s,c s , c . Give p = ( j 1 , d , s , c ) p=(j_1,d,s,c) p = ( j 1 , d , s , c ) to A \mathcal{A} A with the oracle determined by T \mathcal{T} T .
Hybrid H ( 1 ) H^{(1)} H ( 1 ) : remove prefix j 1 j_1 j 1 from the sampling operation. Replace O s a m p , 2 λ O_{\mathrm{samp},2\lambda} O samp , 2 λ by H Ψ J ′ ‾ j 1 H_{\Psi_{\overline{J'}_{j_1}}} H Ψ J ′ j 1 , where
∣ Ψ J ′ ‾ j 1 ⟩ = 1 N − C ∑ k = ( k 1 , k 2 ) ∈ [ N ] k 1 ≠ j 1 ∣ k ⟩ ∣ ψ T ⟩ . \left|\Psi_{\overline{J'}_{j_1}}\right\rangle
=\frac{1}{\sqrt{N-C}}\sum_{\substack{k=(k_1,k_2)\in[N]\\k_1\ne j_1}}|k\rangle|\psi_{T}\rangle. Ψ J ′ j 1 ⟩ = N − C 1 k = ( k 1 , k 2 ) ∈ [ N ] k 1 = j 1 ∑ ∣ k ⟩ ∣ ψ T ⟩ .
Measuring ∣ Ψ T ⟩ |\Psi_T\rangle ∣ Ψ T ⟩ gives prefix j 1 j_1 j 1 with probability C / N = 1 / G C/N=1/G C / N = 1/ G , giving ∣ π ( 1 ) − π ( 0 ) ∣ ≤ O ( q / G ) |\pi^{(1)}-\pi^{(0)}|\le O(q/\sqrt{G}) ∣ π ( 1 ) − π ( 0 ) ∣ ≤ O ( q / G ) . Hybrid H ( 2 ) H^{(2)} H ( 2 ) : change encryption and decryption at J J J . For each p-key k k k , replace U ~ e n c T ( k , b ) \widetilde{U}^{T}_{\mathrm{enc}}(k,b) U enc T ( k , b ) and U ~ d e c T ( k , y , z ) \widetilde{U}^{T}_{\mathrm{dec}}(k,y,z) U dec T ( k , y , z ) by
U ~ e n c ( k , b ) = { U e n c T ( J , b ) , k = J ′ , U e n c T ( k , b ) , k ≠ J ′ , \widetilde{U}_{\mathrm{enc}}(k,b)=
\begin{cases}
U^{T}_{\mathrm{enc}}(J,b), & k=J',\\
U^{T}_{\mathrm{enc}}(k,b), & k\ne J',
\end{cases} U enc ( k , b ) = { U enc T ( J , b ) , U enc T ( k , b ) , k = J ′ , k = J ′ ,
U ~ d e c ( k , y , z ) = { U d e c T ( J , y , z ) , k = J ′ , U d e c T ( k , y , z ) , k ≠ J ′ . \widetilde{U}_{\mathrm{dec}}(k,y,z)=
\begin{cases}
U^{T}_{\mathrm{dec}}(J,y,z), & k=J',\\
U^{T}_{\mathrm{dec}}(k,y,z), & k\ne J'.
\end{cases} U dec ( k , y , z ) = { U dec T ( J , y , z ) , U dec T ( k , y , z ) , k = J ′ , k = J ′ .
The queries in H ( 1 ) H^{(1)} H ( 1 ) are independent of j 2 ′ j'_2 j 2 ′ , so measuring a query’s p-key would give J ′ J' J ′ with probability at most 1 / C 1/C 1/ C , averaged over j 2 ′ j'_2 j 2 ′ . Thus ∣ π ( 2 ) − π ( 1 ) ∣ ≤ O ( q / C ) |\pi^{(2)}-\pi^{(1)}|\le O(q/\sqrt{C}) ∣ π ( 2 ) − π ( 1 ) ∣ ≤ O ( q / C ) .
Hybrid H ( 3 ) H^{(3)} H ( 3 ) : restore sampling with the exchanged pairs of rows. Set T ′ = Swap J , J ′ ( T ) T'=\operatorname{Swap}_{J,J'}(T) T ′ = Swap J , J ′ ( T ) , exchanging the pairs of rows at J , J ′ J,J' J , J ′ in both tables, and replace the sampling operation by H Ψ T ′ H_{\Psi_{T'}} H Ψ T ′ . Since ∣ Ψ − j 1 ′ T ⟩ = ∣ Ψ − j 1 T ′ ⟩ |\Psi^{T}_{-j'_1}\rangle=|\Psi^{T'}_{-j_1}\rangle ∣ Ψ − j 1 ′ T ⟩ = ∣ Ψ − j 1 T ′ ⟩ , the same bound as in H ( 1 ) H^{(1)} H ( 1 ) gives ∣ π ( 3 ) − π ( 2 ) ∣ ≤ O ( q / G ) |\pi^{(3)}-\pi^{(2)}|\le O(q/\sqrt{G}) ∣ π ( 3 ) − π ( 2 ) ∣ ≤ O ( q / G ) .
We have ∣ ψ J T ⟩ = ∣ ψ J ′ T ⟩ |\psi^{T}_{J}\rangle=|\psi^{T}_{J'}\rangle ∣ ψ J T ⟩ = ∣ ψ J ′ T ⟩ and ∣ ϕ J , 1 T ⟩ = ∣ ϕ J ′ , 1 T ⟩ |\phi^{T}_{J,1}\rangle=|\phi^{T}_{J',1}\rangle ∣ ϕ J , 1 T ⟩ = ∣ ϕ J ′ , 1 T ⟩ . For either encryption or decryption, omitting b b b or ( y , z ) (y,z) ( y , z ) from the notation,
U ~ ( k ) = { U T ′ ( J ′ ) , k = J , U T ′ ( k ) , k ≠ J . \widetilde{U}(k)=
\begin{cases}
U^{T'}(J'), & k=J,\\
U^{T'}(k), & k\ne J.
\end{cases} U ( k ) = { U T ′ ( J ′ ) , U T ′ ( k ) , k = J , k = J .
Thus H ( 3 ) ( T ; d , j 2 ′ ) ≡ Sim ( T ′ ; d , j 2 ′ ) H^{(3)}(T;d,j'_2)\equiv\operatorname{Sim}(T';d,j'_2) H ( 3 ) ( T ; d , j 2 ′ ) ≡ Sim ( T ′ ; d , j 2 ′ ) . For every fixed d , j 2 ′ d,j'_2 d , j 2 ′ , the tuple X j 1 ′ ′ X'_{j'_1} X j 1 ′ ′ has distribution P X j 1 P_{X_{j_1}} P X j 1 , since its pairs of rows are independent and identically distributed. Hence H ( 3 ) H^{(3)} H ( 3 ) has the simulated distribution.
The real experiment has uniform d d d . Averaging over d d d , applying the triangle inequality, and using G = C G=C G = C gives
∣ E X j 1 ← P X j 1 [ p A , a O ( j 1 ) − p S , a O ( j 1 ) ] ∣ ≤ O ( q G + q C ) = O ( q C ) , \left|\mathop{\mathbb{E}}_{X_{j_1}\leftarrow P_{X_{j_1}}}\left[p^{O}_{A,a}(j_1)-p^{O}_{S,a}(j_1)\right]\right|
\le O\left(\frac{q}{\sqrt{G}}+\frac{q}{\sqrt{C}}\right)
=O\left(\frac{q}{\sqrt{C}}\right), E X j 1 ← P X j 1 [ p A , a O ( j 1 ) − p S , a O ( j 1 ) ] ≤ O ( G q + C q ) = O ( C q ) ,
which implies the stated bound.
Lemma 5.15 (Point-function obfuscation under a relative-entropy bound). Suppose R \mathcal{R} R has relative entropy at most L L L from P W ∏ k ∈ [ G ] P X k P_{\mathcal{W}_{\prod k\in[G]}P_{X_k}} P W ∏ k ∈ [ G ] P X k . For every uniform QPT adversary A \mathcal{A} A , let q ≥ 1 q\ge1 q ≥ 1 bound all oracle calls in the real and simulated experiments, including preparation and preprocessing. Then, for every point a ∈ { 0 , 1 } λ a\in\{0,1\}^{\lambda} a ∈ { 0 , 1 } λ and every integer 1 ≤ h ≤ G 1\le h\le G 1 ≤ h ≤ G ,
∣ E O ← R d a ( O ) ∣ ≤ O ( q h G + L h ) . \left|\mathop{\mathbb{E}}_{O\leftarrow\mathcal{R}}d_a(O)\right|
\le O\left(q\sqrt{\frac{h}{G}}+\sqrt{\frac{L}{h}}\right). ∣ E O ← R d a ( O ) ∣ ≤ O ( q G h + h L ) . Moreover, the same bound with L + ( λ + 1 ) ln 2 L+(\lambda+1)\ln2 L + ( λ + 1 ) ln 2 in place of L L L holds for E O ← R max a ∈ { 0 , 1 } λ ∣ d a ( O ) ∣ \mathop{\mathbb{E}}_{O\leftarrow\mathcal{R}}\max_{a\in\{0,1\}^{\lambda}}|d_a(O)| E O ← R max a ∈ { 0 , 1 } λ ∣ d a ( O ) ∣ .
Proof. The proof is the same as that for Lemma 5.12 , but adapted to the setting of the point function construction. Fix a point a a a . For each E ∈ { A , S } E\in\{\mathcal{A},\mathcal{S}\} E ∈ { A , S } , define hybrids H E ( 0 ) , H E ( 1 ) , H E ( 2 ) H_E^{(0)},H_E^{(1)},H_E^{(2)} H E ( 0 ) , H E ( 1 ) , H E ( 2 ) , where E = A E=\mathcal{A} E = A denotes the real experiment and E = S E=\mathcal{S} E = S the simulated experiment. Below, each hybrid outputs the adversary’s bit, and let π E ( k ) : = Pr [ H E ( k ) = 1 ] \pi_E^{(k)}:=\Pr[H_E^{(k)}=1] π E ( k ) := Pr [ H E ( k ) = 1 ] .
Hybrid H E ( 0 ) H_E^{(0)} H E ( 0 ) : the original experiment under R \mathcal{R} R . Draw the oracle description from R \mathcal{R} R and independently choose a uniform prefix j 1 ∈ [ G ] j_1\in[G] j 1 ∈ [ G ] . In the real experiment, choose a uniform suffix j 2 ∈ [ C ] j_2\in[C] j 2 ∈ [ C ] , sample s , c s,c s , c honestly at p-key ( j 1 , j 2 ) (j_1,j_2) ( j 1 , j 2 ) with c c c encrypting one, set d = j 2 ⊕ a d=j_2\oplus a d = j 2 ⊕ a , and give p = ( j 1 , d , s , c ) p=(j_1,d,s,c) p = ( j 1 , d , s , c ) to A \mathcal{A} A with the original oracle. In the simulated experiment, choose a uniform suffix j 2 ′ ∈ [ C ] j'_2 \in[C] j 2 ′ ∈ [ C ] , sample s , c s,c s , c in the same way at ( j 1 , j 2 ′ ) (j_1,j'_2) ( j 1 , j 2 ′ ) , and choose d d d independently and uniformly; give the same program format to A \mathcal{A} A , answering its queries by the simulator’s rules above. Since, choosing a uniform h h h -subset H ⊆ [ G ] H \subseteq[G] H ⊆ [ G ] containing j 1 j_1 j 1 without using it in the experiment has no effect on the experiment statistics, and since the sampled prefix is uniform for every oracle, we get π A ( 0 ) − π S ( 0 ) = E R d a ( O ) \pi_{\mathcal{A}}^{(0)}-\pi_{\mathcal{S}}^{(0)}=\mathop{\mathbb{E}}_{\mathcal{R}}d_a(\mathcal{O}) π A ( 0 ) − π S ( 0 ) = E R d a ( O ) .
Hybrid H E ( 1 ) H_{\mathcal{E}}^{(1)} H E ( 1 ) : replace the data at the other prefixes in H H H . Modify H E ( 0 ) H_{\mathcal{E}}^{(0)} H E ( 0 ) by replacing each X k X_k X k , for k ∈ H ∖ { j 1 } k\in H\setminus\{j_1\} k ∈ H ∖ { j 1 } , by an independent sample from P X k \mathcal{P}_{X_k} P X k . Use these replacements in every common-oracle operation, leaving X j 1 X_{j_1} X j 1 , the prepared program, and the simulator’s redirection rule unchanged. The subset H H H remains hidden. The corresponding query comparison in the proof of Lemma 5.12, with N N N replaced by G G G , applies because the simulator preserves p-key prefixes and gives
∣ π E ( 1 ) − π E ( 0 ) ∣ ≤ O ( q h G ) . \left|\pi_{\mathcal{E}}^{(1)}-\pi_{\mathcal{E}}^{(0)}\right|\le O\left(q\sqrt{\frac{h}{G}}\right). π E ( 1 ) − π E ( 0 ) ≤ O ( q G h ) .
Hybrid H E ( 2 ) H_{\mathcal{E}}^{(2)} H E ( 2 ) : replace the data at the sampled prefix. Modify H E ( 1 ) H_{\mathcal{E}}^{(1)} H E ( 1 ) by replacing X j 1 X_{j_1} X j 1 with an independent sample from P X j 1 \mathcal{P}_{X_{j_1}} P X j 1 . Use this new tuple both to prepare the program as in H E ( 0 ) H_{\mathcal{E}}^{(0)} H E ( 0 ) and to answer all oracle queries, including the simulator’s redirected queries; retain W W W , H H H , j 1 j_1 j 1 , the outside data X − H X_{-H} X − H , and the independent replacements at the other prefixes in H H H . Applying Lemma 5.8 to X 1 , … , X G X_1,\ldots,X_G X 1 , … , X G , exactly as in the corresponding comparison in Lemma 5.12, gives
∣ π E ( 2 ) − π E ( 1 ) ∣ ≤ L 2 h . \left|\pi_{\mathcal{E}}^{(2)}-\pi_{\mathcal{E}}^{(1)}\right|\le\sqrt{\frac{L}{2h}}. π E ( 2 ) − π E ( 1 ) ≤ 2 h L .
In H E ( 2 ) H_{\mathcal{E}}^{(2)} H E ( 2 ) , the tuple X j 1 X_{j_1} X j 1 is independent of all remaining oracle data, so Lemma 5.14 gives ∣ π A ( 2 ) − π S ( 2 ) ∣ ≤ O ( q / C + q / N ) \left|\pi_{\mathcal{A}}^{(2)}-\pi_{\mathcal{S}}^{(2)}\right|\le O(q/\sqrt{C}+q/\sqrt{N}) π A ( 2 ) − π S ( 2 ) ≤ O ( q / C + q / N ) . Combining these comparisons by the triangle inequality yields
∣ E R d a ( O ) ∣ ≤ O ( q h G + L h + q C + q N ) . \left|\mathop{\mathbb{E}}_{\mathcal{R}}d_a(\mathcal{O})\right|\le O\left(q\sqrt{\frac{h}{G}}+\sqrt{\frac{L}{h}}+\frac{q}{\sqrt{C}}+\frac{q}{\sqrt{N}}\right). ∣ E R d a ( O ) ∣ ≤ O ( q G h + h L + C q + N q ) .
Since C = G C=G C = G , N = G C N=GC N = GC , and h ≥ 1 h\ge1 h ≥ 1 , the last two terms are absorbed into the first.
For the maximum absolute difference, use the final argument of the same qPKE proof, appending to W W W both a maximizing point a a a and the sign bit σ = 1 [ d a ( O ) < 0 ] \sigma=1[d_a(\mathcal{O})<0] σ = 1 [ d a ( O ) < 0 ] . An independent uniform point and bit in the reference distribution give entropy budget L + ( λ + 1 ) ln 2 L+(\lambda+1)\ln2 L + ( λ + 1 ) ln 2 , proving the second claim. □ \square □
Moving to an oracle with no qOWFs
Let P \mathcal{P} P be the oracle distribution defined in Section 5.2. We will condition on this distribution to obtain a distribution where qOWFs do not exist.
Whole-function agreement. Fix an evaluator E E E , a parameter λ ≥ 2 \lambda\ge2 λ ≥ 2 , and a cutoff a = a ( λ ) = ⌈ c log 2 λ ⌉ a=a(\lambda)=\lceil c\log_2\lambda\rceil a = a ( λ ) = ⌈ c log 2 λ ⌉ , where c ≥ 1 c\ge1 c ≥ 1 is fixed. Let q = q ( λ ) ≥ 1 q=q(\lambda)\ge1 q = q ( λ ) ≥ 1 be a polynomial upper bound on the number of oracle queries and the lengths queried by E E E . Keep the oracle blocks at lengths n < a n<a n < a fixed. Sample the remaining blocks independently as specified by P \mathcal{P} P . We use this sampling procedure in the next four lemmas, with this cutoff. At one remaining length, P \mathcal{P} P samples independent tables A A A , B B B and a uniform τ ∈ [ 0 , 1 ] \tau\in[0,1] τ ∈ [ 0 , 1 ] . Write F ( A , B , τ ) F(A,B,\tau) F ( A , B , τ ) for the resulting block. For fixed A , B A,B A , B , increasing τ \tau τ from zero to one continuously changes the operations defined by A A A into those defined by B B B . At τ = 1 \tau=1 τ = 1 , the operations depend only on B B B . They therefore equal the operations at τ = 0 \tau=0 τ = 0 for any block whose first table is B B B . Lemma 5.7 also bounds the operator-norm change by a constant times the change in τ \tau τ .
The running-time bound of E E E limits the lengths it can query to a finite set. Applying Lemma 5.5 independently at these lengths at or above the cutoff constructs random continuous paths between two independent samples of those blocks. At every fixed value of the path parameter, those blocks have exactly the distribution specified by P \mathcal{P} P . The blocks below a a a and the PSPACE oracle stay fixed. Define d ( O , O ′ ) d(O,O') d ( O , O ′ ) as the maximum operator-norm difference between corresponding operations at lengths E E E can query. This also bounds the difference between queries made in superposition over operation names and lengths. Taking the maximum, rather than a sum, keeps the path’s change bound independent of the lengths and their number.
Let D ⊆ { 0 , 1 } m ( λ ) D \subseteq\{0,1\}^{m(\lambda)} D ⊆ { 0 , 1 } m ( λ ) be a fixed input set, independent of the remaining blocks. Call an oracle reliable on D D D if, on every x ∈ D x \in D x ∈ D , some output of E O ( x ) E^O(x) E O ( x ) has probability at least 5 / 6 5/6 5/6 . These unique outputs define a function on D D D .
Lemma 5.16 (Whole-function agreement). If the oracle is reliable on D D D with probability at least 1 − ε 1-\varepsilon 1 − ε , where 0 ≤ ε ≤ 1 / 2 0 \le\varepsilon\le1/2 0 ≤ ε ≤ 1/2 , then there is a function f f f on D D D such that, with probability at least
1 − C ( q + 1 ) ε , (6) 1-C(q+1)\varepsilon, \tag*{(6)} 1 − C ( q + 1 ) ε , (6) the oracle is reliable on D D D and the most likely output of E E E is f ( x ) f(x) f ( x ) for every x ∈ D x \in D x ∈ D . Here C C C is a constant.
Proof. Replacing oracle queries one at a time bounds the change in the probability of any output event by 2 q d ( O , O ′ ) 2q\,d(O,O') 2 q d ( O , O ′ ) ; intermediate measurements may be deferred. Partition the reliable oracles into sets computing the same function on D D D . Two different sets disagree at some input, where one output has probability at least 5 / 6 5/6 5/6 in one set and at most 1 / 6 1/6 1/6 in the other. For any oracles O , O ′ O,O' O , O ′ in different sets, the query bound therefore gives
d ( O , O ′ ) ≥ 5 / 6 − 1 / 6 2 q = 1 3 q . d(O,O') \ge\frac{5/6-1/6}{2q}=\frac{1}{3q}. d ( O , O ′ ) ≥ 2 q 5/6 − 1/6 = 3 q 1 . Here d d d is the maximum operator-norm difference defined above. The reliable function classes form a finite measurable family. Let ε b a d \varepsilon_{\mathrm{bad}} ε bad be the probability that the oracle is not reliable on D D D , so ε b a d ≤ ε ≤ 1 / 2 \varepsilon_{\mathrm{bad}} \le\varepsilon\le1/2 ε bad ≤ ε ≤ 1/2 . Applying Corollary 5.3 and its finite-product extension with δ = 1 / ( 3 q ) \delta=1/(3q) δ = 1/ ( 3 q ) , one class has probability at least
1 − ε b a d − 9 v 0 q ε b a d 1 − ε b a d ≥ 1 − ( 1 + 18 v 0 q ) ε . 1-\varepsilon_{\mathrm{bad}}-\frac{9v_0q\varepsilon_{\mathrm{bad}}}{1-\varepsilon_{\mathrm{bad}}} \ge1-(1+18v_0q)\varepsilon. 1 − ε bad − 1 − ε bad 9 v 0 q ε bad ≥ 1 − ( 1 + 18 v 0 q ) ε . Choose f f f to be the common function computed by the oracles in this largest class. Since v 0 v_0 v 0 is an absolute constant, taking C = 1 + 18 v 0 C=1+18v_0 C = 1 + 18 v 0 gives (5.6). □ \square □
Recovering reliable answers. We estimate the fixed blocks and simulate the remaining blocks. Averaging the simulated evaluation in polynomial space then recovers the answers on which most oracles agree.
Lemma 5.17 (Recovering reliable answers). Suppose that, for every x ∈ D x \in D x ∈ D , some answer a x a_x a x satisfies
Pr O ← P [ Pr [ E O ( x ) = a x ] ≥ 5 / 6 ] ≥ 9 / 10. \Pr_{O\leftarrow\mathcal{P}}\left[\Pr\left[E^O(x)=a_x\right]\ge5/6\right]\ge9/10. O ← P Pr [ Pr [ E O ( x ) = a x ] ≥ 5/6 ] ≥ 9/10.
A QPT procedure outputs classical estimates T T T of the operations below length a ( λ ) a(\lambda) a ( λ ) , defining a function g T g_T g T computable in polynomial space from λ , T \lambda,T λ , T , such that
Pr T [ ∀ x ∈ D , g T ( x ) = a x ] ≥ 1 − λ − 3 . \Pr_T[\forall x \in D,\ g_T(x)=a_x] \ge1-\lambda^{-3}. T Pr [ ∀ x ∈ D , g T ( x ) = a x ] ≥ 1 − λ − 3 .
Proof. At lengths below the logarithmic cutoff a a a , the oracle operations have polynomial dimension. Using the available oracle access, we reconstruct these operations by standard Hadamard-test estimation of their matrix entries [5 Section 2.2] . For an operation of dimension d 0 d_0 d 0 , use controlled Hadamard tests to estimate each matrix entry to additive error 1 / ( 1024 q d 0 ) 1/(1024qd_0) 1/ ( 1024 q d 0 ) . The estimated matrix is then within 1 / ( 1024 q ) 1/(1024q) 1/ ( 1024 q ) in operator norm. Replacing it by a nearest unitary increases this bound by at most a factor of two. Approximate that unitary by a circuit to error 1 / ( 512 q ) 1/(512q) 1/ ( 512 q ) and store the circuit description in T T T . Thus each stored circuit has operator-norm error at most 1 / ( 256 q ) 1/(256q) 1/ ( 256 q ) . The concentration bound for the Hadamard tests and a union bound over all entries give this guarantee simultaneously with probability at least 1 − λ − 3 1-\lambda^{-3} 1 − λ − 3 , using polynomially many tests. Replacing the queries one at a time then changes any output probability by at most 2 q / ( 256 q ) = 1 / 128 2q/(256q)=1/128 2 q / ( 256 q ) = 1/128 , uniformly over inputs and the remaining blocks.
For the simulation at lengths n ≥ a n \ge a n ≥ a , condition on A j ∩ B j = ∅ \mathcal{A}_j \cap\mathcal{B}_j=\varnothing A j ∩ B j = ∅ for every pair of rows. The excluded probability is at most
∑ n ≥ a 4 N M 2 / Z = ∑ n ≥ a 4 ⋅ 2 − 7 n < 1 16 . \sum_{n\ge a} 4NM^2/Z=\sum_{n\ge a}4\cdot2^{-7n}<\frac{1}{16}. n ≥ a ∑ 4 N M 2 / Z = n ≥ a ∑ 4 ⋅ 2 − 7 n < 16 1 .
Thus conditioning changes any averaged output probability by less than 1 / 16 1/16 1/16 . The pairs of rows remain independent under this conditioning.
At each such length, let I 1 , I 2 , I 3 , I 4 I_1,I_2,I_3,I_4 I 1 , I 2 , I 3 , I 4 be four consecutive intervals of size M M M in [ Z ] [Z] [ Z ] . Under this conditioning, the four sets of c-texts A j , 0 , A j , 1 , B j , 0 , B j , 1 \mathcal{A}_{j,0},\mathcal{A}_{j,1},\mathcal{B}_{j,0},\mathcal{B}_{j,1} A j , 0 , A j , 1 , B j , 0 , B j , 1 are sampled by choosing an independent uniform permutation π j \pi_j π j for each pair of rows and setting
A j , b = π j − 1 ( I b + 1 ) , B j , b = π j − 1 ( I b + 3 ) ( b ∈ { 0 , 1 } ) . \mathcal{A}_{j,b}=\pi_j^{-1}(I_{b+1}),\qquad\mathcal{B}_{j,b}=\pi_j^{-1}(I_{b+3})\quad(b\in\{0,1\}). A j , b = π j − 1 ( I b + 1 ) , B j , b = π j − 1 ( I b + 3 ) ( b ∈ { 0 , 1 }) .
Choose k = O ( q ) k=O(q) k = O ( q ) to be twice an upper bound on the total number of coherent queries to the s-keys and permutations used to simulate E E E . We replace each uniform permutation by an almost k k k -wise independent permutation from [37 ] : on any at most k k k distinct inputs, its images are within statistical distance δ \delta δ of those of a uniform permutation. Such permutations have descriptions of length polynomial in n , q , log ( 1 / δ ) n,q,\log(1/\delta) n , q , log ( 1/ δ ) . For each length, use a k k k -wise independent function of j j j whose output contains the two s-keys and the random bits specifying π j \pi_j π j . Thus any k k k pairs of rows have the same joint distribution as if these strings were chosen independently. The functions at different lengths are sampled independently. Only polynomially many lengths can be queried, so all these choices have a polynomial-length description when log ( 1 / δ ) \log(1/\delta) log ( 1/ δ ) is polynomial in λ \lambda λ .
Fix τ \tau τ at each length. Each operation uses constantly many coherent queries to the s-keys and permutations, including their inverses. Applying π j − 1 \pi_j^{-1} π j − 1 to the prescribed interval superpositions prepares the c-text states. Evaluating π j ( c ) \pi_j(c) π j ( c ) determines the O d e c O_{\mathrm{dec}} O dec operation.
Exact k k k -wise independent permutations preserve the averaged output probabilities for this number of quantum queries. For the almost independent permutations, the bound in [6 Theorem 1.1] lets us choose δ \delta δ with polynomial log ( 1 / δ ) \log(1/\delta) log ( 1/ δ ) so that the total replacement error over all pairs of rows is negligible. By [53 Fact 2] , a quantum algorithm making at most k / 2 k/2 k /2 queries to this function has the same averaged output probabilities whether it is k k k -wise independent or fully random. This applies even when a query is in superposition over j j j .
Replace the uniform choice of τ ∈ [ 0 , 1 ] \tau\in[0,1] τ ∈ [ 0 , 1 ] by a uniform choice from the equally spaced points
{ 0 , 2 − s , 2 ⋅ 2 − s , … , ( 2 s − 1 ) 2 − s } , \{0,2^{-s},2\cdot2^{-s},\ldots,(2^s-1)2^{-s}\}, { 0 , 2 − s , 2 ⋅ 2 − s , … , ( 2 s − 1 ) 2 − s } ,
where s s s is polynomial in λ \lambda λ . Rounding τ \tau τ down to this grid changes it by at most 2 − s 2^{-s} 2 − s . Lemma 5.7 and the query hybrid bound therefore bound the change in any output probability by O ( q 2 − s ) O(q2^{-s}) O ( q 2 − s ) . Choose s s s large enough to make this at most 1 / 128 1/128 1/128 . For each choice of these functions and τ \tau τ all simulated operations and the fixed PSPACE queries are computable in polynomial space. We can therefore approximate each output-bit probability in polynomial space by [51 ] . Enumerating the polynomial-length descriptions of these functions and the grid indices and averaging these probabilities still uses polynomial space.
Condition on the event that every circuit in T T T has operator-norm error at most 1 / ( 256 q ) 1/(256q) 1/ ( 256 q ) ; its failure probability is at most λ − 3 \lambda^{-3} λ − 3 , as proved above. Choose the permutation, grid, simulated-circuit, and numerical approximation errors to be at most 1 / 128 1/128 1/128 each. Together with the 1 / 128 1/128 1/128 error from replacing the fixed operations, their sum is less than 1 / 16 1/16 1/16 . We call T T T accurate when the stated operator-norm bounds hold. Including the conditioning error, the computed average then differs from the original one by at most 1 / 8 1/8 1/8 , uniformly over inputs. Define g T g_T g T by rounding each computed output-bit probability at 1 / 2 1/2 1/2 .
For every x ∈ D x \in D x ∈ D , each bit of a x a_x a x is correct with probability at least ( 9 / 10 ) ( 5 / 6 ) = 3 / 4 (9/10)(5/6)=3/4 ( 9/10 ) ( 5/6 ) = 3/4 in the original average. The error bound therefore ensures that rounding recovers a x a_x a x . Thus accurate estimates give g T ( x ) = a x g_T(x)=a_x g T ( x ) = a x simultaneously for all x ∈ D x \in D x ∈ D .
Inversion. Under pointwise correctness, we recover the entire function and find any preimage. Under average correctness, we instead sample a preimage nearly uniformly, to avoid concentrating on inputs where recovery fails.
Lemma 5.18 (Inversion under pointwise correctness). Fix the blocks below a ( λ ) a(\lambda) a ( λ ) as in Lemma 5.17, and sample the remaining blocks according to P \mathcal{P} P . Suppose that, with probability at least 9 / 10 9/10 9/10 , the resulting oracle is reliable on the full input domain and computes the same function f ∗ f_* f ∗ . One QPT inverter with PSPACE access returns a preimage of every y ∈ Im ( f ∗ ) y \in\operatorname{Im}(f_*) y ∈ Im ( f ∗ ) with probability at least 1 − λ − 3 1-\lambda^{-3} 1 − λ − 3 .
Proof. Lemma 5.17 gives g T = f ∗ g_T=f_* g T = f ∗ everywhere except with probability λ − 3 \lambda^{-3} λ − 3 . Given y y y , use the PSPACE oracle to find the lexicographically first x x x satisfying g T ( x ) = y g_T(x)=y g T ( x ) = y .
We now show inversion under average correctness. Let K K K be the polynomial factor in Lemma 5.16, and write
ε = Pr x ← { 0 , 1 } m ( λ ) [ Pr O ← P [ max y Pr [ E O ( x ) = y ] < 5 / 6 ] ] . \varepsilon=\underset{x\mathrel{\leftarrow}\{0,1\}^{m(\lambda)}}{\Pr}\left[\underset{\mathcal{O}\mathrel{\leftarrow}\mathcal{P}}{\Pr}\left[\max_y\Pr[E^{\mathcal{O}}(x)=y]<5/6\right]\right]. ε = x ← { 0 , 1 } m ( λ ) Pr [ O ← P Pr [ y max Pr [ E O ( x ) = y ] < 5/6 ] ] .
Lemma 5.19 (Inversion under average correctness). There exists a QPT inverter with access to O \mathcal{O} O and the PSPACE oracle such that, outside a set of oracles of probability at most O ( K λ 2 ε ) O(K\lambda^2\varepsilon) O ( K λ 2 ε ) , its success probability is at least
1 − O ( η + λ − 2 ) 1-O(\eta+\lambda^{-2}) 1 − O ( η + λ − 2 ) whenever E O E^{\mathcal{O}} E O has average correctness error at most η \eta η under uniform inputs.
Proof. For each input x x x , let ε x \varepsilon_x ε x be the probability that the oracle is not reliable on { x } \{x\} { x } . Then E x ε x = ε \mathbb{E}_x\varepsilon_x=\varepsilon E x ε x = ε . For inputs with ε x ≤ 1 / ( 10 K ) \varepsilon_x\leq1/(10K) ε x ≤ 1/ ( 10 K ) , Lemma 5.16 gives common answers, which Lemma 5.17 recovers as g T g_T g T . The expected fraction of inputs either excluded by this threshold or failing to produce their common answer with probability at least 5 / 6 5/6 5/6 is O ( K ε ) O(K\varepsilon) O ( K ε ) . By Markov’s inequality, outside a set of oracles of probability O ( K λ 2 ε ) O(K\lambda^{2}\varepsilon) O ( K λ 2 ε ) , this fraction is O ( λ − 2 ) O(\lambda^{-2}) O ( λ − 2 ) . Thus, whenever T T T is accurate and E O E^{O} E O has average correctness error η \eta η ,
Pr x [ g T ( x ) ≠ f ( x ) ] = O ( η + λ − 2 ) . \Pr_{x}[g_{T}(x) \ne f(x)] = O(\eta+ \lambda^{-2}). x Pr [ g T ( x ) = f ( x )] = O ( η + λ − 2 ) .
The inverter computes T T T independently of the challenge. Given y y y , it samples a nearly uniform preimage under g T g_{T} g T , or returns failure if none exists. This requires only polynomially many queries to the PSPACE oracle.
Since f f f and g T g_{T} g T agree on all but an O ( η + λ − 2 ) O(\eta+ \lambda^{-2}) O ( η + λ − 2 ) fraction of inputs, sampling a uniform preimage of the challenge under g T g_{T} g T inverts f f f with probability 1 − O ( η + λ − 2 ) 1 - O(\eta+ \lambda^{-2}) 1 − O ( η + λ − 2 ) for a uniform challenge input. The same bound holds for evaluations of E E E , after including evaluation error, estimation failure, and the negligible sampling error.
We now essentially established that on oracles where the evaluator is correct, we can invert it with PSPACE oracle. However, there may be oracles where the correctness does not hold on certain security parameters and, thus, the inversion attack may not succeed. Nevertheless, this still allows us to rule out qOWFs because on such parameters correctness does not hold. In other words, we can select an oracle such that at infinitely many selected security parameters for each evaluator, either security does not hold or correctness does not hold.
Moreover, since the number of evaluators is countable, we can actually enumerate over all evaluators and choose one oracle such that for every evaluator, there is an infinite sequence of security parameters where the evaluator does not satisfy correctness or can be inverted. This gives us a single oracle where no qOWF exists. We then show in section 5.3 that qPKE can be built relative to this oracle which gives us the final separation.
Selecting the distribution. For any distribution R \mathcal{R} R on the oracle descriptions of Section 5.2, write R ≤ r \mathcal{R}_{\le r} R ≤ r for its restriction to lengths at most r r r .
Theorem 5.20 (Oracle selection and absence of one-way functions). There is a distribution Q \mathcal{Q} Q on the oracle descriptions of Section 5.2 with the following properties.
With Q \mathcal{Q} Q -probability one, no qOWF1 _1 1 or qOWF2 _2 2 exists.
For every r ≥ 1 r \ge1 r ≥ 1 , the relative entropy (KL-divergence) of Q \mathcal{Q} Q from the base distribution P \mathcal{P} P , restricted to lengths at most r r r , is at most L ( r ) = 2 r L(r) = 2r L ( r ) = 2 r :
D ( Q ≤ r ∥ P ≤ r ) ≤ L ( r ) = 2 r . (7) D(\mathcal{Q}_{\le r}\Vert\mathcal{P}_{\le r}) \le L(r) = 2r. \tag*{(7)} D ( Q ≤ r ∥ P ≤ r ) ≤ L ( r ) = 2 r . (7)
Proof. The construction of Q \mathcal{Q} Q and its proof follow by applying the preceding lemmas to all uniform evaluators. We enumerate all possible evaluators with explicit polynomial running-time bounds. Consider each evaluator infinitely often for pointwise correctness and infinitely often for average correctness under uniform inputs. Each step of the following procedure (which eventually generates Q \mathcal{Q} Q ) chooses a finite group of new oracle blocks and fixes them permanently.
For the evaluator considered at a given step, use its bounds q q q and K ≥ 2 K \ge2 K ≥ 2 and its cutoff a ( λ ) a(\lambda) a ( λ ) from the preceding lemmas. Set
θ ( λ ) = 1 10 6 K ( λ ) λ 8 . \theta(\lambda) = \frac{1}{10^{6}K(\lambda)\lambda^{8}}. θ ( λ ) = 1 0 6 K ( λ ) λ 8 1 .
Choose the constant c c c in a ( λ ) a(\lambda) a ( λ ) once for this evaluator so that ln ( 1 / θ ( λ ) ) ≤ a ( λ ) \ln(1/\theta(\lambda)) \le a(\lambda) ln ( 1/ θ ( λ )) ≤ a ( λ ) at all selected parameters. These logarithmic cutoffs allow polynomial-time estimation of the operations below the cutoff. Number all steps by i = 1 , 2 , … i = 1,2,\ldots i = 1 , 2 , … , assigning each evaluator and correctness requirement an infinite subsequence of these indices. When we later analyze a fixed evaluator, we restrict to its assigned indices; i i i always refers to the full sequence of steps.
At step i i i , use a parameter λ i ≥ i + 2 \lambda_i \ge i+2 λ i ≥ i + 2 and write
θ i = θ ( λ i ) , a i = a ( λ i ) , b i = max { a i , q ( λ i ) } . \theta_i = \theta(\lambda_i), \qquad a_i = a(\lambda_i), \qquad b_i = \max\{a_i,q(\lambda_i)\}. θ i = θ ( λ i ) , a i = a ( λ i ) , b i = max { a i , q ( λ i )} .
Choose the sequence of evaluators, correctness requirements, and increasing parameters in advance, with a i + 1 > max { 2 a i , b i } a_{i+1} > \max\{2a_i,b_i\} a i + 1 > max { 2 a i , b i } . Sample the blocks below a 1 a_1 a 1 from P \mathcal{P} P . At step i i i , keep the blocks below a i a_i a i fixed and define B i B_i B i according to the correctness requirement being considered:
In both cases, these output probabilities are for the chosen evaluator at parameter λ i \lambda_i λ i .
The event B i B_i B i depends on the chosen evaluator and the new oracle blocks. The output probabilities defining B i B_i B i are over the evaluator’s internal randomness; the probability below is over sampling the new blocks from P \mathcal{P} P . The rule below forces B i B_i B i whenever it is sufficiently likely. Otherwise, its small probability lets us apply the preceding lemmas to obtain inversion guarantees.
If
Pr P [ B i ∣ fixed blocks ] ≥ θ i , \Pr_{\mathcal{P}}[B_i \mid\text{fixed blocks}] \ge\theta_i, P Pr [ B i ∣ fixed blocks ] ≥ θ i ,
sample the blocks at lengths a i , … , b i a_i,\ldots,b_i a i , … , b i from P \mathcal{P} P conditioned on B i B_i B i . Otherwise, sample them from P \mathcal{P} P without conditioning. Sample the blocks at lengths b i + 1 , … , a i + 1 − 1 b_i+1,\ldots,a_{i+1}-1 b i + 1 , … , a i + 1 − 1 independently from P \mathcal{P} P . All sampled blocks are fixed permanently. The events B i B_i B i are measurable and depend only on blocks fixed by this step, so later steps cannot change the evaluator’s behavior at λ i \lambda_i λ i . The selection procedure need not be efficient. Let Q Q Q be the distribution of the complete oracle description generated by this procedure.
Conditioning on an event of probability ρ \rho ρ contributes ln ( 1 / ρ ) \ln(1/\rho) ln ( 1/ ρ ) to relative entropy. Thus, for every choice of the previously fixed blocks, step i i i contributes at most
ln ( 1 / θ i ) ≤ a i . \ln(1/\theta_i) \le a_i. ln ( 1/ θ i ) ≤ a i .
Unconditioned sampling contributes zero. The chain rule for relative entropy therefore gives
D ( Q ≤ r ∥ P ≤ r ) ≤ ∑ i : a i ≤ r a i ≤ 2 r , D(Q_{\le r}\mathbin\Vert\mathcal{P}_{\le r}) \le\sum_{i:a_i\le r} a_i \le2r, D ( Q ≤ r ∥ P ≤ r ) ≤ i : a i ≤ r ∑ a i ≤ 2 r ,
where the last inequality follows from a i + 1 > 2 a i a_{i+1} > 2a_i a i + 1 > 2 a i . If r r r falls within a step, apply the bound through that step and discard the blocks above r r r ; this cannot increase relative entropy.
At an unconditioned step i i i , keep the previously sampled blocks fixed and put λ = λ i \lambda=\lambda_i λ = λ i and θ = θ i \theta=\theta_i θ = θ i . Here K K K is the previously chosen bound for which Lemma 5.16 gives agreement probability at least 1 − K ε 1-K\varepsilon 1 − K ε for this evaluator at λ i \lambda_i λ i . By the selection rule,
Pr P [ B i ∣ previously fixed blocks ] < θ , \Pr_{\mathcal{P}}[B_i \mid\text{previously fixed blocks}] < \theta, P Pr [ B i ∣ previously fixed blocks ] < θ ,
and the new blocks are sampled directly from P \mathcal{P} P .
In the pointwise case, Lemma 5.16 gives a set of oracles of probability at least 1 − K θ 1-K\theta 1 − K θ that reliably compute the same function on every input. In the average case, the expected fraction of unreliable inputs is at most 2 θ 2\theta 2 θ : outside B i B_i B i this fraction is at most θ \theta θ , and B i B_i B i itself has probability below θ \theta θ . Lemma 5.19 therefore gives an exceptional set of probability O ( K λ 2 θ ) O(K\lambda^{2}\theta) O ( K λ 2 θ ) .
Let F i F_i F i be the event of falling outside the common-function set in the pointwise case, or inside the exceptional set in the average case. Set F i = ∅ F_i = \varnothing F i = ∅ at conditioned steps. The bounds hold for every choice of the previously fixed blocks, so
Pr Q [ F i ] ≤ O ( K λ 2 θ ) = O ( λ i − 6 ) . \Pr_{\mathcal{Q}}[F_i] \le O(K\lambda^{2}\theta) = O(\lambda_i^{-6}). Q Pr [ F i ] ≤ O ( K λ 2 θ ) = O ( λ i − 6 ) .
Since λ i ≥ i + 2 \lambda_i \ge i+2 λ i ≥ i + 2 , these probabilities are summable. By Borel–Cantelli, only finitely many F i F_i F i occur with Q \mathcal{Q} Q -probability one. At each conditioned step, the conditional law assigns probability zero to B i c B_i^c B i c . A countable union of these null failure events has probability zero, so every conditioned step satisfies its event B i B_i B i simultaneously with Q \mathcal{Q} Q -probability one.
Fix an oracle for which every conditioned step satisfies B i B_i B i and only finitely many F i F_i F i occur. Fix an evaluator satisfying one of the correctness requirements with negligible error. At its sufficiently late scheduled steps, conditioning on B i B_i B i would force correctness error greater than 1 / 6 1/6 1/6 on some input in the pointwise case, or average error greater than θ / 6 \theta/6 θ /6 in the average case. Both contradict correctness, since θ \theta θ is inverse polynomial. Hence these steps are unconditioned and outside F i F_i F i .
Lemma 5.18 or Lemma 5.19 now gives a uniform inverter with success probability at least 2 / 3 2/3 2/3 at infinitely many selected security parameters for this evaluator and correctness requirement, such that the inverter’s description does not depend on these selected parameters. In the pointwise case (Definition 1), the guarantee holds on every image, and negligible evaluation error also gives the evaluation guarantee for every input sampler. In the average case (Definition 2 ), this success guarantee holds for uniformly sampled inputs. Hence, the inverter contradicts the one-wayness guarantee for both definitions (Definitions 1 and 2 ) in § 3.2 .
Corollary 5.21 (Oracle distribution with qPKE and point-function obfuscation without qOWFs). *Let Q \mathcal{Q} Q be the distribution on the oracle descriptions of § 5.3 supplied by Theorem 5.20 . With Q \mathcal{Q} Q -probability one, no qOWF1 _1 1 or qOWF2 _2 2 exists, while the qPKE construction of § 5.5 is IND-CPA secure and the point-function obfuscator satisfies Definition 7.
In particular, there is a fixed oracle O ∈ supp ( Q ) O \in\operatorname{supp}(\mathcal{Q}) O ∈ supp ( Q ) with all these properties and perfect correctness for qPKE, thus yielding Theorem 5.1 .
Proof of Corollary 5.21. Fix a uniform adversary for each primitive, and let q ( λ ) q(\lambda) q ( λ ) bound the queries in their security experiments, including honest preparation and the obfuscation simulator’s calls. Let r ( λ ) ≥ 2 λ r(\lambda) \ge2\lambda r ( λ ) ≥ 2 λ be a polynomial bound on all accessible oracle lengths. Theorem 5.20 gives relative-entropy budget L = 2 r ( λ ) L = 2r(\lambda) L = 2 r ( λ ) .
For qPKE, apply Lemma 5.12 with n = λ n = \lambda n = λ , N = 2 λ N = 2^\lambda N = 2 λ , and h = ⌈ 2 λ / 2 ⌉ h = \lceil2^{\lambda/2}\rceil h = ⌈ 2 λ /2 ⌉ . Use L + ln 2 L + \ln2 L + ln 2 for the absolute-advantage bound. For correctness, apply Lemma 5.9 to the block at length λ \lambda λ with budget L L L , and bound the maximum of the two correctness errors by their sum. Since q , r q,r q , r are polynomial and M 2 / Z = 2 − 8 λ M^2/Z = 2^{-8\lambda} M 2 / Z = 2 − 8 λ , the expected absolute advantage and correctness error are at most poly ( λ ) 2 − Ω ( λ ) \operatorname{poly}(\lambda)2^{-\Omega(\lambda)} poly ( λ ) 2 − Ω ( λ ) .
For point-function obfuscation, the block at length 2 λ 2\lambda 2 λ has C = G = 2 λ C = G = 2^\lambda C = G = 2 λ , N = 2 2 λ N = 2^{2\lambda} N = 2 2 λ , Y = 2 16 λ Y = 2^{16\lambda} Y = 2 16 λ , M = 2 4 λ M = 2^{4\lambda} M = 2 4 λ , and Z = 2 24 λ Z = 2^{24\lambda} Z = 2 24 λ . Apply Lemma 5.15 with h = ⌈ 2 λ / 2 ⌉ h = \lceil2^{\lambda/2}\rceil h = ⌈ 2 λ /2 ⌉ and Λ = L + ( λ + 1 ) ln 2 \Lambda= L + (\lambda+1)\ln2 Λ = L + ( λ + 1 ) ln 2 . Its expected maximum absolute gap is at most poly ( λ ) 2 − Ω ( λ ) \operatorname{poly}(\lambda)2^{-\Omega(\lambda)} poly ( λ ) 2 − Ω ( λ ) . Honest preparation and evaluation use only this block, so Lemma 5.10 with relative-entropy budget 4 λ 4\lambda 4 λ gives expected correctness error 2 − Ω ( λ ) 2^{-\Omega(\lambda)} 2 − Ω ( λ ) .
Let e ( O ) e(O) e ( O ) denote either absolute security gap (maximized over points for obfuscation) or either correctness error. For each positive integer c c c , Markov’s inequality gives
∑ λ ≥ 1 Pr O ∼ Q [ e ( O ) > λ − c ] ≤ ∑ λ ≥ 1 λ c E O ∼ Q e ( O ) < ∞ . \sum_{\lambda\ge1} \Pr_{O \sim\mathcal{Q}}[e(O) > \lambda^{-c}] \le\sum_{\lambda\ge1} \lambda^c \mathbb{E}_{O \sim\mathcal{Q}} e(O) < \infty. λ ≥ 1 ∑ O ∼ Q Pr [ e ( O ) > λ − c ] ≤ λ ≥ 1 ∑ λ c E O ∼ Q e ( O ) < ∞.
Borel–Cantelli and a countable intersection over uniform adversaries and positive integers c c c show that all these errors are negligible with probability one. Intersect this event with the probability-one absence of both qOWF1 _1 1 s and qOWF2 _2 2 s from Theorem 5.20 , and call the resulting event H \mathcal{H} H . Thus Q ( H ) = 1 \mathcal{Q}(\mathcal{H})=1 Q ( H ) = 1 , with the single obfuscation simulator of § 5.7 working for all points. Independent bitwise encryption extends qPKE to polynomial-length messages by a polynomial hybrid and a union bound.
For the fixed oracle’s exact qPKE correctness, let C n C_n C n be the event that some pair of rows at length n n n has A j ∩ B j ≠ ∅ A_j \cap B_j \ne\varnothing A j ∩ B j = ∅ , and put G = ⋂ n ≥ 1 C n c \mathcal{G}=\bigcap_{n\ge1} C_n^{c} G = ⋂ n ≥ 1 C n c . At selection step i i i , conditioning increases probabilities by at most θ i − 1 ≤ e a i \theta_i^{-1}\le e^{a_i} θ i − 1 ≤ e a i . Using the construction of Q \mathcal{Q} Q and P ( C n ) ≤ 4 ⋅ 2 − 7 n \mathcal{P}(C_n)\le4\cdot2^{-7n} P ( C n ) ≤ 4 ⋅ 2 − 7 n , we obtain
Q ( C n ) ≤ exp ( ∑ i : a i ≤ n a i ) P ( C n ) ≤ 4 ( e 2 / 128 ) n , \mathcal{Q}(C_n)\le\exp\left(\sum_{i:a_i\le n}a_i\right)\mathcal{P}(C_n)\le4(e^2/128)^n, Q ( C n ) ≤ exp ( i : a i ≤ n ∑ a i ) P ( C n ) ≤ 4 ( e 2 /128 ) n ,
Q ( G c ) ≤ 4 ∑ n ≥ 1 ( e 2 / 128 ) n < 1. \mathcal{Q}(\mathcal{G}^{c})\le4\sum_{n\ge1}(e^2/128)^n<1. Q ( G c ) ≤ 4 n ≥ 1 ∑ ( e 2 /128 ) n < 1.
Hence Q ( G ∩ H ) = Q ( G ) > 0 \mathcal{Q}(\mathcal{G}\cap\mathcal{H})=\mathcal{Q}(\mathcal{G})>0 Q ( G ∩ H ) = Q ( G ) > 0 . The support of Q \mathcal{Q} Q has full measure, so choose O ∈ G ∩ H ∩ supp ( Q ) \mathcal{O}\in\mathcal{G}\cap\mathcal{H}\cap\operatorname{supp}(\mathcal{Q}) O ∈ G ∩ H ∩ supp ( Q ) . Observation 5.6 gives exact honest qPKE correctness there, completing the proof.
Corollary 5.22 (Access to unitary implementations). There is no uniform relativizing fully black-box construction of a qOWF1 _1 1 or qOWF2 _2 2 from either primitive, even with access to full unitary implementations of its algorithms and their inverse, conjugate, transpose, and controlled versions. For point-function obfuscation, the reduction must be valid for the single-program guarantee of Definition 7.
Proof. Both the construction and its security reduction must remain valid relative to a common additional oracle. Defer measurements, retain discarded registers, and store random coins in workspace to obtain a uniform polynomial-size unitary implementation W O W^{O} W O of each primitive algorithm. Reverse its gates for the inverse, conjugate them for the entrywise conjugate, use ( W O ) T = ( W O ) † (W^{O})^{T}=(W^{O})^{\dagger} ( W O ) T = ( W O ) † for the transpose, and control each gate for controlled access. The required oracle operations are available. These implementations act correctly on arbitrary inputs and workspace, while honest challenges keep their private workspace hidden.
Instantiate the proposed construction at the oracle of Corollary 5.21 and expand its implementation queries into these circuits. The result is a uniform QPT evaluator with polynomial overhead. Either its qOWF correctness fails, or the inversion argument in Theorem 5.20 supplies an inverter succeeding at infinitely many parameters. The latter contradicts the reduction and primitive security. The inversion guarantee covers every challenge sampler for qOWF1 _1 1 and the prescribed uniform sampler for qOWF2 _2 2 .
Constructing qPKE from qiO and EV-OWPuzz
In this section, we construct qPKE from EV-OWPuzz and qiO. We use the qiO of Definition 8, which obfuscates quantum circuits computing classical functions and produces classical programs. Let ( O , E ) (O,E) ( O , E ) be its obfuscation and evaluation algorithms, respectively. For brevity, we remove the security parameter 1 λ 1^\lambda 1 λ from their input syntax. We amplify its correctness as in Remark 3.4, so that, except for a negligible fraction of obfuscated programs, evaluation is correct with negligible error on every input. Throughout this section, all samplers, verifiers, obfuscation algorithms, and adversaries are QPT unless stated otherwise, with classical inputs and outputs. All lengths are bounded by fixed polynomials in λ \lambda λ , and programs compared under qiO are padded if required to have the same circuit size along with input and output lengths.
Suppression lemma
For an EV-OWPuzz scheme ( S a m p , V ) (\mathsf{Samp},V) ( Samp , V ) with correctness error η \eta η , write v p ( a ) : = Pr [ V ( p , a ) = 1 ] v_p(a) := \Pr[V(p,a)=1] v p ( a ) := Pr [ V ( p , a ) = 1 ] for any p , a p,a p , a , as in Definition 5. A puzzle verifier may accept many answers, including answers with intermediate acceptance probabilities. The goal of this section is to design a procedure that accepts only one accepting answer and suppresses the acceptance probability of every other input, including other previously valid answers. We do this so that the resulting circuit implements a point function, which can then be used to prove the point-hiding property for qiO that we need to prove security of our qPKE construction given in § 6.3 . We follow the threshold selection and hashing argument of Aharonov, Ben-Or, Brandão, and Sattath [2 Lemma 39 and Section 5] , and then use independent repetition to reduce the error.
Lemma 6.1 (Suppressing all but one accepting answer). For any EV-OWPuzz with answers padded to a fixed length m = m ( λ ) ≥ λ + 5 m=m(\lambda)\ge\lambda+5 m = m ( λ ) ≥ λ + 5 , and for any sampled puzzle p p p that has an answer a a a satisfying v p ( a ) ≥ 2 / 3 v_p(a)\ge2/3 v p ( a ) ≥ 2/3 (which happens with probability at least 1 − 3 η 1-3\eta 1 − 3 η over the sampling of p p p ), there is an efficient randomized procedure that with probability at least inverse polynomial in m m m , constructs a polynomial-size quantum circuit W p W_p W p such that there is an answer a ⋆ a^\star a ⋆ satisfying Pr [ W p ( a ⋆ ) = 1 ] ≥ 1 − 2 − λ \Pr[W_p(a^\star)=1]\ge1-2^{-\lambda} Pr [ W p ( a ⋆ ) = 1 ] ≥ 1 − 2 − λ , Pr [ W p ( a ) = 1 ] ≤ 2 − λ \Pr[W_p(a)=1]\le2^{-\lambda} Pr [ W p ( a ) = 1 ] ≤ 2 − λ for every a ≠ a ⋆ a\ne a^\star a = a ⋆ , and v p ( a ⋆ ) > 1 / 3 v_p(a^\star)>1/3 v p ( a ⋆ ) > 1/3 .
Proof. We first repeat V ( p , ⋅ ) V(p,\cdot) V ( p , ⋅ ) independently O ( log m ) O(\log m) O ( log m ) times and take a majority. Write q ( a ) q(a) q ( a ) for the resulting acceptance probability, and choose the repetition count so that
v p ( a ) ≤ 1 / 3 ⟹ q ( a ) ≤ 1 8 m , v p ( a ) ≥ 2 / 3 ⟹ q ( a ) ≥ 1 − 1 8 m . v_p(a)\le1/3\Longrightarrow q(a)\le\frac{1}{8m},\qquad v_p(a)\ge2/3\Longrightarrow q(a)\ge1-\frac{1}{8m}. v p ( a ) ≤ 1/3 ⟹ q ( a ) ≤ 8 m 1 , v p ( a ) ≥ 2/3 ⟹ q ( a ) ≥ 1 − 8 m 1 .
Note that this does not give any guarantee on answers with previously intermediate acceptance probabilities. Next, we guess j j j uniformly from { 1 , … , m − 2 } \{1,\ldots,m-2\} { 1 , … , m − 2 } and k k k uniformly from { 0 , … , m } \{0,\ldots,m\} { 0 , … , m } , and sample a pairwise independent hash h : { 0 , 1 } m → { 0 , 1 } k + 2 h:\{0,1\}^{m}\to\{0,1\}^{k+2} h : { 0 , 1 } m → { 0 , 1 } k + 2 using a uniform binary matrix and an independent uniform offset. Thus, distinct inputs have independent uniform hash values. We want the zero bucket, i.e., the set of answers that hash to zero, to keep one answer with acceptance at least ( j + 1 ) / m (j+1)/m ( j + 1 ) / m and no other answer with acceptance greater than j / m j/m j / m . Define W p W_p W p to reject inputs whose hash is nonzero; otherwise, it repeats the amplified verifier independently O ( m 2 λ ) O(m^2\lambda) O ( m 2 λ ) times and accepts when the fraction of accepting trials exceeds ( j + 1 / 2 ) / m (j+1/2)/m ( j + 1/2 ) / m .
We now bound the probability that these guesses succeed. For j = 1 , … , m − 1 j=1,\ldots,m-1 j = 1 , … , m − 1 , let S j = { a : q ( a ) ≥ j / m } S_j=\{a:q(a)\ge j/m\} S j = { a : q ( a ) ≥ j / m } . These sets are nested and S m − 1 S_{m-1} S m − 1 is nonempty. Some j ∈ { 1 , … , m − 2 } j\in\{1,\ldots,m-2\} j ∈ { 1 , … , m − 2 } satisfies ∣ S j ∣ ≤ 4 ∣ S j + 1 ∣ |S_j|\le4|S_{j+1}| ∣ S j ∣ ≤ 4∣ S j + 1 ∣ ; otherwise ∣ S 1 ∣ > 4 m − 2 ∣ S m − 1 ∣ > 2 m |S_1|>4^{m-2}|S_{m-1}|>2^m ∣ S 1 ∣ > 4 m − 2 ∣ S m − 1 ∣ > 2 m . For this j j j , the sets
A = { a : q ( a ) ≥ ( j + 1 ) / m } , B = { a : q ( a ) > j / m } A=\{a:q(a)\ge(j+1)/m\},\qquad B=\{a:q(a)>j/m\} A = { a : q ( a ) ≥ ( j + 1 ) / m } , B = { a : q ( a ) > j / m }
satisfy ∅ ≠ A ⊆ B \varnothing\ne A\subseteq B ∅ = A ⊆ B and ∣ B ∣ ≤ 4 ∣ A ∣ |B|\le4|A| ∣ B ∣ ≤ 4∣ A ∣ .
Fix this guess of j j j and a guess satisfying 2 k ≤ ∣ B ∣ < 2 k + 1 2^k\le|B|<2^{k+1} 2 k ≤ ∣ B ∣ < 2 k + 1 . Write M = 2 k + 2 M=2^{k+2} M = 2 k + 2 . For each a ∈ A a\in A a ∈ A , pairwise independence and a union bound give
Pr [ h ( a ) = 0 and h ( b ) ≠ 0 for all b ∈ B ∖ { a } ] ≥ 1 M − ∣ B ∣ − 1 M 2 ≥ 1 2 M . \Pr[h(a)=0\text{ and }h(b)\ne0\text{ for all }b\in B\setminus\{a\}]
\ge\frac{1}{M}-\frac{|B|-1}{M^2}\ge\frac{1}{2M}. Pr [ h ( a ) = 0 and h ( b ) = 0 for all b ∈ B ∖ { a }] ≥ M 1 − M 2 ∣ B ∣ − 1 ≥ 2 M 1 .
These events are disjoint for distinct a ∈ A a\in A a ∈ A . Since M ≤ 4 ∣ B ∣ M\le4|B| M ≤ 4∣ B ∣ , their total probability is at least ∣ A ∣ / ( 8 ∣ B ∣ ) ≥ 1 / 32 |A|/(8|B|)\ge1/32 ∣ A ∣/ ( 8∣ B ∣ ) ≥ 1/32 . The guesses of j j j and k k k contribute factors 1 / ( m − 2 ) 1/(m-2) 1/ ( m − 2 ) and 1 / ( m + 1 ) 1/(m+1) 1/ ( m + 1 ) , giving success probability at least 1 / [ 32 ( m − 2 ) ( m + 1 ) ] 1/[32(m-2)(m+1)] 1/ [ 32 ( m − 2 ) ( m + 1 )] , which is inverse polynomial in m m m . On this event, the zero bucket (i.e., the set of answers that hash to zero) contains one answer a ⋆ a^\star a ⋆ with acceptance at least ( j + 1 ) / m (j+1)/m ( j + 1 ) / m , and every other retained answer has acceptance at most j / m j/m j / m . Hoeffding’s inequality applied to the midpoint test therefore gives error at most 2 − λ 2^{-\lambda} 2 − λ on every input. Moreover, q ( a ⋆ ) ≥ 2 / m > 1 / ( 8 m ) q(a^\star) \ge2/m > 1/(8m) q ( a ⋆ ) ≥ 2/ m > 1/ ( 8 m ) implies v p ( a ⋆ ) > 1 / 3 v_p(a^\star) > 1/3 v p ( a ⋆ ) > 1/3 by the initial amplification. Finally, whenever the lemma’s hypothesis fails, the verifier rejects every answer with probability greater than 1 / 3 1/3 1/3 . Since it rejects an honestly sampled puzzle-answer pair with probability at most η \eta η , such puzzles occur with probability at most 3 η 3\eta 3 η . □ \square □
From EV-OWPuzz to Hiding a Random Point under qiO
We now use the suppression lemma to prove the point-hiding property needed for the security of our qPKE scheme, described in Section 6.3. Write P u ( x ) = 1 { x = u } P_u(x)=\mathbf{1}\{x=u\} P u ( x ) = 1 { x = u } for the point function at u ∈ { 0 , 1 } m u\in\{0,1\}^{m} u ∈ { 0 , 1 } m , where m m m is the answer length fixed in Lemma 6.1, and write Z ( x ) = 0 Z(x)=0 Z ( x ) = 0 for the zero function on the same domain. To apply obfuscation security, we pad all the programs that we will compare to a common size s = s ( λ ) s=s(\lambda) s = s ( λ ) , which is a fixed polynomial large enough for every circuit size obfuscated in the proof below.
Lemma 6.2 (Hiding a random point). Assume EV-OWPuzz exists and let ( O , E ) (O,E) ( O , E ) be a qiO scheme satisfying Definition 8. For every polynomial t t t , t t t independent obfuscations of P u P_u P u under O O O , for a uniformly sampled u ← { 0 , 1 } m u\leftarrow\{0,1\}^{m} u ← { 0 , 1 } m , is computationally indistinguishable from t t t independent obfuscations of Z Z Z under O O O .
We adapt the single-point extraction argument of Boyle, Chung, and Pass [11 Section 6.1, Theorem 6.2] to the quantum circuit obtained from suppression.
Proof. Suppose a QPT distinguisher D D D has absolute distinguishing gap at least δ ( λ ) = 1 / q ( λ ) \delta(\lambda)=1/q(\lambda) δ ( λ ) = 1/ q ( λ ) for a polynomial q q q and infinitely many security parameters. Given a puzzle p p p , our inverter runs suppression once to obtain W W W , chooses r ← { 0 , 1 } m r\leftarrow\{0,1\}^{m} r ← { 0 , 1 } m , and forms the padded circuit Q r ( x ) = W ( x ⊕ r ) Q_r(x)=W(x\oplus r) Q r ( x ) = W ( x ⊕ r ) . By Lemma 6.1, conditioned on the suppression procedure being successful with answer a ⋆ a^\star a ⋆ , Q r Q_r Q r computes the point function at u = a ⋆ ⊕ r u=a^\star\oplus r u = a ⋆ ⊕ r with error at most 2 − λ 2^{-\lambda} 2 − λ on every input. Since r r r is uniform, so is u u u . By the indistinguishability security of qiO, conditioned on the successful trial of the suppression procedure, replacing the t t t independent obfuscations of P u P_u P u by obfuscations of Q r Q_r Q r , one at a time, changes D D D ’s average acceptance probability by a negligible additive term. Moreover, the negligible change in acceptance probability holds for every W W W in the support of a successful trial and all r r r . Otherwise, select W , r , a ⋆ W,r,a^\star W , r , a ⋆ for which the change is at least inverse-polynomial at infinitely many security parameters, and compare the acceptance probabilities for the obfuscations of Q r Q_r Q r , P u P_u P u , i.e., output 1 1 1 on acceptance. This gives a distinguisher that violates the indistinguishability security of qiO (see Definition 8).
Put α r = Pr [ D ( O ( Q r ) 1 , … , O ( Q r ) t ) = 1 ] \alpha_r=\Pr[D(O(Q_r)_1,\ldots,O(Q_r)_t)=1] α r = Pr [ D ( O ( Q r ) 1 , … , O ( Q r ) t ) = 1 ] and β = Pr [ D ( O ( Z ) 1 , … , O ( Z ) t ) = 1 ] \beta=\Pr[D(O(Z)_1,\ldots,O(Z)_t)=1] β = Pr [ D ( O ( Z ) 1 , … , O ( Z ) t ) = 1 ] . For all sufficiently large parameters at which D D D has gap at least δ \delta δ , we have ∣ E r [ α r − β ] ∣ ≥ δ / 2 |\mathbb{E}_r[\alpha_r-\beta]|\ge\delta/2 ∣ E r [ α r − β ] ∣ ≥ δ /2 . Since ∣ α r − β ∣ ≤ 1 |\alpha_r-\beta|\le1 ∣ α r − β ∣ ≤ 1 , at least a δ / 4 \delta/4 δ /4 fraction of choices of r r r satisfy ∣ α r − β ∣ ≥ δ / 4 |\alpha_r-\beta|\ge\delta/4 ∣ α r − β ∣ ≥ δ /4 .
For each input position i i i , the inverter forms
Q r , i ( x ) = { Q r ( x ) , x i = 1 , 0 , x i = 0 , Q_{r,i}(x)=
\begin{cases}
Q_r(x), & x_i=1,\\
0, & x_i=0,
\end{cases} Q r , i ( x ) = { Q r ( x ) , 0 , x i = 1 , x i = 0 ,
and pads it to size s s s . If u i = 1 u_i=1 u i = 1 , this circuit computes the same point function as Q r Q_r Q r ; if u i = 0 u_i=0 u i = 0 , it computes zero, in both cases with error at most $2^{-\lambda}$ on every input. Let α r , i \alpha_{r,i} α r , i be D D D ’s acceptance probability on t t t independent obfuscations of Q r , i Q_{r,i} Q r , i . By the indistinguishability security of qiO, α r , i \alpha_{r,i} α r , i is negligibly close to α r \alpha_r α r when u i = 1 u_i=1 u i = 1 and to β \beta β when $u_i=0. The inverter estimates α r \alpha_r α r , β \beta β , and all α r , i \alpha_{r,i} α r , i to accuracy δ / 100 \delta/100 δ /100 , using fresh independent obfuscations and independent runs of D D D , and then taking the fraction of accepting runs. Taking O ( δ − 2 log ( m + 2 ) ) O(\delta^{-2}\log(m+2)) O ( δ − 2 log ( m + 2 )) samples per estimate makes all estimates accurate with probability at least 3 / 4 3/4 3/4 by standard Chernoff bounds and a union bound over the m + 2 m+2 m + 2 estimates. Next, the inverter sets u ^ i = 1 \hat{u}_i=1 u ^ i = 1 if the estimate of α r , i \alpha_{r,i} α r , i is closer to that of α r \alpha_r α r , and sets u ^ i = 0 \hat{u}_i=0 u ^ i = 0 otherwise. For any r r r satisfying ∣ α r − β ∣ ≥ δ / 4 |\alpha_r-\beta|\geq\delta/4 ∣ α r − β ∣ ≥ δ /4 and sufficiently large λ \lambda λ , the negligible differences above are less than δ / 100 \delta/100 δ /100 . When all estimates are accurate (which conditioned on the suppression procedure being successful, happens with probability at least 3 / 4 3/4 3/4 ), the distance to the correct estimate is at most 3 δ / 100 3\delta/100 3 δ /100 , while the distance to the other is at least δ / 4 − 3 δ / 100 \delta/4-3\delta/100 δ /4 − 3 δ /100 . Thus, conditioned on successful suppression and a choice of r r r satisfying ∣ α r − β ∣ ≥ δ / 4 |\alpha_r-\beta|\geq\delta/4 ∣ α r − β ∣ ≥ δ /4 , u ^ = u \hat{u}=u u ^ = u , and hence the inverter outputs u ^ ⊕ r = a ∗ \hat{u}\oplus r=a^* u ^ ⊕ r = a ∗ , with probability at least 3 / 4 3/4 3/4 over the independent obfuscations and runs of D D D . Note that an honestly sampled puzzle satisfies the suppression hypothesis with probability at least 1 − 3 η 1-3\eta 1 − 3 η . For each such puzzle, suppression succeeds with probability at least γ = γ ( λ ) \gamma=\gamma(\lambda) γ = γ ( λ ) , an inverse-polynomial bound supplied by Lemma 6.1 . Moreover, conditioned on successful suppression, there are at least a δ / 4 \delta/4 δ /4 fraction of choices of r r r such that ∣ α r − β ∣ ≥ δ / 4 |\alpha_r-\beta|\geq\delta/4 ∣ α r − β ∣ ≥ δ /4 , and hence, permits the inverter to recover a ∗ a^* a ∗ with probability at least 3 / 4 3/4 3/4 . Finally, we know that a ∗ a^* a ∗ is accepted by the puzzle verifier with probability at least 1 / 3 1/3 1/3 . Hence the probability that the inverter outputs an answer that V ( p , ⋅ ) V(p,\cdot) V ( p , ⋅ ) (the puzzle verifier’s verification with respect to p p p ) accepts, is at least
( 1 − 3 η ) γ δ 4 1 4 1 3 = ( 1 − 3 η ) γ δ 16 (1-3\eta)\gamma\frac{\delta}{4}\frac{1}{4}\frac{1}{3}=\frac{(1-3\eta)\gamma\delta}{16} ( 1 − 3 η ) γ 4 δ 4 1 3 1 = 16 ( 1 − 3 η ) γ δ
on infinitely many security parameters, contradicting the EV-OWPuzz security since ( 1 − 3 η ) γ δ 16 \frac{(1-3\eta)\gamma\delta}{16} 16 ( 1 − 3 η ) γ δ is non-negligible in λ \lambda λ .
Finally, the inverter is clearly a uniform QPT algorithm, since suppression and obfuscation run in polynomial time on every trial, which completes the proof of the lemma. □ \square □
qPKE construction
We can now state the construction and prove security of it using Lemma 6.2. As noted in the technical overview, the EV-OWPuzz assumption only shows up in the security proof to prove point hiding; the qPKE algorithms themselves only use qiO.
Theorem 6.3 (Public-key encryption from puzzles and quantum obfuscation). There exists a construction of IND-CPA public-key encryption with classical keys and ciphertexts (as defined in Definition 6) given an EV-OWPuzz scheme (Definition 5) and a qiO scheme (as defined in Definition 8).
Proof. It suffices to encrypt one bit. Let m , s m,s m , s be as in Lemma 6.2. Choose a polynomial size s ′ s' s ′ large enough for a circuit containing an obfuscation of a size-s s s program and running the evaluator E E E . Such a bound exists because O O O and E E E run in polynomial time. We fix s s s first, then s ′ s' s ′ , and pad all ciphertext programs to size s ′ s' s ′ .
KeyGen ( 1 λ ) \operatorname{KeyGen}(1^\lambda) KeyGen ( 1 λ ) : choose u ← { 0 , 1 } m u\leftarrow\{0,1\}^m u ← { 0 , 1 } m , set s k = u \mathsf{sk}=u sk = u , and output p k ← O ( P u ) \mathsf{pk}\leftarrow O(P_u) pk ← O ( P u ) , using the padded point circuit.
Enc ( p k , b ) \operatorname{Enc}(\mathsf{pk},b) Enc ( pk , b ) : construct the quantum circuit C p k , b ( x ) = b ∧ E ( p k , x ) C_{\mathsf{pk},b}(x)=b\wedge E(\mathsf{pk},x) C pk , b ( x ) = b ∧ E ( pk , x ) , padded to size s ′ s' s ′ , and output c ← O ( C p k , b ) c\leftarrow O(C_{\mathsf{pk},b}) c ← O ( C pk , b ) .
Dec ( u , c ) \operatorname{Dec}(u,c) Dec ( u , c ) : output E ( c , u ) E(c,u) E ( c , u ) .
All keys and ciphertexts are classical. The ciphertext circuit runs the quantum evaluator E E E , which is why we need obfuscation for quantum circuits.
For correctness, Remark 3.4 ensures that, except with probability 2 − λ 2^{-\lambda} 2 − λ over the public key, E ( p k , x ) E(\mathrm{pk},x) E ( pk , x ) computes P u ( x ) P_u(x) P u ( x ) with error at most 2 − λ 2^{-\lambda} 2 − λ on every input. For each such key, C p k , b C_{\mathrm{pk},b} C pk , b computes b ∧ P u b \wedge P_u b ∧ P u with the same error bound. The correctness of qiO then gives E ( c , u ) = b E(c,u)=b E ( c , u ) = b with negligible error. This bound holds uniformly over these keys because Definition 8 requires correctness for every family of such circuits. The exceptional keys contribute only negligible error.
For security, first replace the public key with p k ← O ( Z ) \mathrm{pk} \mathrel{\leftarrow} O(Z) pk ← O ( Z ) . Lemma 6.2 with t = 1 t=1 t = 1 makes this change computationally indistinguishable. The reduction can run the adversary and generate its challenge ciphertext from the given public key, so the lemma applies to the full encryption experiment.
By Remark 3.4, except with probability 2 − λ 2^{-\lambda} 2 − λ , this public key evaluates to zero with error at most 2 − λ 2^{-\lambda} 2 − λ on every input. Both C p k , 0 C_{\mathrm{pk},0} C pk , 0 and C p k , 1 C_{\mathrm{pk},1} C pk , 1 then compute zero with negligible error on every input, and they also have the same size s ′ s' s ′ due to padding. Hence, their obfuscations are indistinguishable by qiO, even given pk as classical auxiliary information. As above, the guarantee holds uniformly over these keys, and exceptional keys contribute negligible probability. Finally, replace the public key by an obfuscation of a random point again. These changes give indistinguishable encryptions of zero and one under the real key distribution.
For polynomially many ciphertexts, replace them one at a time; public encryption lets the reduction generate all other ciphertexts itself. Encrypting each bit of a polynomial-length message separately and changing the encrypted bits one at a time gives IND-CPA security for polynomial-length messages.
AI Methodology
The concepts and proof ideas were mainly generated by the authors. However, the proof of the barrier theorem (Theorem 5.2 ) was produced through interaction with ChatGPT 6 Astra. We also used ChatGPT 6 Astra to help write the other proofs, improve presentation, and check for mistakes. The authors take responsibility for any mistakes or issues.