# Pseudorandom Strings from Pseudorandom Quantum States

Prabhanjan Ananth
UCSB<EMAIL_ADDRESS>Yao-Ting Lin
UCSB<EMAIL_ADDRESS>Henry Yuen
Columbia University<EMAIL_ADDRESS>
###### Abstract

We study the relationship between notions of pseudorandomness in the quantum
and classical worlds. Pseudorandom quantum state generator (PRSG), a
pseudorandomness notion in the quantum world, is an efficient circuit that
produces states that are computationally indistinguishable from Haar random
states. PRSGs have found applications in quantum gravity, quantum machine
learning, quantum complexity theory, and quantum cryptography. Pseudorandom
generators, on the other hand, a pseudorandomness notion in the classical
world, is ubiquitous to theoretical computer science. While some separation
results were known between PRSGs, for some parameter regimes, and PRGs, their
relationship has not been completely understood.

In this work, we show that a natural variant of pseudorandom generators called
_quantum pseudorandom generators (QPRGs)_ can be based on the existence of
logarithmic output length PRSGs. Our result along with the previous
separations gives a better picture regarding the relationship between the two
notions. We also study the relationship between other notions, namely,
pseudorandom function-like state generators and pseudorandom functions. We
provide evidence that QPRGs can be as useful as PRGs by providing
cryptographic applications of QPRGs such as commitments and encryption
schemes.

Our primary technical contribution is a method for pseudodeterministically
extracting uniformly random strings from Haar-random states.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Future Directions
    3. 1.3 Technical Overview
      1. 1.3.1 Core Contribution: Pseudodeterministic Extractor
      2. 1.3.2 From Pseudodeterminism Extractor to Quantum PRGs
      3. 1.3.3 Quantum Pseudorandom Functions
      4. 1.3.4 Applications
  2. 2 Preliminaries
    1. 2.1 Quantum Algorithms
    2. 2.2 Pseudorandomness Notions
    3. 2.3 Basics of Statistics and Haar Measure
      1. 2.3.1 Chi-Squared Distributions
      2. 2.3.2 Haar Measure
    4. 2.4 Quantum State Tomography
  3. 3 Deterministically Extracting Classical Strings from Quantum States
  4. 4 Quantum PRGs and PRFs
    1. 4.1 Construction of QPRGs
    2. 4.2 Construction of Selectively Secure QPRFs
  5. 5 Applications
    1. 5.1 Pseudorandom One-Time Pad (POTP)
    2. 5.2 Quantum Commitment with Classical Communication
    3. 5.3 Non-Adaptive CPA-Secure Quantum Private-Key Encryption with Classical Ciphertexts
  6. A Full Proof of Theorem 4.5

##  1 Introduction

Deterministically generating long pseudorandom strings from a few random bits
is a fundamental task in classical cryptography. Pseudorandom generators
(PRGs) are a primitive that achieves this task and are ubiquitous throughout
cryptography. Beyond cryptography, pseudorandom generators have found
applications in complexity theory [RR94, LP20] and derandomization [NW94,
IW97].

The concept of pseudorandomness has also been explored in other contexts. Of
interest is the notion of pseudorandom quantum states, a popular
pseudorandomness notion studied in the quantum setting. Pseudorandom quantum
states (PRS), introduced by Ji, Liu, and Song [JLS18], are efficiently
computable states that are computationally indistinguishable from Haar-random
states. PRS have found numerous applications in other areas such as physics
[BFV20, BFG+22], quantum machine learning [HBC+22], and cryptography [AQY22,
MY21].

While some recent works make progress towards understanding the feasibility of
PRSGs (PRS generators), its relationship with PRGs111We are interested in PRGs
that guarantee security against efficient quantum adversaries. Typically, such
PRGs are referred to as post-quantum PRGs. For brevity, henceforth, by PRGs we
will mean post-quantum PRGs. and its implications to cryptography, there are
still some important gaps that are yet to be filled. While the directions
listed below might come across as seemingly unrelated, we will discuss how our
work addresses all these three different directions.

Direction 1. Separating PRSGs and PRGs We summarize the implication from PRGs
to PRSGs222The “S” is emphasized in this paragraph to highlight the difference
between PRSGs and PRGs. and back in the table below. [JLS18] showed that any
quantum-query secure PRF (implied by PRGs) implies the existence of
$\omega(\lambda)$-output length PRSGs, where $\lambda$ is the seed length. On
the other hand, Kretschmer [Kre21] showed a separation between
$\omega(\lambda)$-length PRSGs and PRGs. In the $c\cdot\log(\lambda)$-regime,
where $c\in\mathbb{R}$ and $c\ll 1$, [BS20] showed that
$c\cdot\log(\lambda)$-length PRSGs can be constructed unconditionally. Hence
there is a trivial separation between $c\cdot\log(\lambda)$-length PRSGs, with
$c\ll 1$, and PRGs since the latter requires computational assumptions. In the
same work, [BS20] showed that $c\cdot\log(\lambda)$-length PRSGs, when $c\gg
1$, can be constructed from PRGs. However, whether PRSGs with output length at
least $\log(\lambda)$ imply PRGs or are separated from it is currently
unknown.

Output Length of PRSG | Implied by PRG? | Implication to PRG?
---|---|---
$\omega(\log(\lambda))$ | Yes [JLS18] | Black-box separation [Kre21]
$c\cdot\log(\lambda))$, $c\geq 1$ | Yes [BS20] | unknown
$c\cdot\log(\lambda))$, $c\ll 1$ | N/A | Separation
| (Information-theoretic [BS20]) | (trivial)

Thus, the following question has been left open.

> Does $\log(\lambda)$-length PRS imply PRGs or is it (black-box) separated
> from PRGs?

Direction 2. Hybrid Cryptography. While the recent results demonstrate
constructions of quantum cryptographic tasks such as commitments, zero-
knowledge and secure computation from assumptions potentially weaker than one-
way functions, the main drawback of these constructions is that they require
the existence of quantum communication channels, an undesirable feature.
Starting with the work of Gavinsky [Gav12], there has been an effort in
building quantum cryptographic primitives using classical communication
channels. We can thus characterize the class of cryptographic primitives into
three categories: classical cryptography (that uses only classical resources),
hybrid cryptography (uses quantum computing but classical communication
channels) and quantum cryptography (no restrictions). Hybrid cryptography has
the advantage that the primitives in this category could be based on
assumptions weaker than classical cryptography but on the other hand, has the
advantage that we only need classical communication channels. Towards a deeper
understanding of hybrid cryptography, the following is a pertinent question:

> Identify foundational primitives in hybrid cryptography and understand their
> relationship with classical and quantum cryptographic primitives.

Direction 3. Domain Extension, Generically. Given any pseudorandom generator
of output length $m$, we know how to generically transform it into another
secure pseudorandom generator of length $\ell$, for any $\ell>m$. On the other
hand, we have limited results for pseudorandom quantum states. Recently,
[GJMZ23] showed that multi-copy $\omega(\lambda)$-length PRS implies a single-
copy PRS with large output length. However, we are not aware of any length
extension transformation that preserves the number of copies. Investigating
this question will help us understand the relationship between PRSs of
different output lengths. This leads to the following question:

> Can we generically transform a multi-copy $n$-output PRS into a multi-copy
> $\ell$-output PRS, where $\ell\gg n$? Or is there a black-box separation?

##### Our Work.

Towards simultaneously addressing all three directions above, we introduce the
notion of _quantum pseudorandom generators (QPRGs)_ : which are like classical
PRGs in that the input is a short classical string and the output is a longer
classical string that is computationally indistinguishable from uniform, but
(a) generation algorithm is a quantum algorithm, and (b) the mapping from seed
to output only has to be _pseudodeterministic_ (i.e., for a fixed seed, the
output is a fixed string with high probability). We first show that
assumptions that are plausibly weaker than the existence of classical
OWFs/PRGs can be used to build QPRGs: we show that QPRGs can be constructed
from logarithmic-output PRSGs. In other words, we can generate pseudorandom
strings using pseudorandom quantum states in a (pseudo-)deterministic fashion.
We then present cryptographic applications of QPRGs and highlight some
implications for the structure of classical versus quantum cryptography.

The reader might wonder whether the notion of quantum generation of classical
pseudorandomness is trivial. After all, since quantum computation is
inherently probabilistic and can generate unlimited randomness starting from a
fixed input, why would one need _pseudo_ randomness? However, for
cryptographic applications having a source of randomness is not enough; it is
important that some random-looking string can be _deterministically generated_
using a secret key.

###  1.1 Our Results

##### Quantum PRGs from PRS.

Informally, a $(1-\varepsilon)$-pseudodeterministic QPRG is a quantum
algorithm $G$ where

  * •

(_Pseudodeterminism_) For $1-\varepsilon$ fraction of seeds
$k\in\\{0,1\\}^{\lambda}$ outputs a fixed string $y_{k}\in\\{0,1\\}^{n}$ with
probability at least $1-\varepsilon$, and

  * •

(_Pseudorandomness_) For all efficient quantum distinguishers $A$,

$\Big{|}\Pr_{k\leftarrow\\{0,1\\}^{\lambda}}[A(G(k))=1]-\Pr_{y\leftarrow\\{0,1\\}^{n}}[A(y)=1]\Big{|}\leq\mathsf{negl}(\lambda)~{}.$

In other words, no efficient quantum adversary can distinguish between the
output of the generator and a uniformly random string.

(See Section 4 for a formal definition of QPRGs). Our first result is the
following:

######  Theorem 1.1 (Informal).

Assuming the existence of logarithmic PRS, there exist
$\Big{(}1-\frac{1}{\mathsf{poly}(\lambda)}\Big{)}$-pseudodeterministic QPRGs.

Our result has several implications.

  * •

Implication to Direction 1 (Separating PRSGs and PRGs). Perhaps surprisingly,
our result suggests that in the logarithmic output regime, PRS and PRGs are
not separated. This is unlike the super-logarithmic output regime and sub-
logarithmic output regime both of which are separated from PRGs. In contrast,
in the classical setting, achieving more pseudorandom bits is harder (in some
cases strictly [OW14]) than achieving a few pseudorandom bits. Our result when
combined with prior results [JLS18, BS20] gives a better picture on the
relationship between PRS and PRGs (refer to the table in the introduction).

  * •

Implication to Direction 2 (Hybrid Cryptography). Quantum pseudorandom
generator is a hybrid cryptographic primitive since it has a quantum
generation algorithm but classical inputs and outputs. Later, we show that
QPRGs imply many other hybrid cryptographic primitives such as quantum bit
commitments with classical communication, quantum encryption with classical
ciphertexts, and so on. Our results suggest that QPRGs could play a similar
role in hybrid cryptography as PRGs did in classical cryptography. Proving
whether QPRGs is a minimal assumption in hybrid cryptography, akin to how PRGs
is a minimal assumption in classical cryptography [Gol90], is an interesting
open question. Furthermore, our result above highlights connections between
hybrid and quantum cryptography.

  * •

Implication to Direction 3 (Domain Extension, Generically). In the above
result, unfortunately, we only obtain QPRGs with inverse polynomial
pseudodeterminism error. Suppose we can reduce the error to be negligible then
we claim that $O(\log(\lambda))$-output PRS can be generically transformed
into $\omega(\log(\lambda))$-output PRS. This can be achieved by appropriately
instantiating the construction of Ji, Liu, and Song [JLS18] using quantum
pseudorandom generators, which in turn can be built from
$O(\log(\lambda))$-output PRS. Thus, the question of whether we can
generically increase the output length of PRS is related to the question of
reducing pseudodeterminism error in the above theorem.

  * •

Other Implications: New Approach to Pseudorandomness. One implication of our
QPRG construction is that it demonstrates an “inherently quantum” way to
generate classical pseudorandomness. There are plausible candidates for PRS
(even the logarithmic-length ones) that don’t seem to involve any classical
OWFs in them at all; for example, it is conjectured that random polynomial-
size quantum circuits generate pseudorandom states [AQY22].

##### Applications of Quantum PRGs.

Next we investigate the cryptographic applications of QPRGs. We demonstrate
that QPRGs can effectively replace classical pseudorandom generators in some
applications; although the QPRGs are not entirely deterministic, being
$(1-\frac{1}{\mathsf{poly}(\lambda)})$-pseudodeterministic is good enough.

Concretely, we explore two applications: statistically binding and
computationally hiding commitments, and pseudo one-time pads. While [AGQY22]
previously demonstrated that these applications can be based on logarithmic
PRS, we provide alternate proofs assuming the existence of QPRGs combined with
Theorem 1.1. Moreover, our constructions resemble the textbook constructions
of classical commitments and pseudo one-time pads and thus, are conceptually
simpler than the ones presented by [AGQY22].

A statistically binding commitment scheme is a fundamental cryptographic
notion where a sender commits to a value such that it is infeasible, even if
it is computationally unbounded, for them to change their commitment to a
different value. Statistically binding quantum commitments have been a
critical tool to achieve another fundamental notion in cryptography, namely
secure computation [BCKM21, GLSV21]. We demonstrate that statistically binding
and computationally hiding commitments can be constructed from QPRGs.

######  Theorem 1.2 (Informal).

Assuming the existence of
$(1-\frac{1}{\mathsf{poly}(\lambda)})$-pseudodetermininistic QPRGs, there
exist statistically binding and computationally hiding quantum commitments
with classical communication.

It is worth mentioning that there is another recent work [BBSS23] that also
builds quantum commitments with classical communication albeit from
incomparable assumptions333They consider a variant of PRS referred to as PRS
with proof of deletion. On one hand, they don’t have restriction on the output
length like we do and on the other hand, they assume that PRS satisfies the
additional proof of deletion property whereas we don’t..

Pseudo one-time pads are a variation of the one-time pad encryption scheme,
where the encryption key is much smaller than the message length. As
demonstrated by [AQY22], pseudo one-time pads are useful for constructing
classical garbling schemes [AIK06] and quantum garbling schemes [BY22], which
have numerous applications in cryptography. We demonstrate that pseudo one-
time pads can be constructed from QPRGs.

######  Theorem 1.3 (Informal).

Assuming the existence of
$(1-\frac{1}{\mathsf{poly}(\lambda)})$-pseudodetermininistic QPRGs, there
exist pseudo one-time pads.

##### Quantum PRFs.

In addition to the above, we also explore pseudorandom functions with a
quantum generation algorithm, which we call quantum pseudorandom functions
(QPRFs). We show the following theorem:

######  Theorem 1.4 (Informal).

Assuming the existence of $(\omega(\log\lambda),O(\log\lambda))$-PRFS, there
exists a quantum pseudorandom function (QPRF) satisfying determinism with
probability at least $\left(1-\frac{1}{\mathsf{poly}(\lambda)}\right)$.

In the above theorem, we use pseudorandom function-like states [AQY22], a
quantum analog of pseudorandom functions, to accomplish this. The notion of
pseudorandom function-like states says the following: $t$ copies of states
$(\ket{\psi_{x_{1}}},\ldots,\ket{\psi_{x_{q}}})$ are computationally
indistinguishable from $t$ copies of $q$ Haar states, where
$\ket{\psi_{x_{i}}}$, for every $i\in[q]$, is produced using an efficient PRFS
generator that receives as input a key $k\in\left\\{0,1\right\\}^{\lambda}$,
picked uniformly at random, and an input
$x_{i}\in\left\\{0,1\right\\}^{\lambda}$. Just like in the case of QPRGs, in
the above theorem, we require PRFS with logarithmic input length.

We show how to leverage QPRFs to achieve private-key encryption with QPT
algorithms and classical communication, which is the first result to achieve
this notion from assumptions potentially weaker than one-way functions.

###  1.2 Future Directions

Our research raises several important open questions that remain to be
explored. Below, we highlight two particularly interesting ones.

##### Separating QPRGs and QPRFs from Classical Cryptography.

While QPRGs and QPRFs are similar in flavor to their classical counterparts,
their ability to generate quantum states suggests that they may be based on
weaker assumptions than classical pseudorandom generators and functions. A key
question is whether there is a fundamental separation between QPRGs and PRGs,
as well as between QPRFs and PRFs. Proving that there is no separation would
require a mechanism to efficiently dequantize the generation algorithm, which
is a challenging task. This is especially true if the quantum generation
algorithm involves running a quantum algorithm that is believed to be
difficult to efficiently dequantize; for example, Shor’s algorithm.

##### Reducing Determinism Error.

One limitation of both QPRGs and QPRFs is that they suffer from inverse
polynomial determinism error. It would be interesting to explore whether this
error can be reduced to negligible, or whether a negative result can be
proven. Understanding the fundamental limits of determinism in quantum
pseudorandomness could have important implications. For instance, due to the
inverse polynomial error, it is unclear how to apply the GGM transformation
[GGM86] to go from quantum pseudorandom generators to quantum pseudorandom
functions.

###  1.3 Technical Overview

We summarise our technical contributions below:

  * •

We identify the definition of pseudodeterministic extractor that gives quantum
pseudorandom generators. We then realize the notion of pseudodeterministic
extractors; this is our core technical contribution and it involves using
interesting properties about the Haar measure in the analysis.

  * •

We define and realize quantum pseudorandom functions from logarithmic output
pseudorandom function-like states. Defining quantum PRFs turns out to be
subtle.

  * •

We demonstrate applications of quantum pseudorandom generators and functions
to commitments and encryption schemes. Especially, in commitment schemes, it
turns out to be tricky to argue security due to the inverse polynomial
determinism error.

####  1.3.1 Core Contribution: Pseudodeterministic Extractor

We focus on the goal of building a quantum pseudorandom generator from
$O(\log(\lambda))$-qubit pseudorandom quantum states. Towards this goal, we
identify the important step as follows: extracting
$\mathsf{poly}(d(\lambda))$-length binary strings from
$\log(d(\lambda))$-qubit Haar states in such a way, the following key
properties are satisfied:

  * •

Pseudodeterminism: Running the extraction process on
$\mathsf{poly}(d(\lambda))$-copies of $|\psi\rangle$ should give the same
string $y$ with a very high probability. Ideally, with probability at least
$1-\frac{1}{\mathsf{poly}(d(\lambda))}$,

  * •

Efficiency: The extraction process should run in time
$\mathsf{poly}(d(\lambda))$,

  * •

Statistical Indistinguishability: The string $y$ is statistically close to the
uniform distribution over $\\{0,1\\}^{\mathsf{poly}(d(\lambda))}$ as long as
$|\psi\rangle$ is sampled from the Haar distribution. Here, we allow the total
variation distance error to be as large as $O(\frac{1}{d})$.

It turns out most of the work goes in achieving the pseudodeterminism
property.

##### Toy Case.

Towards designing an extractor satisfying the above three properties, we first
consider an alternate task. Instead of $\mathsf{poly}(d(\lambda))$-copies of
the $\log(d(\lambda))$-qubit state $|\psi\rangle$, we are given all the
amplitudes of $|\psi\rangle$, say $(\alpha_{1},\ldots,\alpha_{d(\lambda)})$,
in the clear. Can we extract true randomness from this? For instance, we could
extract $b_{1},\ldots,b_{d(\lambda)}$, where $b_{i}$ is the first bit of the
real component of $\alpha_{i}$. Firstly, it is not even clear that $b_{i}$ is
distributed to according to the uniform distribution over $\\{0,1\\}$.
Moreover, all the bits $b_{1},\ldots,b_{d(\lambda)}$ are not independent and
in fact, are correlated with each other due to the normalization condition
$\sum_{i}|\alpha_{i}|^{2}=1$.

Fortunately, we can rely upon a result in random matrix theory [Mec19], that
states the following: suppose $(\alpha_{1},\ldots,\alpha_{d(\lambda)})$ are
drawn from a Haar measure in ${\mathcal{S}}(\mathbb{R}^{d})$ then it holds
that any $o(d(\lambda))$ co-ordinates of
$(\alpha_{1},\ldots,\alpha_{d(\lambda)})$ are $1/o(d(\lambda))$-close in total
variation distance with $o(d(\lambda))$-dimensional vector where each
component is drawn from i.i.d Gaussian ${\mathcal{N}}(0,\frac{1}{d})$.

We generalize this result to the case when
$(\alpha_{1},\ldots,\alpha_{d(\lambda)})$ are drawn from a Haar measure in
${\mathcal{S}}(\mathbb{C}^{d})$, and not ${\mathcal{S}}(\mathbb{R}^{d})$ (see
Corollary 2.13) at the cost of reducing the standard deviation from
$\frac{1}{d}$ to $\frac{1}{2d}$. We then use our observation to come up with
an extractor as follows. The extractor takes as input444For the current
discussion, we assume that the extractor has an infinite input tape that
allows for storing infinite bits of precision of the complex numbers.
$(\alpha_{1},\ldots,\alpha_{d(\lambda)})$,

  * •

Choose the first $k=o(d(\lambda))$ entries among
$(\alpha_{1},\ldots,\alpha_{d(\lambda)})$.

  * •

Rounding step: for every $i\in[k]$, if ${\sf Re}(\alpha_{i})>0$, then set
$b_{i}=0$. Otherwise, set $b_{i}=1$.

  * •

Output $b_{1}\cdots b_{k}$.

From our observation and the symmetricity of ${\mathcal{N}}(0,\frac{1}{d})$,
it follows that when $(\alpha_{1},\ldots,\alpha_{d(\lambda)})$ is drawn from a
Haar distribution on ${\mathcal{S}}(\mathbb{C}^{d})$ then the output of the
extractor is $o(\frac{1}{d(\lambda)})$-close to uniform distribution on
$\\{0,1\\}^{k}$. Moreover, the above procedure is deterministic.

##### Challenges.

Our hope is to leverage the above ideas to design an extractor that can
extract given $\mathsf{poly}(d(\lambda))$-copies of a
$O(\log(d(\lambda)))$-qubit Haar state $\ket{\psi}$. We encounter a couple of
challenges.

  1. 1.

First challenge: We have access only to the copies of
$\ket{\psi}\\!\bra{\psi}$ without the amplitudes given to us in plain text,
making it infeasible to implement the previously described method. However, we
can still carry out tomography and retrieve an estimated version of the matrix
$\ket{\psi}\\!\bra{\psi}$. If the amplitudes of $\ket{\psi}$ are
$\\{\alpha_{x}\\}_{x\in[d]}$ then the $(x,y)^{th}$ entry in the density matrix
$\ket{\psi}\\!\bra{\psi}$ is $\alpha_{x}\alpha_{y}^{*}$. We need to analyze
the distribution corresponding to $\alpha_{x}\alpha_{y}^{*}$ and, design an
approach for obtaining a uniform distribution from it.

  2. 2.

Second challenge: Tomography is inherently a probabilistic technique, and
hence, each time tomography is executed on multiple copies of $\ket{\psi}$,
the output obtained may differ. Additionally, the trace distance between the
density matrix obtained via tomography and the original density matrix is
inversely proportional to the dimension, which is polynomial in this case, and
this may be significant. Both of these factors collectively affect the
determinism guarantees of the extractor. In general, it is not feasible to
partition ${\mathcal{S}}(\mathbb{C}^{d})$ into regions labeled by a bitstring
such that given multiple copies of a state in a region, the corresponding
bitstring can be deterministically recovered.

We tackle the above challenges using the following insights.

##### Addressing the first challenge.

We first tackle the first bullet above. Notice that the diagonal entries in
the density matrix $\ket{\psi}\\!\bra{\psi}$ is
$\\{|\alpha_{i}|^{2}\\}_{i\in[d(\lambda)]}$, where
$\ket{\psi}=\sum_{i}\alpha_{i}\ket{i}$. If $\alpha_{j}=a_{j}+ib_{j}$ then
$|\alpha_{j}|^{2}=a_{j}^{2}+b_{j}^{2}$. Given our earlier observation about
the closeness of $o(d(\lambda))$ entries in a vector drawn from
${\mathcal{S}}(\mathbb{C}^{d})$ with iid Gaussian, we will make the following
simplifying assumption. We assume that $(\alpha_{1},\ldots,\alpha_{k})$, where
$k=o(d)$, is sampled such that for every $i\in[k]$, $a_{i}$ and $b_{i}$ are
distributed according to i.i.d Gaussian ${\mathcal{N}}(0,\frac{1}{2d})$. From
this, it follows that $|\alpha_{i}|^{2}$ is distributed according to a chi-
squared distribution with 2 degrees of freedom. Unfortunately, chi-squared
distribution does not have the same nice symmetricity property as a Gaussian
distribution. So we will instead extract randomness in a different way.

We divide $(|\alpha_{1}|^{2},\ldots,|\alpha_{k}|^{2})$ into blocks of size $r$
and denote $\ell$ to be the number of blocks, where $r,\ell=o(d)$. Then, add
the elements in a block. Call the resulting elements $q_{1},\ldots,q_{\ell}$.
From central limit theorems [SM62], one can show that $q_{1},\ldots,q_{\ell}$
are $O(1/\sqrt{r})$-close to $\ell$ samples drawn i.i.d from
$\mathcal{N}(\frac{r}{d},\frac{r}{d^{2}})$. Thus, using central limit theorem,
we are back to the normal distribution, except that the mean is shifted to
$\frac{r}{d}$ rather than 0. This gives rise to a natural rounding mechanism.

We will check if $q_{i}>\frac{r}{d}$ and if so, we set a bit $b_{i}=0$ and if
not, we set it to be 0. By carefully choosing the parameters $k$ and $\ell$
and combining the above observations, we can argue that $b_{1},\ldots,b_{k}$
is $O(d^{-1/6})$-close to the uniform distribution on $\\{0,1\\}^{\ell}$.

To summarise, the informal description of the extractor is as follows: given
$\mathsf{poly}(d)$ copies of a $d$-dimensional state $\ket{\psi}$,

  * •

First perform tomography to recover a matrix
$M\in\mathbb{C}^{d}\times\mathbb{C}^{d}$ that is an approximation of
$\ket{\psi}\\!\bra{\psi}$

  * •

Then, pick $o(d)$ diagonal entries in $M$ and break this into $\ell$ blocks of
size $r$.

  * •

Sum up all the entries in each block to get $\ell$ values
$q_{1},\ldots,q_{\ell}$. Round every $q_{i}$ to get $b_{i}$.

  * •

Output $b_{1},\ldots,b_{\ell}$.

##### Addressing the second challenge.

While the above construction seems promising, we still have not addressed the
second challenge pertaining to the determinism property. It could be the case
that all the $q_{i}$s are very close to the mean and due to the tomography
error, every time we try to extract we set $b_{i}=0$ sometimes and $b_{i}=1$
the rest of the time. This should not be surprising as we said earlier, that
it should not be possible to partition ${\mathcal{S}}(\mathbb{C}^{d})$ such
that for every $\ket{\psi}$, there is a bitstring $b_{\psi}$ such that given
many copies of $\ket{\psi}$, the extractor always outputs the same bitstring
$b_{\psi}$.

In fact, we can identify a forbidden region in
${\mathcal{N}}(\frac{r}{d},\frac{r}{d^{2}})$ (see Figure 1 below) such that if
$q_{i}$ falls into the forbidden region then there is a significant chance
that $q_{i}$ will be classified as either 0 or 1. The forbidden region has
width $\frac{1}{d}$ on either side of the mean. Given this, we give up all
hope of achieving perfect determinism and instead shoot for determinism with
$o(1/d)$ error.

We identify a set of $d(\lambda)$-dimensional states ${\mathcal{G}}_{\Delta}$,
where $\Delta=\frac{1}{d}$, such that if a state $\ket{\psi}$ is in
${\mathcal{G}}_{\Delta}$ then it holds that none of $q_{1},\ldots,q_{\ell}$,
generated from $\ket{\psi}$, lies in the forbidden region. The setting of
$\Delta$ is carefully chosen to accommodate for the error in tomography.

$x$${\mathcal{N}}\left(\frac{r}{d},\frac{r}{d^{2}}\right)$$\frac{1}{d}$ Figure
1: The red region denotes the forbidden region.

Once ${\mathcal{G}}_{\Delta}$ is identified, we prove two things:

  * •

Firstly, if a state is sampled from the Haar distribution on
${\mathcal{S}}(\mathbb{C}^{d(\lambda)})$ then with at least
$1-o\left(\frac{1}{d}\right)$ probability,
$\ket{\psi}\in{\mathcal{G}}_{\Delta}$.

  * •

Secondly, for every $\ket{\psi}\in\mathcal{G}_{\Delta}$, the probability that
the extractor, given $\mathsf{poly}(d(\lambda))$-copies of $\ket{\psi}$,
outputs the same string twice is at least $1-o\left(\frac{1}{d}\right)$.
Roughly, this follows from the fact that $(q_{1},\ldots,q_{\ell})$, generated
from $\ket{\psi}$, gets misclassified with very small probability.

We can leverage the above two observations to show that our extractor
satisfies determinism with probability at least $1-o\left(\frac{1}{d}\right)$.

####  1.3.2 From Pseudodeterminism Extractor to Quantum PRGs

With the pseudodeterministic extractor in hand, we propose the following
construction of quantum pseudorandom generators: on input a seed
$k\in\\{0,1\\}^{\lambda}$,

  * •

Perform this procedure polynomially many times: run the PRS generator on $k$
to produce the PRS state $\ket{\psi}$,

  * •

Run the pseudodeterministic extractor (discussed in Section 1.3.1) on
polynomially many copies of $\ket{\psi}$ to obtain a binary string $y$,

  * •

Output $y$.

Recall that the guarantees of the pseudodeterministic extractor only hold for
Haar states. In the above construction, we are invoking the extractor on PRS
states. However, we can invoke the security of PRSGs to replace PRS states
with Haar states and then invoke the guarantees of the extractor. Just like
the extractor, the above quantum PRG would also suffer from an inverse
polynomial determinism error. Similarly, the above construction would suffer
from inverse polynomial error in security; that is, the output of the above
QPRG (on a random seed) cannot be distinguished from a uniformly random output
with at most inverse polynomial error. We call a QPRG that satisfies inverse
polynomial determinism error and inverse polynomial security error to be a
weak QPRG and a QPRG that satisfies negligible security error to be a strong
QPRG.

While we currently do not know how to reduce the pseudodeterminism error,
there is still hope to reduce the security error. Indeed, there are security
amplification techniques that are well studied in the classical cryptography
literature.

##### From Weak QPRG to Strong QPRG.

The naive approach of going from a weak QPRG to a strong QPRG is to use
parallel repetition: on input a seed of length $s\cdot\lambda$, break the seed
into $s$ parts, apply QPRG on each of them and then XOR the outputs. While
this should help security (as we see below), it hurts pseudodeterminism. Using
union bound, we can argue that the pseudodeterminism error increases by a
multiplicative factor of $\lambda$. Thus, if we start with a weak PRG with a
sufficiently small pseudodeterminism error then this multiplicative factor
won’t hurt us.

To prove that the security error is negligible, we will use XOR-based security
amplification techniques [DIJK09, MT09, MT10]. The analysis in the
amplification theorems [DIJK09, MT09, MT10] was initially tailored to
classical settings, using a careful analysis, we show that the analysis also
extends to the quantum setting.

####  1.3.3 Quantum Pseudorandom Functions

We also demonstrate the connections between quantum pseudorandom functions and
logarithmic-output pseudorandom function-like states [AGQY22].

Roughly speaking, a quantum pseudorandom function is a pseudorandom function
except that the generation algorithm is quantum and moreover, we allow for
inverse polynomial determinism error. Defining the security of this notion
requires some care. If we allow the adversary to make arbitrary queries to the
oracle (that is either the QPRF or the random function) then such a notion is
clearly impossible to achieve. For instance, the adversary can query the same
input twice; in the case when the oracle implements a random function, we
always get the same output, and in the QPRF case, there is an inverse
polynomial probability with which we get different outputs. Hence, we restrict
our attention to the setting when the adversary only makes selective and
distinct queries. We show that this definition is sufficient for applications.

The construction of QPRFs from logarithmic-output PRFS follows along similar
lines as the construction of QPRGs from pseudodeterminism extractors.

####  1.3.4 Applications

We show that QPRGs imply both statistically binding commitments and pseudo-
one-time pads. The constructions are similar to the existing constructions
from (classical) pseudorandom generators except that we need to contend with
the inverse polynomial determinism error. For most of the applications, naive
parallel repetition and a majority argument are sufficient to circumvent the
determinism issue. However, for the application of commitments, the analysis
turns out to be relatively more complicated.

##### Commitments.

The construction of statistically binding commitments from QPRGs is inspired
by Naor commitments [Nao91].

To recall Naor’s construction: the receiver sends a random string $r$ of
length $3\lambda$ to the sender who applies a classical pseudorandom generator
with output length $3\lambda$ on a random seed of length $\lambda$. Depending
on the message bit, the sender either XORs the output with $r$ or sends the
PRG output as-is. The proof of binding relies upon the fact that the number of
pairs of keys whose outputs when XORed with each other lead to $r$ is
precisely upper bounded by $2^{2\lambda}$, which is negligible in comparison
with all possible values of $r$.

A natural modification to the above construction is to replace the PRG with
quantum pseudorandom generator. The immediate issue that arises here is
correctness due to the inverse polynomial determinism error. Again, using
naive parallel repetition we can resolve the determinism error: where the
sender computes many QPRG outputs on independent seeds and depending on the
message, the outputs are either XORed with $r$ or kept as-is. In the modified
construction, arguing hiding is fairly straightfoward. However, arguing the
binding property requires some care.

Naor’s binding argument cannot be immediately generalized to the QPRG setting
since it has inverse polynomial determinism error. However, we come up with a
different argument in this setting: in two technical claims, 5.10 and 5.11, we
prove that the statistical binding property still holds. Roughly speaking, the
intuition behind the argument is as follows. Suppose ${\sf Bad}$ be the set of
QPRG seeds where the pseuodeterminism error is too high; larger than any
inverse polynomial and ${\sf Good}$ be the set containing the rest of the QPRG
seeds. If the adversarial sender chooses from ${\sf Bad}$ in the commit phase
(or even in the opening phase), it could only hurt itself because it will not
be able to control the output of the QPRG during the verification process
executed by the receiver in the opening phase. On the other hand, if the
adversarial sender commits to seed from ${\sf Good}$ in the commit phase and
sends (a possibly different) seed from ${\sf Good}$ in the opening phase then
using the fact that the outputs are mostly deterministic, we can argue that
with overwhelming probability over $r$, the XOR of the two seeds does not
equal $r$.

##  2 Preliminaries

We refer the reader to [NC10] for a comprehensive reference on the basics of
quantum information and quantum computation. We use $I$ to denote the identity
operator. We use $\mathcal{S}(\mathcal{H})$ to denote the set of unit vectors
in the Hilbert space $\mathcal{H}$. We use $\mathcal{D}(\mathcal{H})$ to
denote the set of density matrices in the Hilbert space $\mathcal{H}$. Let
$P,Q$ be distributions. We use $d_{TV}(P,Q)$ to denote the total variation
distance between them. Let $\rho,\sigma\in\mathcal{D}(\mathcal{H})$ be density
matrices. We write $\operatorname{TD}(\rho,\sigma)$ to denote the trace
distance between them, i.e.,

$\operatorname{TD}(\rho,\sigma)=\frac{1}{2}\|\rho-\sigma\|_{1}$

where ${\left\lVert X\right\rVert}_{1}=\mathrm{Tr}(\sqrt{X^{\dagger}X})$
denotes the trace norm. We denote ${\left\lVert
X\right\rVert}:=\sup_{\ket{\psi}}\\{\braket{\psi}{X}{\psi}\\}$ to be the
operator norm where the supremum is taken over all unit vectors. For a vector
$\ket{x}$, we denote its Euclidean norm to be
${\left\lVert\ket{x}\right\rVert}_{2}$. We use the notation $M\geq 0$ to
denote the fact that $M$ is positive semi-definite.

##### Haar Measure.

The Haar measure over $\mathbb{C}^{d}$, denoted by
$\mathscr{H}(\mathbb{C}^{d})$ is the uniform measure over all $d$-dimensional
unit vectors. One useful property of the Haar measure is that for all
$d$-dimensional unitary matrices $U$, if a random vector $\ket{\psi}$ is
distributed according to the Haar measure $\mathscr{H}(\mathbb{C}^{d})$, then
the state $U\ket{\psi}$ is also distributed according to the Haar measure. For
notational convenience we write $\mathscr{H}_{m}$ to denote the Haar measure
over $m$-qubit space, or $\mathscr{H}((\mathbb{C}^{2})^{\otimes m})$.

###  2.1 Quantum Algorithms

A quantum algorithm $A$ is a family of generalized quantum circuits
$\\{A_{\lambda}\\}_{\lambda\in\mathbb{N}}$ over a discrete universal gate set
(such as $\\{CNOT,H,T\\}$). By generalized, we mean that such circuits can
have a subset of input qubits that are designated to be initialized in the
zero state, and a subset of output qubits that are designated to be traced out
at the end of the computation. Thus a generalized quantum circuit
$A_{\lambda}$ corresponds to a _quantum channel_ , which is a is a completely
positive trace-preserving (CPTP) map. When we write $A_{\lambda}(\rho)$ for
some density matrix $\rho$, we mean the output of the generalized circuit
$A_{\lambda}$ on input $\rho$. If we only take the quantum gates of
$A_{\lambda}$ and ignore the subset of input/output qubits that are
initialized to zeroes/traced out, then we get the _unitary part_ of
$A_{\lambda}$, which corresponds to a unitary operator which we denote by
$\hat{A}_{\lambda}$. The _size_ of a generalized quantum circuit is the number
of gates in it, plus the number of input and output qubits.

We say that $A=\\{A_{\lambda}\\}_{\lambda}$ is a _quantum polynomial-time
(QPT) algorithm_ if there exists a polynomial $p$ such that the size of each
circuit $A_{\lambda}$ is at most $p(\lambda)$. We furthermore say that $A$ is
_uniform_ if there exists a deterministic polynomial-time Turing machine $M$
that on input $1^{\lambda}$ outputs the description of $A_{\lambda}$.

We also define the notion of a _non-uniform_ QPT algorithm $A$ that consists
of a family $\\{(A_{\lambda},\rho_{\lambda})\\}_{\lambda}$ where
$\\{A_{\lambda}\\}_{\lambda}$ is a polynomial-size family of circuits (not
necessarily uniformly generated), and for each $\lambda$ there is additionally
a subset of input qubits of $A_{\lambda}$ that are designated to be
initialized with the density matrix $\rho_{\lambda}$ of polynomial length.
This is intended to model nonuniform quantum adversaries who may receive
quantum states as advice. Nevertheless, the reductions we show in this work
are all uniform.

The notation we use to describe the inputs/outputs of quantum algorithms will
largely mimick what is used in the classical cryptography literature. For
example, for a state generator algorithm $G$, we write $G_{\lambda}(k)$ to
denote running the generalized quantum circuit $G_{\lambda}$ on input
$\ket{k}\\!\bra{k}$, which outputs a state $\rho_{k}$.

Ultimately, all inputs to a quantum circuit are density matrices. However, we
mix-and-match between classical, pure state, and density matrix notation; for
example, we may write $A_{\lambda}(k,\ket{\theta},\rho)$ to denote running the
circuit $A_{\lambda}$ on input
$\ket{k}\\!\bra{k}\otimes\ket{\theta}\\!\bra{\theta}\otimes\rho$. In general,
we will not explain all the input and output sizes of every quantum circuit in
excruciating detail; we will implicitly assume that a quantum circuit in
question has the appropriate number of input and output qubits as required by
context.

###  2.2 Pseudorandomness Notions

The notion of pseudorandom quantum states was first introduced by Ji, Liu, and
Song in [JLS18]. We present the following relaxed definition of pseudorandom
state (PRS) generators.555In [JLS18], the output of the generator needs to be
pure; while we allow it to be mixed. We note that the relaxation is due to
[AQY22].

######  Definition 2.1 (Pseudorandom State (PRS) Generator).

We say that a QPT algorithm $G$ is a _pseudorandom state (PRS) generator_ if
the following holds.

  1. 1.

State Generation. For all $\lambda\in\mathbb{N}$ and all
$k\in{\\{0,1\\}}^{\lambda}$, the algorithm $G$ behaves as
$G_{\lambda}(k)=\rho_{k}$ for some $n(\lambda)$-qubit (possibly mixed) quantum
state $\rho_{k}$.

  2. 2.

Pseudorandomness. For all polynomials $t(\cdot)$ and any (non-uniform) QPT
distinguisher $A$, there exists a negligible function $\varepsilon(\cdot)$
such that for all $\lambda\in\mathbb{N}$, we have

$\displaystyle\left|\Pr_{k\leftarrow{\\{0,1\\}}^{\lambda}}[A_{\lambda}(G_{\lambda}(k)^{\otimes
t(\lambda)})=1]-\Pr_{\ket{\vartheta}\leftarrow\mathscr{H}_{n(\lambda)}}[A_{\lambda}(\ket{\vartheta}^{\otimes
t(\lambda)})=1]\right|\leq\varepsilon(\lambda).$

We also say that $G$ is an _$n(\lambda)$ -PRS generator_ to succinctly
indicate that the output length of $G$ is $n(\lambda)$.

######  Definition 2.2 (Selectively Secure Pseudorandom Function-Like State
(PRFS) Generators).

We say that a QPT algorithm $G$ is a _selectively secure pseudorandom
function-like state (PRFS) generater_ if for all polynomials
$q(\cdot),t(\cdot)$, any (non-uniform) QPT distinguisher $A$, and any family
of pairwise distinct indices
$\left(\left\\{x_{1},\dots,x_{q(\lambda)}\right\\}\subseteq{\\{0,1\\}}^{m(\lambda)}\\}\right)_{\lambda}$,
there exists a negligible function $\varepsilon(\cdot)$ such that for all
$\lambda\in\mathbb{N}$,

$\Big{\lvert}\Pr_{k\leftarrow{\\{0,1\\}}^{\lambda}}\left[A_{\lambda}(x_{1},\dots,x_{q(\lambda)},G_{\lambda}(k,x_{1})^{\otimes
t(\lambda)},\dots,G_{\lambda}(k,x_{q(\lambda)})^{\otimes
t(\lambda)})=1\right]\\\
-\Pr_{\ket{\vartheta_{1}},\dots,\ket{\vartheta_{q(\lambda)}}\leftarrow\mathscr{H}_{n(\lambda)}}\left[A_{\lambda}(x_{1},\dots,x_{q(\lambda)},\ket{\vartheta_{1}}^{\otimes
t(\lambda)},\dots,\ket{\vartheta_{q(\lambda)}}^{\otimes
t(\lambda)})=1\right]\Big{\rvert}\leq\varepsilon(\lambda).$

We also say that $G$ is an _$(m(\lambda),n(\lambda))$ -PRFS generator_ to
succinctly indicate that its input length is $m(\lambda)$ and its output
length is $n(\lambda)$.

###  2.3 Basics of Statistics and Haar Measure

A simple yet useful observation is that for any two density matrices, the
difference between any of their diagonal entries is bounded above by their
trace distance.

######  Fact 2.3.

For any density matrices $\rho,\sigma\in\mathcal{D}(\mathbb{C}^{d})$, it holds
that
$\max_{i\in[d]}|\rho_{ii}-\sigma_{ii}|\leq\operatorname{TD}(\rho,\sigma)$,
where $\rho_{ii},\sigma_{ii}$ denote the $i$-th diagonal entry of
$\rho,\sigma$ respectively, i.e., $\rho_{ii}=\langle i|\rho|i\rangle$ and
$\sigma_{ii}=\langle i|\sigma|i\rangle$.

###### Proof.

Note that the trace distance has the following variational form:

$\operatorname{TD}(\rho,\sigma)=\max_{0\leq M\leq
I}\mathrm{Tr}(M(\rho-\sigma)).$

Furthermore, trace distance is symmetric. Therefore, taking
$M:=\ket{i}\\!\bra{i}$ for $i\in[d]$, we have
$\operatorname{TD}(\rho,\sigma)\geq\max(\rho_{ii}-\sigma_{ii},\sigma_{ii}-\rho_{ii})=|\rho_{ii}-\sigma_{ii}|$
as desired. ∎

######  Fact 2.4.

Let $X,Y$ be random variables and $f$ be a function. Then
$d_{TV}(f(X),f(Y))\leq d_{TV}(X,Y)$.

######  Lemma 2.5 (Chernoff-Hoeffding Inequality).

Let $X_{1},X_{2},\ldots,X_{n}$ be independent random variables, such that
$0\leq X_{i}\leq 1$ for all $i\in[n]$. Let $X=\sum_{i=1}^{n}X_{i}$ and
$\mu=\mathop{\mathbb{E}}[X]$. Then for any $\varepsilon>0$,

$\Pr[|X-\mu|>\varepsilon)]\leq 2e^{-\frac{2\varepsilon^{2}}{n}}.$

####  2.3.1 Chi-Squared Distributions

We present the definition and properties of the chi-squared distribution in
the following.

######  Definition 2.6 (Chi-Squared Distribution).

Let $Z_{1},\dots,Z_{k}$ be i.i.d. Gaussian random variables
$\mathcal{N}(0,1)$. The random variable

$Q:=\sum_{i\in[k]}Z_{i}^{2}.$

is distributed according to the _chi-squared distribution with $k$ degrees of
freedom_, denoted by $Q\sim\chi^{2}_{k}$.

######  Fact 2.7.

Let $Z\sim\mathcal{N}(0,1)$. $Z^{2}$ has a finite third moment.

######  Fact 2.8.

For all $k\in\mathbb{N}$, the following holds. Let $Q\sim\chi^{2}_{k}$. The
mean of $Q$ is $k$ and the variance of $Q$ is $2k$. Moreover, suppose
$Q_{1}\sim\chi^{2}_{k_{1}}$ and $Q_{2}\sim\chi^{2}_{k_{2}}$, then
$Q_{1}+Q_{2}\sim\chi^{2}_{k_{1}+k_{2}}$. When $k=1$, we often omit the
subscript and denote it by $\chi^{2}$.

We introduce a strong version of the central limit theorem that characterizes
the _total variation distance_ between the sum of i.i.d. _absolutely
continuous_ 666A random variable $X$ is absolutely continuous if there exists
a (probability density) function $f:\mathbb{R}\to[0,1]$ such that $\Pr[X\leq
x]=\int_{-\infty}^{x}f(t)\,dt$ for all $x\in\mathbb{R}$ and
$\int_{-\infty}^{\infty}f(t)\,dt=1$. random variables and Gaussian random
variables. Note that most versions of central limit theorems state only the
convergence in _cumulative density function_ , which is not sufficient for our
purpose.

######  Lemma 2.9 ([SM62, Theorem 1], restated).

Let $X_{1},\dots,X_{k}$ be i.i.d. random variables. If $X_{1}$ is absolutely
continuous and has a finite third moment, then

$d_{TV}\left(\frac{\sum_{i\in[k]}(X_{i}-\mu)}{\sqrt{k}\sigma},Z\right)=O\left(\frac{1}{\sqrt{k}}\right),$

where $\mu$ is the mean of $X_{1}$, $\sigma$ is the standard deviation of
$X_{1}$ and $Z\sim\mathcal{N}(0,1)$. Equivalently,
$d_{TV}(\sum_{i\in[k]}X_{i},Z^{\prime})=O(1/\sqrt{k})$, where
$Z^{\prime}\sim\mathcal{N}(k\mu,k\sigma^{2})$.

Since a random variable with a chi-squared distribution is the sum of squared
i.i.d. Gaussian random variables, we have the following immediate corollary.

######  Corollary 2.10.

Let $Q$ be a random variable with a distribution $\chi^{2}_{k}$. Then
$d_{TV}(Q,Z)=O(1/\sqrt{k})$, where $Z\sim\mathcal{N}(k,2k)$.

###### Proof.

By definition, $Q=\sum_{i\in[k]}Z_{i}^{2}$ where $Z_{i}\sim\mathcal{N}(0,1)$.
It immediately follows from the facts that $Z_{i}^{2}$ is absolutely
continuous, $\mathop{\mathbb{E}}\left[Z_{i}^{2}\right]=1$,
$\mathsf{Var}\left(Z_{i}^{2}\right)=2$, the third moment of $Z_{i}^{2}$ is
finite and Lemma 2.9. ∎

####  2.3.2 Haar Measure

Given a $d$-dimensional Haar state, all coordinates of the state are
correlated due to the unit-norm condition. The following theorem states that
the _joint distribution_ of $k=o(d)$ fraction of the coordinates in
$\mathcal{S}(R^{d})$ is statistically close to a random vector with i.i.d.
Gaussian entries. The theorem was first proven in [DF87]. We will use the
version stated in [Mec19].

######  Theorem 2.11 ([Mec19, Theorem 2.8]).

For every integer $d\geq 5$ and every $k\in\mathbb{N}$ that satisfies $1\leq
k\leq d-4$, let $X=(X_{1},\dots,X_{d})$ be a uniform point on
$\mathcal{S}(\mathbb{R}^{d})$. Let $Z$ be a random vector in $\mathbb{R}^{k}$
with i.i.d. Gaussian entries $\mathcal{N}(0,1/d)$. Then

$\displaystyle
d_{TV}\left((X_{1},\dots,X_{k}),Z\right)\leq\frac{2(k+2)}{d-k-3}.$

The above lemma can be extended to uniformly random vectors on
$\mathcal{S}(\mathbb{C}^{d})$. For a complex number $\alpha$, we denote by
${\sf Re}(\alpha)$ and ${\sf Im}(\alpha)$, in order, the real part and
imaginary part of $\alpha$.

######  Lemma 2.12.

Let $\ket{\psi}=\sum_{i\in[d]}\alpha_{i}\ket{i}$ be a uniform point on
$\mathcal{S}(\mathbb{C}^{d})$. Then $({\sf Re}(\alpha_{1}),\dots,{\sf
Re}(\alpha_{d}),$ ${\sf Im}(\alpha_{1}),\dots,{\sf Im}(\alpha_{d}))$ is a
uniform point on $\mathcal{S}(\mathbb{R}^{2d})$.

###### Proof.

First proposed by Muller [Mul59], a uniform point on
$\mathcal{S}(\mathbb{R}^{2d})$ can be sampled via the following procedures:

  1. 1.

For $i\in[2d]$, sample $a_{i}\leftarrow\mathcal{N}(0,\sigma^{2})$.

  2. 2.

Output $\sum_{i\in[2d]}\frac{a_{i}}{\sqrt{\sum_{j\in[2d]}a_{j}^{2}}}\ket{i}$.

Where $\sigma^{2}$ in step 1 could be an arbitrary positive number.

On the other hand, a uniform point on $\mathcal{S}(\mathbb{C}^{d})$ can be
sampled as follows:

  1. 1.

For $i\in[d]$, sample $\alpha_{i}\sim\mathbb{C}\mathcal{N}(0,1)$.

  2. 2.

Output
$\sum_{i\in[d]}\frac{\alpha_{i}}{\sqrt{\sum_{j\in[d]}|\alpha_{j}|^{2}}}\ket{i}$.

Particularly, in step 1, sampling $\alpha\sim\mathbb{C}\mathcal{N}(0,1)$ is
equivalent to sampling $\alpha=a+ib$ according to $a\sim\mathcal{N}(0,1/2)$,
$b\sim\mathcal{N}(0,1/2)$ by the definition of the complex normal
distribution. Hence, picking $\sigma^{2}=1/2$ completes the proof. ∎

######  Corollary 2.13.

For every integer $d\geq 3$ and every $k\in\mathbb{N}$ that satisfies $1\leq
2k\leq 2d-4$, let $\ket{\psi}=\sum_{i\in[d]}\alpha_{i}\ket{i}$ be a random
point on $\mathcal{S}(\mathbb{C}^{d})$. Let $Z$ be a random vector in
$\mathbb{R}^{2k}$ with i.i.d. Gaussian entries $\mathcal{N}(0,1/(2d))$. Then

$\displaystyle d_{TV}\left(({\sf Re}(\alpha_{1}),\dots,{\sf
Re}(\alpha_{k}),{\sf Im}(\alpha_{1}),\dots,{\sf
Im}(\alpha_{k})),Z\right)\leq\frac{2(2k+2)}{2d-2k-3}.$

###### Proof.

It immediately follows from Theorem 2.11 and Lemma 2.12. ∎

Next, the following simple fact gives an upper bound of the probability that a
Gaussian random variable takes values near its mean.

######  Fact 2.14.

Let $Z\sim\mathcal{N}(\mu,\sigma^{2})$. For any $\Delta>0$,

$\displaystyle\Pr[|Z-\mu|\leq\Delta]\leq\sqrt{\frac{2}{\pi}}\frac{\Delta}{\sigma}.$

###### Proof.

Let
$f(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^{2}}$
be the probability density function of $\mathcal{N}(\mu,\sigma^{2})$. The
probability $\int_{\mu-\Delta}^{\mu+\Delta}f(x)\,dx$ can be upper-bounded by
$f(\mu)\cdot 2\Delta=\sqrt{\frac{2}{\pi}}\frac{\Delta}{\sigma}$. ∎

###  2.4 Quantum State Tomography

######  Lemma 2.15 ([AGQY22, Corollary 7.6]).

There exists a tomography procedure $\mathsf{Tomography}$ that satisfies the
following. For any error tolerance $\delta=\delta(\lambda)\in(0,1]$ and any
dimension $d=d(\lambda)\in\mathbb{N}$, given at least $t=t(\lambda):=36\lambda
d^{3}/\delta$ copies of a $d$-dimensional density matrix $\rho$,
$\mathsf{Tomography}(\rho^{\otimes t})$ outputs a matrix
$M\in\mathbb{C}^{d\times d}$ such that the following holds:

$\displaystyle\Pr\left[\|M-\rho\|^{2}_{F}\leq\delta:M\leftarrow\mathsf{Tomography}(\rho^{\otimes
t})\right]\geq 1-\mathsf{negl}(\lambda),$

where ${\left\lVert\cdot\right\rVert}_{F}$ denotes the Frobenius norm.
Moreover, the running time of $\mathsf{Tomography}$ is polynomial in
$1/\delta,d$ and $\lambda$.

By using the fact that ${\left\lVert
A\right\rVert}_{1}\leq\sqrt{d}{\left\lVert A\right\rVert}_{F}$, we have the
following immediate corollary.

######  Corollary 2.16.

There exists a tomography procedure $\mathsf{Tomography}$ that satisfies the
following. For any error tolerance $\delta=\delta(\lambda)\in(0,1]$ and any
dimension $d=d(\lambda)\in\mathbb{N}$, given at least
$t=t(\lambda):=144\lambda d^{4}/\delta^{2}$ copies of a $d$-dimensional
density matrix $\rho$, $\mathsf{Tomography}(\rho^{\otimes t})$ outputs a
matrix $M\in\mathbb{C}^{d\times d}$ such that the following holds:

$\displaystyle\Pr\left[\operatorname{TD}(M,\rho)\leq\delta:M\leftarrow\mathsf{Tomography}(\rho^{\otimes
t})\right]\geq 1-\mathsf{negl}(\lambda).$

Moreover, the running time of $\mathsf{Tomography}$ is polynomial in
$1/\delta,d$ and $\lambda$.

##  3 Deterministically Extracting Classical Strings from Quantum States

In this section, we show how to pseudodeterministically extract classical
strings from $O(\log(\lambda))$-qubit quantum states in _polynomial_ time. We
first present the outline of our construction.

  1. 1.

Take as input $t(\lambda)$ copies of a $d(\lambda)$-dimensional (possibly
mixed) quantum state $\rho$. Note that for our applications, we require
$d(\lambda)=\mathsf{poly}(\lambda)$ and $t(\lambda)=\mathsf{poly}(\lambda)$.

  2. 2.

Perform $\mathsf{Tomography}$ on the input $\rho^{\otimes t(\lambda)}$ to get
an approximation $M\in\mathbb{C}^{d\times d}$ of its classical description.

  3. 3.

Pick the first $k=o(d)$ diagonal entries of $M$, denoted by
$p_{1},\dots,p_{k}$. Divide them into $\ell$ groups where each of them is of
size $r$ (namely, $k=\ell\cdot r$).

  4. 4.

In each group, consider the sum of all the elements. By $q_{i}$ we denote the
sum of the $i$-th group.

  5. 5.

For each $q_{i}$, we round it to a bit, called $b_{i}$, according to which
side it deviates from $r/d$.

  6. 6.

Output the concatenation of every bit $b_{1}||\dots||b_{\ell}$.

In particular, we are interested in the case where the input is (polynomially
many copies of) a _Haar state_. Informally, a Haar state can be thought of as
a uniformly random point on a high-dimensional sphere. We can partition the
sphere into many regions and assign each region a unique bitstring. Given the
input quantum state, the goal of the extractor is to find the corresponding
bitstring. Hence, Haar states can be viewed as a natural source of randomness.
Below, we present our main theorem.

######  Theorem 3.1.

There exists a quantum algorithm ${\sf Ext}$ such that for all $d(\cdot)$,
there exists a (deterministic) function
$f:\mathcal{D}(\mathbb{C}^{d(\lambda)})\to{\\{0,1\\}}^{\ell(\lambda)}$
associated with ${\sf Ext}$, where $\ell(\lambda)=\lfloor
d(\lambda)^{1/6}\rfloor$. On input
$t(\lambda)=\mathsf{poly}(d(\lambda),\lambda)$ copies of a
$d(\lambda)$-dimensional density matrix $\rho$, the algorithm ${\sf Ext}$
outputs an $\ell(\lambda)$-bit string $y$ and satisfies the following
conditions.

  * •

Efficiency: The running time is polynomial in $d$ and $\lambda$.

  * •

Correctness: For all $\lambda\in\mathbb{N}$, there exists a set
$\mathcal{G}_{\Delta}\subseteq\mathcal{S}(\mathbb{C}^{d(\lambda)})$ such that

    1. 1.

$\Pr\left[\ket{\psi}\in\mathcal{G}_{\Delta}:\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})\right]\geq
1-O(d(\lambda)^{-1/6}).$

    2. 2.

For all $\ket{\psi}\in\mathcal{G}_{\Delta}$,

$\displaystyle\Pr\left[y=f(\ket{\psi}\\!\bra{\psi}):y\leftarrow{\sf
Ext}\left(\ket{\psi}\\!\bra{\psi}^{\otimes t(\lambda)}\right)\right]\geq
1-\mathsf{negl}(\lambda),$

where the probability is over the randomness of the extractor ${\sf Ext}$.

  * •

Statistical Closeness to Uniformity: For sufficiently large
$\lambda\in\mathbb{N}$,

$\displaystyle d_{TV}(Y_{\lambda},U_{\ell(\lambda)})\leq
O(d(\lambda)^{-1/6}),$

where $U_{\ell(\lambda)}$ is the uniform distribution over all
$\ell(\lambda)$-bit strings and the random variable $Y_{\lambda}$ is defined
by the following process:

$\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)}),Y_{\lambda}\leftarrow{\sf
Ext}\left(\ket{\psi}\\!\bra{\psi}^{\otimes t(\lambda)}\right).$

###### Proof.

Here we present our construction of the extractor ${\sf Ext}$.

######  Construction 3.2 (The Extractor ${\sf Ext}$).

  * •

Input: $t(\lambda):=144\lambda d(\lambda)^{8}$ copies of a
$d(\lambda)$-dimensional quantum state
$\rho\in\mathcal{D}(\mathbb{C}^{d(\lambda)})$.

  * •

Perform $\mathsf{Tomography}(\rho^{\otimes t(\lambda)})$ with error tolerance
$\delta(\lambda):=d(\lambda)^{-5/3}$ to get the classical description
$M\in\mathbb{C}^{d(\lambda)\times d(\lambda)}$ that approximates $\rho$.

  * •

Run ${\sf Round}(M)$ to get $y\in{\\{0,1\\}}^{\ell(\lambda)}$.

  * •

Output $y$.

The classical post-processing procedure ${\sf Round}(M)$ is defined as
follows:
Round($M$): • Input: a matrix $M\in\mathbb{C}^{d(\lambda)\times d(\lambda)}$.
• Set parameters $k(\lambda):=d(\lambda)^{5/6}$,
$r(\lambda):=d(\lambda)^{2/3}$ and $\ell(\lambda):=d(\lambda)^{1/6}$. • Let
$p_{1},\dots,p_{d(\lambda)}$ be the diagnal entries of $M$. For
$i\in\left\\{1,\dots,\ell(\lambda)\right\\}$, let
$q_{i}:=\sum_{j=1}^{r}p_{(i-1)r+j}.$ • For
$i\in\left\\{1,\dots,\ell(\lambda)\right\\}$, define
$b_{i}=\begin{cases}0,&\text{ if }q_{i}<r/d\\\ 1,&\text{ if
}q_{i}>r/d.\end{cases}$ • Output $b_{1}||\dots||b_{\ell(\lambda)}$.

By Corollary 2.16 and the fact that $t(\lambda)=\mathsf{poly}(d,\lambda)$ and
$\delta(\lambda)=1/\mathsf{poly}(d)$, it is easy to see that the running time
of the extractor ${\sf Ext}$ is polynomial in $d$ and $\lambda$. Before
proving the correctness and statistical closeness to uniformity, we present
several statistical properties.

First, the distribution of the real and imaginary parts of any $k=o(d)$
coordinates of a Haar state $\ket{\psi}\sim\mathscr{H}(\mathbb{C}^{d})$ is
statistically close to a random vector with i.i.d. Gaussian entries.

######  Claim 3.3.

Let $\ket{\psi}=\sum_{i=1}^{d}\alpha_{i}\ket{i}$ be a uniformly random point
on $\mathcal{S}(\mathbb{C}^{d})$. Then

$d_{TV}\left(({\sf Re}(\alpha_{1}),{\sf Im}(\alpha_{1}),\dots,{\sf
Re}(\alpha_{k}),{\sf Im}(\alpha_{k})),Z\right)=O\left(k/d\right),$

where $Z$ is a random variable in $\mathbb{R}^{2k}$ with i.i.d. Gaussian
entries $\mathcal{N}(0,1/(2d))$.

###### Proof.

It immediately follows from Corollary 2.13. ∎

Next, since the $i$-th diagonal entry $p_{i}$ of $\ket{\psi}\bra{\psi}$ is the
squared absolute value of the $i$-th coordinate $\alpha_{i}$ of $\ket{\psi}$,
the joint distribution of $(p_{1},\dots,p_{k})$ is statistically close to a
random vector in $\mathbb{R}^{k}$ with i.i.d. $\chi_{2}^{2}$ entries.

######  Claim 3.4.

$d_{TV}\left((p_{1},\dots,p_{k}),Q/(2d)\right)=O(k/d)$ where $Q$ is a random
variable in $\mathbb{R}^{k}$ with i.i.d. $\chi^{2}_{2}$ entries.

###### Proof.

For $i\in[k]$, each diagonal entry $p_{i}=|\alpha_{i}|^{2}={\sf
Re}(\alpha_{i})^{2}+{\sf Im}(\alpha_{i})^{2}$. By 3.3, the total variation
distance induced by replacing the real and imaginary parts of the amplitudes
with i.i.d. Gaussians $\mathcal{N}(0,1/(2d))$ is $O(k/d)$. Then by setting
$f(x_{1},\dots,x_{2k}):=\left(x_{1}^{2}+x_{2}^{2},\dots,x_{2k-1}^{2}+x_{2k}^{2}\right)$
in 2.4 and the definition of $\chi^{2}_{2}$, we complete the proof. ∎

Now, we consider the distribution of $q_{i}$’s. Note that the sum of $r$
i.i.d. $\chi_{2}^{2}$ random variables is identically distributed to
$\chi_{2r}^{2}$ by the property of the $\chi^{2}$-distribution in 2.8. Namely,
the joint distribution of $(q_{1},\dots,q_{\ell})$ is statistically close to a
random vector in $\mathbb{R}^{\ell}$ with i.i.d. $\chi_{2r}^{2}$ entries.

######  Claim 3.5.

$d_{TV}\left((q_{1},\dots,q_{\ell}),R/(2d)\right)=O(k/d)$ where $R$ is a
random variable in $\mathbb{R}^{\ell}$ with i.i.d. $\chi^{2}_{2r}$ entries.

###### Proof.

Recall that $q_{i}:=\sum_{j=1}^{r}p_{(i-1)r+j}$. From 3.4, we have
$d_{TV}\left((p_{1},\dots,p_{k}),Q/(2d)\right)=O(k/d)$, where
$Q=(Q_{1},\dots,Q_{k})$ is a random variable in $\mathbb{R}^{k}$ with i.i.d.
$\chi^{2}_{2}$ entries. Hence by the data processing inequality (2.4) and
setting

$f(x_{1},\dots,x_{k}):=\left(\sum_{j=1}^{r}x_{j},\sum_{j=1}^{r}x_{r+j},\dots,\sum_{j=1}^{r}x_{(\ell-1)r+j}\right),$

we have $d_{TV}\left((q_{1},\dots,q_{\ell}),R/(2d)\right)=O(k/d)$, where we
use the fact that the sum of $r$ i.i.d. $\chi^{2}_{2}$ random variables is
identically distributed to $\chi^{2}_{2r}$. ∎

Moreover, a $\chi^{2}_{2r}$ random variable is the sum of $r$ i.i.d.
absolutely continuous random variables. Hence, relying on the aforementioned
central limit theorem, it is statistically close to a Gaussian distribution.

######  Lemma 3.6.

$d_{TV}\left((q_{1},\dots,q_{\ell}),Z/(2d)\right)=O(k/d)+O(\ell/\sqrt{r})$
where $Z$ is a random variable in $\mathbb{R}^{\ell}$ with i.i.d.
$\mathcal{N}(2r,4r)$ entries, i.e., $Z/(2d)$ has i.i.d.
$\mathcal{N}(r/d,r/d^{2})$ entries.

###### Proof.

By Corollary 2.10 and hybrids over every coordinate for $i\in[\ell]$, we have
$d_{TV}(R/(2d),Z/(2d))=O(\ell/\sqrt{r})$, where $R$ is defined in 3.5.
Together with 3.5 finishes the proof. ∎

Now, we are ready to prove the correctness and the statistical closeness to
uniform properties.

Correctness. First, define the function
$f:\mathcal{D}(\mathbb{C}^{d(\lambda)})\to{\\{0,1\\}}^{\ell(\lambda)}$
associated with the extractor as

$f(\sigma):={\sf Round}(\sigma).$

Due to the continuous nature of quantum states, it is impossible to discretize
them perfectly. For any $\sigma\in\mathcal{D}(\mathbb{C}^{d})$, consider the
corresponding $q_{1},\dots,q_{\ell}$ defined in 3.2. If _all_
$q_{1},\dots,q_{\ell}$ are sufficiently away from $r/d$, then the extractor is
able to output the correct string with high probability by the correctness of
$\mathsf{Tomography}$. Here, we define the set $\mathcal{G}_{\Delta}$ of “good
states” whose $q_{1},\dots,q_{\ell}$ are _all_ $\Delta$-away from $r/d$ (the
parameter $\Delta(\lambda)$ will be chosen later). The following claim
characterizes the probability of a Haar random state being in
$\mathcal{G}_{\Delta}$.

######  Claim 3.7.

Let the set
$\mathcal{G}_{\Delta}\subseteq\mathcal{S}(\mathbb{C}^{d(\lambda)})$ be

$\displaystyle\mathcal{G}_{\Delta}:=\left\\{\ket{\psi}\in\mathcal{S}(\mathbb{C}^{d(\lambda)}):\forall
i\in[\ell],\ \left|q_{i}-\frac{r}{d}\right|>\Delta\right\\},$

where each $q_{i}$ is defined on the matrix $\ket{\psi}\\!\bra{\psi}$. It
holds that

$\displaystyle\Pr\left[\ket{\psi}\in\mathcal{G}_{\Delta}:\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})\right]\geq
1-O\left(\frac{k}{d}\right)-O\left(\frac{\ell}{\sqrt{r}}\right)-O\left(\frac{\Delta\ell
d}{\sqrt{r}}\right).$

###### Proof.

By Lemma 3.6, the total variation distance between $(q_{1},\dots,q_{\ell})$
and the random variable $Z=(Z_{1},\dots,Z_{\ell})$ with i.i.d. Gaussian
entries $Z_{i}\sim\mathcal{N}(r/d,r/d^{2})$ is $O(k/d)+O(\ell/\sqrt{r})$.
Hence,

$\displaystyle\Pr\left[\ket{\psi}\in\mathcal{G}_{\Delta}:\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})\right]$
$\displaystyle=\Pr\left[\forall i\in[\ell],\
\left|q_{i}-\frac{r}{d}\right|>\Delta\right]$
$\displaystyle\geq\Pr\left[\forall i\in[\ell],\
\left|Z_{i}-\frac{r}{d}\right|>\Delta\right]-O\left(\frac{k}{d}\right)-O\left(\frac{\ell}{\sqrt{r}}\right).$

Moreover, by 2.14, for every coordinate $i\in[\ell]$, it holds that

$\Pr\left[\left|Z_{i}-\frac{r}{d}\right|\leq\Delta\right]\leq
O\left(\frac{\Delta}{\sqrt{r}/d}\right).$

By a union bound over $i\in[\ell]$, with all but $O\left(\frac{\Delta\ell
d}{\sqrt{r}}\right)$ probability every $Z_{i}$ is $\Delta$-away from $r/d$.
Collecting the probabilities completes the proof of 3.7. ∎

Hence, by setting $\Delta(\lambda)=1/d(\lambda)$, the choice of parameters
$r(\lambda)=d(\lambda)^{2/3}$, $\ell(\lambda)=d(\lambda)^{1/6}$,
$k(\lambda)=d(\lambda)^{5/6}$ and 3.7, we have

$\displaystyle\Pr\left[\ket{\psi}\in\mathcal{G}_{\Delta}:\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})\right]\geq
1-O(d(\lambda)^{-1/6}).$

Next, given a state which is in $\mathcal{G}_{\Delta}$, the output bitstring
extracted from it will be $f(\ket{\psi}\\!\bra{\psi})$ with overwhelming
probability by the correctness of $\mathsf{Tomography}$ in Corollary 2.16.

######  Claim 3.8.

If $\ket{\psi}\in\mathcal{G}_{\Delta}$, then running ${\sf Ext}$ in 3.2 with
error tolerance $\delta(\lambda)=d^{-5/3}=\Delta(\lambda)/r(\lambda)$ for
$\mathsf{Tomography}$ satisfies

$\Pr\left[y=f(\ket{\psi}\\!\bra{\psi}):y\leftarrow{\sf
Ext}\left(\ket{\psi}\\!\bra{\psi}^{\otimes t(\lambda)}\right)\right]\geq
1-\mathsf{negl}(\lambda),$

where the probability is over the randomness of the extractor ${\sf Ext}$.

###### Proof.

Let $M$ be the classical description obtained by running
$\mathsf{Tomography}(\ket{\psi}\\!\bra{\psi}^{\otimes t(\lambda)})$ with error
tolerance $\delta$ and $t\geq 144\lambda d^{8}\geq 144\lambda
d^{4}/\delta^{2}$. Let $\hat{p}_{i}$’s and $\hat{q}_{j}$’s be the
corresponding diagonal entries and sums of $M$. By Corollary 2.16 ,
$\operatorname{TD}(\ket{\psi}\\!\bra{\psi},M)\leq\delta$ holds with
overwhelming probability. For the rest of the proof, we assume that this event
holds. Then by 2.3, we have $|p_{i}-\hat{p}_{i}|\leq\delta$ for every
$i\in[k]$. Since $\ket{\psi}\in\mathcal{G}_{\Delta}$, we have
$|q_{i}-r/d|>\Delta$ for every $i\in[\ell]$. We now show that if
$q_{i}>r/d+\Delta$, then $\hat{q}_{i}>r/d$. For every $i\in[\ell]$, by the
triangle inequality and the fact that $\delta=\Delta/r$, we have

$\hat{q}_{i}=q_{i}-(q_{i}-\hat{q}_{i})>\left(\frac{r}{d}+\Delta\right)-\sum_{j=1}^{r}\left|p_{(i-1)r+j}-\hat{p}_{(i-1)r+j}\right|\geq\frac{r}{d}+\Delta-r\cdot\delta=\frac{r}{d}.$

Similarly, we have $q_{i}<r/d-\Delta$ implies that $\hat{q}_{i}<r/d$. Hence,
this ensures the consistency between ${\sf Round}(M)$ and ${\sf
Round}(\ket{\psi}\\!\bra{\psi})$ and completes the proof of 3.8. ∎

##### Statistical Closeness to Uniformity.

We finish the proof with a hybrid argument:

  * •

$\mathsf{H}_{1}:$ In the first hybrid, the output is generated according to
3.2.

    1. 1.

Sample $\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})$.

    2. 2.

Perform $\mathsf{Tomography}(\rho^{\otimes t(\lambda)})$ with
$t(\lambda):=144\lambda d(\lambda)^{8}$ and error tolerance
$\delta(\lambda):=d(\lambda)^{-5/3}$ to get the classical description
$M\in\mathbb{C}^{d(\lambda)\times d(\lambda)}$ that approximates $\rho$.

    3. 3.

Output $y={\sf Round}(M)$.

  * •

$\mathsf{H}_{2}:$ In the second hybrid, the input of ${\sf Round}$ is changed
to the exact description of the quantum state.

    1. 1.

Sample $\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})$.

    2. 2.

Output $y={\sf Round}(\ket{\psi}\\!\bra{\psi})$.

  * •

$\mathsf{H}_{3}:$ In the third hybrid, the output is generated by rounding
i.i.d. Gaussians.

    1. 1.

Sample $z_{1},\dots,z_{\ell}\leftarrow\mathcal{N}(r/d,r/d^{2})$.

    2. 2.

For $i\in[\ell]$,

$b_{i}=\begin{cases}0,&\text{ if }z_{i}<r/d\\\ 1,&\text{ if
}z_{i}>r/d.\end{cases}$

    3. 3.

Output $b_{1}||\dots||b_{\ell(\lambda)}$.

We can bound the total variation distance between $\mathsf{H}_{1}$ and
$\mathsf{H}_{2}$ by $O(\delta)=O(d^{-5/3})$ using Corollary 2.16 and our
chosen error tolerance. Additionally, the total variation distance between
$\mathsf{H}_{2}$ and $\mathsf{H}_{3}$ is at most $O(d^{-1/6})$ from Lemma 3.6.
Finally, since Gaussians are symmetric about the mean, the output string in
$\mathsf{H}_{3}$ is uniformly and randomly distributed. This finishes the
proof of Theorem 3.1. ∎

##  4 Quantum PRGs and PRFs

In this section, we present our main application of the extractor in Section
3. We introduce the notion of _pseudodeterministic quantum pseudorandom
generators_ (QPRGs). As the name suggests, QPRGs is a pseudorandom generator
with quantum generation satisfying only _pseudodeterminism_ property. To be
more precise, by pseudodeterminism we mean that there exist some constant
$c>0$ and at least $1-O(\lambda^{-c})$ fraction of “good seeds” for which the
output is almost certain. That is, for each good seed, the probability (over
the randomness of the QPRG) of the most likely output is at least
$1-O(\lambda^{-c})$.

###  4.1 Construction of QPRGs

######  Definition 4.1 (Weak/Strong Pseudodeterministic Quantum Pseudorandom
Generator).

A weak pseudodeterministic quantum pseudorandom generator $G_{\lambda}$,
abbreviated as wQPRG, is a uniform QPT algorithm that on input a seed
$k\in{\\{0,1\\}}^{\lambda}$, outputs a bitstring of length $\ell(\lambda)$
with the following guarantees:

  * •

Pseudodeterminism: There exists a constant $c>0$ and a function
$\mu(\lambda)=O(\lambda^{-c})$ such that for every $\lambda\in\mathbb{N}$,
there exists a set of “good seeds”
$\mathcal{K}_{\lambda}\subseteq{\\{0,1\\}}^{\lambda}$ satisfying the
following:

    1. 1.

$\Pr[k\in\mathcal{K}_{\lambda}:k\leftarrow{\\{0,1\\}}^{\lambda}]\geq
1-\mu(\lambda)$.

    2. 2.

For any $k\in\mathcal{K}_{\lambda}$, it holds that

$\max\limits_{y\in{\\{0,1\\}}^{\ell(\lambda)}}\Pr[y=G_{\lambda}(k)]\geq
1-\mu(\lambda),$

where the probability is over the randomness of $G_{\lambda}$.

  * •

Stretch: The output length of $G_{\lambda}$, namely $\ell(\lambda)$, is
strictly greater than $\lambda$.

  * •

Weak Security: For every (non-uniform) QPT distinguisher $A$, there exists a
polynomial $\nu(\cdot)$ such that the following holds for sufficiently large
$\lambda\in\mathbb{N}$,

$\left|\Pr\left[A_{\lambda}(y)=1:\begin{subarray}{c}k\leftarrow{\\{0,1\\}}^{\lambda},\\\
y\leftarrow
G_{\lambda}(k)\end{subarray}\right]-\Pr\left[A_{\lambda}(y)=1:y\leftarrow{\\{0,1\\}}^{\ell(\lambda)}\right]\right|\leq
1-\frac{1}{\nu(\lambda)},$ (1)

where the probability of the first experiment is over the choice of $k$ and
the randomness of $G_{\lambda}$ and $A_{\lambda}$.

If $G$ further satisfies the strong security property defined below, we call
$G$ a _strong pseudodeterministic quantum pseudorandom generator_ ,
abbreviated as sQPRG.

  * •

Strong Security: For every (non-uniform) QPT distinguisher $A$, there exists a
negligible function $\varepsilon(\cdot)$ such that the following holds for
sufficiently large $\lambda\in\mathbb{N}$,

$\left|\Pr\left[A_{\lambda}(y)=1:\begin{subarray}{c}k\leftarrow{\\{0,1\\}}^{\lambda},\\\
y\leftarrow
G_{\lambda}(k)\end{subarray}\right]-\Pr\left[A_{\lambda}(y)=1:y\leftarrow{\\{0,1\\}}^{\ell(\lambda)}\right]\right|\leq\varepsilon(\lambda),$

where the probability of the first experiment is over the choice of $k$ and
the randomness of $G_{\lambda}$ and $A_{\lambda}$.

We call the left-hand side of Equation 1 the _distinguishing advantage_ of
$A$. We say that $G$ is _$(1-\delta(\lambda))$ -pseudorandom_ or _has
pseudorandomness $1-\delta(\lambda)$_ if the maximum distinguishing advantage
over all non-uniform QPT adversaries is at most $\delta(\lambda)$. We say that
$G$ has pseudodeterminism $1-\mu(\lambda)$ if it satisfies the
pseudodeterminism property for the function $\mu(\cdot)$.

We begin with an $n(\lambda)$-PRS (recall that $n(\lambda)$ is its output
length), where $n(\lambda)=O(\log\lambda)$ and the dimension of its output is
$d(\lambda)=2^{n(\lambda)}=\mathsf{poly}(\lambda)$.

######  Theorem 4.2 ($O(\log\lambda)$-PRS implies wQPRG).

Assuming the existence of $(c\log\lambda)$-PRS for some constant $c>6$, then
there exists a $\left(1-O(\lambda^{-c/6})\right)$-pseudorandom wQPRG with
pseudodeterminism $1-O(\lambda^{-c/12})$ and output length
$\ell(\lambda)=\lambda^{c/6}>\lambda$.

###### Proof.

Consider the following construction.

######  Construction 4.3 (Weak Quantum Pseudorandom Generators).

  1. 1.

Input: a security parameter $1^{\lambda}$ and a seed
$k\in{\\{0,1\\}}^{\lambda}$.

  2. 2.

Run $(c\log\lambda)$-$\mathsf{PRS}(k)$ $t$ times to get $\rho_{k}^{\otimes
t(\lambda)}$, where $t(\lambda)=144\lambda d(\lambda)^{8}=O(\lambda^{8c+1})$
as defined in 3.2.

  3. 3.

Run ${\sf Ext}(\rho_{k}^{\otimes t(\lambda)})$ defined in 3.2 to get
$y\in{\\{0,1\\}}^{\ell(\lambda)}$.

  4. 4.

Output $y$.

##### Efficiency.

Since $t(\lambda)=\mathsf{poly}(\lambda)$ and $d(\lambda)=O(\lambda^{c})$, the
running time is polynomial in $\lambda$ from Theorem 3.1.

##### Pseudodeterminism.

We complete the proof by a hybrid argument. Consider the following hybrids.

  * •

$\mathsf{H}_{1}:$ In the first hybrid, $y$ is generated according to 4.3.

    1. 1.

Sample $k\leftarrow{\\{0,1\\}}^{\lambda}$.

    2. 2.

Run $\mathsf{PRS}(k)$ $t$ times to get $\rho_{k}^{\otimes t(\lambda)}$.

    3. 3.

Run $y\leftarrow{\sf Ext}(\rho_{k}^{\otimes t(\lambda)})$.

    4. 4.

Output $y$.

  * •

$\mathsf{H}_{2}:$ In the second hybrid, the input is changed to a Haar state.

    1. 1.

Sample $\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})$.

    2. 2.

Run $y\leftarrow{\sf Ext}(\ket{\psi}\\!\bra{\psi}^{\otimes t(\lambda)})$.

    3. 3.

Output $y$.

For the sake of contradiction, suppose there exists at least $\mu(\lambda)\neq
O(\lambda^{-c/12})$ fraction of “bad seeds” (the complement of the set
$\mathcal{K}_{\lambda}$ of good seeds) for which the probability of the most
likely output is at most $1-\mu(\lambda)$. Then we construct an efficient
distinguisher for $\mathsf{PRS}$ as follows:

  1. 1.

Take as input $2t(\lambda)=\mathsf{poly}(\lambda)$ copies of $\rho$ which is
either sampled from $\mathsf{PRS}$ with a random key or
$\mathscr{H}(\mathbb{C}^{d(\lambda)})$.

  2. 2.

Run ${\sf Ext}(\rho^{\otimes t(\lambda)})$ twice independently and get the
output $y_{1},y_{2}$ respectively.

First, if $\rho$ is sampled from $\mathscr{H}(\mathbb{C}^{d(\lambda)})$, then
by the correctness of ${\sf Ext}$ in Theorem 3.1, we have

$p_{1}:=\Pr\left[y_{1}=y_{2}:\rho\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})\right]\geq(1-O(d(\lambda)^{1/6}))\cdot(1-\mathsf{negl}(\lambda))^{2}\geq
1-h(\lambda),$

where $h(\lambda)=O(\lambda^{-c/6})$.

On the other hand, consider the case in which $\rho$ is sampled from
$\mathsf{PRS}$. Without loss of generality, we can assume that
$\mu(\lambda)<1/2$ for sufficiently large $\lambda$. Otherwise, the
distinguishing advantage would already be non-negligible. Then,

$\displaystyle p_{2}$
$\displaystyle:=\Pr\left[y_{1}=y_{2}:\rho\leftarrow\mathsf{PRS}(k)\right]=\Pr[k\in\mathcal{K}_{\lambda}]\Pr[y_{1}=y_{2}\mid
k\in\mathcal{K}_{\lambda}]+\Pr[k\notin\mathcal{K}_{\lambda}]\Pr[y_{1}=y_{2}\mid
k\notin\mathcal{K}_{\lambda}]$ $\displaystyle\leq(1-\mu(\lambda))\cdot
1+\mu(\lambda)\cdot(1-\mu(\lambda))=1-\mu(\lambda)^{2}.$

Now, for any sufficiently large $\lambda\in\mathbb{N}$ such that
$1/2>\mu(\lambda)$, we do a case analysis. Suppose
$h(\lambda)\geq\mu(\lambda)^{2}$, then we have
$\sqrt{h(\lambda)}>\mu(\lambda)$. Otherwise, if $h(\lambda)<\mu(\lambda)^{2}$,
then the distinguishing advantage $|p_{1}-p_{2}|$ satisfies

$\mathsf{negl}(\lambda)=|p_{1}-p_{2}|=p_{1}-p_{2}\geq\mu(\lambda)^{2}-h(\lambda)$

due to the security of $\mathsf{PRS}$. Hence, it holds that
$\sqrt{h(\lambda)+\mathsf{negl}(\lambda)}>\mu(\lambda)$. However, combining
two cases would imply that $\mu(\lambda)=O(\lambda^{-c/12})$ and lead to a
contradiction.

##### Stretch.

From Theorem 3.1, the output length of 4.3 is given by
$\ell(\lambda)=d(\lambda)^{1/6}=\lambda^{c/6}>\lambda$ since $c>6$.

##### Weak Security.

We complete the proof by a hybrid argument. Consider the following hybrids:

  * •

$\mathsf{H}_{1}:$ In the first hybrid, the adversary receives a string $y$
which is generated according to 4.3.

    1. 1.

Sample $k\leftarrow{\\{0,1\\}}^{\lambda}$.

    2. 2.

Run $\mathsf{PRS}(k)$ $t$ times to get $\rho_{k}^{\otimes t(\lambda)}$.

    3. 3.

Run $y\leftarrow{\sf Ext}(\rho_{k}^{\otimes t(\lambda)})$.

    4. 4.

Output $y\in{\\{0,1\\}}^{\ell(\lambda)}$.

  * •

$\mathsf{H}_{2}:$ In the second hybrid, the input is changed to a Haar state.

    1. 1.

Sample $\ket{\psi}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})$.

    2. 2.

Run $y\leftarrow{\sf Ext}(\ket{\psi}\\!\bra{\psi}^{\otimes t(\lambda)})$.

    3. 3.

Output $y\in{\\{0,1\\}}^{\ell(\lambda)}$.

  * •

$\mathsf{H}_{3}:$ Sample $y\leftarrow{\\{0,1\\}}^{\ell(\lambda)}$. Output
$y\in{\\{0,1\\}}^{\ell(\lambda)}$. In the third hybrid, the adversary receives
a string sampled from the uniform distribution.

The computational indistinguishability of hybrids $\mathsf{H}_{1}$ and
$\mathsf{H}_{2}$ follows from the security of $\mathsf{PRS}$. Otherwise,
running ${\sf Ext}$ on the samples once would be an efficient distinguisher in
the PRS security experiment. The statistical indistinguishability of hybrids
$\mathsf{H}_{2}$ and $\mathsf{H}_{3}$ follows from the statistical closeness
to uniform property of Theorem 3.1. In particular, the statistical distance is
$O(d(\lambda)^{-1/6})=O(\lambda^{-c/6})$. ∎

While we do not have a non-trivial way to amplify the pseudodeterminism
property, the security amplification can be achieved by techniques in [CHS05,
DIJK09, MT09, MT10]. In particular, we will use the security amplification for
(classical) weak PRGs in [DIJK09]. The construction is to run the weak PRG $G$
on input $s(\lambda)=\omega(\log\lambda)$ independently and randomly chosen
seeds $k_{1},\dots,k_{s}$ and then output the bit-wise XOR of the $s$ strings
$G(k_{1}),\dots,G(k_{s})$.

######  Theorem 4.4 ([DIJK09, Theorem 6]).

Let $s(\lambda)=\omega(\log\lambda)$. Let
$G:{\\{0,1\\}}^{\lambda}\to{\\{0,1\\}}^{\ell(\lambda)}$ be a weak PRG with
$(1-\delta)$-pseudorandomness such that $\delta<1/2$ and
$\ell(\lambda)>s(\lambda)\cdot\lambda$. Define the function $G^{\oplus
s}:{\\{0,1\\}}^{s(\lambda)\lambda}\to{\\{0,1\\}}^{\ell(\lambda)}$ as
$G^{\oplus s}(k_{1},\dots,k_{s}):=\bigoplus_{i=1}^{s}G(k_{i})$. Then
$G^{\oplus s}$ is a strong PRG.

We observed that Theorem 4.4 could be extended to QPRGs.

######  Theorem 4.5 (Security amplification for QPRGs).

Let $G:{\\{0,1\\}}^{\lambda}\to{\\{0,1\\}}^{\ell(\lambda)}$ be a wQPRG that
has pseudodeterminism $1-O(\lambda^{-c})$ and pseudorandomness $1-\delta$ such
that $c>1$, $\delta(\lambda)\leq 0.49+o(1)$ and
$\ell(\lambda)>s(\lambda)\cdot\lambda$, where $s(\lambda)=\Theta(\lambda)$.
Define the QPT algorithm $G^{\oplus
s}:{\\{0,1\\}}^{s(\lambda)\lambda}\to{\\{0,1\\}}^{\ell(\lambda)}$ as
$G^{\oplus s}(k_{1},\dots,k_{s}):=\bigoplus_{i=1}^{s}G(k_{i})$. Then
$G^{\oplus s}$ is a sQPRG with pseudodeterminism $1-O(\lambda^{-(c-1)})$ and
output length $\ell(\lambda)$.

###### Proof sketch.

We first prove the pseudodeterminism property. Fix the security parameter
$\lambda$. The set of good seeds of $G^{\oplus s}$ is defined to be the
$s(\lambda)$-fold Cartesian product
$\mathcal{K}_{\lambda}\times\dots\times\mathcal{K}_{\lambda}\subseteq{\\{0,1\\}}^{s(\lambda)\lambda}$,
where $\mathcal{K}_{\lambda}$ is the set of good seeds of $G$. By the
pseudodeterminism of $G$ and a union bound over $i\in[s]$, we have

$\Pr\left[\forall i\in[s],\
k_{i}\in\mathcal{K}_{\lambda}:k=k_{\lambda}||\dots||k_{\lambda}\leftarrow{\\{0,1\\}}^{s(\lambda)\lambda}\right]\geq
1-O(s/\lambda^{c})=1-O(\lambda^{-(c-1)}).$

Next, for every
$(k_{1},\dots,k_{s})\in\mathcal{K}_{\lambda}\times\dots\times\mathcal{K}_{\lambda}$
and every $i\in[s]$, there exists some $y_{i}\in{\\{0,1\\}}^{\ell(\lambda)}$
such that $\Pr[y_{i}=G(k_{i})]\geq 1-1/\lambda^{c}$ for every $i\in[s]$.
Hence, by a union bound over $i\in[s]$, it holds that

$\Pr\left[\bigoplus_{i=1}^{s}y_{i}=G^{\oplus
s}(k_{1},\dots,k_{s})\right]\geq\Pr\left[\bigwedge_{i=1}^{s}y_{i}=G(k_{i})\right]\geq
1-O(s/\lambda^{c})=1-O(\lambda^{-(c-1)}).$

That is, $G^{\oplus s}$ has pseudodeterminism $1-O(\lambda^{-(c-1)})$. The
full proof of (strong) security is deferred to Appendix A. ∎

From Theorem 4.2, Theorem 4.5 and picking $s(\lambda)=\lambda$, we have the
following corollary.

######  Corollary 4.6.

Assuming the existence of $(c\log\lambda)$-PRS for some constant $c>12$, then
there exists a sQPRG
$G^{\oplus\lambda}:{\\{0,1\\}}^{\lambda^{2}}\to{\\{0,1\\}}^{\ell(\lambda)}$
with pseudodeterminism $1-O(\lambda^{-(c/12-1)})$ and output length
$\ell(\lambda)=\lambda^{c/6}>\lambda^{2}$.

###  4.2 Construction of Selectively Secure QPRFs

In the same spirit, it is natural to consider the concept of
pseudodeterministic quantum pseudorandom functions (QPRFs). However, when the
pseudodeterminism is only $1-O(\lambda^{-c})$, there is a caveat. An attacker
that can make _adaptive_ queries can easily distinguish a QPRF with this level
of pseudodeterminism from a random function as follows: the distinguisher
simply queries the oracle on _the same point_ polynomially many times and
checks if the answers are all the same. A random function will always produce
identical outputs, while a QPRF with pseudodeterminism $1-O(\lambda^{-c})$
will generate different outputs with constant probability. Intuitively, non-
determinism allows the QPRF output to appear more random, thus it should
strengthen its security.

Below, we show that we can use a selectively secure
$(m(\lambda),n(\lambda))$-PRFS, where $m(\lambda)=\omega(\log\lambda)$ and
$n(\lambda)=O(\log\lambda)$, to construct a selectively secure QPRF with input
length $m(\lambda)$ and output length $\mathsf{poly}(\lambda)$.

######  Definition 4.7 (Selectively Secure Quantum Pseudorandom Functions).

A _selectively secure quantum pseudorandom function_
$F:{\\{0,1\\}}^{\lambda}\times{\\{0,1\\}}^{m(\lambda)}\to{\\{0,1\\}}^{\ell(\lambda)}$
is a QPT algorithm with the following guarantees:

  * •

Pseudodeterminism: There exists a constant $c>0$ and a function
$\mu(\lambda)=O(\lambda^{-c})$ such that for every $\lambda\in\mathbb{N}$ and
every $x\in{\\{0,1\\}}^{m(\lambda)}$, there exists a set of “good keys”
$\mathcal{K}_{\lambda,x}\subseteq{\\{0,1\\}}^{\lambda}$ satisfying the
following:

    1. 1.

$\Pr[k\in\mathcal{K}_{\lambda,x}:k\leftarrow{\\{0,1\\}}^{\lambda}]\geq
1-\mu(\lambda)$.

    2. 2.

For any $k\in\mathcal{K}_{\lambda,x}$, it holds that

$\max\limits_{y\in{\\{0,1\\}}^{\ell(\lambda)}}\Pr[y=F(k,x)]\geq
1-\mu(\lambda),$

where the probability is over the randomness of $F$.

  * •

Selective Security: For any polynomial $q(\cdot)$, any (non-uniform) QPT
distinguisher $A$ and any family of pairwise distinct indices
$\left(\left\\{x_{1},\dots,x_{q(\lambda)}\right\\}\subseteq{\\{0,1\\}}^{m(\lambda)}\\}\right)_{\lambda}$,
there exists a negligible function $\varepsilon(\cdot)$ such that for all
$\lambda\in\mathbb{N}$,

$\Bigg{|}\Pr\left[A_{\lambda}(x_{1},\dots,x_{q{(\lambda)}},y_{1},\dots,y_{q(\lambda)})=1:\begin{subarray}{c}k\leftarrow{\\{0,1\\}}^{\lambda},\\\
y_{1}\leftarrow F(k,x_{1}),\dots,y_{q{(\lambda)}}\leftarrow
F(k,x_{q{(\lambda)}})\end{subarray}\right]\\\
-\Pr\left[A_{\lambda}(x_{1},\dots,x_{q{(\lambda)}},y_{1},\dots,y_{q(\lambda)})=1:y_{1},\dots,y_{q{(\lambda)}}\leftarrow{\\{0,1\\}}^{\ell(\lambda)}\right]\Bigg{|}\leq\varepsilon(\lambda).$

We will construct a selectively secure quantum pseudorandom function based on
a selectively secure $(m(\lambda),n(\lambda))$-PRFS, where
$m(\lambda)=\omega(\log\lambda)$ and $n(\lambda)=O(\log\lambda)$.

######  Theorem 4.8 ($(\omega(\log\lambda),O(\log\lambda))$-PRFS implies
selectively secure QPRF).

Assuming the existence of selectively secure $(m(\lambda),c\log\lambda)$-PRFS
for some constant $c>12$ and $m(\lambda)=\omega(\log\lambda)$, then there
exists a selectively secure QPRF
$F:{\\{0,1\\}}^{\lambda^{2}}\times{\\{0,1\\}}^{m(\lambda)}\to{\\{0,1\\}}^{\ell(\lambda)}$
with pseudodeterminism $1-O(\lambda^{-(c/12-1)})$, input length $m(\lambda)$
and output length $\ell(\lambda)=\lambda^{c/6}$.

###### Proof.

Consider the following construction:

######  Construction 4.9 (Selectively Secure Quantum Pseudorandom Functions).

  1. 1.

Input: a key $k\in{\\{0,1\\}}^{\lambda^{2}}$ and input
$x\in{\\{0,1\\}}^{m(\lambda)}$.

  2. 2.

Parse $k$ as $k_{1}||\dots||k_{\lambda}$ such that
$k_{i}\in{\\{0,1\\}}^{\lambda}$ for every $i\in[\lambda]$.

  3. 3.

For $i\in[\lambda]$, run ${\sf PRFS}(k_{i},x)$ to get $\rho_{k_{i},x}^{\otimes
t(\lambda)}$, where $t(\lambda)=144\lambda d(\lambda)^{8}$.

  4. 4.

For $i\in[\lambda]$, run ${\sf Ext}(\rho_{k_{i},x}^{\otimes t(\lambda)})$ to
get $y_{i}\in{\\{0,1\\}}^{\ell(\lambda)}$.

  5. 5.

Let $y=\bigoplus_{i=1}^{\lambda}y_{i}$, output
$y\in{\\{0,1\\}}^{\ell(\lambda)}$.

##### Pseudodeterminism.

We complete the proof by a hybrid argument. For any fixed
$x\in{\\{0,1\\}}^{m(\lambda)}$, consider the following hybrids.

  * •

$\mathsf{H}_{1}:$ In the first hybrid, $y$ is generated according to 4.9.

    1. 1.

Sample $k\leftarrow{\\{0,1\\}}^{\lambda^{2}}$.

    2. 2.

Parse $k$ as $k_{1}||\dots||k_{\lambda}$ such that
$k_{i}\in{\\{0,1\\}}^{\lambda}$ for every $i\in[\lambda]$.

    3. 3.

For $i\in[\lambda]$, run ${\sf PRFS}(k_{i},x)$ $t$ times to get
$\rho_{k_{i},x}^{\otimes t(\lambda)}$.

    4. 4.

For $i\in[\lambda]$, run ${\sf Ext}(\rho_{k_{i},x}^{\otimes t(\lambda)})$ to
get $y_{i}\in{\\{0,1\\}}^{\ell(\lambda)}$.

    5. 5.

Let $y=\bigoplus_{i=1}^{\lambda}y_{i}$, output
$y\in{\\{0,1\\}}^{\ell(\lambda)}$.

  * •

$\mathsf{H}_{2}:$ In the second hybrid, the input of ${\sf Ext}$ is changed to
Haar states.

    1. 1.

For $i\in[\lambda]$, sample
$\ket{\psi_{i}}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})$.

    2. 2.

For $i\in[\lambda]$, run ${\sf Ext}(\ket{\psi_{i}}\\!\bra{\psi_{i}}^{\otimes
t(\lambda)})$ to get $y_{i}\in{\\{0,1\\}}^{\ell(\lambda)}$.

    3. 3.

Let $y=\bigoplus_{i=1}^{\lambda}y_{i}$, output
$y\in{\\{0,1\\}}^{\ell(\lambda)}$.

Similar to proving pseudodeterminism in Theorem 4.2, there exists at least
$1-O(\lambda^{-c/12})$ fraction of good keys
$\mathcal{K}^{\prime}_{\lambda,x}\subseteq{\\{0,1\\}}^{\lambda}$ such that for
any $k\in\mathcal{K}^{\prime}_{\lambda,x}$,

$\max\limits_{y\in{\\{0,1\\}}^{\ell(\lambda)}}\Pr[y={\sf Ext}({\sf
PRFS}(k,x)^{\otimes t})]\geq 1-O(\lambda^{-c/12}),$

where the probability is over the randomness of ${\sf Ext}$. Otherwise,
running ${\sf Ext}$ independently twice on input ${\sf PRFS}(k,x)^{\otimes t}$
and comparing the output would be an efficient distinguisher that contradicts
the security of ${\sf PRFS}$. The set of good keys for $F$ is defined to be
the $\lambda$-fold Cartesian product
$\mathcal{K}^{\prime}_{\lambda,x}\times\dots\times\mathcal{K}^{\prime}_{\lambda,x}\subseteq{\\{0,1\\}}^{\lambda^{2}}$.
Then following the same lines for proving pseudodeterminism in Theorem 4.5, we
can conclude that 4.9 has pseudodeterminism $1-O(\lambda^{-(c/12-1)})$.

##### Selective Security.

Before we prove the security, we introduce a simple lemma regarding the
indistinguishability of polynomially many samples of Haar states and the
output of a PRS generator with i.i.d. uniform seeds.

######  Lemma 4.10.

Let $\mathsf{PRS}$ be an $n(\cdot)$-PRS. Then for any polynomials
$t(\cdot),p(\cdot)$ and any QPT distinguisher $A$, there exists a negligible
function $\varepsilon(\cdot)$ such that

$\Pr\left[A\left(\rho^{\otimes t(\lambda)}_{1},\dots,\rho^{\otimes
t(\lambda)}_{q(\lambda)}\right)=1:\begin{subarray}{c}k_{1},\dots,k_{q(\lambda)}\leftarrow{\\{0,1\\}}^{\lambda},\\\
\rho_{1}\leftarrow\mathsf{PRS}(k_{1}),\dots,\rho_{q(\lambda)}\leftarrow\mathsf{PRS}(k_{q(\lambda)})\end{subarray}\right]\\\
-\Pr\left[A\left(\ket{\vartheta_{1}}^{\otimes
t(\lambda)},\dots,\ket{\vartheta_{q(\lambda)}}^{\otimes
t(\lambda)}\right)=1:\ket{\vartheta_{1}},\dots,\ket{\vartheta_{q(\lambda)}}\leftarrow\mathscr{H}_{n(\lambda)}\right]\leq\varepsilon(\lambda).$

###### Proof.

Consider the following hybrids $\mathsf{H}_{i}$ for
$i\in\left\\{0,1,\dots,q\right\\}$:

  1. 1.

For $1\leq j\leq i$, sample $k_{j}\leftarrow{\\{0,1\\}}^{\lambda}$ and run
$\mathsf{PRS}(k_{j})$ $t$ times to get $\rho^{\otimes t}_{j}$.

  2. 2.

For $i+1\leq j\leq q$, sample
$\ket{\vartheta_{j}}\leftarrow\mathscr{H}_{n(\lambda)}$.

  3. 3.

Output $\left(\rho^{\otimes t(\lambda)}_{1},\dots,\rho^{\otimes
t(\lambda)}_{i},\ket{\vartheta_{i+1}}^{\otimes
t(\lambda)},\dots,\ket{\vartheta_{q(\lambda)}}^{\otimes t(\lambda)}\right)$.

It is sufficient to prove the computational indistinguishability between
$\mathsf{H}_{i}$ and $\mathsf{H}_{i+1}$. Note that the only difference is the
$(i+1)$-th coordinate of the sample. Suppose there exist polynomials
$t(\cdot),q(\cdot)$ and a QPT adversary $A$ that has a non-negligible
advantage for distinguishing $\mathsf{H}_{i}$ from $\mathsf{H}_{i+1}$. Based
on $A$, we will construct a reduction $R$ to break the security of
$\mathsf{PRS}$. The reduction $R$ is defined as follows:

  1. 1.

Input: $\sigma^{\otimes t(\lambda)}$ where $\sigma$ is sampled from either
$\mathsf{PRS}(k)$ with a random $k$ or $\mathscr{H}_{n(\lambda)}$.

  2. 2.

For $1\leq j\leq i$, sample $k_{j}\leftarrow{\\{0,1\\}}^{\lambda}$ and run
$\mathsf{PRS}(k_{j})$ $t$ times to get $\rho^{\otimes t(\lambda)}_{j}$.

  3. 3.

For $i+2\leq j\leq q$, sample a $t(\lambda)$-state design $\gamma_{j}$.777Note
that is not efficient for the security reduction to sample Haar random states
in each hybrid. Instead of sampling Haar random states, the security reduction
uses $t(\lambda)$-state designs. It is known that $t(\lambda)$-state designs
can be efficiently generated (in time polynomial in $t(\lambda)$) [AE07,
DCEL09].

  4. 4.

Run $A\left(\rho^{\otimes t(\lambda)}_{1},\dots,\rho^{\otimes
t(\lambda)}_{i},\sigma^{\otimes
t(\lambda)},\gamma_{i+2},\dots,\gamma_{q}\right)$ and output whatever $A$
outputs.

First, the running time $R$ is polynomial in $\lambda$. Moreover, $R$
perfectly simulates the view of $A$ and thus has the same distinguishing
advantage as that of $A$. However, this contradicts the security of
$\mathsf{PRS}$. ∎

We complete the proof of selective security by hybrid arguments. Here, we
outline the structure of the hybrids: $\mathsf{H}_{1}$ is 4.9. In
$\mathsf{H}_{1.i}$ for $i\in\left\\{0,1,\dots,\lambda\right\\}$, we replace
the output of ${\sf PRFS}(k_{i},\cdot)$ with independent Haar states. The
computational indistinguishability between $\mathsf{H}_{1.i}$ and
$\mathsf{H}_{1.i+1}$ follows from the selective security of ${\sf PRFS}$.
Finally, in $\mathsf{H}_{2}$, all the input quantum states of the extractor
${\sf Ext}$ are now independent Haar states. It remains to show that the
resulting output strings are computationally indistinguishable from
independent, uniform strings. Fortunately, we observe that we can recycle the
proof of strong security of QPRGs in Theorem 4.5 as follows. In
$\mathsf{H}_{3}$, all the independent Haar states are replaced with the output
of $\mathsf{PRS}$ with i.i.d. uniform seeds. The computational
indistinguishability between $\mathsf{H}_{2}$ and $\mathsf{H}_{3}$ follows
from Lemma 4.10. However, the description of $\mathsf{H}_{3}$ is exactly the
same as running the strong QPRG $G^{\oplus s}$ defined in Theorem 4.5 on
i.i.d. uniform seeds. Hence, the output strings are computationally
indistinguishable from independent, uniform strings due to the strong security
of $G^{\oplus s}$. Formally, consider the following hybrids:

  * •

$\mathsf{H}_{1}:$ In the first hybrid, the adversary receives input-output
pairs according to the selective security experiment and 4.9.

    1. 1.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary.

    2. 2.

For $j\in[\lambda]$, sample $k_{j}\leftarrow{\\{0,1\\}}^{\lambda}$.

    3. 3.

For $i\in[q]$, do the following,

      1. (a)

For $j\in[\lambda]$, run ${\sf PRFS}(k_{j},x_{i})$ to get
$\rho_{k_{j},x_{i}}^{\otimes t(\lambda)}$, and run ${\sf
Ext}(\rho_{k_{j},x_{i}}^{\otimes t(\lambda)})$ to get
$y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

      2. (b)

Let $y_{i}=\bigoplus_{j=1}^{\lambda}y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

    4. 4.

Output $(x_{1},y_{1}),\dots,(x_{q},y_{q})$.

  * •

$\mathsf{H}_{1.a}$ for $a\in\left\\{0,1,\dots,\lambda\right\\}:$

    1. 1.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary.

    2. 2.

For every $j\in\left\\{a+1,\dots,\lambda\right\\}$, sample
$k_{j}\leftarrow{\\{0,1\\}}^{\lambda}$.

    3. 3.

For $i\in[q]$, do the following,

      1. (a)

For $j\in\left\\{1,\dots,a\right\\}$, sample
$\ket{\psi_{i,j}}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})$, and run
${\sf Ext}(\ket{\psi_{i,j}}\\!\bra{\psi_{i,j}}^{\otimes t(\lambda)})$ to get
$y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

      2. (b)

For $j\in\left\\{a+1,\dots,\lambda\right\\}$, run ${\sf PRFS}(k_{j},x_{i})$ to
get $\rho_{k_{j},x_{i}}^{\otimes t(\lambda)}$, and run ${\sf
Ext}(\rho_{k_{j},x_{i}}^{\otimes t(\lambda)})$ to get
$y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

      3. (c)

Let $y_{i}=\bigoplus_{j=1}^{\lambda}y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

    4. 4.

Output $(x_{1},y_{1}),\dots,(x_{q},y_{q})$.

  * •

$\mathsf{H}_{2}:$ In the second hybrid, all the input of ${\sf Ext}$ is
changed to Haar random states.

    1. 1.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary.

    2. 2.

For $i\in[q]$, do the following,

      1. (a)

For $j\in[\lambda]$, sample
$\ket{\psi_{i,j}}\leftarrow\mathscr{H}(\mathbb{C}^{d(\lambda)})$ and run ${\sf
Ext}(\ket{\psi_{i,j}}\\!\bra{\psi_{i,j}}^{\otimes t(\lambda)})$ to get
$y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

      2. (b)

Let $y_{i}=\bigoplus_{j=1}^{\lambda}y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

    3. 3.

Output $(x_{1},y_{1}),\dots,(x_{q},y_{q})$.

  * •

$\mathsf{H}_{3}:$ In the third hybrid, all the input of ${\sf Ext}$ is changed
to the output of an $n(\lambda)$-$\mathsf{PRS}$.

    1. 1.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary.

    2. 2.

For $i\in[q]$, $j\in[\lambda]$, sample
$k_{i,j}\leftarrow{\\{0,1\\}}^{\lambda}$.

    3. 3.

For $i\in[q]$, do the following,

      1. (a)

For $j\in[\lambda]$, run $\mathsf{PRS}(k_{i,j})$ $t$ times to get
$\rho_{k_{i,j}}^{\otimes t(\lambda)}$, and run ${\sf
Ext}(\rho_{k_{i,j}}^{\otimes t(\lambda)})$ to get
$y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

      2. (b)

Let $y_{i}=\bigoplus_{j=1}^{\lambda}y_{i,j}\in{\\{0,1\\}}^{\ell(\lambda)}$.

    4. 4.

Output $(x_{1},y_{1}),\dots,(x_{q},y_{q})$.

  * •

$\mathsf{H}_{4}:$ In the fourth hybrid, each $y_{i}$ is the output of the
$\mathsf{sQPRG}$ defined in Theorem 4.5 with $s(\lambda)$ set to be $\lambda$,
where the underlying $\mathsf{wQPRG}$ is defined to be the one in 4.3.

    1. 1.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary.

    2. 2.

For $i\in[q]$, sample $k_{i}\leftarrow{\\{0,1\\}}^{\lambda^{2}}$.

    3. 3.

For $i\in[q]$, run $y_{i}\leftarrow\mathsf{sQPRG}(k_{i})$.

    4. 4.

Output $(x_{1},y_{1}),\dots,(x_{q},y_{q})$.

  * •

$\mathsf{H}_{5}:$ In the last hybrid, the adversary receives independently and
uniformly sampled query-answer pairs.

    1. 1.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary.

    2. 2.

Sample $y_{1},\dots,y_{q{(\lambda)}}\leftarrow{\\{0,1\\}}^{\ell(\lambda)}$.

    3. 3.

Output $(x_{1},y_{1}),\dots,(x_{q},y_{q})$.

Hybrids $\mathsf{H}_{1}$ and $\mathsf{H}_{1,0}$ are identically distributed.
For $a\in[\lambda]$, hybrids $\mathsf{H}_{1,a-1}$ and $\mathsf{H}_{1,a}$ are
computationally indistinguishable due to the selective security of ${\sf
PRFS}$. Formally, suppose there exists some $a\in[\lambda]$ and a QPT
adversary $A$ that can distinguish $\mathsf{H}_{1,a-1}$ from
$\mathsf{H}_{1,a}$ with non-negligible advantage. We construct a reduction $R$
that breaks the selective security of ${\sf PRFS}$ as follows:888Recall that
in the definition of selective security, the indices are required to be
pairwise distinct.

  1. 1.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary $A$.

  2. 2.

For every $j\in\left\\{a+1,\dots,\lambda\right\\}$, sample
$k_{j}\leftarrow{\\{0,1\\}}^{\lambda}$.

  3. 3.

Send $x_{1},\dots,x_{q}$ to the challenger and receive $\sigma^{\otimes
t(\lambda)}_{1},\dots,\sigma^{\otimes t(\lambda)}_{q}$, where each
$\sigma_{i}$ is sampled either from ${\sf PRFS}(k,x_{i})$ with the same
uniformly random key or $\mathscr{H}(\mathbb{C}^{d}(\lambda))$.

  4. 4.

For $i\in[q]$, do the following,

    1. (a)

For $j\in\left\\{1,\dots,a-1\right\\}$, sample a $t(\lambda)$-state design
$\gamma_{i,j}$ and run ${\sf Ext}(\gamma_{i,j})$ to get $y_{i,j}$.

    2. (b)

Run ${\sf Ext}(\sigma^{\otimes t(\lambda)}_{i})$ to get $y_{i,a}$.

    3. (c)

For $j\in\left\\{a+1,\dots,\lambda\right\\}$, run ${\sf PRFS}(k_{j},x_{i})$
$t$ times to get $\rho_{k_{j},x_{i}}^{\otimes t(\lambda)}$, and run ${\sf
Ext}(\rho_{k_{j},x_{i}}^{\otimes t(\lambda)})$ to get $y_{i,j}$.

    4. (d)

Let $y_{i}=\bigoplus_{j=1}^{\lambda}y_{i,j}$.

  5. 5.

Run $A((x_{1},y_{1}),\dots,(x_{q},y_{q}))$ and output whatever $A$ outputs.

The reduction $R$ perfectly simulates $A$’s view. Hence, the distinguishing
advantage of $R$ is non-negligible, which leads to a contradiction. Hybrids
$\mathsf{H}_{1,\lambda}$ and $\mathsf{H}_{2}$ are identically distributed. The
computational indistinguishability of hybrids $\mathsf{H}_{2}$ and
$\mathsf{H}_{3}$ follows from the security of $\mathsf{PRS}$. In particular,
polynomially many samples from $\mathsf{PRS}$ with independent, uniform keys
are computationally indistinguishable from i.i.d. Haar states as shown in
Lemma 4.10. Suppose there exists a QPT adversary $A$ that has a non-negligible
advantage for distinguishing $\mathsf{H}_{2}$ from $\mathsf{H}_{3}$. We
construct a reduction $R$ that contradicts Lemma 4.10 as follows:

  1. 1.

Input: $\left\\{\sigma^{\otimes
t(\lambda)}_{i,j}\right\\}_{i\in[q],j\in[\lambda]}$ where all the samples are
sampled either from $\mathsf{PRS}(k_{i,j})$ with i.i.d. uniform keys or
$\mathscr{H}_{n(\lambda)}$. Note that the number of samples is
$q(\lambda)\cdot\lambda=\mathsf{poly}(\lambda)$.

  2. 2.

Receive $x_{1},\dots,x_{q{(\lambda)}}\in{\\{0,1\\}}^{m(\lambda)}$ from the
adversary $A$.

  3. 3.

For $i\in[q]$, do the following,

    1. (a)

For $j\in[\lambda]$, run ${\sf Ext}(\sigma^{\otimes t(\lambda)}_{i,j})$ to get
$y_{i,j}$.

    2. (b)

Let $y_{i}=\bigoplus_{j=1}^{\lambda}y_{i,j}$.

  4. 4.

Run $A((x_{1},y_{1}),\dots,(x_{q},y_{q}))$ and output whatever $A$ outputs.

Since $R$ runs in polynomial time and has the same distinguishing advantage as
that of $A$, this contradicts Lemma 4.10. Hybrids $\mathsf{H}_{3}$ and
$\mathsf{H}_{4}$ are syntactically identical. Finally, the computationally
indistinguishability between $\mathsf{H}_{4}$ and $\mathsf{H}_{5}$ follows
from the strong security of $\mathsf{sQPRG}$. To be more precise, similar to
classical secure PRGs, polynomially many samples of either the output of a
$\mathsf{sQPRG}$ with i.i.d. uniform seeds or i.i.d. uniform bitstrings are
computationally indistinguishable. The proof is similar to that of Lemma 4.10.
∎

##  5 Applications

In this section, we present applications based on sQPRGs and selectively
secure QPRFs introduced in Section 4. One key advantage of using sQPRGs or
selectively secure QPRFs as the starting point is that we can build higher-
level primitives simply by following the classical construction with a slight
modification, and then security will follow from the same reasoning. However,
we must address the issue of correctness since sQPRGs and selectively secure
QPRFs have only $1-O(\lambda^{-c})$ pseudodeterminism. To resolve the issue,
we apply a simple parallel repetition followed by a majority vote to boost
correctness at the expense of increased communication complexity and key
length.

###  5.1 Pseudorandom One-Time Pad (POTP)

We construct a pseudorandom one-time pad (POTP) scheme with classical
communication from sQPRGs. A POTP is an encryption scheme in which the message
length is strictly greater than the key length.

######  Definition 5.1.

A _pseudorandom one-time pad (POTP)_ for messages of length $\ell(\lambda)$ is
a triple of QPT algorithms $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ such
that the following holds:

  * •

Correctness: There exists a negligible function $\varepsilon(\cdot)$ such that
for every $\lambda\in\mathbb{N}$ and every message
$m\in{\\{0,1\\}}^{\ell(\lambda)}$,

$\Pr\left[m=m^{\prime}:\begin{subarray}{c}k\leftarrow\mathsf{Gen}(1^{\lambda}),\\\
c\leftarrow\mathsf{Enc}(1^{\lambda},k,m),\\\
m^{\prime}\leftarrow\mathsf{Dec}(1^{\lambda},k,c)\end{subarray}\right]\geq
1-\varepsilon(\lambda).$

  * •

Stretch: For every $\lambda\in\mathbb{N}$, $\ell(\lambda)>k(\lambda)$, where
$k(\lambda)$ is the output length of $\mathsf{Gen}(1^{\lambda})$, i.e., the
key length.

  * •

Security: For any (non-uniform ) QPT adversary $A$, there exists a negligible
function $\varepsilon(\cdot)$ such that for every
$m_{0},m_{1}\in{\\{0,1\\}}^{\ell(\lambda)}$ and $\lambda\in\mathbb{N}$,

$\left|\Pr\left[A_{\lambda}(c)=1:\begin{subarray}{c}k\leftarrow\mathsf{Gen}(1^{\lambda}),\\\
c\leftarrow\mathsf{Enc}(1^{\lambda},k,m_{0})\end{subarray}\right]-\Pr\left[A_{\lambda}(c)=1:\begin{subarray}{c}k\leftarrow\mathsf{Gen}(1^{\lambda}),\\\
c\leftarrow\mathsf{Enc}(1^{\lambda},k,m_{1})\end{subarray}\right]\right|\leq\varepsilon(\lambda).$

Suppose $G_{\lambda}:{\\{0,1\\}}^{\lambda}\to{\\{0,1\\}}^{\ell(\lambda)}$ is a
sQPRG with output length $\ell(\lambda)>\lambda^{2}$ and pseudodeterminism
$1-O(\lambda^{-c})$ for arbitrary $c>0$. Consider the following construction:

######  Construction 5.2 (Pseudorandom One-Time Pad (POTP)).

  * •

$\mathsf{Gen}(1^{\lambda}):$ on input $1^{\lambda}$, outputs a key
$k\leftarrow{\\{0,1\\}}^{\lambda^{2}}$.

  * •

$\mathsf{Enc}(1^{\lambda},k,m):$ on input $1^{\lambda}$, a key
$k\in{\\{0,1\\}}^{\lambda^{2}}$ and a message
$m\in{\\{0,1\\}}^{\ell(\lambda)}$,

    1. 1.

Parse $k$ as $k_{1}||\dots||k_{\lambda}$ such that
$k_{i}\in{\\{0,1\\}}^{\lambda}$ for every $i\in[\lambda]$.

    2. 2.

For $i\in[\lambda]$, compute $c_{i}:=m\oplus
G_{\lambda}(k_{i})\in{\\{0,1\\}}^{\ell(\lambda)}$.

    3. 3.

Output $c:=c_{1}||\dots||c_{\lambda}\in{\\{0,1\\}}^{\lambda\ell(\lambda)}$.

  * •

$\mathsf{Dec}(1^{\lambda},k,c):$ on input $1^{\lambda}$, a key
$k\in{\\{0,1\\}}^{\lambda^{2}}$ and a ciphertext
$c\in{\\{0,1\\}}^{\lambda\ell(\lambda)}$,

    1. 1.

Parse $k$ as $k_{1}||\dots||k_{\lambda}$ and $c$ as
$c_{1}||\dots||c_{\lambda}$ such that $k_{i}\in{\\{0,1\\}}^{\lambda}$ and
$c_{i}\in{\\{0,1\\}}^{\ell(\lambda)}$ for all $i\in[\lambda]$.

    2. 2.

For $i\in[\lambda]$, compute $m_{i}:=c_{i}\oplus
G_{\lambda}(k_{i})\in{\\{0,1\\}}^{\ell(\lambda)}$.

    3. 3.

Output $m:={\sf MAJ}(m_{1},\dots,m_{\lambda})$, where ${\sf MAJ}$ denotes the
majority function.

For the stretch property, the message length of 5.2 satisfies
$\ell(\lambda)>k(\lambda)=\lambda^{2}$.

######  Lemma 5.3.

5.2 satisfies the correctness property.

###### Proof.

On input a random key
$k=k_{1}||\dots||k_{\lambda}\in{\\{0,1\\}}^{\lambda^{2}}$, for every
$i\in[\lambda]$ we have $\Pr\left[k_{i}\in\mathcal{K}_{\lambda}\right]\geq
1-O(\lambda^{-c})>0.9$ for sufficiently large $\lambda$ by the
pseudodeterminism of $G$, where $\mathcal{K}_{\lambda}$ is the set of good
seeds of $G$. We denote by ${\sf Good}$ the event that at least $0.8\lambda$
of the $k_{i}$’s belong in $\mathcal{K}_{\lambda}$. For each $k_{i}$, let
$G_{E}(k_{i})$ and $G_{D}(k_{i})$ denote the output of $G$ evaluated by
$\mathsf{Enc}$ and $\mathsf{Dec}$, respectively. If
$k_{i}\in\mathcal{K}_{\lambda}$, then the probability that
$G_{E}(k_{i})=G_{D}(k_{i})$ is at least $(1-O(\lambda^{-c}))^{2}$. Hence, the
success probability of the majority vote is at least

$\displaystyle\Pr_{k\leftarrow{\\{0,1\\}}^{\lambda^{2}}}\left[|\left\\{i\in[\lambda]:G_{E}(k_{i})=G_{D}(k_{i})\right\\}|>\lambda/2\right]$
$\displaystyle\geq$ $\displaystyle\Pr[{\sf
Good}]\cdot\Pr_{k\leftarrow{\\{0,1\\}}^{\lambda^{2}}}\left[|\left\\{i\in[\lambda]:G_{E}(k_{i})=G_{D}(k_{i})\right\\}|>\lambda/2\mid{\sf
Good}\right],$

where the probability is over $k$, $G_{E}$ and $G_{D}$.

First, $\Pr[{\sf Good}]=1-2^{-\Omega(\lambda)}$ by Lemma 2.5. Moreover,
conditioned on the event ${\sf Good}$ happening, the expected number of $i$’s
such that $G_{E}(k_{i})=G_{D}(k_{i})$ is at least
$0.8\lambda\cdot(1-O(\lambda^{-c}))^{2}>0.7\lambda$ for sufficiently large
$\lambda$. Using Lemma 2.5 again, the result of the majority vote is correct
with probability at least $1-\mathsf{negl}(\lambda)$. ∎

######  Lemma 5.4.

5.2 satisfies the security property.

###### Proof.

The security follows from the security of $G$ and a hybrid argument. In
particular, consider the following hybrids. Fix $m_{0},m_{1}$.

  * •

$\mathsf{H}_{0}:$ Run $k\leftarrow\mathsf{Gen}(1^{\lambda})$, Run
$c\leftarrow\mathsf{Enc}(1^{\lambda},k,m_{0})$. Output $c$.

  * •

$\mathsf{H}_{0.a}$ for $a\in\left\\{0,1,\dots,\lambda\right\\}:$

    1. 1.

For $i\in\left\\{1,\dots,a\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\ell(\lambda)}$.

    2. 2.

For $i\in\left\\{a+1,\dots,\lambda\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$.

    3. 3.

Output $c=m_{0}\oplus k_{1}||\dots||m_{0}\oplus k_{a}||m_{0}\oplus
G_{\lambda}(k_{a+1})||\dots||m_{0}\oplus G_{\lambda}(k_{\lambda})$.

  * •

$\mathsf{H}_{1}:$ For $i\in[\lambda]$, sample
$c_{i}\leftarrow{\\{0,1\\}}^{\ell(\lambda)}$. Output
$c=c_{1}||\dots||c_{\lambda}$.

  * •

$\mathsf{H}_{1.b}$ for $b\in\left\\{0,1,\dots,\lambda\right\\}:$

    1. 1.

For $i\in\left\\{1,\dots,b\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$.

    2. 2.

For $i\in\left\\{b+1,\dots,\lambda\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\ell(\lambda)}$.

    3. 3.

Output $c=m_{1}\oplus G_{\lambda}(k_{1})||\dots||m_{1}\oplus
G_{\lambda}(k_{b})||m_{1}\oplus k_{b+1}||\dots||m_{1}\oplus k_{\lambda}$.

  * •

$\mathsf{H}_{2}:$ Run $k\leftarrow\mathsf{Gen}(1^{\lambda})$. Run
$c\leftarrow\mathsf{Enc}(1^{\lambda},k,m_{1})$. Output $c$.

First, hybrids $\mathsf{H}_{0}$ and $\mathsf{H}_{0.0}$ are identically
distributed. For $a\in[\lambda]$, hybrids $\mathsf{H}_{0.a-1}$ and
$\mathsf{H}_{0.a}$ are computational indistinguishabile due to the security of
$G$. Specifically, suppose there exist some $a\in[\lambda]$ and a QPT
adversary $A$ that has a non-negligible advantage for distinguishing
$\mathsf{H}_{0.a-1}$ from $\mathsf{H}_{0.a}$. Then consider the following
reduction $R$ that breaks the strong security of $G$:

  1. 1.

Input: $y\in{\\{0,1\\}}^{\ell(\lambda)}$ that is either sampled from
$G_{\lambda}(k)$ with a uniform seed $k$ or a unifrom $\ell(\lambda)$-bit
string.

  2. 2.

For $i\in\left\\{1,\dots,a-1\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\ell(\lambda)}$.

  3. 3.

For $i\in\left\\{a+1,\dots,\lambda\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$.

  4. 4.

Output $c=m_{0}\oplus k_{1}||\dots||m_{0}\oplus k_{a-1}||m_{0}\oplus
y||m_{0}\oplus G_{\lambda}(k_{a+1})||\dots||m_{0}\oplus
G_{\lambda}(k_{\lambda})$.

As $R$ runs in polynomial time and has the same distinguishing advantage as
that of $A$, it contradicts the strong security of $G$. Hybrids
$\mathsf{H}_{0.\lambda}$ and $\mathsf{H}_{1}$ are identically distributed.
Hybrids $\mathsf{H}_{1}$ and $\mathsf{H}_{1.0}$ are identically distributed.
Similarly, for $b\in[\lambda]$, hybrids $\mathsf{H}_{1.b-1}$ and
$\mathsf{H}_{1.b}$ are computational indistinguishabile due to the security of
$G$. Finally, hybrids $\mathsf{H}_{1.\lambda}$ and $\mathsf{H}_{2}$ are
identically distributed. ∎

###  5.2 Quantum Commitment with Classical Communication

Next, we construct a (bit) commitment scheme with classical communication from
sQPRGs. We follow the definition in [AQY22, AGQY22] closely.

######  Definition 5.5.

A bit commitment scheme is given by a pair of (uniform) QPT algorithms
$(C,R)$, where $C=\left\\{C_{\lambda}\right\\}_{\lambda\in\mathbb{N}}$ is
called the _committer_ and
$R=\left\\{R_{\lambda}\right\\}_{\lambda\in\mathbb{N}}$ is called the
_receiver_. There are two phases in a commitment scheme: a commit phase and a
reveal phase.

  * •

Commit phase: In the (possibly interactive) commitment phase between
$C_{\lambda}$ and $R_{\lambda}$, the committer $C_{\lambda}$ commits to a bit
$b$. The communication between $C_{\lambda}$ and $R_{\lambda}$ is
classical.999Alternately, both the committer and the receiver measure every
message they receive in the computational basis. We denote the execution of
the commit phase to be
$\sigma_{CR}\leftarrow\mathsf{Commit}\braket{C_{\lambda}(b),R_{\lambda}}$,
where $\sigma_{CR}$ is the tensor product of $C_{\lambda}$’s state and
$R_{\lambda}$’s state after the commit phase.

  * •

Reveal phase: In the reveal phase $C_{\lambda}$ interacts with $R_{\lambda}$
and the output is a trit $\mu\in\left\\{0,1,\bot\right\\}$ indicating the
receiver’s output bit or a rejection flag. We denote an execution of the
reveal phase where the committer and receiver start with the joint state
$\sigma_{CR}$ by
$\mu\leftarrow\mathsf{Reveal}\braket{C_{\lambda}(b),R_{\lambda},\sigma_{CR}}$.

We anticipate the commitment scheme to satisfy the following properties:

  * •

Correctness: We say that a commitment scheme $(C,R)$ satisfies correctness if

$\Pr\left[b^{\prime}=b:\begin{subarray}{c}\sigma_{CR}\leftarrow\mathsf{Commit}\braket{C_{\lambda}(b),R_{\lambda}},\\\
b^{\prime}\leftarrow\mathsf{Reveal}\braket{C_{\lambda}(b),R_{\lambda},\sigma_{CR}}\end{subarray}\right]\geq
1-\varepsilon(\lambda),$

where $\varepsilon(\cdot)$ is a negligible function.

  * •

Computational Hiding: We say that a commitment scheme $(C,R)$ satisfies
computational hiding if for any malicious QPT receiver
$\left\\{R_{\lambda}^{*}\right\\}_{\lambda\in\mathbb{N}}$, for any QPT
distinguisher $\left\\{D_{\lambda}\right\\}_{\lambda\in\mathbb{N}}$, the
following holds:

$\left|\Pr\limits_{(\tau,\sigma_{CR^{*}})\leftarrow\mathsf{Commit}\braket{C_{\lambda}(0),R_{\lambda}^{*}}}[D_{\lambda}(\sigma_{R^{*}})=1]-\Pr\limits_{(\tau,\sigma_{CR^{*}})\leftarrow\mathsf{Commit}\braket{C_{\lambda}(1),R_{\lambda}^{*}}}[D_{\lambda}(\sigma_{R^{*}})=1]\right|\leq\varepsilon(\lambda),$

where $\varepsilon(\cdot)$ is a negligible function and $\tau$ is the
transcript in the commitment phase.

  * •

Statistical Binding: We say that a commitment scheme $(C,R)$ satisfies
statistical binding if for any malicious computational unbounded committer
$\left\\{C_{\lambda}^{*}\right\\}_{\lambda\in\mathbb{N}}$, the following
holds:

$\Pr\left[\mathsf{Reveal}\braket{C^{*},R_{\lambda},\sigma_{C^{*}R}}=0\land\mathsf{Reveal}\braket{C^{*},R_{\lambda},\sigma_{C^{*}R}}=1:\begin{subarray}{c}(\tau,\sigma_{C^{*}R})\leftarrow\mathsf{Commit}\braket{C^{*},R_{\lambda}}\end{subarray}\right]\leq\varepsilon(\lambda).$

where $\varepsilon(\cdot)$ is a negligible function and $\tau$ is the
transcript in the commitment phase.

Suppose $G_{\lambda}:{\\{0,1\\}}^{\lambda}\to{\\{0,1\\}}^{\ell(\lambda)}$ is a
sQPRG with output length $\ell(\lambda)=3\lambda$ and pseudodeterminism
$1-O(\lambda^{-c})$ for arbitrary $c>0$. Consider the following construction,
which is adapted from Naor’s commitment scheme [Nao89]:

######  Construction 5.6 (Quantum Bit Commitment with Classical
Communication).

  * •

Commit phase:

    1. 1.

The receiver $R$ samples $r\leftarrow{\\{0,1\\}}^{3\lambda}$ and sends it to
the committer $C$.

    2. 2.

For $i\in[\lambda]$, the committer $C$ samples
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$.

    3. 3.

The committer $C$ on input $b\in{\\{0,1\\}}$, outputs

$\mathsf{Com}=\begin{cases}G(k_{1})||\dots||G(k_{\lambda})&\text{if }b=0\\\
G(k_{1})\oplus r||\dots||G(k_{\lambda})\oplus r&\text{if }b=1.\\\ \end{cases}$

  * •

Reveal phase:

    1. 1.

The committer $C$ sends the decommitment message $(b,k_{1},\dots,k_{\lambda})$
to the receiver $R$.

    2. 2.

The receiver $R$ parses $\mathsf{Com}$ as $y_{1}||\dots||y_{\lambda}$ where
$y_{i}\in{\\{0,1\\}}^{3\lambda}$ for all $i\in[\lambda]$.

    3. 3.

For $i\in[\lambda]$, the receiver $R$ checks whether $y_{i}=G(k_{i})$ if
$b=0$; checks whether $y_{i}=G(k_{i})\oplus r$ if $b=1$. Let
$N\in\left\\{0,1,\dots,\lambda\right\\}$ be the number of occurrences where
the equality holds

    4. 4.

If $N\geq 2\lambda/3$, the receiver $R$ outputs $b$; otherwise outputs $\bot$.

######  Lemma 5.7.

5.6 satisfies the correctness property.

###### Proof.

The proof is similar to that of Lemma 5.3. In particular, the correctness
follows from the pseudodeterminism of $G$ and Lemma 2.5. ∎

######  Lemma 5.8.

5.6 satisfies the computational hiding property.

###### Proof.

The proof is similar to the proof of Lemma 5.4. Consider the following hybrids
for any fixed $r\in{\\{0,1\\}}^{3\lambda}$.

  * •

$\mathsf{H}_{0}:$ For $i\in[\lambda]$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$. Output
$\mathsf{Com}=G(k_{1})||\dots||G(k_{\lambda})$;

  * •

$\mathsf{H}_{0.a}$ for $a\in\left\\{0,1,\dots,\lambda\right\\}:$

    1. 1.

For $i\in\left\\{1,\dots,a\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{3\lambda}$.

    2. 2.

For $i\in\left\\{a+1,\dots,\lambda\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$.

    3. 3.

Output $\mathsf{Com}=k_{1}||\dots||k_{a}||G(k_{a+1})||\dots||G(k_{\lambda})$.

  * •

$\mathsf{H}_{1}:$ For $i\in[\lambda]$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{3\lambda}$. Output
$\mathsf{Com}=k_{1}||\dots||k_{\lambda}$.

  * •

$\mathsf{H}_{2}:$ For $i\in[\lambda]$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{3\lambda}$. Output $\mathsf{Com}=k_{1}\oplus
r||\dots||k_{\lambda}\oplus r$.

  * •

$\mathsf{H}_{2.b}$ for $b\in\left\\{0,1,\dots,\lambda\right\\}:$

    1. 1.

For $i\in\left\\{1,\dots,b\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$.

    2. 2.

For $i\in\left\\{b+1,\dots,\lambda\right\\}$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{3\lambda}$.

    3. 3.

Output $c=G(k_{1})\oplus r||\dots||G(k_{b})\oplus r||k_{b+1}\oplus
r||\dots||k_{\lambda}\oplus r$.

  * •

$\mathsf{H}_{3}:$ For $i\in[\lambda]$, sample
$k_{i}\leftarrow{\\{0,1\\}}^{\lambda}$. Output $G(k_{1})\oplus
r||\dots||G(k_{\lambda})\oplus r$;

Hybrids $\mathsf{H}_{0}$ and $\mathsf{H}_{0.0}$ are identically distributed.
For $a\in[\lambda]$, following the same lines in Lemma 5.4, hybrids
$\mathsf{H}_{0.a-1}$ and $\mathsf{H}_{0.a}$ are computational
indistinguishabile due to the strong security of $G$. Hybrids
$\mathsf{H}_{0.\lambda}$ and $\mathsf{H}_{1}$ are identically distributed.
Hybrids $\mathsf{H}_{1}$ and $\mathsf{H}_{2}$ are identically distributed.
Hybrids $\mathsf{H}_{2}$ and $\mathsf{H}_{2.0}$ are identically distributed.
Similarly, for $b\in[\lambda]$, hybrids $\mathsf{H}_{2.b-1}$ and
$\mathsf{H}_{2.b}$ are computational indistinguishabile due to the strong
security of $G$. Finally, hybrids $\mathsf{H}_{2.\lambda}$ and
$\mathsf{H}_{3}$ identically distributed. ∎

######  Lemma 5.9.

5.6 satisfies the statistical binding property.

###### Proof.

To prove the statistical binding property, we introduce the following
definition. For every $k\in{\\{0,1\\}}^{\lambda}$, define
$F(k):=\operatornamewithlimits{argmax}_{y\in{\\{0,1\\}}^{3\lambda}}\Pr[G(k)=y]$
(if it is not unique, then we pick the lexicographically first one). Let the
set of “bad randomness” ${\sf Bad}\subseteq{\\{0,1\\}}^{3\lambda}$ be

${\sf Bad}:=\left\\{r\in{\\{0,1\\}}^{3\lambda}\mid\exists
k,k^{\prime}\in{\\{0,1\\}}^{\lambda}\text{ s.t. }F(k)\oplus
F(k^{\prime})=r\right\\}.$

Then it is easy to see that $\Pr[r\in{\sf
Bad}:r\leftarrow{\\{0,1\\}}^{3\lambda}]\leq 2^{\lambda}\cdot
2^{\lambda}/2^{3\lambda}=2^{-\lambda}$. Now, the analysis starts to deviate
from the proof of the classical case. Classically, if $r\notin{\sf Bad}$, then
it is impossible for the malicious committer to succeed. However, since now
$G$ is _pseudodeterministic_ , there is still a chance that $G(k)\oplus
G(k^{\prime})=r$ for some $k,k^{\prime}$ even if $r\notin{\sf Bad}$.
Fortunately, according to the definition of the set ${\sf Bad}$, the XOR of
the _most likely_ output of $G(k)$ and $G(k^{\prime})$ for any $k,k^{\prime}$
must not equal $r$. Below, we will show that the probability that $G(k)\oplus
G(k^{\prime})=r$ conditioned on $r\notin{\sf Bad}$ is at most $1/2$ for any
$k,k^{\prime}$.

First, we state a basic fact regarding the inner product of two probability
vectors that have distinct mostly likely outcomes.

######  Claim 5.10.

Let $p,q\in\mathbb{R}^{n}$ be two probability vectors such that
$\operatornamewithlimits{argmax}_{i\in[n]}p_{i}\neq\operatornamewithlimits{argmax}_{i\in[n]}q_{i}$
(if it is not unique, then we pick the lexicographically first one). Then
$\sum_{i\in[n]}p_{i}q_{i}\leq 1/2$.

###### Proof.

Without loss of generality, we assume that the coordinates of $p$ are sorted
in non-increasing order, i.e., $1\geq p_{1}\geq p_{2}\geq\dots\geq p_{n}\geq
0$. Since
$\operatornamewithlimits{argmax}_{i\in[n]}p_{i}\neq\operatornamewithlimits{argmax}_{i\in[n]}q_{i}$,
we have $q_{1}$ to not be the maximum coordinate.

We claim that there exists $(q^{\prime}_{1},\ldots,q^{\prime}_{n})$ such that
the following holds:

  * •

$\forall i\geq 3$, $q^{\prime}_{i}=0$,

  * •

$\sum_{i\in[n]}p_{i}q_{i}\leq\sum_{i\in[n]}p^{\prime}_{i}q^{\prime}_{i}$.

  * •

$q^{\prime}_{1}\leq q^{\prime}_{2}$.

Suppose we instantiate $q^{\prime}_{1}=q_{1}$ and $q^{\prime}_{2}=\sum_{i\geq
2}q_{i}$ then the above three bullet points hold.

Now, we have the following:

$\displaystyle\sum_{i\in[n]}p_{i}q^{\prime}_{i}$ $\displaystyle=$
$\displaystyle p_{1}q^{\prime}_{1}+p_{2}q^{\prime}_{2}.$

Since $q^{\prime}_{1}\leq q^{\prime}_{2}$, $q^{\prime}_{1}+q^{\prime}_{2}=1$
and $p_{1}\geq p_{2}$, the above expression is maximized when
$q^{\prime}_{1}=q^{\prime}_{2}=\frac{1}{2}$. Thus,
$\sum_{i\in[n]}p_{i}q^{\prime}_{i}\leq\frac{1}{2}(p_{1}+p_{2})\leq\frac{1}{2}$.
This further implies that $\sum_{i\in[n]}p_{i}q_{i}\leq\frac{1}{2}$. ∎

######  Claim 5.11.

For every $r\notin{\sf Bad}$ and every $k,k^{\prime}\in{\\{0,1\\}}^{\lambda}$,
$\Pr[G(k)\oplus G(k^{\prime})=r]\leq 1/2$, where the probability is over the
randomness of $G$.

###### Proof.

Fix $k,k^{\prime}$ and $r\notin{\sf Bad}$. First, recall that $r\notin{\sf
Bad}$ means $F(k)\oplus F(k^{\prime})\neq r$. The probability can be written
as

$\displaystyle\Pr[G(k)\oplus
G(k^{\prime})=r]=\sum_{z\in{\\{0,1\\}}^{3\lambda}}\Pr[G(k)=z]\Pr[G(k^{\prime})=z\oplus
r].$

Now, we define the probability vectors
$u,u^{\prime}\in\mathbb{R}^{2^{3\lambda}}$ for the random variables
$G(k),G(k^{\prime})$ respectively. More precisely, the coordinate of $u$ is
defined to be $u_{y}:=\Pr[G(k)=y]$; $u^{\prime}$ is defined similarly. We use
the above notation to rewrite the quantity as follows.

$\displaystyle\sum_{y\in{\\{0,1\\}}^{3\lambda}}\Pr[G(k)=y]\Pr[G(k^{\prime})=y\oplus
r]=\sum_{y\in{\\{0,1\\}}^{3\lambda}}u_{y}\cdot u^{\prime}_{y\oplus r}.$

Then we set $p$ and $q$ in 5.10 to be the vertors that satisfy $p_{y}=u_{y}$
and $q_{y}=u_{y\oplus r}$ for all $y\in{\\{0,1\\}}^{3\lambda}$. Let
$y_{\max}$, $y^{\prime}_{\max}$ be the most likely outcome of $G(k)$,
$G(k^{\prime})$ respectively. Given that $r\notin{\sf Bad}$, we have
$y_{\max}\oplus y^{\prime}_{\max}\neq r$. Hence, $u$ and $u^{\prime}$ satisfy
the condition in 5.10. Finally, by 5.10, we can conclude that $\Pr[G(k)\oplus
G(k^{\prime})=r]\leq 1/2$. ∎

To prove statistical binding, we have

$\displaystyle\Pr\left[\mathsf{Reveal}\braket{C^{*},R_{\lambda},\sigma_{C^{*}R}}=0\land\mathsf{Reveal}\braket{C^{*},R_{\lambda},\sigma_{C^{*}R}}=1:\begin{subarray}{c}(\tau,\sigma_{C^{*}R})\leftarrow\mathsf{Commit}\braket{C^{*},R_{\lambda}}\end{subarray}\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}\limits_{r\leftarrow{\\{0,1\\}}^{3\lambda}}\left[\max_{k,k^{\prime}\in{\\{0,1\\}}^{\lambda^{2}}}\Pr\left[G(k_{1})||\dots||G(k_{\lambda})=G(k^{\prime}_{1})\oplus
r||\dots||G(k^{\prime}_{\lambda})\oplus r\right]\right]$ $\displaystyle\leq$
$\displaystyle\Pr\limits_{r\leftarrow{\\{0,1\\}}^{3\lambda}}[r\in{\sf Bad}]+$
$\displaystyle\mathop{\mathbb{E}}\limits_{r\leftarrow{\\{0,1\\}}^{3\lambda}}\left[\max_{k,k^{\prime}\in{\\{0,1\\}}^{\lambda^{2}}}\Pr\left[G(k_{1})||\dots||G(k_{\lambda})=G(k^{\prime}_{1})\oplus
r||\dots||G(k^{\prime}_{\lambda})\oplus r\right]\mid r\notin{\sf Bad}\right].$

The first term $\Pr[r\in{\sf Bad}]$ is at most $2^{-\lambda}$ as we shown. Let
$\xi(n,p)$ be the probability that there are at least $2n/3$ heads when
independently tossing a coin $n$ times, where the coin satisfies that
$\Pr[\mathsf{Head}]=p$. Then, the second term can be written as

$\displaystyle\mathop{\mathbb{E}}\limits_{r\leftarrow{\\{0,1\\}}^{3\lambda}}\left[\max_{k,k^{\prime}\in{\\{0,1\\}}^{\lambda^{2}}}\Pr\left[G(k_{1})||\dots||G(k_{\lambda})=G(k^{\prime}_{1})\oplus
r||\dots||G(k^{\prime}_{\lambda})\oplus r\right]\mid r\notin{\sf Bad}\right]$
$\displaystyle=\mathop{\mathbb{E}}\limits_{r\leftarrow{\\{0,1\\}}^{3\lambda}}\left[\xi\left(\lambda,\max_{k,k^{\prime}\in{\\{0,1\\}}^{\lambda}}\Pr[G(k)\oplus
G(k^{\prime})=r]\right)\mid r\notin{\sf Bad}\right]$
$\displaystyle\leq\xi\left(\lambda,\frac{1}{2}\right)=2^{-\Omega(\lambda)},$

where the inequality follows from 5.11; the last equality follows from Lemma
2.5. ∎

###  5.3 Non-Adaptive CPA-Secure Quantum Private-Key Encryption with Classical
Ciphertexts

Finally, we construct a non-adaptive CPA-Secure private-key encryption with
classical ciphertexts from selectively secure QPRFs.

######  Definition 5.12 (Non-Adaptive CPA-Secure Quantum Private-key
Encryption).

We say that a tuple of QPT algorithms
$(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is a _non-adaptive CPA-secure
quantum private-key encryption scheme_ if the following holds:

  * •

Correctness: There exists a negligible function $\varepsilon(\cdot)$ such that
for every $\lambda\in\mathbb{N}$ and every message $m$,

$\Pr_{k\leftarrow{\\{0,1\\}}^{\lambda}}\left[\mathsf{Dec}(1^{\lambda},k,\mathsf{Enc}(1^{\lambda},k,m))=m\right]\geq
1-\varepsilon(\lambda).$

  * •

Non-adaptive CPA security: For every polynomial $q(\cdot)$, any (non-uniform)
QPT adversary $A$, there exists a negligible function $\varepsilon(\cdot)$
such that for all $\lambda\in\mathbb{N}$, the adversary $A$ has at most
$\varepsilon(\lambda)$ advantage in the following experiment:

    1. 1.

The challenger generates a key $k$ by running $\mathsf{Gen}(1^{\lambda})$ and
a uniform bit $b\in{\\{0,1\\}}$.

    2. 2.

The adversary $A$ is given input $1^{\lambda}$.

    3. 3.

The adversary $A$ chooses messages
$(m^{0}_{1},m^{1}_{1})\dots,(m^{0}_{q},m^{1}_{q})$ and sends them to the
challenger.

    4. 4.

The challenger sends
$\mathsf{Enc}(k,m^{b}_{1}),\dots,\mathsf{Enc}(k,m^{b}_{q})$ to the adversary
$A$.

    5. 5.

The adversary $A$ outputs a bit $b^{\prime}\in{\\{0,1\\}}$.

    6. 6.

The challenger output $1$ if $b^{\prime}=b$, and $0$ otherwise.

Suppose
$F:{\\{0,1\\}}^{\lambda}\times{\\{0,1\\}}^{m(\lambda)}\to{\\{0,1\\}}^{\ell(\lambda)}$
is a selectively secure QPRF with $m(\lambda)=\omega(\log\lambda)$ and
pseudodeterminism $1-O(\lambda^{-c})$ for arbitrary $c>0$. In the classical
case, selectively secure pseudorandom functions imply the existence of non-
adaptive CPA-secure private-key encryption schemes. With a slight
modification, we have the following construction.

######  Construction 5.13 (Non-Adaptive CPA-Secure Quantum Private-Key
Encryption Scheme).

  1. 1.

$\mathsf{Gen}(1^{\lambda}):$ on input $1^{\lambda}$, output
$k\leftarrow{\\{0,1\\}}^{\lambda^{2}}$.

  2. 2.

$\mathsf{Enc}(1^{\lambda},k,m):$ on input a key
$k\in{\\{0,1\\}}^{\lambda^{2}}$ and a message
$m\in{\\{0,1\\}}^{\ell(\lambda)}$,

     * •

Parse $k$ as $k_{1}||\dots||k_{\lambda}$ such that
$k_{i}\in{\\{0,1\\}}^{\lambda}$ for every $i\in[\lambda]$.

     * •

Choose a uniform string $r\leftarrow{\\{0,1\\}}^{m(\lambda)}$.

     * •

For $i\in[\lambda]$, compute $F(k_{i},r)$.

     * •

Output $c=(r,m\oplus F(k_{1},r),\dots,m\oplus F(k_{\lambda},r))$.

  3. 3.

$\mathsf{Dec}(1^{\lambda},k,c):$ on input a key
$k\in{\\{0,1\\}}^{\lambda^{2}}$ and a ciphertext
$c=(r,c_{1},\dots,c_{\lambda})\in{\\{0,1\\}}^{m(\lambda)+\lambda\ell(\lambda)}$,

     * •

Parse $k$ as $k_{1}||\dots||k_{\lambda}$ such that
$k_{i}\in{\\{0,1\\}}^{\lambda}$ for every $i\in[\lambda]$.

     * •

For $i\in[\lambda]$, compute $m_{i}:=c_{i}\oplus
F(k_{i},r)\in{\\{0,1\\}}^{\ell(\lambda)}$.

     * •

Output $m:={\sf MAJ}(m_{1},\dots,m_{\lambda})$.

######  Lemma 5.14.

5.13 satisfies the correctness property.

###### Proof.

The proof is similar to that of Lemma 5.3. The correctness follows from the
pseudodeterminism of $F$ and Lemma 2.5. ∎

The following lemma follows the proof of Lemma 7.3 in [AQY22] closely.

######  Lemma 5.15.

5.13 satisfies non-adaptive CPA security.

###### Proof.

We finish the proof with a hybrid argument. Consider the following hybrids.

  * •

$\mathsf{H}_{1}:$ The adversary receives
$\left(\mathsf{Enc}(k,m^{b}_{1}),\dots,\mathsf{Enc}(k,m^{b}_{q})\right)$,
which by definition is

$\left((r_{1},m^{b}_{1}\oplus F(k_{1},r_{1}),\dots,m^{b}_{1}\oplus
F(k_{\lambda},r_{1})),\dots,(r_{q},m^{b}_{q}\oplus
F(k_{1},r_{q}),\dots,m^{b}_{q}\oplus F(k_{\lambda},r_{q}))\right)$

where $r_{1},\dots,r_{q}$ are independently and uniformly chosen.

  * •

$\mathsf{H}_{1.i}$ for $i\in\left\\{0,1,\dots,\lambda\right\\}:$ The adversary
receives

$\displaystyle\Bigg{(}\left(r_{1},m^{b}_{1}\oplus
R_{1}(r_{1}),\dots,m^{b}_{1}\oplus R_{i}(r_{1}),m^{b}_{1}\oplus
F(k_{i+1},r_{1})),\dots,m^{b}_{1}\oplus F(k_{\lambda},r_{1})\right),$
$\displaystyle\dots,\left(r_{q},m^{b}_{q}\oplus
R_{1}(r_{q}),\dots,m^{b}_{q}\oplus R_{i}(r_{q}),m^{b}_{q}\oplus
F(k_{i+1},r_{q})),\dots,m^{b}_{q}\oplus F(k_{\lambda},r_{q})\right)\Bigg{)}$

where $r_{1},\dots,r_{q}$ are independently, uniformly chosen and
$R_{1}(\cdot),\dots,R_{i}(\cdot)$ are independent random functions.

  * •

$\mathsf{H}_{2}:$ The adversary receives

$\displaystyle\Bigg{(}\left(r_{1},m^{b}_{1}\oplus
R_{1}(r_{1}),\dots,m^{b}_{1}\oplus
R_{\lambda}(r_{1})\right),\dots,\left(r_{q},m^{b}_{q}\oplus
R_{1}(r_{q}),\dots,m^{b}_{q}\oplus R_{\lambda}(r_{q})\right)\Bigg{)}$

where $r_{1},\dots,r_{q}$ are independently, uniformly chosen and
$R_{1}(\cdot),\dots,R_{\lambda}(\cdot)$ are independent random functions.

  * •

$\mathsf{H}_{3}:$ Instead of sampling $r_{1},\dots,r_{q}$ independently, they
are sampled uniformly at random conditioned on them all being distinct. The
adversary receives

$\displaystyle\Bigg{(}\left(r_{1},m^{b}_{1}\oplus
R_{1}(r_{1}),\dots,m^{b}_{1}\oplus
R_{\lambda}(r_{1})\right),\dots,\left(r_{q},m^{b}_{q}\oplus
R_{1}(r_{q}),\dots,m^{b}_{q}\oplus R_{\lambda}(r_{q})\right)\Bigg{)}$

where $R_{1}(\cdot),\dots,R_{\lambda}(\cdot)$ are independent random
functions.

Hybrids $\mathsf{H}_{1}$ and $\mathsf{H}_{1.0}$ are identically distributed.
For $i\in\left\\{0,1,\dots,\lambda-1\right\\}$, hybrids $\mathsf{H}_{1.i}$ and
$\mathsf{H}_{1.i+1}$ are computational indistinguishabile from the selective
security of $F$. In particular, suppose there exist some $i\in[\lambda]$ and a
QPT adversary $A$ such that the difference between $A$’s winning probabilities
in $\mathsf{H}_{1.i}$ and $\mathsf{H}_{1.i+1}$ is non-negligible. Consider the
following reduction $R$ that breaks the selective security of the underlying
QPRF $F$.

  1. 1.

Receive $(m^{0}_{1},m^{1}_{1})\dots,(m^{0}_{q},m^{1}_{q})$ from $A$.

  2. 2.

Sample $x_{1},x_{2},\dots,x_{q}\leftarrow{\\{0,1\\}}^{m(\lambda)}$.

  3. 3.

Query the oracle on $x_{1},x_{2},\dots,x_{q}$ and obtain
$y_{1},y_{2},\dots,y_{q}$, where $y_{i}$’s are either sampled from
$F(k,x_{i})$ with a uniform key $k$ or i.i.d. uniform $\ell(\lambda)$-bit
strings.

  4. 4.

For $j\in\left\\{1,2,\dots,q\right\\}$, do the following

    1. (a)

Sample independent random functions $R_{1}(\cdot),\dots,R_{i}(\cdot)$ and
compute $R_{1}(x_{j}),$ $R_{2}(x_{j}),$ $\dots,R_{i}(x_{j})$.101010The
reduction $R$ uses lazy evaluation to simulate each random function instead of
sampling the whole function table.

    2. (b)

Sample $k_{i+2},\dots,k_{\lambda}\leftarrow{\\{0,1\\}}^{\lambda}$ and compute
$F(k_{i+2},x_{j}),\dots,F(k_{\lambda},x_{j})$.

  5. 5.

Sample a uniform bit $b\in{\\{0,1\\}}$.

  6. 6.

Send

$\displaystyle(x_{1},m^{b}_{1}\oplus R_{1}(x_{1}),\dots,m^{b}_{1}\oplus
R_{i}(x_{1}),m^{b}_{1}\oplus y_{1},m^{b}_{1}\oplus
F(k_{i+2},x_{1}),\dots,F(k_{\lambda},x_{1})),$
$\displaystyle(x_{2},m^{b}_{2}\oplus R_{1}(x_{2}),\dots,m^{b}_{2}\oplus
R_{i}(x_{2}),m^{b}_{2}\oplus y_{2},m^{b}_{2}\oplus
F(k_{i+2},x_{2}),\dots,F(k_{\lambda},x_{2})),$ $\displaystyle\quad\vdots$
$\displaystyle(x_{q},m^{b}_{q}\oplus R_{1}(x_{q}),\dots,m^{b}_{q}\oplus