1 Introduction↩︎

Pseudorandom quantum states (\(\mathsf{PRS}\)) were introduced by Ji, Liu, and Song [1] as the quantum analogue of classical pseudorandom generators (\(\mathsf{PRG}\)) [2]. Informally, an \(n\)-\(\mathsf{PRS}\) generator is a quantum polynomial-time algorithm that, on input \(k \in \{0,1\}^\lambda\), outputs a \(n\)-qubit state \(\ket{\phi_k}\) that is computationally indistinguishable from a Haar-random state, even when an adversary is given polynomially many copies of the state.

Two size regimes of \(\mathsf{PRS}\) have emerged as central: \((1)\) short pseudorandom states (\(\mathsf{SPRS}\)), where the output length \(n\) is logarithmic in \(\lambda\), and \((2)\) long pseudorandom states (\(\mathsf{LPRS}\)), where \(n\) scales linearly with \(\lambda\). These regimes display markedly different behavior. In contrast to \(\mathsf{PRG}\)s, no known reduction connects \(\mathsf{SPRS}\) and \(\mathsf{LPRS}\). In fact, a separation exists indicating \(\mathsf{LPRS}\not\rightarrow \mathsf{SPRS}\) [3], and there is evidence that the reverse direction is also difficult [4].

Both \(\mathsf{SPRS}\) and \(\mathsf{LPRS}\) can be realized from \(\mathsf{PRG}\)s [1], [5]. In the other direction, Kretschmer [6] proved a black-box separation between \(\mathsf{PRG}\)s and \(\mathsf{LPRS}\)s,¹ yet this does not rule out a reduction to \(\mathsf{SPRS}\)s. His argument relies crucially on a concentration inequality for quantum states (Theorem 5.17 in [7]) that fails in the short-state regime. Our approach does not use this result, thereby circumventing that limitation.

The difference between the two regimes is also reflected in their cryptographic applications, where \(\mathsf{SPRS}\) have a wider range of known applications. Long pseudorandom states enable a variety of constructions—such as quantum pseudo-encryption, quantum bit-commitment protocols, length-restricted one-time signatures with quantum public keys, and private-key quantum money [1], [8], [9]. Despite this, employing \(\mathsf{LPRS}\)s as a complete replacement for \(\mathsf{PRG}\)s remains elusive. Short pseudorandom states, by contrast, admit a closer connection to classical pseudorandomness: through quantum state tomography, one can extract a classical pseudorandom string from \(\mathsf{SPRS}\)s [10]. However, tomography is inherently probabilistic, leading to a notion termed pseudodeterministic \(\mathsf{PRG}\)s—generators that may exhibit non-determinism on a inverse-polynomial fraction of inputs.² Nevertheless, this conversion enables many of the applications of \(\mathsf{PRG}\)s such as many-time digital signatures and quantum public-key encryption with tamper-resilient keys [12]—capabilities still beyond reach for \(\mathsf{LPRS}\)s.

Despite these advances, \(\mathsf{PRG}\)s and \(\mathsf{SPRS}\)s have not been proven black-box separated, which somewhat limits the significance of these results. While partial results exist (see 1.2), no complete black-box separation between \(\mathsf{PRG}\)s and \(\mathsf{SPRS}\)s is currently known, raising the following question:

This question has been highlighted in several recent works [10], [12], [13], underscoring its importance for clarifying the structure of computational hardness in the quantum setting. More generally, understanding which assumptions are separated from \(\mathsf{PRG}\)s and mapping the hierarchy among MicroCrypt primitives remains a fundamental challenge in the study of quantum pseudorandomness.

1.1 Our Results↩︎

In this work, we resolve the above open problem by establishing a black-box separation between \(\mathsf{PRG}\)s and \(n\)-\(\mathsf{PRS}\)s of any size \(n\in O(\lambda)\), thus ruling out constructions from \(\mathsf{SPRS}\). Our result holds relative to a unitary quantum oracle with inverse access, thereby encompassing a broad class of black-box constructions [3].

The \(\mathsf{PRG}\) notion we consider is the quantum-evaluable variant, which permits a negligible probability of error or non-determinism. This choice is essentially tight: if one allows an inverse-polynomial error, the resulting generator becomes pseudodeterministic and can indeed be constructed from an \(\mathsf{SPRS}\) in a black-box manner—hence, such a relaxed version cannot be separated. This is the reason why our separation needs to deal very delicately with the correctness condition of \(\mathsf{PRG}\)s.

Moreover, prior works have shown that \(\mathsf{SPRS}\)s imply a rich class of cryptographic primitives [10], [12], leading to the following corollary.

1.2 Related Works↩︎

Ananth, Lin, and Yuen [10] were the first to formally investigate applications specific to \(\mathsf{SPRS}\)s. They showed how to construct pseudodeterministic \(\mathsf{PRG}\)s from \(\mathsf{SPRS}\)s, and used them to obtain applications such as statistically binding commitments with classical communication and CPA-secure symmetric encryption with classical ciphertexts.

While pseudodeterministic \(\mathsf{PRG}\)s proved useful, their nondeterminism complicates their use as direct substitutes for standard \(\mathsf{PRG}\)s in some applications. To mitigate this, Barhoush et al. [12] introduced the notion of \(\bot\)-pseudodeterministic pseudorandom generators (\(\bot\text{-}\mathsf{PRG}\)s), which they build from pseudodeterministic \(\mathsf{PRG}\)s by marking nondeterministic outcomes with the symbol \(\bot\). This small but powerful refinement allows cryptographic schemes to handle \(\bot\) outputs explicitly, enabling applications such as \(\mathsf{DS}\) and \(\mathsf{QPKE}\).

On the negative side, there are several separations that are relevant to this work:

• \((\mathsf{LPRS}\not\rightarrow \mathsf{PRG}):\) Kretschmer [6] presented a separation between \(\mathsf{PRG}\)s and \(\mathsf{LPRS}\)s, implying that \(\mathsf{LPRS}\) constitute a potentially weaker assumption than \(\mathsf{PRG}\)s.

• \((\mathsf{LPRS}\not\rightarrow \textsf{DS}):\) Coladangelo and Mutreja [3] showed that even digital signatures are separated from \(\mathsf{LPRS}\).

• \((\mathsf{LPRS}\not\rightarrow \mathsf{SPRS}):\) This is a direct corollary to the separation above by [3], but it was also shown through an alternative approach by [14].

• \((\bot\text{-}\mathsf{PRG}\not\rightarrow \mathsf{OWSG}):\) Barhoush, Nishimaki, and Yamakawa [13] showed that one-way state generators \((\textsf{OWSG})\) are separated from \(\bot\text{-}\mathsf{PRG}\)s, relative to a non-unitary CPTP map. Here, \(\textsf{OWSG}\)s are the quantum analogues of one-way functions \((\mathsf{OWF})\) and every \(\mathsf{OWF}\) is a \(\textsf{OWSG}\). However, CPTP separations rule out a more limited class of constructions than unitary separations. In particular, CPTP separation does not cover reductions that use unitary access to the underlying primitive or attack (see [3], [13] for further discussion about these differences). In comparison, our result is based on a unitary oracle and separates \(\mathsf{SPRS}\) from \(\mathsf{PRG}\)s. In one sense, this improves on [13], as \(\mathsf{SPRS}\)s imply \(\bot\text{-}\mathsf{PRG}\)s; yet, because \(\mathsf{PRG}\)s also imply \(\mathsf{OWSG}\)s, the two separations are not directly comparable.

• \((\mathsf{SPRS}\not\rightarrow \mathsf{PRG}):\) At the same time as our work, Bouaziz–Ermann, Hhan, Muguruza, and Vu [4] introduced a novel conjecture on product states such that, if it holds, \(\mathsf{PRG}\)s and \(\mathsf{SPRS}\)s can be separated under a different approach than our own. Our result strengthens their separation as we do not assume any conjectures.

• \((\text{quantum-evaluable }\mathsf{OWF}\not\rightarrow \text{classical-evaluable }\mathsf{OWF}):\) Kretschmer, Qian, Tal [15] show a separation between classical-evaluable OWFs and quantum-evaluable OWFs. Our separations are not comparable with theirs. Note taht all definitions in this work consider quantum-evaluable algorithms.

1.3 Technical Overview↩︎

We now describe our separation between \(\mathsf{PRG}\)s and \(\ell\)-\(\mathsf{PRS}\)s for any function \(\ell(\lambda)\in O(\lambda)\). The discussion below presents a high-level overview that omits several technical subtleties appearing in the full proof.

We use two unitary oracles in the separation:

1. A PSPACE oracle \(\mathcal{C}\), which is used to break any \(\mathsf{PRG}\).

2. A \(\ell\)-Common Haar Function-Like State (CHFS) oracle [4] \(\mathcal{O}\), which, on an input \(x\in \{0,1\}^*\), outputs a Haar random state \(\ket{\phi_x}\) of size \(\ell(\lvert x\rvert)\), where \(\lvert x\rvert\) denotes the length of \(x\).

The existence of \(\mathsf{PRS}\)s relative to such oracles follows from Theorem 5.1 in [4] and was similarly established earlier in [6]. This construction only uses oracle access to \(\mathcal{O}\).

Suppose, toward a contradiction, that there exists a black-box construction of a \(\mathsf{PRG}\) from a \(\mathsf{PRS}\). This would imply the existence of a \(\mathsf{PRG}\) \(G^{\mathcal{O}}\) in this oracle model that may query \(\mathcal{O}\). Because \(\mathsf{PRS}\) satisfies correctness for all oracles \(\mathcal{O}\), the resulting \(\mathsf{PRG}\) \(G\) must also satisfy correctness for any oracle—that is, for every oracle \(\mathcal{O}\) and input \(k\), the evaluation \(G^{\mathcal{O}}(k)\) must produce a fixed output except with negligible probability.

Now consider two CHFS oracles \(\mathcal{O}\) and \(\hat{\mathcal{O}}\). For any \(\lambda \in \mathbb{N}\), define the set of disagreement inputs: \[\begin{align} \textsf{Disagr}^{\mathcal{O},\hat{\mathcal{O}}}_\lambda = \left\{\, k \in \{0,1\}^\lambda \mid G^{\mathcal{O}}(k) \neq G^{\hat{\mathcal{O}}}(k) \,\right\}. \end{align}\]

Intuitively, two situations can arise:

1. There exists a sufficiently large \(\lambda\) such that for any pair of oracles \(\mathcal{O},\hat{\mathcal{O}}\), the set \(\textsf{Disagr}^{\mathcal{O},\hat{\mathcal{O}}}_{\lambda}\) consists of only a negligible fraction of inputs.

2. There exists an infinite sequence \((\lambda_j)_{j\in \mathbb{N}}\) such that for each \(j\), there exists a pair of oracles \(\mathcal{O}^j,\hat{\mathcal{O}}^j\) such that the set \(\textsf{Disagr}^{\mathcal{O}^j,\hat{\mathcal{O}}^j}_{\lambda_j}\) consists of an inverse-polynomial fraction of inputs.

If the first case holds for all pairs of oracles, then \(G^{\mathcal{O}}\) is essentially independent of \(\mathcal{O}\) for large enough \(\lambda\) and exists without oracle access. However, it is well known that no such \(\mathsf{PRG}\) can exist relative to a PSPACE oracle; thus, this case leads to a contradiction.

We therefore focus on the second case: there exist an infinite sequence \((\lambda_j)_{j \in \mathbb{N}}\) such that, for each \(j\), there exists a pair of oracles \((\mathcal{O}^j, \hat{\mathcal{O}}^j)\) such that the set \(\textsf{Disagr}^{\mathcal{O}^j,\hat{\mathcal{O}}^j}_{\lambda_j}\) consists of a inverse-polynomial fraction of inputs.

Assume that \(G\) makes at most \(T = T(\lambda)\) oracle queries for some polynomial \(T\), and define \(m = T \cdot \lambda\). For each \(j\), we construct a sequence of intermediate oracles \(\mathcal{O}^j_1, \ldots, \mathcal{O}^j_m\), starting with \(\mathcal{O}^j_1 = \mathcal{O}^j\) and ending with \(\mathcal{O}^j_m = \hat{\mathcal{O}}^j\), such that for every input state \(\rho\), \[\begin{align} \textsf{Tr}\left(\mathcal{O}^j_i(\rho), \mathcal{O}^j_{i+1}(\rho)\right) \le \frac{1}{m}. \end{align}\] To build this sequence, we gradually “move’’ all the output states of \(\mathcal{O}^j\) toward that of \(\hat{\mathcal{O}}^j\), reducing the trace distance by at most \(1/m\) at each step. After at most \(m\) steps, we reach \(\hat{\mathcal{O}}^j\).

For any \(i \in [m]\), the trace distance between the responses of \(\mathcal{O}^j_i\) and \(\mathcal{O}^j_{i+1}\) on any query is bounded by \(1/m\). Since \(G\) makes at most \(T\) oracle queries, it cannot distinguish between \(\mathcal{O}^j_i\) and \(\mathcal{O}^j_{i+1}\) with probability exceeding \(T/m < 1/\lambda_j\). Therefore, for any input \(k \in \{0,1\}^{\lambda_j}\), \[\begin{align} \label{eq:trace-dis321} \textsf{Tr}\left(G^{\mathcal{O}^j_i}(k), G^{\mathcal{O}^j_{i+1}}(k)\right) \le \frac{1}{\lambda_j}. \end{align}\tag{1}\]

Now consider an input \(k\) such that \(y_k = G^{\mathcal{O}^j}(k)\) and \(\hat{y}_k = G^{\hat{\mathcal{O}}^j}(k)\) are distinct with high probability. As we progress along the oracle sequence \(\mathcal{O}^j_1, \ldots, \mathcal{O}^j_m\), the probability that \(G^{\mathcal{O}^j_i}(k)\) outputs \(y_k\) must gradually decrease, while the probability of outputting \(\hat{y}_k\) must gradually increase.

Hence, there must exist some index \(i_k\) such that \(G^{\mathcal{O}^j_{i_k}}(k)\) is non-deterministic—that is, it outputs both \(y_k\) and \(\hat{y}_k\) with non-negligible probability.

At this point, no direct contradiction arises yet, since \(G\) may be non-deterministic on a negligible fraction of inputs. However, we have established that there exists a non-negligible fraction of inputs on which \(G^{\mathcal{O}^j}\) and \(G^{\hat{\mathcal{O}}^j}\) disagree. For each such input, some generator in the sequence \(G^{\mathcal{O}^j_1}, \ldots, G^{\mathcal{O}^j_m}\) must be non-deterministic on that input. Because \(m\) is polynomial while the fraction of such inputs is non-negligible, there must exist an index \(i_j\) for which \(G^{\mathcal{O}^j_{i_j}}\) is non-deterministic on a non-negligible fraction of inputs.

Still, this does not immediately violate correctness, since \(G^{\mathcal{O}^j_{i_j}}\) might be non-deterministic only for the specific parameter \(\lambda_j\) and fully deterministic for all larger \(\lambda > \lambda_j\).

To overcome this, we combine the oracles \(\mathcal{O}^j_{i_j}\) for all \(j \in \mathbb{N}\) into a single oracle \(\overline{\mathcal{O}}\) such that, for infinitely many \(\lambda\), \(G^{\overline{\mathcal{O}}}\) is non-deterministic on a non-negligible fraction of inputs. This yields a contradiction: any valid black-box construction must preserve correctness whenever the underlying primitive does, and \(\mathsf{PRS}\)s in this oracle model satisfy correctness for all oracles.

A final subtlety arises because \(G\) may always query its oracle on small inputs, independent of the security parameter. In that case, it becomes unclear how to combine oracles that differ on small inputs. To address this, we modify \(G\) so that it queries \(\mathcal{O}\) only on inputs of length at least \(\log(\lambda)\); for smaller inputs, \(G\) can internally simulate \(\mathcal{O}\) using its own randomness, following the simulation approach of [16].

2 Preliminaries↩︎

2.1 Notation↩︎

We let \([n]= \{1,2,\ldots,n\}\) and let \(\negl[x]\) denote any function that is asymptotically smaller than the inverse of any polynomial.

We let \(x\leftarrow X\) denote that \(x\) is chosen from the values in \(X\), according to the distribution \(X\). If \(X\) is a set, then \(x\leftarrow X\) simply means \(x\) is chosen uniformly at random from the set. We let \((\{0,1\}^n)^{\{0,1\}^m}\) denote the set of functions mapping \(\{0,1\}^m\rightarrow \{0,1\}^n\).

We refer the reader to [17] for a detailed exposition to preliminary quantum information. We let \(\mathcal{S}(\mathcal{H})\) and \(\mathcal{U}(\mathcal{H})\) denote the set of unit vectors and unitary operators, respectively, on the Hilbert space \(\mathcal{H}\) and let \(\textsf{Haar}(\mathbb{C}^d)\) denote the Haar measure over \(\mathbb{C}^d\) which is the uniform measure over all \(d\)-dimensional unit vectors. We let \(\textsf{Tr}\) denote the total trace distance between two density matrices or two distributions.

We follow the standard notations to define quantum algorithms. We say that a quantum algorithm \(A\) is QPT if it consists of a family of quantum algorithms \(\{A_\lambda\}_{\lambda}\) such that the run-time of each algorithm \(A_\lambda\) is bounded by some polynomial \(p(\lambda)\). We say that \(A_\lambda(x)\) is non-deterministic if evaluating \(A_\lambda(x)\) twice yields distinct values with non-negligible probability. For a constant \(c\in (0,1)\), we say that \(A_\lambda(x)\) is \(c\)-non-deterministic if evaluating \(A_\lambda(x)\) twice yields distinct values with at least \(c\) probability. We avoid using the \(\lambda\) subscript in algorithms to avoid excessive notation.

2.2 Pseudorandom Primitives↩︎

We define pseudorandom states (\(\mathsf{PRS}\)s), first introduced in [1].

We will also recall the standard definition for \(\mathsf{PRG}\)s.

2.3 Common Haar Function-like State Oracle↩︎

We first recall the definition of a swap unitary [18].

We now define the (unitarized) Common Haar Function-Like State (CHFS) oracle as in [4].

2.4 Black-Box Separation↩︎

Black-box separating primitives using oracles was first considered in [19] and later formalized in the quantum setting in [3]. We briefly define the relative notions for this work.

We now formalize the notion of constructions relative to an oracle.

We are now ready to define the notion of fully black-box construction.

The following result from [3] shows the relation between fully black-box constructions and oracle separations.

2.5 Useful Lemma↩︎

We state a result that will be used in our separation. Intuitively, this result states that small enough \(\mathsf{PRS}\) exist unconditionally. In particular, a sufficiently long random string enables the construction of a sufficiently small \(\mathsf{PRS}\).

3 Separation↩︎

In this section, we present our separation of \(\mathsf{PRG}\) from \(\mathsf{PRS}\).

Proof. Our approach is to show that there exists a unitary quantum oracle with inverse access, relative to which there is no black-box construction of \(\mathsf{PRG}\) from \(\mathsf{PRS}\) with inverse access. Then, by 2, this means there cannot exist such a construction in the plain model as well.

We only show the proof for the case \(n\mathrel{\vcenter{:}}= 2\lambda+ r\), where the polynomial \(r=r(\lambda)\mathrel{\vcenter{:}}= \lambda^2\cdot q(2^{\ell(\log(\lambda))},\lambda)\) and \(q\) is specified in 2. Specifically, \(r\) is chosen so that a string \(k\) of length \(r\) is sufficient to describe a set of states \(\{\ket{\phi_{x,k}}\}_{x\in \{0,1\}^d:\;d \leq \log(\lambda)}\), where \(\ket{\phi_{x,k}}\) is of size \(\ell(\lvert x\rvert)\), such that these states act as statistical \(\mathsf{PRS}\).

Note that ruling out a \((2\lambda+r)\)-\(\mathsf{PRG}\) is sufficient to rule out all possible lengths \(n>\lambda\), since any \(\mathsf{PRG}\) can be composed sufficiently many times to build a \(\mathsf{PRG}\) with longer output length, meaning that different output length regimes are essentially equivalent.

Our proof is relative to two unitary oracles: a (unitarized) PSPACE oracle \(\mathcal{C}\) and a \(\ell\)-CHFS oracle \(\mathcal{O}\) sampled from a set of oracles \(\mathsf{O}_\ell\). Given that both oracles are self-inverse, it is sufficient to give access to \(\mathcal{T}\mathrel{\vcenter{:}}=(\mathcal{C},\mathcal{O})\).

Assume for contradiction that there exists a black-box construction of a \(n\)-\(\mathsf{PRG}\) from a \(\ell\)-\(\mathsf{PRS}\). First, we state the following result which follows directly from Theorem 4.1 in [4].

There exists a \(\ell\)-\(\mathsf{PRS}\) relative to \(\mathcal{T}\). The \(\mathsf{PRS}\) construction only uses oracle access to \(\mathcal{O}\) and satisfies security with probability 1 over the distribution of \(\mathcal{O}\) and satisfies correctness for all \(\mathcal{O}\in \mathsf{O}_\ell\).

By Claim [claim:exist] and the existence of a black-box construction, there exists a \(\mathsf{PRG}\) \(\overline{G}:\{0,1\}^\lambda\rightarrow \{0,1\}^{n}\) relative to \(\mathcal{T}\). Furthermore, \(\overline{G}\) only uses oracle access to \(\mathcal{O}\) and satisfies security with probability 1 over the distribution of \(\mathcal{O}\) and satisfies correctness for all \(\mathcal{O}\), given that these properties are satisfied for the underlying \(\mathsf{PRS}\). Assume \(\overline{G}\) queries the oracle at most \(T=T(\lambda)\) times for some polynomial \(T\) and define the polynomial \(m=m(\lambda)\mathrel{\vcenter{:}}= T\cdot \lambda\).

We now construct an algorithm \(G:\{0,1\}^{n-\lambda}\rightarrow \{0,1\}^{n}\) (see 1) using \(\overline{G}\), that does not query the oracle on any input of length less than \(\log(\lambda)\).

By abuse of notation, we view the input length of \(G\) as \(\lambda\) from now on. Recall that \(\overline{G}^\mathcal{O}\) satisfies correctness for any oracle \(\mathcal{O}\in \mathsf{O}_\ell\). It is clear that \(G\) inherits this property. In particular, for any \(\mathcal{O}\in \mathsf{O}_\ell\), there exists a negligible function \(\epsilon\) (may depend on \(\mathcal{O}\)) such that: for all \(\lambda\in \mathbb{N}\) and for any \(k\gets \{0,1\}^\lambda\), there exists a string \(y_k\) such that \[\begin{align} \label{eq:correctness} \Pr_{k\gets \{0,1\}^\lambda}\left[{G}^{\mathcal{O}}(k)=y_k\right]\geq 1-\epsilon(\lambda). \end{align}\tag{2}\]

Definition 8. For any pair of oracles \(\mathcal{O},\hat{\mathcal{O}}\in \mathsf{O}_\ell\) and \(\lambda\in \mathbb{N}\), define the set \(\textsf{Disagr}^{\mathcal{O},\hat{\mathcal{O}}}_\lambda\) as the set of inputs \(k\in \{0,1\}^\lambda\) such that, \[\begin{align} \Pr\left[G^{\mathcal{O}}(k)\neq G^{\hat{\mathcal{O}}}(k)\right]\geq 1/3. \end{align}\]

There exists some integer \(\lambda^*>0\), such that any pair of oracles \(\mathcal{O},\hat{\mathcal{O}}\in \mathsf{O}_\ell\) satisfy the following: for all integers \(\lambda>\lambda^*\), \[\begin{align} \Pr_{k\gets \{0,1\}^{\lambda}}\left[k\in \textsf{Disagr}^{\mathcal{O},\hat{\mathcal{O}}}_{\lambda} \right]< \frac{1}{\lambda}. \end{align}\]

Proof. Assume for contradiction that the claim does not hold. This means that there exists an infinite sequence \((\lambda_j)_{j\in \mathbb{N}}\) of integers such that for each \(j\in \mathbb{N}\) there exists a pair of oracle \(\mathcal{O}^j,\hat{\mathcal{O}}^j\in \mathsf{O}_\ell\) satisfying: \[\begin{align} \Pr_{k\gets \{0,1\}^{\lambda_j}}\left[k\in \textsf{Disagr}^{\mathcal{O}^j,\hat{\mathcal{O}}^j}_{\lambda_j} \right]\geq \frac{1}{\lambda_j}. \end{align}\]

Fix \(j\in \mathbb{N}\). We can define a sequence of \(m\) oracles \(\mathcal{O}^j_1,\ldots, \mathcal{O}^j_{m}\) starting with \(\mathcal{O}^j_1=\mathcal{O}^j\) and ending with \(\mathcal{O}^j_{m}=\hat{\mathcal{O}}^j\) such that for any \(i\in [m]\) and input \(\rho\), \[\begin{align} \textsf{Tr}\left(\mathcal{O}^j_i(\rho),\mathcal{O}^j_{i+1}(\rho)\right)\leq \frac{1}{m}. \end{align}\] It is not difficult to see that such a sequence must exist. In particular, for any \(i\in [m]\), let \(\Phi^j_i\) be the product state that classifies the oracle \(\mathcal{O}^j_i\) as described in 4. To build this sequence, we gradually “move’’ all the output states of \(\Phi^j_1\) toward that of \(\Phi^j_m\), reducing the trace distance by at most \(1/m\) at each step. After at most \(m\) steps, we reach \(\Phi^j_m\), giving the oracle \(\hat{\mathcal{O}}^j\).

Given that \(G\) queries the oracle at most \(T\) times, it cannot distinguish oracle access to \(\mathcal{O}^j_i\) or \(\mathcal{O}^j_{i+1}\) with better than \(\frac{T}{m}<\frac{1}{{\lambda_j}}\) probability. Therefore, for any input \(k\in \{0,1\}^{{\lambda_j}}\), \[\begin{align} \label{eq:trace-dis} \textsf{Tr}\left(G^{\mathcal{O}^j_i}(k),G^{\mathcal{O}^j_{i+1}}(k)\right)\leq \frac{1}{{\lambda_j}}. \end{align}\tag{3}\]

Now recall that there exists a set of inputs \(\textsf{Disagr}^{\mathcal{O}^j,\hat{\mathcal{O}}^j}_{{\lambda_j}}\) where \(G^{\mathcal{O}^j}\) and \(G^{\hat{\mathcal{O}}^j}\) do not agree with at least \(1/3\) probability.

For any input \(k\in \textsf{Disagr}^{\mathcal{O}^j,\hat{\mathcal{O}}^j}_{{\lambda_j}}\) there are three cases that can occur:

1. There exists distinct values \(y_k,\hat{y}_k\) such that \[\begin{align} \tag{4} \Pr\left[G^{\mathcal{O}^j}(k)=y_k\right]&\geq \frac{9}{10}\\ \tag{5} \Pr\left[G^{\hat{\mathcal{O}}^j}(k)=\hat{y}_k\right]&\geq \frac{9}{10}. \end{align}\]

2. There does not exist a value \(y_k\) such that 4 holds. In other words, \(G^{\mathcal{O}^j}(k)\) is \(\left(\frac{1}{10}\right)\)-non-deterministic i.e. evaluating \(G^{\mathcal{O}^j}(k)\) twice yields two distinct values with at least \(\frac{1}{10}\) probability.

3. There does not exist a value \(\hat{y}_k\) such that 5 holds. In other words, \(G^{\hat{\mathcal{O}}^j}(k)\) is \(\left(\frac{1}{10}\right)\)-non-deterministic.

We analyze each case separately.

• (Case 1): Consider the following probabilities: \[\begin{align} p_{k,i}&\mathrel{\vcenter{:}}= \Pr\left[G^{\mathcal{O}^j_i}(k)=y_k\right]\\ \hat{p}_{k,i}&\mathrel{\vcenter{:}}= \Pr\left[G^{\mathcal{O}^j_i}(k)=\hat{y}_k\right]. \end{align}\] Notice that, by 4 5 , we have \(p_{k,1}\geq 9/10\) and \(\hat{p}_{k,m}\geq 9/10\).

  On the other hand, 3 states the output distribution under two consecutive oracles differs by at most \(\frac{1}{\lambda_j}\). This means that there exists \(i_k\in [m]\) such that \[\begin{align} \frac{1}{4}\leq \frac{1}{2}-\frac{2}{{\lambda_j}}\leq \Pr\left[G^{\mathcal{O}^j_{i_k}}(k)=y_k\right]\leq \frac{1}{2}+\frac{2}{{\lambda_j}}\leq\frac{3}{4}. \end{align}\] In other words, \(G^{\mathcal{O}^j_{i_k}}(k)\) is \(\left(\frac{1}{10}\right)\)-non-deterministic.

• (Case 2): In this case, \(G^{\mathcal{O}^j}(k)\) is \(\left(\frac{1}{10}\right)\)-non-deterministic so set \(i_k\) to \(1\), noting that \(\mathcal{O}^j=\mathcal{O}^j_1\).

• (Case 3): In this case, \(G^{\hat{\mathcal{O}}^j}(k)\) is \(\left(\frac{1}{10}\right)\)-non-deterministic so set \(i_k\) to \(m\), noting that \(\hat{\mathcal{O}}^j=\mathcal{O}^j_m\).

In other words, in all cases, there is an index \(i_k\) such that \(G^{\mathcal{O}^j_{i_k}}(k)\) is \(\left(\frac{1}{10}\right)\)-non-deterministic.

More generally, for every input in \({\textsf{Disagr}}^{\mathcal{O}^j,\hat{\mathcal{O}}^j}_{{\lambda_j}}\) there exists an oracle in the sequence under which the evaluation of \(G\) is \(\left(\frac{1}{10}\right)\)-non-deterministic.

The number of inputs in the set \({\textsf{Disagr}}^{\mathcal{O}^j,\hat{\mathcal{O}}^j}_{{\lambda_j}}\) is at least \(\frac{2^{\lambda_j}}{\lambda_j}\). Therefore, there is an index, which we denote by \(i_j\), such that there are at least \(\frac{2^{{\lambda_j}}}{m\lambda_j}\) inputs \(k\in \{0,1\}^{\lambda_j}\), where \(G^{\mathcal{O}^j_{i_j}}(k)\) is \(\left(\frac{1}{10}\right)\)-non-deterministic.

By performing this analysis for each \(j\in \mathbb{N}\), we establish, for every large enough \(j\), there is some oracle \(\overline{\mathcal{O}}^j\) such that \(G^{\overline{\mathcal{O}}^j}\) is \(\left(\frac{1}{10}\right)\)-non-deterministic on at least \(\frac{1}{m\lambda_j}\) fraction of inputs \(k\in \{0,1\}^{\lambda_j}\). Let \(\overline{\Phi}^j\mathrel{\vcenter{:}}= \left\{\ket{\overline{\phi}^{j}_{x}}\right\}_{x\in \{0,1\}^*}\) be the state classifying the oracle \(\overline{\mathcal{O}}^j\).

Assume without loss of generality, that for every \(j\in \mathbb{N}\), \(\lambda_{j+1}>2^{2^{\lambda_j}}\). If the sequence does not satisfy this requirement, we can simply take a subsequence which does.

Notice that for any input \(k_j\in \{0,1\}^{\lambda_j}\), \(G^\mathcal{O}(k_j)\) does not query the oracle on input of length less than \(\log(\lambda_j)\) by definition, and since \(G\) is a QPT algorithm, it does not query on an input of length larger than \(2^{\lambda_j}\). Similarly, for any input \(k_{j+1}\in \{0,1\}^{\lambda_{j+1}}\), \(G^\mathcal{O}(k_{j+1})\) does not query the oracle on input of length less than \(\log(\lambda_{j+1})>\log(2^{2^{\lambda_{j}}})=2^{\lambda_j}\), which is larger than the maximum query length when run on \(k_j\). In other words, the queries of \(G\) do not intersect under different security parameters in the sequence \((\lambda_j)_{j\in \mathbb{N}}\).

This allows us to define the following product state: \[\begin{align} \overline{\Phi}\mathrel{\vcenter{:}}= \left\{ \ket{\overline{\phi}^j_x}\ket{1} \right\}_{x\in U_j} \cup \left\{\ket{0^{\ell(\lvert x\rvert) }}\ket{1}\right\}_{x\in U'}. \end{align}\] Here, \(U_j\mathrel{\vcenter{:}}= \left\{x:\;x\in \{0,1\}^* \wedge \log(\lambda_j)\leq \lvert x\rvert \leq 2^{\lambda_j}\right\}\) and \(U'\mathrel{\vcenter{:}}= \{x:\forall j\in \mathbb{N}, \;x\notin U_j \}\).

Define the oracle \(\overline{\mathcal{O}}\) as the one determined by \(\overline{\Phi}\) as described in 4. Notice that for an input \(\rho\) of size \(\log(\lambda_j)\leq \lvert \rho\rvert\leq 2^{\lambda_j}\), we have \(\overline{\mathcal{O}}(\rho)=\overline{\mathcal{O}}^j(\rho)\).

To summarize, for every \(j\in \mathbb{N}\) we have

• \(G^{\overline{\mathcal{O}}^j}\) is \(\left(\frac{1}{10}\right)\)-non-deterministic on \(\frac{1}{m\lambda_j}\) fraction of inputs in \(\{0,1\}^{\lambda_j}\).

• For an input \(k_j\in \{0,1\}^{\lambda_j}\), \(G^{\overline{\mathcal{O}}^j}(k_j)\) queries the oracle on inputs of length at most \(2^{\lambda_j}\) and at least \(\log(\lambda_j)\).

• For any state \(\rho\) of size \(\log(\lambda_j)\leq \lvert \rho\rvert\leq 2^{\lambda_j}\), \(\overline{\mathcal{O}}(\rho)=\overline{\mathcal{O}}^j(\rho)\).

Therefore, there is an infinite sequence \((\lambda_j)_{j\in \mathbb{N}}\) of security parameters such that, for each \(j\in \mathbb{N}\), \(G^{\overline{\mathcal{O}}}\) is \(\left(\frac{1}{10}\right)\)-non-deterministic on an inverse-polynomial fraction \(\left(\frac{1}{\lambda_j m}\right)\) of inputs in \(\{0,1\}^{\lambda_j}\). This contradicts the correctness requirement for \(G\) (as described in 2 ). 0◻ ◻

Define the oracle \(I\) to be the element of \(\mathsf{O}_\ell\) that is the identity mapping. Define the oracle \(\mathcal{T}_{\geq w}\mathrel{\vcenter{:}}= (\mathcal{C},\mathcal{O}_{\geq w})\) where \(\mathcal{O}_{\geq w}\) only answers queries of length at least \(w\).

Consider the following hybrids of \(\mathsf{PRG}\) security experiment.

• \(\textsf{Exp}^\adv_1(\lambda):\)

  1. Sample oracle \(\mathcal{O}\gets \mathsf{O}_\ell\).

  2. Sample \(k\leftarrow \{0,1\}^\lambda\) and \(b\leftarrow \{0,1\}\).

  3. If \(b=0\), generate \(y\leftarrow \overline{G}^\mathcal{O}(k)\). Else, sample \(y\leftarrow \{0,1\}^n\).

  4. \(b'\leftarrow \adv^\mathcal{T}(y)\).

  5. If \(b'=b\), output \(1\). Otherwise, output \(0\).

• \(\textsf{Exp}^\adv_2(\lambda):\)

  1. Sample oracle \(\mathcal{O}\gets \mathsf{O}_\ell\).

  2. Sample \(k\leftarrow \{0,1\}^\lambda\) and \(b\leftarrow \{0,1\}\).

  3. If \(b=0\), generate \(y\leftarrow \overline{G}^\mathcal{O}(k)\). Else, sample \(y\leftarrow \{0,1\}^n\).

  4. \(b'\leftarrow \adv^{\mathcal{T}_{\geq \log(\lambda)}}(y)\). Notice that \(\adv\) only has access to \(\mathcal{T}_{\geq \log(\lambda)}\) in this variant.

  5. If \(b'=b\), output \(1\). Otherwise, output \(0\).

• \(\textsf{Exp}^\adv_3(\lambda):\)

  1. Sample oracle \(\mathcal{O}\gets \mathsf{O}_\ell\).

  2. Sample \(k\leftarrow \{0,1\}^{n-\lambda}\) and \(b\leftarrow \{0,1\}\).

  3. If \(b=0\), generate \(y\leftarrow {G}^\mathcal{O}(k)\). Else, sample \(y\leftarrow \{0,1\}^n\).

  4. \(b'\leftarrow \adv^{\mathcal{T}_{\geq \log(\lambda)}}(y)\).

  5. If \(b'=b\), output \(1\). Otherwise, output \(0\).

• \(\textsf{Exp}^\adv_4(\lambda):\)

  1. Sample oracle \(\mathcal{O}\gets \mathsf{O}_\ell\).

  2. Sample \(k\leftarrow \{0,1\}^{n-\lambda}\) and \(b\leftarrow \{0,1\}\).

  3. If \(b=0\), generate \(y\leftarrow {G}^I(k)\). Else, sample \(y\leftarrow \{0,1\}^n\).

  4. \(b'\leftarrow \adv^{\mathcal{T}_{\geq \log(\lambda)}}(y)\).

  5. If \(b'=b\), output \(1\). Otherwise, output \(0\).

• \(\textsf{Exp}^\adv_5(\lambda):\)

  1. Sample oracle \(\mathcal{O}\gets \mathsf{O}_\ell\).

  2. Sample \(k\leftarrow \{0,1\}^{n-\lambda}\) and \(b\leftarrow \{0,1\}\).

  3. If \(b=0\), generate \(y\leftarrow {G}^\mathcal{O}(k)\). Else, sample \(y\leftarrow \{0,1\}^n\).

  4. \(b'\leftarrow \adv^{\mathcal{C}}(y)\).

  5. If \(b'=b\), output \(1\). Otherwise, output \(0\).

It was shown in [20] using a variant of Borel-Cantelli Lemma (Lemma 2.9 in [20]) that if a primitive \(A\) exists in an idealized model and there is an adversary against another primitive \(B\) with constant advantage, say \(1/10\), (over the distribution of oracles) then this is sufficient to rule out black-box constructions of \(B\) from \(A\). More formally, Lemma 2.9 in [20] gives the following result.

For any QPT adversary \(\adv\) and large enough \(\lambda\), \[\begin{align} \Pr\left[\textsf{Exp}^\adv_1(\lambda)=1\right]\leq \frac{1}{2}+\frac{1}{10}. \end{align}\]

We now show that the experiment hybrids are indistinguishable except with small probability.

For any QPT algorithm \(\adv\), there exists a QPT algorithm \(\mathcal{B}\) such that \[\begin{align} \Pr\left[\textsf{Exp}^\adv_2(\lambda)=1\right]\leq \Pr\left[\textsf{Exp}^\mathcal{B}_1(\lambda)=1\right]. \end{align}\]

Proof. This is clear because the only difference between these experiments is that the adversary’s oracle access is restricted. 0◻ ◻

For any QPT algorithm \(\adv\), there exists a QPT algorithm \(\mathcal{B}\) such that, \[\begin{align} \Pr\left[\textsf{Exp}^\mathcal{B}_3(\lambda)=1\right]\leq \Pr\left[\textsf{Exp}^\adv_2(\lambda)=1\right]+\negl[\lambda]. \end{align}\]

Proof. Notice that the only real difference between these hybrids is that in \(\textsf{Exp}^\adv_2(\lambda)\), the evaluation \(\overline{G}^\mathcal{O}(k)\) uses \(\mathcal{O}\) for all queries. Meanwhile, in \(\textsf{Exp}^\mathcal{B}_3(\lambda)\), the evaluation of \({G}^\mathcal{O}(k)\) runs \(\overline{G}\) but with oracle access to \(\mathcal{O}\) restricted only on queries of length larger than \(\log(\lambda)\), and for shorter queries, it uses an oracle simulated using the randomness of the input (see 1).

By 2, the states generated using the random input \(k_2\) (see 1) are statistically indistinguishable from Haar random states. As a result, the simulated oracle \(\mathcal{O}_{k_2}\) is statistically indistinguishable from a CHFS oracle. Hence, if the results of the experiments can be distinguished, this can be converted into an attack against 2. 0◻ ◻

For any QPT algorithm \(\adv\) and large enough \(\lambda\), \[\begin{align} \Pr\left[\textsf{Exp}^\adv_4(\lambda)=1\right]\leq \Pr\left[\textsf{Exp}^\adv_3(\lambda)=1\right]+\frac{1}{3}+\frac{1}{\lambda}. \end{align}\]

Proof. The only difference between these hybrids is \(G\) is given access to \(I\) in \(\textsf{Exp}^\adv_4(\lambda)\) and is given access to \(\mathcal{O}\) in \(\textsf{Exp}^\adv_3(\lambda)\).

By Claim [claim:main], there exists a constant \(\lambda^*\) such that for any \(\lambda>\lambda^*\), we have \[\begin{align} \Pr_{k\gets \{0,1\}^\lambda}\left[k\in \textsf{Disagr}^{I,\mathcal{O}}_\lambda \right]< \frac{1}{\lambda}. \end{align}\] Therefore, there is at least \(1-\frac{1}{\lambda}\) probability that the key \(k\) sampled in the experiment does not belong to this set. In this case, we have \[\begin{align} \Pr\left[G^{\mathcal{O}}(k)=G^{I}(k)\right]\geq 2/3. \end{align}\] Therefore, \(\textsf{Exp}^\adv_3(\lambda)\) and \(\textsf{Exp}^\adv_4(\lambda)\) can only be distinguished with at most \[\left(1-\frac{1}{\lambda}\right)\cdot \frac{1}{3}+\frac{1}{\lambda}\cdot 1< \frac{1}{3}+\frac{1}{\lambda}\] probability. 0◻ ◻

For any QPT algorithm \(\adv\), there exists a QPT algorithm \(\mathcal{B}\) such that \[\begin{align} \Pr\left[\textsf{Exp}^\adv_5(\lambda)=1\right]\leq \Pr\left[\textsf{Exp}^\mathcal{B}_4(\lambda)=1\right]. \end{align}\]

Proof. This is clear because the only difference between these experiments is that the adversary’s oracle access is restricted. 0◻ ◻

As a result of Claims [claim:adv], [claim:1], [claim:2], [claim:3], and [claim:4], and the triangle inequality, we have for large enough \(\lambda\), \[\begin{align} \label{eq:322} \Pr\left[\textsf{Exp}^\adv_5(\lambda)=1\right]\leq \frac{1}{2}+\frac{1}{10}+\frac{1}{3} +\frac{1}{\lambda}+\negl[\lambda]= \frac{14}{15}+\frac{1}{\lambda}+\negl[\lambda]. \end{align}\tag{6}\] Notice that \(\textsf{Exp}^\adv_5(\lambda)\) is just the \(\mathsf{PRG}\) security experiment for \({G}^{I}\) against \(\adv^\mathcal{C}\). However, \({G}^{I}\) can be easily simulated with a QPT algorithm without any oracle access since \(I\) is just the identity.

On the other hand, there exists a trivial search attack, using a PSPACE oracle, against \(\mathsf{PRG}\) security, given that any polynomial-space quantum computations with classical inputs can be simulated using a PSPACE oracle. In particular, there exists an adversary \(\overline{\adv}\) such that \[\begin{align} \Pr\left[\textsf{Exp}^{\overline{\adv}}_5(\lambda)=1\right]\geq 1-\negl[\lambda]. \end{align}\] contradicting 6 above.

Therefore, there does not exist a black-box construction of a \(n\)-\(\mathsf{PRG}\) from a \(\ell\)-\(\mathsf{PRS}\). 0◻ ◻

References↩︎