Generic Number-of-Copies Amplification for Pseudorandom States Zvika Brakerski and Miri Zenilman Weizmann Institute of Science
arXiv:2606.29325v1 [quant-ph] 28 Jun 2026
{zvika.brakerski, miri.butel}@weizmann.ac.il
Abstract We show that any quantum pseudorandom state that is secure against single-copy distinguishers, i.e. a 1-PRS, can be amplified to t-copy security, i.e. to a t-PRS, without additional assumptions, for any polynomial t in the security parameter. Prior work (Ananth and Goldin, arXiv 2025) was only able to show this for a restricted class of 1-PRS constructions, namely ones whose generators only use a small number of ancilla qubits. Technically, we show that by carefully accounting for the randomness that is used in the construction, and using quantum extractors, it is possible to eliminate an ancilla register of any length and obtain a meaningful t-PRS outcome.
Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 3 4
2 Preliminaries 6 2.1 Quantum Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Pseudorandom States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Quantum Extractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Simulating symmetrization of states . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Auxiliary Claims . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Constructing t-PRS from 1-PRS 3.1 Parameter Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Our Amplification Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
13 13 13 13 14
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, quantumcryptographic primitives such as quantum pseudorandom states (PRS) [JLS18] could be used to achieve cryptographic functionality [MY22; AQY22] but are plausibly not implied by one-way functions, the most fundamental classical cryptographic primitive [Kre21; KQST23]. 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. [MY22; AGQY22; BCQ23; BGH+23; MY24; KT24; BJ24; CGG24; CCC+25]. 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.1 We note that we are only considering pure-state PRS in this work. The original [JLS18] definition required that the PRS is indistinguishable from random even when given an a-priori unbounded number of copies of the state.2 This in particular means that if the output state contains m qubits, then any construction with 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 Haarrandom 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 [MY22; GJMZ23; CCC+25; BCN25]. 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 [LMW24]. This is in contrast to [JLS18]-style PRS which are known to be violated given a P #P oracle, and are known to imply more elaborate cryptographic tasks [JLS18; AGQY22]. Indeed, there are explicit separation results between 1PRS and PRS [CCS25]. 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 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.
2
not much is known about their place within Microcrypt. It was shown in [GJMZ23][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.3 Since this entropy is roughly tm, it will be convenient to compare tm to the key size k, and we refer to the value tm − k as the “stretch” of the t-PRS. One can also infer from [KT24] that if t ≥ c · 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 [AG25] (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(λ) 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(λ) (where λ is the security parameter). Slightly more formally, we show the following result. Theorem 1.1 (Informal). Let G be an efficient 1-PRS generator with seed length k and output e which is a t-PRS with seed length length m, and let t = poly(λ). Then there exists an efficient G ′ ′ ′ e k = t(k + k + O(λ)) and output length m e = m + k , where k ≤ poly(λ, |G|) (where |G| is the size of the purified circuit that generates the 1-PRS). 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 e k ≈ tk and m e ≈ 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 e k ≈ t(k + k ′ ) and m e ≈ m + k ′ . The dependence on |G| comes from depolarizing the ancilla qubits used in the execution of G. However, we have some “parasitic costs” that require an additional O(λ) 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(λ)). 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(λ). 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 (dk, dm) for any d = poly(λ), 3 One could also consider comparing against the randomness-complexity of a state t-design, but the numbers are very similar.
3
by concatenating d instantiations side by side. Taking the appropriate value d = O(λ), 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 e k. This is unavoidable if we accept the aforementioned separations. Once we have t ≥ c · 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 [AG25] (paraphrased for the purposes of this paper). Let G be a purified circuit that generates the 1-PRS with the following syntax: G|i⟩|0⟩ = |φi ⟩|gi ⟩, where i ∈ {0, 1}k is a seed value, |φi ⟩ is the produced m-qubit state, and |gi ⟩ 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 1 2λ/2
X
(−1)f1 (i) |i⟩|φf2 (i) ⟩ ,
i∈{0,1}λ
where f1 is a random binary function and f2 is a random function from {0, 1}λ to {0, 1}k . Now if we take t copies of this state, we get a state of the form: 1 2λt/2
X
Pt
(−1) j=1 f1 (ij ) |i⟩ | {z } λ t
i∈({0,1} )
denote (−1)f1 (i)
t O
|φf2 (ij ) ⟩ =
j=1
|
{z
1 2λt/2
X
(−1)f1 (i) |i⟩|φf2 (i) ⟩ .
i
}
denote |φf2 (i) ⟩
An overwhelming fraction of the mass of this tensor product resides on vectors where 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 i, i′ unless i′ is a permutation of 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 i only ranges over distinct values, and furthermore, each |i⟩ only has correlations with its symmetric counterparts. Furthermore, we notice that when restricted to distinct i, the state |φf2 (i) ⟩ is just a t-tensor of t independent instances of the 1PRS. 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 ttensor of independent Haar-random states is close to a t-copy Haar random state.4 Therefore, the above simplified version of AG indeed produces a state that is t-copy indistinguishable from Haar, but it uses random functions f1 , f2 . This is where AG notice that it is possible to create the above t-tuple by making only t oracle calls to f1 , f2 . They can therefore use the well 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.
4
known result by Zhandry [Zha12] and replace f1 , f2 by 2t-wise independent functions. This means that the seed length of the construction is roughly e k = 2t(λ + k) (assuming for simplicity λ ≤ k). The output length is m e = λ+m. Therefore, the new stretch that they get is tm− e e k = t(m−2k −λ). 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 |gi ⟩ is empty. A central technical challenge in AG is how to address the possibility of a nonempty |gi ⟩. Their idea is to use quantum one-time pad (QOTP): to use randomness from the seed to completely depolarize |gi ⟩, 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 ∈ {0, 1} to any 1-qubit state completely depolarizes the state of this qubit. Their final construction, therefore, is of the form 1 2λ/2
X
(−1)f1 (i) |i⟩|φf4 (i) ⟩X f2 (i) Z f3 (i) |gf4 (i) ⟩ ,
i∈{0,1}λ
where all f1 , f2 , f3 , f4 are 2t-wise independent as before (note that now f4 plays the same role as f2 in the simplified construction). The output length of f2 , f3 is exactly the qubit-length of |gi ⟩, which is the number of output ancilla qubits in the circuit G. We denote this number by a. With this addition, the parameters they achieve are e k = 2t(λ + k + 2a) and m e = λ + m + a. e Now tm e − k = t(m − 2k − a − λ), so it is not even enough that m > 2k, but it also needs to account for the a qubits of the ancilla. Therefore their result is only applicable in a fairly narrow regime of parameters. 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 f1 is required to be 2t-wise independent, the state after symmetric decoupling is, well, symmetric, and therefore it suffices to take f2 , f3 , f4 to only be t-wise independent. Therefore, for the simple variant without ancilla, we can obtain tm e −e k = t(m − k − λ), where we recall that O(λ) slackness can be handled by sequential composition. Second, we need to handle the dependence on a. To this end, we use a similar technique to the one used by Cavalar et al. [CCC+25] 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 P common random string. To explain this, consider a maximally entangled state (U1 ⊗ U2 ) x |x⟩|x⟩, where U1 , U2 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.
5
The idea in [CCC+25] 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/ε) qubits becomes ε-close to maximally mixed. Therefore it suffices to depolarize the remaining n + log(1/ε) qubits, using a key of length 2(n + log(1/ε)) 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 ε = 2−λ and obtain the following construction: X 1 (−1)f1 (i) |i⟩|f5 (i)⟩|φf4 (i) ⟩X f2 (i) Z f3 (i) Uf5 (i) |gf4 (i) ⟩ , 2λ/2 λ i∈{0,1}
where U is a family of unitary 2-designs, f1 is a 2t-wise independent function with output length 1, f2 , f3 , f4 , f5 are t-wise independent with output lengths a/2 + λ, a/2 + λ, k, κ, where κ is the seed length of the 2-design. Note that X f2 (i) Z f3 (i) only act on the first a/2 + λ qubits of the state Uf5 (i) |gf4 (i) ⟩. We therefore achieve e k = 2tλ + t(k + a + 2λ + κ), m e = λ + m + a + κ. This finally e implies that for our construction tm e − k = t(m − k − 3λ), 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 |R| to denote the dimension of the system, that is, |R| = 2m . We now define properties of linear operators acting on quantum systems. m Let H ∼ = C2 be a Hilbert space over m qubits, and A a linear operator acting on H. We say that A is a sub-normalized state if it is PSD and Tr[A] ≤ 1. The trace norm of A is defined by h√ i ∥A∥1 = Tr A† A = sum of singular values of A . We say that A is a quantum state if it is sub-normalized and Tr[A] = 1. If ρ, σ are sub-normalized then we write ρ ⪯ σ when σ − ρ is PSD, i.e. 0 ⪯ σ − ρ. The trace distance of quantum states ρ, σ is defined by 1 TD (ρ, σ) = ∥ρ − σ∥1 . 2 We move to definitions that consider a tensor product of t identical Hilbert spaces. Definition 2.1 (The Distinct Set and The Distinct Subspace). Let n, t ∈ N. • The distinct set is defined as dis(n, t) = {(i1 , . . . , it ) | ∀j ̸= k
ij ̸= ik } ⊆ ({0, 1}n )t .
• The distinct subspace is the subspace spanned by the distinct set, i.e., span {|i⟩ | i ∈ dis(n, t)} ⊆ n (C2 )⊗t , where if i = (i1 , . . . , it ) then |i⟩ is a shorthand for |i1 ⟩ ⊗ · · · ⊗ |it ⟩. 6
• The projector onto the distinct subspace is defined as X Πn,t = |i⟩⟨i| . dis i∈dis(n,t)
If a system consists of t copies of registers CE where C P is a register of n qubits, then the projector onto the distinct subspace of C is Πn,t = I ⊗ E i∈dis(n,t) |i⟩⟨i|C . dis,C m Definition 2.2 (Symmetric Subspace). Let m, t ∈ N and a Hilbert space over m qubits, H ∼ = C2 . Consider the Hilbert space H′ = H⊗t . For any permutation π ∈ St define the unitary permutation operator
t O
X
Pπ =
|xj ⟩⟨xπ(j) |
x1 ,...,xt ∈{0,1}m j=1
X
=
|x1 , ..., xt ⟩⟨xπ(1) , ..., xπ(t) | .
x1 ,...,xt ∈{0,1}m
Define the symmetric subspace to be Sym(m, t) = |ψ⟩ ∈ H′ | Pπ |ψ⟩ = |ψ⟩
∀π ∈ St
.
We list some important properties of the symmetric subspace (see [Har13] for a detailed discussion): 1 P • The operator Πm,t π∈St Pπ is a projector onto the symmetric subspace. We denote Sym = t! the normalized projector by ρm,t Sym = i h • dim(Sym(m, t)) = Tr Πm,t Sym =
Πm,t Sym Tr[Πm,t Sym ]
.
2m +t−1 . t
⊗t where µ is the Haar random distribution of states over m qubits. • ρm,t m Sym = E|ψ⟩←µm |ψ⟩⟨ψ| • For any system of m qubits with subsystem of n qubits residing in register C, the projectors n,t m,t n,t n,t m,t Πm,t Sym and Πdis,C commute, i.e. ΠSym Πdis,C = Πdis,C ΠSym . 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. Claim 2.3. Let R be a system of r qubits and C a system of n qubits. Denote p = n + r, and define H = (HR ⊗ HC )⊗t . Let ρp,t Sym be the normalized projector onto the symmetric subspace of H, and p,t p,t n,t ⊗t 2t Πn,t dis,C the projector onto the distinct subspace of HC . If 2n ≤ 1 then ρSym − ρSym Πdis,C n,t p,t n,t Proof. Since ρp,t Sym and Πdis,C commute, ρSym (I − Πdis,C ) is PSD, so p,t n,t ρp,t Sym − ρSym Πdis,C
1
n,t = ρp,t Sym (I − Πdis,C ) 1 h i p,t n,t = Tr ρSym (I − Πdis,C ) h i n,t = 1 − Tr ρp,t Π Sym dis,C
7
2
1
≤ 2tn .
Observe that n,t ρp,t Sym Πdis,C =
1
· 2n+r +t−1 t
1 X t!
t O
X
|xj ⟩⟨xπ(j) |R ⊗ |ij ⟩⟨iπ(j) |C .
π∈St i∈dis(n,t),x∈({0,1}r )t j=1
For a fixed t-tuple i ∈ dis(n, t), index j ∈ [t] and permutation π ∈ St , ( 1 ij = iπ(j) Tr[|ij ⟩⟨iπ(j) |C ] = ⟨ij |iπ(j) ⟩ = 0 ij ̸= iπ(j) . So the pair i, π contribute to the trace ⇐⇒ for all j ∈ [t], ij = iπ(j) . Since i is a tuple of distinct elements, this is equivalent to π being the identity. Therefore, n h i 2rt |dis(n, t)| 2rt 2t p,t n,t Tr ρSym Πdis,C = 2n+r +t−1 = 2n+r +t−1 . t! t t Therefore, p,t n,t ρp,t Sym − ρSym Πdis,C
2n
t−1 Y · 2rt j(2r + 1) = 1 − 2n+r +t−1 = 1 − 1 − n+r . 2 +j 1 j=0 t | {z } t
ϵj
For each j, ϵj =
2j · 2r 2j j(2r + 1) ≤ = n := ϵ′j . n+r n+r 2 +j 2 2
n,t p,t ≤ 1− By assumption, 22tn ≤ 1, so also ϵj ≤ ϵ′j ≤ 1 for all j. Hence ρp,t Sym − ρSym Πdis,C 1 Q P ′ ′ and we can use the union bound 1 − j (1 − ϵj ) ≤ j ϵj and get
n,t p,t ρp,t Sym − ρSym Πdis,C
2.2
1
≤
t−1 X 2j j=0
= 2n
Qt−1
′ j=0 (1−ϵj )
2t(t − 1) t2 ≤ . 2 · 2n 2n
Pseudorandom States
A quantum polynomial time (QPT) algorithm is a sequence of quantum circuits C = {Cλ }λ which are polynomially bounded, that is, there exists a polynomial p(·) such that the circuits Cλ are of size at most p(λ).5 A unitary quantum algorithm is a sequence of quantum circuits such that each Cλ 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 sequencehof sub-normalized i states ρλ ρ = {ρλ }λ , denoted Pr[Cλ (ρλ ) = 1], to be 0 if Tr[ρλ ] = 0 and otherwise Pr Cλ ∥ρλ ∥ = 1 ·Tr[ρλ ]. 1
5
Note that this definition is non-uniform but a uniform version can be defined analogously in a straightforward manner.
8
With this convention, the usual definitions of statistical and computational indistinguishability c of quantum state ensembles extend directly to sub-normalized states. We use the notation ≈ s to denote that states are computationally indistinguishable, and ≈ to denote that states are statistically indistinguishable. Proposition 2.4. Let ρ = {ρλ }λ and σ = {σλ }λ be ensembles of sub-normalized states of the same dimensions, and ε a negligible function. If for all λ, ∥ρλ − σλ ∥1 ≤ ε(λ) then any quantum distinguisher A = {Aλ }λ can distinguish ρ from σ with advantage at most ε, i.e. |Pr[Aλ (ρλ ) = 1] − Pr[Aλ (σλ ) = 1]| ≤ ε(λ) . Moreover, if for all λ, ρλ and σλ are normalized and TD (ρλ , σλ ) ≤ ε(λ) then also in this case A can distinguish ρ from σ with advantage at most ε. 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. Definition 2.5 (Pure State Generator). A (k, m)-pure-state ensemble is a set of m-qubit pure quantum states, indexed by a k-bit classical key: S = {|φi ⟩}i . A unitary quantum algorithm G is a (pure-state) generator for the ensemble S if on input i it outputs |φi ⟩, more explicitly, if G|i⟩|0l ⟩ = |φi ⟩|gi ⟩, where |gi ⟩ is an a-qubit “garbage output” to be discarded. Asymptotically, given a sequence of ensembles {Sλ }λ , where λ ∈ N is the security parameter, a unitary QPT algorithm G = {Gλ }λ is a pure state generator for this sequence if Gλ generates Sλ for all λ. We can now define pseudorandom states which are generated by a pure state generator and have randomness properties. Definition 2.6 (Pseudorandom State). A sequence of ensembles S = {Sλ }λ generated by a pure state generator, where λ is the security parameter, is a (k, m, t)-pseudorandom state if k, m, t are polynomials in λ such that Sλ = {|φλ,i ⟩}i is a (k(λ), m(λ))-pure-state ensemble for all λ, and for any QPT distinguishing adversary A = {Aλ }λ , Pr i←{0,1}k(λ)
h
i Aλ |φλ,i ⟩⊗t(λ) = 1 −
Pr
|ψ⟩←µm(λ)
h i Aλ |ψ⟩⊗t(λ) = 1 ≤ negl(λ) ,
where µm(λ) is the Haar distribution over m(λ)-qubit states. 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 < tm, and if a t-PRS satisfies this condition we say it has a stretch of tm − k. Claim 2.7. If there exists an (k, m, 1)-PRS with stretch s = m − k > 0, where λ is the security parameter, then for any polynomial d := d(λ) > 0 there exists a (b k, m, b 1)-PRS for b k = dk, m b = dm, with stretch sb = ds.
9
Proof. The construction is by concatenation. Take d independent copies of the original 1-PRS {|φi ⟩}i , i.e. parse the key b k as d keys ij of length k and output |φi1 ⟩ ⊗ · · · ⊗ |φid ⟩. The “stretch” calculation is straightforward. Security follows by a hybrid argument from the security of the original PRS, by replacing the states |φij ⟩ with |yj ⟩ for random yj , one by one. This is possible since for a random b k = (i1 , . . . , id ) the ij s are random and independent from one another. Furthermore, the density matrix of a single-copy Haar-random state over m b qubits is maximally mixed and can be written as a product of d maximally mixed states over m qubits.
2.3
Quantum Extractor
We first present definitions of min-entropy that will be useful for applying quantum extractors. Definition 2.8 (Conditional min-entropy). Let ρBE ∈ HB ⊗ HE be a sub-normalized state on subsystems B and E. The conditional min-entropy of ρBE is defined as o n H∞ (B|E) = H∞ (B|E)ρ = sup λ | ρBE ⪯ 2−λ IB ⊗ σE , σE
where σE is any sub-normalized state over system E. Definition 2.9 (Conditional Smoothed min-entropy). Let ρBE ∈ HB ⊗ HE be a sub-normalized state on subsystems B and E, and δ > 0. The conditional smoothed min-entropy of ρBE is defined as δ δ H∞ (B|E) = H∞ (B|E)ρ = sup H∞ (B|E)σ , σBE ∈Bδ (ρ)
where B δ (ρ) is the ball of radius δ centered at ρBE , containing sub-normalized states σBE over the system BE. This ball is defined under some metric, typically the Purified Distance P .6 We define quantum strong extractors and state a theorem that enables the use of 2-designs as quantum strong extractors under certain conditions. Definition 2.10 (Quantum Strong Extractor, [BFW14]). Let ℓ ∈ N and B = B1 B2 be a quantum system with B1 and B2 as subsystems, where the subsystem B1 consists of ℓ qubits. A collection of quantum unitaries {U r }r∈R acting on system B is called a (k ′ , ε, δ)-quantum strong extractor that δ (B|E) ≥ k ′ , extracts ℓ qubits if for any quantum state ρBE ∈ HB ⊗ HE with H∞ ! I 1 X IB1 R r r† TD ⊗ ⊗ ρE ≤ ε . |r⟩⟨r| ⊗ Tr U ρBE U , B2 |R| |R| |B1 | r∈R
Theorem 2.11 ([SDTR13; BFW14; DBWR14; CCC+25]). Let n′ , ℓ ∈ N, k ′ ∈ [−n′ , n′ ], and n′ +k′ 1 ε ∈ (0, 1) such that ℓ ≤ 2 − log ε . Then any unitary 2-design on an n′ -qubit system is a (k ′ , ε, ε/12)-quantum strong extractor that extracts ℓ qubits. 6
P (ρ, σ) =
p √ √ 1 − F (ρ, σ)2 where F (ρ, σ) = ρ σ 1 is the fidelity function. Also note that TD (ρ, σ) ≤ P (ρ, σ).
10
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 [AG25], 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. Symmetrization Simulator. Given |ϕ1 ⟩, . . . , |ϕt ⟩, consider the following algorithm: Sample a random distinct t-tuple i ← dis(n, t) and output the quantum state t
1 XO Simti (|ϕ1 ⟩, . . . , |ϕt ⟩) := √ |iπ(j) ⟩|ϕπ(j) ⟩ . t! π∈St j=1 Claim 2.12. The simulator algorithm described is QPT. Proof. Sample a random P distinct i. Then, in an auxiliary register, take a uniform superposition over all permutations √1t! π∈St |π⟩, and use it to compute the state t O 1 X √ |π⟩ |iπ(j) ⟩|ϕπ(j) ⟩ . t! π∈St j=1
Then uncompute π using i, π(i) (since i is distinct, given i and its permuted version allows to compute π and therefore to uncompute the auxiliary register). Claim 2.13. Given input |ϕ1 ⟩, . . . , |ϕt ⟩, the output density matrix of the simulator is 1 |dis(n, t)|
X
t O
(|ij ⟩⟨ij | ⊗ |ϕj ⟩⟨ϕj |) Pπ
i∈dis(n,t),π∈St j=1
Proof. Denote the output density matrix by Simt (|ϕ1 ⟩, . . . , |ϕt ⟩). By definition, i h Simt (|ϕ1 ⟩, . . . , |ϕt ⟩) = Ei←dis(n,t) Simti (|ϕ1 ⟩, . . . , |ϕt ⟩) Simti (|ϕ1 ⟩, . . . , |ϕt ⟩)† =
1 |dis(n, t)|
X i∈dis(n,t)
t 1 X O |iπ′ (j) ⟩⟨iπ(j) | ⊗ |ϕπ′ (j) ⟩⟨ϕπ(j) | . t! ′ π,π ∈St j=1
Nt Fixing a t-tuple i and permutation π, notice that the term j=1 |ij ⟩⟨iπ(j) | ⊗ |ϕj ⟩⟨ϕπ(j) | appears exactly t! times in the summation, exactly once for each i′ that is a permutation of i, that is, ∃π ′ such that π ′ (i′ ) = i. This determines the second permutation π ′′ such that π ′′ (i′ ) = π(i) = π(π ′ (i)).
11
Therefore, summation over i, π, π ′ collapses to summation over i, π and the fraction t!1 cancels out. 1 Sim (|ϕ1 ⟩, . . . , |ϕt ⟩) = |dis(n, t)| t
1 = |dis(n, t)| 1 = |dis(n, t)|
2.5
X i∈dis(n,t)
t 1 X O |iπ′ (j) ⟩⟨iπ(j) | ⊗ |ϕπ′ (j) ⟩⟨ϕπ(j) | t! ′ π,π ∈St j=1
t XO
X
|ij ⟩⟨iπ(j) | ⊗ |ϕj ⟩⟨ϕπ(j) |
i∈dis(n,t) π∈St j=1 t O
X
(|ij ⟩⟨ij | ⊗ |ϕj ⟩⟨ϕj |) Pπ
i∈dis(n,t),π∈St j=1
Auxiliary Claims
For a seeded function family F, we denote f ← 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 ℓF the seed length for sampling a function from F. We state some useful claims that will help us prove that our construction is a t-PRS. Proposition 2.14. Let F ⊆ X → Y be a t-wise independent function family, and let {ρy }y∈Y be a family of sub-normalized states. Then for every t distinct inputs i1 , . . . , it ∈ X , t t h i O O Ef ←F ρf (ij ) = Ef ←F ρf (ij ) . j=1
j=1
Proposition 2.15. For any two families of quantum states {ρi }i , {σi }i , if TD (ρi , σi ) ≤ ε for each i then for any t, ! t t O O TD ρi , σi ≤ tε . i=1
i=1
Proposition 2.16. Let ρ, σ be sub-normalized states, and let U be a unitary operator. If ∥ρ − σ∥1 ≤ ε, then ∥ρU − σU ∥1 ≤ ε. Proposition 2.17. Let D be some distribution, and {ρd }d∈D , {σd }d∈D two families of states over this distribution. Then ∥Ed←D [ρd ] − Ed←D [σd ]∥1 ≤ Ed←D [∥ρd − σd ∥1 ] . In particular, if for all d it holds that ∥ρd − σd ∥1 ≤ ε, then ∥Ed←D [ρd ] − Ed←D [σd ]∥1 ≤ ε. Proposition 2.18. Let ρ be a quantum state on register A, and assume A is split into two registers A = A1 A2 such that A2 holds q qubits. Then IA2 x z x Ex←{0,1}q ,z←{0,1}q (IA1 ⊗ XA Z z ) ρ (IA1 ⊗ ZA XA ) = Tr(ρ) ⊗ . 2 A2 2 2 A2 |IA2 | P Q Proposition 2.19. Let ϵ1 , . . . , ϵt > 0 and ϵ = tj=1 ϵj such that ϵ < 1. Then tj=1 (1 + ϵj ) ≤ eϵ ≤ 1 + ϵ + ϵ2 . 12
Theorem 2.20 ([Vad12], Corollary 3.34). For any t, λ, n ∈ N there is a family of t-wise independent functions F ⊆ {0, 1}λ → {0, 1}n such that choosing a random function from F takes t · max {λ, n} random bits, that is, ℓF = t · max {λ, n}. Moreover, evaluating any function from F takes time poly(n, λ, t).
3
Constructing t-PRS from 1-PRS
3.1
Parameter Setup
Let κ, k, m, a, n, t ∈ N. Let G be a pure state generator for an ensemble {|φi ⟩}i with key length k, output register A of m qubits, and a garbage register qubits, such that for each key B of a i, G(i) = |φi ⟩A |gi ⟩B . Let ε ∈ (0, 1) be such that ℓ = 2a − log 1ε ≥ 0. Let U = {U r }r be an efficiently implementable unitary 2-design on the a-qubit register B with seed length κ. Denote by B2 the register containing the last q := a − ℓ qubits of system B. Let F1 ⊆ {0, 1}n → {0, 1} be a 2t-wise independent function family and F2 ⊆ {0, 1}n → {0, 1}q , F3 ⊆ {0, 1}n → {0, 1}q , F4 ⊆ {0, 1}n → {0, 1}k , F5 ⊆ {0, 1}n → {0, 1}κ all t-wise independent function families.
3.2
Construction
Let fi ∈ Fi , and define the following state. X 1 f (i) f (i) f (i) |ψf1 ,f2 ,f3 ,f4 ,f5 ⟩ = √ (−1)f1 (i) |f5 (i)⟩R XB22 ZB32 UB5 G(f4 (i))AB |i⟩C n 2 i∈{0,1}n X 1 f (i) f (i) f (i) (−1)f1 (i) |f5 (i)⟩R XB22 ZB32 =√ UB5 |φf4 (i) ⟩A |gf4 (i) ⟩B |i⟩C n 2 i∈{0,1}n
3.3
Our Amplification Theorem
Theorem 3.1 (Main Theorem). Let λ be a security parameter, and for each λ define the setup parameters w.r.t λ such that G is a 1-PRS generator, ε is negligible, ℓ ≥ 0, and κ, k, m, a, n, t are e that outputs the polynomially bounded such that n = ω(log(λ)). Define the pure state generator G construction above, namely for key z = (f1 , f2 , f3 , f4 , f5 ) outputs the pure state e G(z) = |ψf1 ,f2 ,f3 ,f4 ,f5 ⟩ . e is a t-PRS with key length Then G 1 a e k = t 2n + 2 max n, + log + max {n, k} + max {n, κ} , 2 ε and output length m e = κ + m + a + n. 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. 13
Corollary 3.2. Let λ be a security parameter and t a polynomial in λ. If there exists a non-trivial 1-PRS then there exists a non-trivial t-PRS with stretch ≥ ts for any polynomial s := s(λ). Proof. Let G be the state generator of a non-trivial 1-PRS with stretch sG . Using Claim 2.7 we b and stretch d · sG for some d which we can instantiate another non-trivial 1-PRS with generator G b will determine later. We then use G as the base 1-PRS generator for the construction described in Theorem 3.1 together with function families F1 , . . . , F5 as guaranteed by Theorem j 2.20, resulting k e Set n = λ, ε = 2−λ . We must make sure that ℓ = ba − log 1 > 0, in a new t-PRS generator G. 2 ε which can be enforced by adding extra ancilla qubits set to |0⟩ if necessary. Using these parameters in Equation 1 gives7 n o 1 e k = t 2λ + b a + 2 log + max b k, λ + κ . ε The output of t copies is tm e = t(κ + m b +b a + λ) qubits. The stretch is n o 1 e b a + 2 log b +b a + λ) − t 2λ + b tm e − k = t(κ + m + max k, λ + κ ε n o 1 =t m b − max b k, λ − λ − 2 log ε n o =t m b − max b k, λ − 3λ To ensurel this mvalue is at least ts we want m b −b k − 3λ ≥ s =⇒ d · sG − 3λ ≥ s. So it suffices to s+3λ 8 take d = sG = poly(λ), resulting in n o tm e −e k=t m b − max b k, λ − 3λ =t m b −b k − 3λ ≥ ts
3.4
Proof of Theorem 3.1
e consists of all the seeds to the function families F1 , . . . , F5 . By Key length. The key of G Theorem 2.20, ℓF1 = 2t · n, 1 a 1 a ℓF2 = ℓF3 = t · max {n, q} = t max n, a − − log = t max n, + log , (1) 2 ε 2 ε ℓF4 = t · max {n, k} , ℓF5 = t · max {n, κ}
So the total length of the key is a 1 e k = t 2n + 2 max n, + log + max {n, k} + max {n, κ} . 2 ε 7
W.l.o.g. we assume that κ ≥ λ, as the seed length of the 2-design can be trivially extended. Similarly, assume that b a is even. 8 W.l.o.g. we can assume b k ≥ λ, since we can always take d ≥ λ.
14
Output length. which is
The output length is simply the total number of qubits in registers R, A, B, C, m e =κ+m+a+n .
The Generator is QPT. Theorem 2.20 ensures that all the functions f1 , . . . , f5 can be evaluated e also has an efficient efficiently, and the 2-design as well as G are efficiently computable. Therefore G 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. Our Hybrids. We turn to proving the security of our construction using a sequence of hybrids. e is computationally indistinguishable Our goal is to show that t copies of a state generated by G from t copies of a Haar-random state over the same dimensions. We introduce a sequence of hybrids Hi , where each hybrid is simply a density matrix. The e on a random seed. The final hybrid hybrid H0 will denote a t-wise application of the generator G c H4 will be density matrix of a t-copy Haar-random state. We will show that H0 ≈ H4 by the following outline: • The hybrid H0 is just the t-wise density matrix of our construction. • The hybrid H1 is a restriction to the so-called distinct subspace. s
We show that H0 ≈ H1 by showing that most of the mass of our density matrix is concentrated in the distinct subspace. • The hybrid H2 is is obtained from the hybrid H1 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. s
We show that H1 ≈ H2 by showing that the application of the extractor followed by the quantum one-time pad in register B of the hybrid H1 (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 H3 is obtained from the hybrid H2 by replacing each of the 1-PRS states (in register A) with a maximally mixed state. c
Using the security of the 1-PRS, we show that H2 ≈ H3 . • The hybrid H4 is the density matrix of a t-copy Haar-random state. s
We show that H3 ≈ H4 by showing that the hybrid H3 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 H4 . Combining all these Hybrids gives s
s
c
s
H0 ≈ H 1 ≈ H 2 ≈ H 3 ≈ H 4 , which completes the security proof of the t-PRS. 15
Formal Hybrid Definitions and Claims. We define H0 as ⊗t † e e H0 := Ef1 ,...,f5 G(f1 , . . . , f5 ) G(f1 , . . . , f5 ) † † t X O ′ ′ ′ ′ f5 (i ) f2 ,f3 ,ij 1 f ,f ,i f (i ) f4 ,f5 ,ij ,i = Ef1 ,...,f5 nt (−1)f1 (ij )−f1 (ij ) VB22 3 j UB5 j ρRABC j UB j VB2 2 ′ n t i,i ∈({0,1} ) j=1
(2) f ,f ,i f (i ) f (i ) where we denote VB22 3 j = XB22 j ZB32 j , f4 ,f5 ,ij ,i′j
ρRAB
= |f5 (ij )⟩⟨f5 (i′j )|R ⊗ |φf4 (ij ) ⟩⟨φf4 (i′j ) |A ⊗ |gf4 (ij ) ⟩⟨gf4 (i′j ) |B , f4 ,f5 ,ij ,i′
f4 ,f5 ,ij ,i′j
ρRABC j = ρRAB
⊗ |ij ⟩⟨i′j |C ,
(3)
and writing Efi throughout the proof is a shorthand for Efi ←Fi . We further denote for any pair of t-tuples i, i′ , † t O ′ ′) † ′ ′ f ,f ,i ,i f (i f ,f ,i 4 5 j 5 2 3 j f ,f ,i f (i ) i,i . = Ef2 ,...,f5 τRAB VB22 3 j UB5 j ρRAB j UB j VB2 (4) j=1
We define H1 as the projection of H0 onto the distinct subspace of register C. This results in the following sub-normalized state. n,t H1 := Πn,t dis,C H0 Πdis,C
(5)
Next, we show that the two hybrids are indistinguishable. n,t Claim 3.3. ∥H0 − H1 ∥1 = H0 − Πn,t dis,C H0 Πdis,C
2
1
≤ 21 · 2tn = negl(λ).
Proof. We can write H0 =
i h Pt ′ ′ 1 X ′ j=1 f1 (ij )−f1 (ij ) τ i,i . ⊗ |i⟩⟨i | E (−1) C f 1 RAB 2nt ′ i,i
n,t n,t n,t Let Πn,t coll,C = I − Πdis,C , we start by showing that Πcoll,C H0 Πdis,C = 0. This follows because n,t Πn,t coll,C H0 Πdis,C =
h i Pt ′ 1 X i,i′ n,t ′ j=1 f1 (ij )−f1 (ij ) Πn,t τ ⊗ E (−1) f1 coll,C |i⟩⟨i |C Πdis,C . 2nt ′ RAB i,i
h i Pt n,t n,t n,t f1 (ij )−f1 (i′j ) ′ ′ j=1 Now let us focus on Ef1 (−1) Πn,t coll,C |i⟩⟨i |C Πdis,C . Whenever Πcoll,C |i⟩⟨i |C Πdis,C ̸= 0 it means that i is not distinct and i′ is distinct. In other words, i′ has t distinct elements, but i has a collision, which means that at least one element in i′ does not appear in i at all. ′ Therefore in this case, since h i f1 is 2t-wise independent and i ∪ i contains at most 2t values, then Pt ′ Ef1 (−1) j=1 f1 (ij )−f1 (ij ) = 0 and the claim follows. From this property we have
16
n,t H0 − Πn,t dis,C H0 Πdis,C
1
n,t = Πn,t coll,C H0 Πcoll,C 1 h i n,t = Tr Πcoll,C H0 h i P X t ′ ′ 1 ′ = Tr nt Ef1 (−1) j=1 f1 (ij )−f1 (ij ) ρi,i RAB ⊗ |i⟩⟨i |C 2 i,i′ ∈dis(n,t) / h ′ i Pt X ′ 1 ′ Ef (−1) j=1 f1 (ij )−f1 (ij ) Tr ρi,i = nt RAB Tr[|i⟩⟨i |C ] 2 i,i′ ∈dis(n,t) / h i X 1 Tr ρi,i ≤ nt RAB 2 i∈dis(n,t) /
=
|{i | i ∈ / dis(n, t)}| 2nt
which is simply the probability of obtaining when sampling t elements independently a1collision t 1 t2 n from a 2 size universe, which is at most 2 · 2n ≤ 2 · 2n . We now give an explicit form for H1 . Claim 3.4. It holds that H1 =
1 2nt
X
i,i ⊗ |i⟩⟨i|C Pπ . τRAB
i∈dis(n,t),π∈St
Proof. We use the same notation as in Equation 4 and write i h P X t ′ i,i′ 1 H1 = Πn,t ⊗ |i⟩⟨i′ |C Πn,t Ef1 (−1) j=1 f1 (ij )−f1 (ij ) τRAB dis,C dis,C nt 2 i,i′ ∈({0,1}n )t h i Pt X ′ 1 i,i′ = nt Ef1 (−1) j=1 f1 (ij )−f1 (ij ) τRAB ⊗ |i⟩⟨i′ |C 2 ′ i,i ∈dis(n,t)
For hany i, i′ ∈ dis(n, t),i if i has an element that does not appear in i′ , or vice versa, then Pt ′ Ef1 (−1) j=1 f1 (ij )−f1 (ij ) = 0. The only terms that don’t vanish are those where i′ is a perh i Pt ′ mutation of i, and in this case Ef1 (−1) j=1 f1 (ij )−f1 (ij ) = 1. Therefore, H1 = =
1 2nt 1 2nt
i,π(i)
X
τRAB ⊗ |i⟩⟨π(i)|C
i∈dis(n,t),π∈St
X i∈dis(n,t),π∈St
17
i,i τRAB ⊗ |i⟩⟨i|C Pπ
The next step is showing that after applying the extractor and a quantum one-time pad in registers B of H1 , the resulting sub-normalized state is almost maximally mixed in registers B and R. We formally define t O X 1 IR IB H2 := nt Ef4 ⊗ ⊗ |φf4 (ij ) ⟩⟨φf4 (ij ) |A ⊗ |ij ⟩⟨ij |C Pπ , (6) 2 |R| |B| j=1
i∈dis(n,t),π∈St
and show that Claim 3.5. ∥H1 − H2 ∥1 ≤ 2tε = negl(λ). Proof. Combining Equation 4 and Claim 3.4 gives t X O † † 1 f ,f ,i f (i ) f4 ,f5 ,ij ,ij f (i ) f ,f ,i Ef4 Ef2 ,f3 ,f5 VB22 3 j UB5 j ρRABC H1 = nt UB5 j VB22 3 j Pπ . 2 j=1
i∈dis(n,t),π∈St
Fixing a t-tuple i and a function f4 , we denote the quantum (normalized) states t † † O f (i ) f ,f ,i f ,f ,i f (i ) f ,f ,i ,i σ1i,f4 = Ef2 ,f3 ,f5 V 2 3 j , V 2 3 j U 5 j ρ4 5 j j U 5 j B2
RABC
B
B
B2
j=1
and
t O IR
IB ⊗ |φf4 (ij ) ⟩⟨φf4 (ij ) |A ⊗ |ij ⟩⟨ij |C . |B| j=1 h i h i P P Observe that H1 = 21nt i∈dis(n,t),π∈St Ef4 σ1i,f4 Pπ and H2 = 21nt i∈dis(n,t),π∈St Ef4 σ2i,f4 Pπ . We will show that TD σ1i,f4 , σ2i,f4 ≤ tε and then conclude from Proposition 2.16 and Proposition 2.17 that ∥H1 − H2 ∥1 ≤ 2tε. For a single index ij note that the functions f2 , f3 , f5 act as random functions, and denote σ2i,f4 =
|R|
⊗
f ,i
4 j = |φf4 (ij ) ⟩⟨φf4 (ij ) |A ⊗ |gf4 (ij ) ⟩⟨gf4 (ij ) |B ⊗ |ij ⟩⟨ij |C , ρABC
f ,i
4 j = |φf4 (ij ) ⟩⟨φf4 (ij ) |A ⊗ |ij ⟩⟨ij |C . ρAC
f ,i
4 j δ (B|AC) ≥ 0. Observe that each ρABC is a pure state with H∞ (B|AC) = 0, so for any δ, H∞ ′ ′ Applying Theorem 2.11 with n = a, k = 0 and ε, we can extract ℓ qubits from B with the guarantee that I IB1 f5 (ij ) f4 ,ij f5 (ij ) † f4 ,ij R TD Ef5 |f5 (ij )⟩⟨f5 (ij )|R ⊗ Tr UB ρABC UB , ⊗ ⊗ ρAC ≤ε. B2 |R| |B1 |
Tensoring with the maximally mixed state on register B2 gives
† I I I I f (i ) f4 ,ij f (i ) f4 ,ij R B1 B2 B2 TD Ef5 |f5 (ij )⟩⟨f5 (ij )|R ⊗ Tr UB5 j ρABC UB5 j ⊗ , ⊗ ⊗ ρAC ⊗ ≤ε B2 |B2 | |R| |B1 | |B2 | | {z } {z } | i ,f4
i ,f4
:=σ2j
:=σ1j
18
i ,f
We start by analyzing σ1j 4 . Observe that for each r, quantum OTP gives (Proposition 2.18) f2 ,f3 ,ij f2 ,f3 ,ij † r f4 ,ij r † Ef2 ,f3 |r⟩⟨r|R ⊗ VB2 UB ρABC (UB ) VB2 I f4 ,ij B2 = |r⟩⟨r|R ⊗ Tr UBr ρABC (UBr )† ⊗ B2 |B2 | So I f5 (ij ) f4 ,ij f5 (ij ) † B2 ρABC UB ⊗ |f5 (ij )⟩⟨f5 (ij )|R ⊗ Tr UB B2 |B2 | f2 ,f3 ,ij f5 (ij ) f4 ,ij f5 (ij ) † f2 ,f3 ,ij † = Ef2 ,f3 ,f5 |f5 (ij )⟩⟨f5 (ij )|R ⊗ VB2 UB ρABC UB VB2
i ,f σ1j 4 = Ef5
i ,f
Now we analyze σ2j 4 . i ,f
IB1 IB2 IR f4 ,ij ⊗ ⊗ ρAC ⊗ |R| |B1 | |B2 | IR IB f4 ,ij = ⊗ ⊗ ρAC |R| |B|
σ2j 4 =
Now consider all the elements of the t-tuple i = (i1 , . . . , it ). From Proposition 2.15, O t t ij ,f4 O i ,f 4 j TD σ1 , σ2 ≤ tε . j=1 j=1 | {z } i,f4
σ2
Since i contains t distinct and f2 , f3 , f5 are t-wise independent functions, we can apply Nt elements, ij Proposition 2.14 on j=1 σ1 , which will give us exactly σ1i,f4 . We define H3 by replacing each of the 1-PRS states in register A of H2 with a maximally mixed state. Formally, t X O 1 IR IB IA H3 := nt ⊗ ⊗ ⊗ |ij ⟩⟨ij |C Pπ . (7) 2 |R| |B| |A| i∈dis(n,t),π∈St
j=1
We use the security of the 1-PRS to show that Claim 3.6. For any distinguishing adversary A, |Pr [A(H2 ) = 1] − Pr [A(H3 ) = 1]| ≤ negl(λ). Proof. As defined in Equation 6, H2 =
1 2nt
X i∈dis(n,t),π∈St
t O IR IB ⊗ ⊗ |φf4 (ij ) ⟩⟨φf4 (ij ) |A ⊗ |ij ⟩⟨ij |C Pπ . Ef4 |R| |B| j=1
19
Since i = (i1 , . . . , it ) are distinct and f4 is t-wise independent, this equals t O X IR 1 IB Es←({0,1}k )t = nt ⊗ ⊗ |φsj ⟩⟨φsj |A ⊗ |ij ⟩⟨ij |C Pπ . 2 |R| |B| j=1
i∈dis(n,t),π∈St
We would like to use the 1-PRS security and “replace” each instance of |φsj ⟩ with a Haar-random state. In other words, we want a reduction from a QPT distinguishing adversary that receives this state to a 1-PRS QPT distinguisher. However, there are two issues we need to overcome. The first is that we are using states that are sub-normalized, and quantum reductions use normalized states. We overcome this by considering the normalized version of this state, as well as the normalized version of the state that is the result of replacing each |φsj ⟩ by a random computational basis state, which is precisely H3 . t X O 1 I I B R Ey←({0,1}m )t ⊗ ⊗ |yj ⟩⟨yj |A ⊗ |ij ⟩⟨ij |C Pπ 2nt |R| |B| j=1 i∈dis(n,t),π∈St t O X I I I 1 R B A ⊗ ⊗ ⊗ |ij ⟩⟨ij |C Pπ = nt 2 |R| |B| |A| i∈dis(n,t),π∈St
j=1
= H3 Notice that we used random computational basis states instead of Haar-random states, since for single-copy security they share the same density matrix. Furthermore, since Tr[H2 ] = Tr[H3 ], then for any QPT distinguishing adversary A, its distinguishing advantage of the normalized states is at least that of the non-normalized states, namely |Pr[A(H2 ) = 1] − Pr[A(H3 ) = 1]| H2 H3 = Pr A = 1 · Tr[H2 ] − Pr A = 1 · Tr[H3 ] Tr[H2 ] Tr[H3 ] H3 H2 ≤ Pr A = 1 − Pr A =1 Tr[H2 ] Tr[H3 ] = |Pr [A (ρ2 ) = 1] − Pr [A (ρ3 ) = 1]| H2 H3 where we define ρ2 := Tr[H and ρ3 := Tr[H . 2] 3] The second issue is how to efficiently simulate these normalized states given independent instances from a 1-PRS distinguisher. For this we will use the symmetrization simulator defined in Subsection 2.4. For generating ρ2 sample independently r ← ({0, 1}κ )t , b ← ({0, 1}a )t , s ← N t ({0, 1}k )t and run the simulator on the state j=1 |rj ⟩R |bj ⟩B |φsj ⟩A . By Claim 2.13 the output
20
state will be
Er,b,s Simt
t O
|rj ⟩R |bj ⟩B |φsj ⟩A
j=1
= Er,b,s
=
=
1 |dis(n, t)|
1 |dis(n, t)| 2nt |dis(n, t)|
X
t O
i∈dis(n,t),π∈St
X i∈dis(n,t),π∈St
|rj ⟩⟨rj |R ⊗ |bj ⟩⟨bj |B ⊗ |φsj ⟩⟨φsj |A ⊗ |ij ⟩⟨ij |C Pπ
j=1
t O IR IB Es ⊗ ⊗ |φsj ⟩⟨φsj |A ⊗ |ij ⟩⟨ij |C Pπ |R| R |B| B j=1
H2 = ρ2
For generating ρ3 , sample N independently r ← ({0, 1}κ )t , b ← ({0, 1}a )t , y ← ({0, 1}m )t and run the simulator on the state tj=1 |rj ⟩R |bj ⟩B |yj ⟩A . A similar calculation shows that in this case the output state will be ρ3 . Hence now we can reduce to the security of 1-PRS. If a QPT distinguishing adversary A can distinguish H2 from H3 with non-negligible advantage then it can distinguish ρ2 from ρ3 with at least the same advantage. Since ρ2 can be simulated given t independent copies of single-copy pseudorandom states and ρ3 can be simulated given t independent states from the computational basis, there exists a QPT distinguishing adversary that distinguishes t independent copies of the 1PRS from t independent copies of random states with non-negligible advantage, simply by running A on the output of the simulator. Applying a standard hybrid argument as in Claim 2.7 to this adversary, we can replace the t coordinates one by one. It follows that the distinguishing advantage in at least one coordinate must be at least a 1/t fraction of the total advantage (and thus still non-negligible), yielding a 1-PRS distinguisher that contradicts 1-PRS security. Therefore it must be that |Pr[A(H2 ) = 1] − Pr[A(H3 ) = 1]| ≤ negl(λ). 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 m,t e H4 := E|ψ⟩←µme |ψ⟩⟨ψ|⊗t = ρSym . (8) We show that 2
Claim 3.7. ∥H3 − H4 ∥1 ≤ 3 2tn = negl(λ).
21
Proof. We develop the expression of H3 . t O X IR IB IA 1 ⊗ ⊗ ⊗ |ij ⟩⟨ij |C Pπ H3 = nt 2 |R| |B| |A| j=1 i∈dis(n,t),π∈St t O X 1 = nt Ex←({0,1}κ+a+m )t |xj ⟩⟨xj |RBA ⊗ |ij ⟩⟨ij |C Pπ 2 j=1 i∈dis(n,t),π∈St t X O 1 = nt (κ+a+m)t |xj ⟩⟨xj |RBA ⊗ |ij ⟩⟨ij |C Pπ 2 ·2 κ+a+m t j=1 i∈dis(n,t),x∈({0,1}
=
) ,π∈St
t! m,t e ΠSym Πn,t dis,C e 2mt
m,t e where ΠSym is the projector onto the symmetric subspace of the whole system, and Πn,t dis,C is the projector onto the distinct subspace of system C. e e , and recall the normalized projector onto the symmetric subspace ρm,t Denote d = 2m Sym = m,t e ΠSym
(d+t−1 ) t
. Notice that t! d + t − 1 t! m,t m,t e m,t e e − ρSym = ρSym Π −1 dt Sym dt t 1 1 t! d + t − 1 = t −1 d t (d + t − 1)! −1 = t d (d − 1)! (d + t − 1)(d + t − 2) . . . d = −1 dt := δ0
and since Πn,t dis,C is a projector, t! m,t t! m,t m,t e m,t e e e ≤ t ΠSym Πn,t − ρSym = δ0 . Πn,t − ρSym ΠSym dis,C dis,C t d d 1 1 2
m,t e m,t e Πn,t ≤ 2tn as long as 22tn ≤ 1, which is true for large enough λ. − ρSym Claim 2.3 gives ρSym dis,C 1 Hence by triangle inequality we get
t! m,t t2 e m,t e ΠSym Πn,t ≤ δ0 + n . − ρSym dis,C t d 2 1
∥H3 − H4 ∥1 = 2
We conclude by showing that δ0 ≤ 2 2tn . δ0 =
(d + t − 1)(d + t − 2) . . . d −1 dt
t−1 Y 1 + j − 1 = d |{z} j=0 ϵj
22
P t2 2 By Proposition 2.19, if ϵ := t−1 j=0 ϵj < 1 then δ0 ≤ ϵ + ϵ ≤ 2ϵ. Asymptotically, d = negl(λ), so Pt−1 j P t2 t2 t2 for large enough λ we have t−1 j=0 d ≤ d < 1. Hence δ0 ≤ 2 d ≤ 2 2n = negl(λ). j=0 ϵj = Acknowledgments. The authors are supported by the Horizon Europe Research and Innovation Program via ERC Project ACQUA (Grant 101087742).
References [AG25]
Prabhanjan Ananth and Eli Goldin. Less is More: On Copy Complexity in Quantum Cryptography. 2025. arXiv: 2510.04992 [quant-ph]. url: https://arxiv.org/abs/ 2510.04992.
[AGQY22]
Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. “Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications”. In: Theory of Cryptography. Ed. by Eike Kiltz and Vinod Vaikuntanathan. Cham: Springer Nature Switzerland, 2022, pp. 237–265. isbn: 978-3-031-22318-1.
[AQY22]
Prabhanjan Ananth, Luowen Qian, and Henry Yuen. “Cryptography from Pseudorandom Quantum States”. In: Advances in Cryptology – CRYPTO 2022. Ed. by Yevgeniy Dodis and Thomas Shrimpton. Cham: Springer Nature Switzerland, 2022, pp. 208– 236. isbn: 978-3-031-15802-5.
[BCN25]
John Bostanci, Boyang Chen, and Barak Nehoran. “Oracle Separation Between Quantum Commitments and Quantum One-Wayness”. In: Advances in Cryptology – EUROCRYPT 2025. Ed. by Serge Fehr and Pierre-Alain Fouque. Cham: Springer Nature Switzerland, 2025, pp. 3–22. isbn: 978-3-031-91098-2.
[BCQ23]
Zvika Brakerski, Ran Canetti, and Luowen Qian. “On the Computational Hardness Needed for Quantum Cryptography”. In: 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 1013, 2023. Ed. by Yael Tauman Kalai. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 24:1–24:21. doi: 10.4230/LIPICS.ITCS.2023.24. url: https: //doi.org/10.4230/LIPIcs.ITCS.2023.24.
[BFW14]
Mario Berta, Omar Fawzi, and Stephanie Wehner. “Quantum to Classical Randomness Extractors”. In: IEEE Trans. Inf. Theory 60.2 (2014), pp. 1168–1192. doi: 10.1109/ TIT.2013.2291780. url: https://doi.org/10.1109/TIT.2013.2291780.
[BGH+23]
Khashayar Barooti, Alex B. Grilo, Loı̈s Huguenin-Dumittan, Giulio Malavolta, Or Sattath, Quoc-Huy Vu, and Michael Walter. “Public-Key Encryption with Quantum Keys”. In: Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part IV. Ed. by Guy N. Rothblum and Hoeteck Wee. Lecture Notes in Computer Science. Springer, 2023, pp. 198–227. doi: 10.1007/978- 3- 031- 48624- 1_8. url: https://doi.org/10. 1007/978-3-031-48624-1_8.
23
[BJ24]
Rishabh Batra and Rahul Jain. “Commitments are Equivalent to Statistically-Verifiable One-Way State Generators”. In: 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024. IEEE, 2024, pp. 1178–1192. doi: 10.1109/FOCS61266.2024.00077. url: https://doi.org/10. 1109/FOCS61266.2024.00077.
[CCC+25]
Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li. A Meta-Complexity Characterization of Minimal Quantum Cryptography. 2025. arXiv: 2510 . 07859 [quant-ph]. url: https : / / arxiv . org / abs / 2510.07859.
[CCS25]
Boyang Chen, Andrea Coladangelo, and Or Sattath. “The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness”. In: Advances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceedings, Part VII. Madrid, Spain: Springer-Verlag, 2025, pp. 108– 137. isbn: 978-3-031-91097-5. doi: 10.1007/978- 3- 031- 91098- 2_5. url: https: //doi.org/10.1007/978-3-031-91098-2_5.
[CGG24]
Kai-Min Chung, Eli Goldin, and Matthew Gray. “On Central Primitives for Quantum Cryptography with Classical Communication”. In: Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VII. Ed. by Leonid Reyzin and Douglas Stebila. Lecture Notes in Computer Science. Springer, 2024, pp. 215–248. doi: 10.1007/9783-031-68394-7_8. url: https://doi.org/10.1007/978-3-031-68394-7_8.
[DBWR14]
Frédéric Dupuis, Mario Berta, Jürg Wullschleger, and Renato Renner. “One-Shot Decoupling”. In: Communications in Mathematical Physics 328.1 (2014), pp. 251– 284. issn: 1432-0916. doi: 10.1007/s00220-014-1990-4. url: https://doi.org/ 10.1007/s00220-014-1990-4.
[GJMZ23]
Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. “Commitments to Quantum States”. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 1579–1588. isbn: 9781450399135. doi: 10.1145/3564246.3585198. url: https: //doi.org/10.1145/3564246.3585198.
[Har13]
Aram W. Harrow. The Church of the Symmetric Subspace. 2013. arXiv: 1308.6595 [quant-ph]. url: https://arxiv.org/abs/1308.6595.
[JLS18]
Zhengfeng Ji, Yi-Kai Liu, and Fang Song. “Pseudorandom Quantum States”. In: Advances in Cryptology – CRYPTO 2018. Ed. by Hovav Shacham and Alexandra Boldyreva. Cham: Springer International Publishing, 2018, pp. 126–152. isbn: 978-3319-96878-0.
[KQST23]
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. “Quantum Cryptography in Algorithmica”. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 1589–1602. isbn: 9781450399135. doi: 10.1145/3564246. 3585225. url: https://doi.org/10.1145/3564246.3585225.
24
[Kre21]
William Kretschmer. “Quantum Pseudorandomness and Classical Complexity”. In: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, Virtual Conference, July 5-8, 2021. Ed. by Min-Hsiu Hsieh. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 2:1–2:20. doi: 10. 4230/LIPICS.TQC.2021.2. url: https://doi.org/10.4230/LIPIcs.TQC.2021.2.
[KT24]
Dakshita Khurana and Kabir Tomer. “Commitments from Quantum One-Wayness”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024. Vancouver, BC, Canada: Association for Computing Machinery, 2024, pp. 968– 978. doi: 10.1145/3618260.3649654. url: https://doi.org/10.1145/3618260. 3649654.
[LMW24]
Alex Lombardi, Fermi Ma, and John Wright. “A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024. Vancouver, BC, Canada: Association for Computing Machinery, 2024, pp. 979–990. doi: 10.1145/3618260. 3649650. url: https://doi.org/10.1145/3618260.3649650.
[MY22]
Tomoyuki Morimae and Takashi Yamakawa. “Quantum Commitments and Signatures Without One-Way Functions”. In: Advances in Cryptology – CRYPTO 2022. Ed. by Yevgeniy Dodis and Thomas Shrimpton. Cham: Springer Nature Switzerland, 2022, pp. 269–295. isbn: 978-3-031-15802-5.
[MY24]
Tomoyuki Morimae and Takashi Yamakawa. “One-Wayness in Quantum Cryptography”. In: 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, Okinawa, Japan, September 9-13, 2024. Ed. by Frédéric Magniez and Alex Bredariol Grilo. LIPIcs. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2024, 4:1–4:21. doi: 10.4230/LIPICS.TQC.2024.4. url: https://doi.org/10.4230/LIPIcs.TQC.2024.4.
[SDTR13]
Oleg Szehr, Frédéric Dupuis, Marco Tomamichel, and Renato Renner. “Decoupling with unitary approximate two-designs”. In: New Journal of Physics 15.5 (2013), p. 053022. doi: 10 . 1088 / 1367 - 2630 / 15 / 5 / 053022. url: https : / / doi . org / 10.1088/1367-2630/15/5/053022.
[Vad12]
Salil P. Vadhan. “Pseudorandomness”. In: Found. Trends Theor. Comput. Sci. 7.1–3 (Dec. 2012), pp. 1–336. issn: 1551-305X. doi: 10.1561/0400000010. url: https: //doi.org/10.1561/0400000010.
[Zha12]
Mark Zhandry. “Secure Identity-Based Encryption in the Quantum Random Oracle Model”. In: Advances in Cryptology – CRYPTO 2012. Ed. by Reihaneh Safavi-Naini and Ran Canetti. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 758–775. isbn: 978-3-642-32009-5.
25