1 Introduction↩︎

Research in recent years uncovered that the complexity-theoretic landscape of quantum cryptography is quite rich and in many cases different from its classical counterpart. In particular, quantum-cryptographic primitives such as quantum pseudorandom states (PRS) [1] could be used to achieve cryptographic functionality [2], [3] but are plausibly not implied by one-way functions, the most fundamental classical cryptographic primitive [4], [5]. The study of “Microcrypt”, the cryptographic landscape that is not implied by one-way functions, has emerged as a central object of inquiry in the theory of quantum cryptography, see e.g.[2], [6]–[13]. In particular, it has become an important task to map out the different primitives and their interconnections.

This work focuses on the existential relation between various notions of PRS, which are an important part of Microcrypt. A PRS is a quantum state that can be efficiently generated (starting from a classical random seed), and is computationally indistinguishable from a truly random quantum state, sampled from the Haar-random distribution.¹ We note that we are only considering pure-state PRS in this work. The original [1] definition required that the PRS is indistinguishable from random even when given an a-priori unbounded number of copies of the state.² This in particular means that if the output state contains \(m\) qubits, then any construction with \({\rm poly}(m)\)-bit seed would require computational hardness (i.e.information theoretic security would be impossible). This would not be the case if we only required \(t\)-copy security for some parameter \(t\). Namely, if we required that \(t\) copies of the PRS are indistinguishable from \(t\) copies of a Haar-random state. In particular, it is possible to achieve this notion information theoretically using so-called “state-designs” with a seed length of roughly \(tm\) bits.

Despite the above, it turns out that studying these so-called \(t\)-PRS may prove quite instructive. In particular, there is much literature on the notion of \(1\)-PRS where only one copy of the state is given to the distinguisher. This object is convenient to work with, since when given just a single copy of the state, the Haar random distribution is identical to the classical uniform distribution. Naturally, it is cryptographically non-trivial to study this object in a setting where the seed length \(k\) is shorter than the output length \(m\). Indeed, this notion of (cryptographic) \(1\)-PRS has been the focus of significant research [2], [13]–[15]. In particular, it is known that \(1\)-PRS is at the “very bottom” of Microcrypt complexity, in the following sense. First, it is known to imply cryptographic functionality (such as commitment schemes). Second, it is not information theoretically possible, so an unbounded (quantum) attacker can distinguish any \(1\)-PRS from random. And third, it seems to reside outside the classical complexity landscape, in the sense that it is not known to be violated by a bounded quantum attacker with access to a completely computationally unbounded classical attacker [16]. This is in contrast to [1]-style PRS which are known to be violated given a \(P^{\# P}\) oracle, and are known to imply more elaborate cryptographic tasks [1], [6]. Indeed, there are explicit separation results between \(1\)-PRS and PRS [17].

In light of the above, it seems instructive to study the middle ground. The setting of \(t\)-PRS where \(t\) is some asymptotically increasing polynomial function, but is a-priori determined and is not up to the adversary. These objects received fairly little attention in the literature thus far and not much is known about their place within Microcrypt. It was shown in [14][Theorem C.2] that a \(t\)-PRS implies a \(1\)-PRS with a longer output size, essentially corresponding to the entropy that can be extracted from \(t\)-copies of a Haar random state. Indeed, comparing to the entropy of a \(t\)-copy Haar-random state is the benchmark for comparing the key size.³ Since this entropy is roughly \(t m\), it will be convenient to compare \(t m\) to the key size \(k\), and we refer to the value \(t m- k\) as the “stretch” of the \(t\)-PRS. One can also infer from [10] that if \(t \ge c \cdot k\) for some global constant \(c\), then a \(t\)-PRS implies a notion called one-way puzzles, which is separated from a \(1\)-PRS. Namely, one should not expect to amplify \(1\)-PRS into that domain. Note that in all of the above, it is not even clear if \(1\)-PRS implies a \(2\)-PRS and certainly not whether it is possible to support a number of copies that grows asymptotically with the security parameter.

Very recently, Ananth and Goldin [18] (henceforth, AG) addressed this question, and showed that if the \(1\)-PRS generator has a very special form, then it is possible to use it to achieve \(t\)-PRS for any \(t\) that is polynomial in the security parameter. Their result produces a non-trivial (i.e.entropy-expanding) \(t\)-PRS only if the circuit \(G\) that generates the \(1\)-PRS does not use too many ancilla qubits (as a function of the other parameters of the \(1\)-PRS). Therefore, this result still does not rule out even a separation between \(1\)-PRS and \(2\)-PRS in the general setting. In this work, we show that it is possible to amplify \(1\)-PRS to \(t\)-PRS generically, for any polynomial \(t=t(\lambda)\) in the security parameter. Thus we show for the first time that increasing the number of copies of a PRS does not yield a stronger object.

1.1 Our Results↩︎

We show that any \(1\)-PRS can be amplified into a \(t\)-PRS for any polynomial \(t=t(\lambda)\) (where \(\lambda\) is the security parameter). Slightly more formally, we show the following result.

Let us try to explain the parameters of the theorem. Naively, we are “cranking together” \(t\) instantiations of the \(1\)-PRS in order to obtain a \(t\)-PRS. So one would expect \(\widetilde{k} \approx t k\) and \(\widetilde{m} \approx m\). However, in the actual implementation, we need some additional randomness to make the process go through, but this randomness is not consumed and is retrieved in the output (this is similar to the use of a seed in a strong extractor, which is one of the tools that we use). So we get to \(\widetilde{k} \approx t(k+k')\) and \(\widetilde{m} \approx m+k'\). The dependence on \(\left\vert {G} \right\vert\) comes from depolarizing the ancilla qubits used in the execution of \(G\). However, we have some “parasitic costs” that require an additional \(O(\lambda)\) per produced copy of the \(t\)-PRS, which leads to the expressions in the theorem.

Therefore, if we consider the “stretch” of our construction we get \(t(m-k-O(\lambda))\). We recall that \(m>k\) since the original \(1\)-PRS is non-trivial. A naive application of this theorem in a setting where \(m-k\) is small (e.g.\(m-k=1\)) might not be suitable for our amplification theorem. However, we notice that all we require is that the additive stretch, i.e.\(m-k\), is greater than \(O(\lambda)\). This can be handled easily by first sequentially repeating the \(1\)-PRS. That is, it is straightforward to go from \(1\)-PRS with parameters \((k,m)\) to \(1\)-PRS with parameters \((d k, d m)\) for any \(d={\rm poly}(\lambda)\), by concatenating \(d\) instantiations side by side. Taking the appropriate value \(d=O(\lambda)\), we get a sufficient stretch to apply our amplification and obtain a valid construction.

We note that whereas we can support arbitrary polynomial dependence of \(t\) in the security parameter, our construction increases the length of the seed as well. Therefore, it is not possible to amplify \(t\) as a function of the (new) seed length \(\widetilde{k}\). This is unavoidable if we accept the aforementioned separations. Once we have \(t \ge c \cdot k\), we get an inherently weaker primitive that we do not expect to construct from \(1\)-PRS.

1.2 Technical Overview↩︎

We start by recalling the basic idea of [18] (paraphrased for the purposes of this paper). Let \(G\) be a purified circuit that generates the \(1\)-PRS with the following syntax: \(G |{i}\rangle|{0}\rangle = |{\varphi_{{i}}}\rangle|{g_i}\rangle\), where \(i \in \{0,1\}^k\) is a seed value, \(|{\varphi_{{i}}}\rangle\) is the produced \(m\)-qubit state, and \(|{g_i}\rangle\) is a garbage state. The generation circuit can always be presented in this way without loss of generality. Let us assume for a second that there is no garbage state, so it is possible to generate a superposition of the form \[\frac{1}{2^{\lambda/2}}\sum_{i \in \{0,1\}^\lambda} (-1)^{f_1(i)} |{i}\rangle|{\varphi_{{f_2(i)}}}\rangle~,\] where \(f_1\) is a random binary function and \(f_2\) is a random function from \(\{0,1\}^\lambda\) to \(\{0,1\}^k\). Now if we take \(t\) copies of this state, we get a state of the form: \[\frac{1}{2^{\lambda t/2}}\sum_{\boldsymbol{i}\in (\{0,1\}^\lambda)^t} \underbrace{(-1)^{\sum_{j=1}^t f_1(i_j)}}_{\text{denote (-1)^{f_1(\boldsymbol{i})}}} |{\boldsymbol{i}}\rangle\underbrace{\bigotimes_{j=1}^t |{\varphi_{{f_2(i_j)}}}\rangle}_{\text{denote |{\varphi_{{f_2(\boldsymbol{i})}}}\rangle}} = \frac{1}{2^{\lambda t/2}} \sum_{\boldsymbol{i}} (-1)^{f_1(\boldsymbol{i})} |{\boldsymbol{i}}\rangle|{\varphi_{{f_2(\boldsymbol{i})}}}\rangle ~.\] An overwhelming fraction of the mass of this tensor product resides on vectors where \(\boldsymbol{i}\) contains \(t\) distinct values. This is known as the “distinct subspace” and plays a very important role in many results having to do with quantum pseudorandomness. The random phase removes all correlations between \(\boldsymbol{i}, \boldsymbol{i}'\) unless \(\boldsymbol{i}'\) is a permutation of \(\boldsymbol{i}\), we refer to this here as “symmetric decoupling”. This is by now a standard technique in quantum pseudorandomness which is not new to our work or to AG, so we will not get into the details. An important note is that in AG, a larger-order root of unity was used instead of \((-1)\), which is wasteful and, as we show in our work, not required. We therefore just use \((-1)\) from the start here, to avoid clutter in the notation.

We may therefore assume from now on that \(\boldsymbol{i}\) only ranges over distinct values, and furthermore, each \(|{\boldsymbol{i}}\rangle\) only has correlations with its symmetric counterparts. Furthermore, we notice that when restricted to distinct \(\boldsymbol{i}\), the state \(|{\varphi_{{f_2(\boldsymbol{i})}}}\rangle\) is just a \(t\)-tensor of \(t\) independent instances of the \(1\)-PRS. Applying the \(1\)-PRS property, this is computationally indistinguishable from a \(t\)-tensor of independent Haar-random states. It holds that a symmetrically decoupled state containing a \(t\)-tensor of independent Haar-random states is close to a \(t\)-copy Haar random state.⁴

Therefore, the above simplified version of AG indeed produces a state that is \(t\)-copy indistinguishable from Haar, but it uses random functions \(f_1, f_2\). This is where AG notice that it is possible to create the above \(t\)-tuple by making only \(t\) oracle calls to \(f_1, f_2\). They can therefore use the well known result by Zhandry [19] and replace \(f_1, f_2\) by \(2t\)-wise independent functions. This means that the seed length of the construction is roughly \(\widetilde{k} = 2t(\lambda+ k)\) (assuming for simplicity \(\lambda\le k\)). The output length is \(\widetilde{m} = \lambda+ m\). Therefore, the new stretch that they get is \(t \widetilde{m} - \widetilde{k} = t(m- 2 k- \lambda)\). Therefore, even for this simple variant, one needs the initial \(1\)-PRS to be at least length-doubling in order to have a chance of getting non-trivial \(t\)-PRS. Note that the sequential composition technique discussed above will not help in this case.

In fact, the above is the most favorable setting for the AG construction. Recall that we assumed that \(|{g_i}\rangle\) is empty. A central technical challenge in AG is how to address the possibility of a non-empty \(|{g_i}\rangle\). Their idea is to use quantum one-time pad (QOTP): to use randomness from the seed to completely depolarize \(|{g_i}\rangle\), i.e.to “encrypt” it so that it is effectively removed from the state. QOTP asserts that applying \(X^x Z^z\) for random \(x,z\in\{0,1\}\) to any \(1\)-qubit state completely depolarizes the state of this qubit. Their final construction, therefore, is of the form \[\frac{1}{2^{\lambda/2}}\sum_{i \in \{0,1\}^\lambda} (-1)^{f_1(i)} |{i}\rangle|{\varphi_{{f_4(i)}}}\rangle X^{f_2(i)} Z^{f_3(i)} |{g_{{f_4(i)}}}\rangle~,\] where all \(f_1, f_2, f_3, f_4\) are \(2t\)-wise independent as before (note that now \(f_4\) plays the same role as \(f_2\) in the simplified construction). The output length of \(f_2, f_3\) is exactly the qubit-length of \(|{g_i}\rangle\), which is the number of output ancilla qubits in the circuit \(G\). We denote this number by \(\mathsf{a}\).

With this addition, the parameters they achieve are \(\widetilde{k} = 2t(\lambda+ k+ 2\mathsf{a})\) and \(\widetilde{m} = \lambda+ m+ \mathsf{a}\). Now \(t \widetilde{m} - \widetilde{k} = t(m-2 k- \mathsf{a}- \lambda)\), so it is not even enough that \(m> 2 k\), but it also needs to account for the \(\mathsf{a}\) qubits of the ancilla. Therefore their result is only applicable in a fairly narrow regime of parameters.

1.2.0.1 Our Improvements.

We would like to use the same components as AG, but ensure that we obtain a meaningful result in all parameter regimes. Conceptually, our techniques can be viewed as handling two artifacts separately.

First, in order to handle the length-doubling constraint, we propose a tighter analysis of the AG approach, showing that the full strength of Zhandry’s result is not required here. Indeed, whereas \(f_1\) is required to be \(2t\)-wise independent, the state after symmetric decoupling is, well, symmetric, and therefore it suffices to take \(f_2, f_3, f_4\) to only be \(t\)-wise independent. Therefore, for the simple variant without ancilla, we can obtain \(t \widetilde{m} - \widetilde{k} = t(m- k- \lambda)\), where we recall that \(O(\lambda)\) slackness can be handled by sequential composition.

Second, we need to handle the dependence on \(\mathsf{a}\). To this end, we use a similar technique to the one used by Cavalar et al. [13] in the context of quantum meta-complexity. While their work is fairly technical, we believe that there is an important underlying intuitive insight. It is well established that QOTP requires a key that is twice the length of the state to be encrypted (the “message state”). However, this is only really required if the message state is fully entangled with an adversarial environment (e.g.encrypting half of an EPR pair). Indeed, for a multi-qubit pure state, it suffices to use a secret key of (roughly) the message-length, assuming the existence of a common random string. To explain this, consider a maximally entangled state \((U_1\otimes U_2) \sum_x |{x}\rangle |{x}\rangle\), where \(U_1, U_2\) are arbitrary. Then it suffices to QOTP encrypt only half of the qubits (which requires \(2n\) bits, the same as the message length) in order to fully randomize the state. Viewed differently, it suffices to trace out half of the state in order for the remainder to become uniform, and the tracing out is implemented by a depolarizing QOTP.

The idea in [13] is to use a quantum strong extractor. Intuitively, applying an extractor scrambles a \(2n\)-qubit pure state so that the entanglement between the first and second half is roughly \(n\), which allows to apply the above intuition. Concretely, if we apply a unitary \(2\)-design (e.g.a random Clifford) to a pure quantum state, the marginal distribution of the first \(n-\log(1/\varepsilon)\) qubits becomes \(\varepsilon\)-close to maximally mixed. Therefore it suffices to depolarize the remaining \(n+\log(1/\varepsilon)\) qubits, using a key of length \(2(n+\log(1/\varepsilon))\) to achieve the required result. This insight can be generalized to non-pure states so long as the min-entropy of the state conditioned on the environment could be lower-bounded (recall that entanglement causes the conditional entropy to be negative). However, for our analysis the pure version suffices. Note that the strong extractor property means that the randomness used to generate the \(2\)-design can also be a part of the output.

Finally, we take \(\varepsilon = 2^{-\lambda}\) and obtain the following construction: \[\frac{1}{2^{\lambda/2}}\sum_{i \in \{0,1\}^\lambda} (-1)^{f_1(i)} |{i}\rangle|{f_5(i)}\rangle |{\varphi_{{f_4(i)}}}\rangle X^{f_2(i)} Z^{f_3(i)} U_{f_5(i)} |{g_{{f_4(i)}}}\rangle~,\] where \(U\) is a family of unitary \(2\)-designs, \(f_1\) is a \(2t\)-wise independent function with output length \(1\), \(f_2, f_3, f_4, f_5\) are \(t\)-wise independent with output lengths \(\mathsf{a}/2+\lambda, \mathsf{a}/2+\lambda, k, \kappa\), where \(\kappa\) is the seed length of the \(2\)-design. Note that \(X^{f_2(i)} Z^{f_3(i)}\) only act on the first \(\mathsf{a}/2+\lambda\) qubits of the state \(U_{f_5(i)} |{g_{{f_4(i)}}}\rangle\). We therefore achieve \(\widetilde{k} = 2t\lambda+ t(k+ \mathsf{a}+ 2 \lambda+ \kappa)\), \(\widetilde{m} = \lambda+ m+ \mathsf{a}+ \kappa\). This finally implies that for our construction \(t \widetilde{m} - \widetilde{k} = t(m- k-3\lambda)\), and therefore, together with sequential repetition if needed, we obtain a \(t\)-PRS for any input \(1\)-PRS.

2 Preliminaries↩︎

2.1 Quantum Information↩︎

For a system of \(m\) qubits residing in register \(R\) we use \(\left\vert {R} \right\vert\) to denote the dimension of the system, that is, \(\left\vert {R} \right\vert = 2^m\). We now define properties of linear operators acting on quantum systems.

Let \({\cal H}\cong {\mathbb{C}}^{2^m}\) be a Hilbert space over \(m\) qubits, and \(A\) a linear operator acting on \({\cal H}\). We say that \(A\) is a sub-normalized state if it is PSD and \(\mathop{\mathrm{Tr}}[A] \leq 1\). The trace norm of \(A\) is defined by \[{\left\| {{A}} \right\|_1} = \mathop{\mathrm{Tr}}\left[ \sqrt{A^{\dagger} A} \right] = \text{sum of singular values of A} ~.\] We say that \(A\) is a quantum state if it is sub-normalized and \(\mathop{\mathrm{Tr}}[A] = 1\). If \(\rho, \sigma\) are sub-normalized then we write \(\rho \preceq \sigma\) when \(\sigma - \rho\) is PSD, i.e. \(0 \preceq \sigma - \rho\). The trace distance of quantum states \(\rho, \sigma\) is defined by \[\mathop{\mathrm{TD}} \left({\rho}, {\sigma} \right) = \frac{1}{2} \left\| {{\rho} - {\sigma}} \right\|_1 ~.\]

We move to definitions that consider a tensor product of \(t\) identical Hilbert spaces.

We list some important properties of the symmetric subspace (see [20] for a detailed discussion):

• The operator \(\Pi_{\mathrm{Sym}}^{{m},{t}} = \frac{1}{t!} \sum_{\pi \in S_t} P_{\pi}\) is a projector onto the symmetric subspace. We denote the normalized projector by \(\rho_{\mathrm{Sym}}^{{m},{t}} = \frac{\Pi_{\mathrm{Sym}}^{{m},{t}}}{\mathop{\mathrm{Tr}}\left[ \Pi_{\mathrm{Sym}}^{{m},{t}} \right]}\).

• \(\dim(\mathrm{Sym}({m},{t})) = \mathop{\mathrm{Tr}}\left[ \Pi_{\mathrm{Sym}}^{{m},{t}} \right] = \binom{2^m + t - 1}{t}\).

• \(\rho_{\mathrm{Sym}}^{{m},{t}} = {\mathbb{E}}_{|{\psi}\rangle \gets \mu_m} \left[ |{{\psi}}\rangle\langle{{\psi}}|^{\otimes t} \right]\) where \(\mu_m\) is the Haar random distribution of states over \(m\) qubits.

• For any system of \(m\) qubits with subsystem of \(n\) qubits residing in register \(C\), the projectors \(\Pi_{\mathrm{Sym}}^{{m},{t}}\) and \(\Pi_{\mathrm{dis}, {C}}^{n, t}\) commute, i.e. \(\Pi_{\mathrm{Sym}}^{{m},{t}} \Pi_{\mathrm{dis}, {C}}^{n, t} = \Pi_{\mathrm{dis}, {C}}^{n, t} \Pi_{\mathrm{Sym}}^{{m},{t}}\).

We prove a simple claim that shows that projecting the normalized projector of the symmetric subspace of the system to the distinct subspace of a subsystem doesn’t end up too far.

2.2 Pseudorandom States↩︎

A quantum polynomial time (QPT) algorithm is a sequence of quantum circuits \(C = \left\{ {C_\lambda} \right\}_\lambda\) which are polynomially bounded, that is, there exists a polynomial \(p(\cdot)\) such that the circuits \(C_\lambda\) are of size at most \(p(\lambda)\).⁵ A unitary quantum algorithm is a sequence of quantum circuits such that each \(C_\lambda\) is a unitary mapping. If the output of a quantum algorithm is a classical bit, we call it a distinguisher (or distinguishing adversary).

For such a distinguisher we define acceptance probability on a sequence of sub-normalized states \(\rho = \left\{ {\rho_{\lambda}} \right\}_{\lambda}\), denoted \(\Pr[C_\lambda(\rho_\lambda)=1]\), to be \(0\) if \(\mathop{\mathrm{Tr}}[\rho_\lambda] = 0\) and otherwise \(\Pr \left[ C_\lambda\left(\frac{\rho_\lambda}{{\left\| {{\rho_\lambda}} \right\|_1}} \right) = 1 \right] \cdot \mathop{\mathrm{Tr}}[\rho_\lambda]\). With this convention, the usual definitions of statistical and computational indistinguishability of quantum state ensembles extend directly to sub-normalized states. We use the notation \({\ \overset{c}{\approx} \ }\) to denote that states are computationally indistinguishable, and \({\ \overset{s}{\approx} \ }\) to denote that states are statistically indistinguishable.

Note that the above proposition is true also for distinguishers that are not polynomially bounded, and in fact we get statistical indistinguishability which implies computational indistinguishability.

We now give a definition of a keyed procedure that generates a pure quantum state. This will allow us to argue about the cryptographic properties of the output.

We can now define pseudorandom states which are generated by a pure state generator and have randomness properties.

We frequently write \(t\)-PRS instead of \((k, m, t)\)-PRS when the parameters \(k, m\) are either arbitrary or clear from the context. As explained in the introduction, we focus on the non-trivial regime where \(k< t m\), and if a \(t\)-PRS satisfies this condition we say it has a stretch of \(t m- k\).

2.3 Quantum Extractor↩︎

We first present definitions of min-entropy that will be useful for applying quantum extractors.

We define quantum strong extractors and state a theorem that enables the use of \(2\)-designs as quantum strong extractors under certain conditions.

2.4 Simulating symmetrization of states↩︎

We introduce a symmetrization simulator that takes \(t\) pure states as input and outputs a pure state representing a symmetrization of the input, entangled with a random \(t\)-tuple of distinct elements. While this simulator was originally introduced by [18], we use a slightly modified variant that restricts the range of the \(t\)-tuple. Furthermore, we analyze the output density matrix of the simulator, which is later used to reduce \(t\)-PRS security to \(1\)-PRS security.

2.4.0.1 Symmetrization Simulator.

Given \(|{\phi_1}\rangle, \ldots, |{\phi_t}\rangle\), consider the following algorithm: Sample a random distinct \(t\)-tuple \(\boldsymbol{i} \gets \mathrm{dis}(n,t)\) and output the quantum state \[\textrm{Sim}_{\boldsymbol{i}}^t \left({|{\phi_1}\rangle, \ldots, |{\phi_t}\rangle} \right) \mathrel{\vcenter{:}}= \frac{1}{\sqrt{t!}}\sum_{\pi \in S_t} \bigotimes_{j=1}^t |{i_{\pi(j)}}\rangle|{\phi_{\pi(j)}}\rangle ~.\]

2.5 Auxiliary Claims↩︎

For a seeded function family \({\cal F}\), we denote \(f \gets {\cal F}\) for sampling a random seed for a function from the family, and associate \(f\) both with the seed itself and with the function it defines. We denote by \(\ell_{{\cal F}}\) the seed length for sampling a function from \({\cal F}\). We state some useful claims that will help us prove that our construction is a \(t\)-PRS.

3 Constructing \(t\)-PRS from \(1\)-PRS↩︎

3.1 Parameter Setup↩︎

Let \(\kappa, k, m, \mathsf{a}, n, t \in {\mathbb{N}}\). Let \(G\) be a pure state generator for an ensemble \(\left\{ {|{\varphi_i}\rangle} \right\}_i\) with key length \(k\), output register \(A\) of \(m\) qubits, and a garbage register \(B\) of \(\mathsf{a}\) qubits, such that for each key \(i\), \(G(i) = |{\varphi_i}\rangle_A |{g_i}\rangle_B\). Let \(\varepsilon\in (0, 1)\) be such that \(\ell = \left\lfloor \frac{\mathsf{a}}{2} - \log \left( \frac{1}{\varepsilon} \right) \right\rfloor \geq 0\). Let \({\cal U}= \left\{ {U^r} \right\}_r\) be an efficiently implementable unitary \(2\)-design on the \(\mathsf{a}\)-qubit register \(B\) with seed length \(\kappa\). Denote by \(B_2\) the register containing the last \(q \mathrel{\vcenter{:}}= \mathsf{a}- \ell\) qubits of system \(B\).

Let \({\cal F}_1 \subseteq \{0,1\}^n \to \{0,1\}\) be a \(2t\)-wise independent function family and \({\cal F}_2 \subseteq \{0,1\}^n \to \{0,1\}^q\), \({\cal F}_3 \subseteq \{0,1\}^n \to \{0,1\}^q\), \({\cal F}_4 \subseteq \{0,1\}^n \to \{0,1\}^k\), \({\cal F}_5 \subseteq\{0,1\}^n \to \{0,1\}^\kappa\) all \(t\)-wise independent function families.

3.2 Construction↩︎

Let \(f_i \in {\cal F}_i\), and define the following state. \[\begin{align} |{\psi_{f_1, f_2, f_3, f_4, f_5}}\rangle &= \frac{1}{\sqrt{2^n}} \sum_{i \in \{0,1\}^n} (-1)^{f_1(i)} |{f_5(i)}\rangle_R \left( X_{B_2}^{f_2(i)} Z_{B_2}^{f_3(i)} \right) U^{f_5(i)}_B \, G(f_4(i))_{AB} \, |{i}\rangle_C \\ &= \frac{1}{\sqrt{2^n}} \sum_{i \in \{0,1\}^n} (-1)^{f_1(i)} |{f_5(i)}\rangle_R \left( X_{B_2}^{f_2(i)} Z_{B_2}^{f_3(i)} \right) U^{f_5(i)}_B |{\varphi_{f_4(i)}}\rangle_A |{g_{f_4(i)}}\rangle_B |{i}\rangle_C \end{align}\]

3.3 Our Amplification Theorem↩︎

Beyond security, our construction preserves the “stretch” property of the \(1\)-PRS relative to \(t\). That is, a \(1\)-PRS with stretch \(s\) yields a \(t\)-PRS with stretch at least \(ts\). In fact, by polynomially amplifying the stretch of the \(1\)-PRS, it is possible to construct a \(t\)-PRS with any stretch \(ts\) for polynomially bounded \(s\).

3.4 Proof of Theorem 15↩︎

3.4.0.1 Key length.

The key of \(\widetilde{G}\) consists of all the seeds to the function families \({\cal F}_1, \dots, {\cal F}_5\). By Theorem 14, \[\label{size95of95seed95spaces} \begin{gather} \ell_{{\cal F}_1} = 2t \cdot n, \\ \ell_{{\cal F}_2} = \ell_{{\cal F}_3} = t \cdot \max \left\{ {n, q} \right\} = t \max \left\{ {n, \mathsf{a}- \left\lfloor \frac{\mathsf{a}}{2} - \log \left(\frac{1}{\varepsilon} \right) \right\rfloor} \right\} = t \max \left\{ {n, \left\lceil \frac{\mathsf{a}}{2} + \log \left(\frac{1}{\varepsilon} \right) \right\rceil} \right\}, \\ \ell_{{\cal F}_4} = t \cdot \max \left\{ {n, k} \right\}, \quad \ell_{{\cal F}_5} = t \cdot \max \left\{ {n, \kappa} \right\} \end{gather}\tag{1}\] So the total length of the key is \[\widetilde{k} = t \left( 2n + 2 \max \left\{ {n, \left\lceil \frac{\mathsf{a}}{2} + \log \left(\frac{1}{\varepsilon} \right) \right\rceil} \right\} + \max \left\{ {n, k} \right\} + \max \left\{ {n, \kappa} \right\} \right) ~.\]

3.4.0.2 Output length.

The output length is simply the total number of qubits in registers \(R, A, B, C\), which is \[\widetilde{m} = \kappa + m+ \mathsf{a}+ n ~.\]

3.4.0.3 The Generator is QPT.

Theorem 14 ensures that all the functions \(f_1, \dots, f_5\) can be evaluated efficiently, and the \(2\)-design as well as \(G\) are efficiently computable. Therefore \(\widetilde{G}\) also has an efficient implementation which includes preparing a uniform superposition over \(i\), applying the gates of \(G\), and using controlled-\(X\), controlled-\(Z\), controlled-\(U\) (for the \(2\)-design) and controlled-phase gates.

3.4.0.4 Our Hybrids.

We turn to proving the security of our construction using a sequence of hybrids. Our goal is to show that \(t\) copies of a state generated by \(\widetilde{G}\) is computationally indistinguishable from \(t\) copies of a Haar-random state over the same dimensions.

We introduce a sequence of hybrids \(\mathsf{H}_i\), where each hybrid is simply a density matrix. The hybrid \(\mathsf{H}_0\) will denote a \(t\)-wise application of the generator \(\widetilde{G}\) on a random seed. The final hybrid \(\mathsf{H}_4\) will be density matrix of a \(t\)-copy Haar-random state. We will show that \(\mathsf{H}_0 {\ \overset{c}{\approx} \ }\mathsf{H}_4\) by the following outline:

• The hybrid \(\mathsf{H}_0\) is just the \(t\)-wise density matrix of our construction.

• The hybrid \(\mathsf{H}_1\) is a restriction to the so-called distinct subspace.

  We show that \(\mathsf{H}_0 {\ \overset{s}{\approx} \ }\mathsf{H}_1\) by showing that most of the mass of our density matrix is concentrated in the distinct subspace.

• The hybrid \(\mathsf{H}_2\) is is obtained from the hybrid \(\mathsf{H}_1\) by “depolarizing” the ancilla register (\(B\)) as well as the extractor-key register (\(R\)), that is, replacing the contents of registers \(R, B\) with maximally mixed states.

  We show that \(\mathsf{H}_1 {\ \overset{s}{\approx} \ }\mathsf{H}_2\) by showing that the application of the extractor followed by the quantum one-time pad in register \(B\) of the hybrid \(\mathsf{H}_1\) (with the key of the extractor stored in register \(R\)), mixes the states in these registers such that they look almost uniformly random.

• The hybrid \(\mathsf{H}_3\) is obtained from the hybrid \(\mathsf{H}_2\) by replacing each of the \(1\)-PRS states (in register \(A\)) with a maximally mixed state.

  Using the security of the \(1\)-PRS, we show that \(\mathsf{H}_2 {\ \overset{c}{\approx} \ }\mathsf{H}_3\).

• The hybrid \(\mathsf{H}_4\) is the density matrix of a \(t\)-copy Haar-random state.

  We show that \(\mathsf{H}_3 {\ \overset{s}{\approx} \ }\mathsf{H}_4\) by showing that the hybrid \(\mathsf{H}_3\) is a sub-normalized state proportional to the projection onto the intersection of the symmetric and distinct subspaces, and captures most of the mass of the normalized projector onto the symmetric subspace, which coincides with hybrid \(\mathsf{H}_4\).

Combining all these Hybrids gives \[\mathsf{H}_0 {\ \overset{s}{\approx} \ } \mathsf{H}_1 {\ \overset{s}{\approx} \ } \mathsf{H}_2 {\ \overset{c}{\approx} \ } \mathsf{H}_3 {\ \overset{s}{\approx} \ } \mathsf{H}_4 ~,\] which completes the security proof of the \(t\)-PRS.

3.4.0.5 Formal Hybrid Definitions and Claims.

We define \(\mathsf{H}_0\) as \[\begin{align}[t] \mathsf{H}_0 &\mathrel{\vcenter{:}}= {\mathbb{E}}_{f_1, \dots, f_5} \left[ \left( \widetilde{G}(f_1, \dots, f_5) \, \widetilde{G}(f_1, \dots, f_5){^\dagger} \right) ^{\otimes t} \right] \\ &= {\mathbb{E}}_{f_1, \dots, f_5} \left[ \frac{1}{2^{nt}} \sum_{\boldsymbol{i}, \boldsymbol{i'} \in (\{0,1\}^n)^t} \bigotimes_{j=1}^t (-1)^{f_1(i_j) - f_1(i'_j)} \, V^{f_2, f_3, i_j}_{B_2} \, U^{f_5(i_j)}_B \rho^{f_4, f_5, i_j, i'_j}_{RABC} \left( U^{f_5(i'_j)}_B \right)^{\dagger} \left( V^{f_2, f_3, i'_j}_{B_2} \right)^{\dagger} \right] \end{align}\] where we denote \(V^{f_2, f_3, i_j}_{B_2} = X^{f_2(i_j)}_{B_2} Z^{f_3(i_j)}_{B_2}\), \[\rho^{f_4, f_5, i_j, i'_j}_{RAB} = |{{f_5(i_j)}}\rangle\langle{{f_5(i'_j)}}|_R \otimes |{{\varphi_{f_4(i_j)}}}\rangle\langle{{\varphi_{f_4(i'_j)}}}|_A \otimes |{{g_{f_4(i_j)}}}\rangle\langle{{g_{f_4(i'_j)}}}|_B ~,\] \[\label{tau95rabc} \rho^{f_4, f_5, i_j, i'_j}_{RABC} = \rho^{f_4, f_5, i_j, i'_j}_{RAB} \otimes |{{i_j}}\rangle\langle{{i'_j}}|_C ~,\tag{2}\] and writing \({\mathbb{E}}_{f_i}\) throughout the proof is a shorthand for \({\mathbb{E}}_{f_i \gets {\cal F}_i}\). We further denote for any pair of \(t\)-tuples \(\boldsymbol{i}, \boldsymbol{i'}\), \[\label{tau95rab} \tau^{\boldsymbol{i}, \boldsymbol{i'}}_{RAB} = {\mathbb{E}}_{f_2, \dots, f_5} \left[ \bigotimes_{j=1}^t V^{f_2, f_3, i_j}_{B_2} \; U^{f_5(i_j)}_B \; \rho^{f_4, f_5, i_j, i'_j}_{RAB} \; \left( U^{f_5(i'_j)}_B \right)^{\dagger} \left( V^{f_2, f_3, i'_j}_{B_2} \right)^{\dagger} \right] ~.\tag{3}\]

We define \(\mathsf{H}_1\) as the projection of \(\mathsf{H}_0\) onto the distinct subspace of register \(C\). This results in the following sub-normalized state. \[\mathsf{H}_1 \mathrel{\vcenter{:}}= \Pi_{\mathrm{dis}, {C}}^{n, t} \;\mathsf{H}_0 \;\Pi_{\mathrm{dis}, {C}}^{n, t}\]

Next, we show that the two hybrids are indistinguishable.

We now give an explicit form for \(\mathsf{H}_1\).

The next step is showing that after applying the extractor and a quantum one-time pad in registers \(B\) of \(\mathsf{H}_1\), the resulting sub-normalized state is almost maximally mixed in registers \(B\) and \(R\).

We formally define \[\label{def95hbd952} \mathsf{H}_2 \mathrel{\vcenter{:}}= \frac{1}{2^{nt}} \sum_{\boldsymbol{i} \in \mathrm{dis}(n,t), \pi \in S_t} {\mathbb{E}}_{f_4} \left[ \bigotimes_{j=1}^t \frac{I_{R}}{|R|} \otimes \frac{I_{B}}{|B|} \otimes |{{\varphi_{f_4(i_j)}}}\rangle\langle{{\varphi_{f_4(i_j)}}}|_A \otimes |{{i_j}}\rangle\langle{{i_j}}|_C \right] P_{\pi} ~,\tag{4}\]

and show that

We define \(\mathsf{H}_3\) by replacing each of the \(1\)-PRS states in register \(A\) of \(\mathsf{H}_2\) with a maximally mixed state. Formally, \[\mathsf{H}_3 \mathrel{\vcenter{:}}= \frac{1}{2^{nt}} \sum_{\boldsymbol{i} \in \mathrm{dis}(n,t), \pi \in S_t} \left( \bigotimes_{j=1}^t \frac{I_{R}}{|R|} \otimes \frac{I_{B}}{|B|} \otimes \frac{I_{A}}{|A|} \otimes |{{i_j}}\rangle\langle{{i_j}}|_{C} \right) P_{\pi} ~.\]

We use the security of the \(1\)-PRS to show that

Finally, recall that the density matrix of a \(t\)-copy Haar random state equals the normalized projector onto the symmetric subspace. Hence we formally define our last hybrid as \[\mathsf{H}_4 \mathrel{\vcenter{:}}= {\mathbb{E}}_{|{\psi}\rangle \gets \mu_{\widetilde{m}}} \left[ |{{\psi}}\rangle\langle{{\psi}}|^{\otimes t} \right] = \rho_{\mathrm{Sym}}^{{\widetilde{m}},{t}} ~.\]

We show that

Acknowledgments.

The authors are supported by the Horizon Europe Research and Innovation Program via ERC Project ACQUA (Grant 101087742).

References↩︎

---

1. If we think of quantum states as unit vectors in a complex Hilbert space, then the Haar random distribution can be thought of as sampling a random vector over the unit sphere.↩︎

2. We recall that, in contrast to the classical setting, the more copies of the same quantum states that are given, the more information about that state can be extracted.↩︎

3. One could also consider comparing against the randomness-complexity of a state \(t\)-design, but the numbers are very similar.↩︎

4. This is not a contribution of our paper so we don’t get into details, but at the level of “footnote intuition” we can explain that being symmetrically invariant means that the \(t\)-fold state behaves the same as \(t\)-copies of one state, and since each marginal is random, this is indeed similar to \(t\)-copies of a Haar random state.↩︎

5. Note that this definition is non-uniform but a uniform version can be defined analogously in a straightforward manner.↩︎

6. \(P(\rho, \sigma) = \sqrt{1 - F(\rho, \sigma)^2}\) where \(F(\rho, \sigma) = {\left\| {{\sqrt{\rho} \sqrt{\sigma}}} \right\|_1}\) is the fidelity function. Also note that \(\mathop{\mathrm{TD}} \left({\rho}, {\sigma} \right) \leq P(\rho, \sigma)\).↩︎

7. W.l.o.g. we assume that \(\kappa\geq \lambda\), as the seed length of the \(2\)-design can be trivially extended. Similarly, assume that \(\widehat{\mathsf{a}}\) is even.↩︎

8. W.l.o.g. we can assume \(\widehat{k} \geq \lambda\), since we can always take \(d \geq \lambda\).↩︎