# Commitments are equivalent to one-way state generators

Rishabh Batra1 Rahul Jain1,2,3

(1 Centre for Quantum Technologies
2Department of Computer Science, National University of Singapore
3 MajuLab, UMI 3654, Singapore)

###### Abstract

One-way state generators ($\mathrm{OWSG}$) [MY22a] are natural quantum analogs
to classical one-way functions. We show that
$O\left(\frac{n}{\log(n)}\right)$-copy $\mathrm{OWSG}$s ($n$ represents the
input length) are equivalent to $\mathrm{poly}(n)$-copy $\mathrm{OWSG}$s and
to quantum commitments. Since known results show that
$o\left(\frac{n}{\log(n)}\right)$-copy $\mathrm{OWSG}$s cannot imply
commitments [CGG+23], this shows that $O\left(\frac{n}{\log(n)}\right)$-copy
$\mathrm{OWSG}$s are the weakest $\mathrm{OWSG}$s from which we can get
commitments (and hence much of quantum cryptography).

Our construction follows along the lines of Håstad, Impagliazzo, Levin and
Luby [HILL99], who obtained classical pseudorandom generators ($\mathrm{PRG}$)
from classical one-way functions ($\mathrm{OWF}$), however with crucial
modifications. Our construction, when applied to the classical case, provides
an alternative to the construction provided by [HILL99]. Since we do not argue
conditioned on the output of the one-way function, our construction and
analysis are arguably simpler and may be of independent interest.

##  1 Introduction

Commitments are one of the most fundamental primitives in cryptography. A
commitment scheme allows a sender to commit some message $m$ (in an encrypted
form) to a receiver such that the following properties hold:

Hiding: the receiver should not be able to learn the message $m$ before the
sender decides to reveal it.

Binding: the sender should not be able to change the message to some
$m^{\prime}\neq m$ once it has committed to $m$.

An intuitive way to think about commitments is as follows: the sender Alice
locks the message to be sent in a physical box and sends it across to the
receiver Bob and keeps the key with herself. When Alice wants to reveal the
message, she just sends the key across to Bob. Hiding follows from the fact
that Bob cannot open the box unless Alice sends the key. Binding follows from
the fact that Alice can’t change the message once she has sent the box across.

There are two types of securities considered in cryptography: statistical
security (against computationally unbounded adversaries) and computational
security (against computationally bounded adversaries). Most of the results in
classical cryptography are based on some computational assumptions.

It is known that both statistical hiding and statistical binding cannot be
achieved using classical protocols. There are some tasks e.g. statistically
secure key distribution that are not possible using classical protocols,
however are possible using quantum protocols [BB84, Eke91]. This leads to the
question if it is possible to have both statistical hiding and statistical
binding using quantum protocols for commitments. It is known that this is also
not possible [May97, Lo97, LC97]. Thus in the quantum regime also,
computational assumptions are necessary for the existence of many
cryptographic primitives.

A pseudorandom generator ($\mathrm{PRG}$) is an efficiently computable
function, $\mathrm{PRG}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{l(n)}$ such that
$l(n)>n$ and $\mathrm{PRG}(U_{n})$ ($U_{n}$ represents the uniform
distribution on $n$ bits) is computationally indistinguishable from
$U_{l(n)}$. A one-way function ($\mathrm{OWF}$) is a function that is
efficiently computable and hard to invert. The existence of one-way functions
is a widely used computational assumption in classical cryptography and many
of the classical cryptographic primitives are known to imply the existence of
one-way functions. An EFID pair [Gol90] is a pair of efficiently samplable
distributions that are statistically far and computationally
indistinguishable. It is known that one-way functions, EFID and $\mathrm{PRG}$
are equivalent to each other [Gol01].

In the quantum world, however, the story is not as straightforward. Morimae
and Yamakawa [MY22b] showed that quantum commitments can be based on
pseudorandom state generators ($\mathrm{PRSG}$) [JLS18, AQY22], which can be
thought of as a generalization of $\mathrm{PRG}$s with quantum outputs. It is
known that $\mathrm{PRSG}$s can exist even if BQP = QMA (relative to a quantum
oracle) [Kre21] or if P = NP (relative to a classical oracle) [KQST23], which
does not allow for the existence of one-way functions (relative to these
oracles).

An $\mathrm{EFI}$ (see Definition 16) is a quantum polynomial time
($\mathrm{QPT}$) algorithm that generates a pair of quantum states that is
statistically far and computationally indistinguishable [BCQ23]. Quantum
commitments are known to be equivalent to EFI [BCQ23, Yan22]. A
$k^{*}$-imbalanced $\mathrm{EFI}$ is a $\mathrm{QPT}$ algorithm that takes as
input a parameter $k$ and generates a pair of states, say $\rho_{0}(k)$ and
$\rho_{1}(k)$, that is computationally indistinguishable for $k\leq k^{*}$ and
is statistically far for $k\geq k^{*}$. It is easily seen that an
$\mathrm{EFI}$ implies an imbalanced-$\mathrm{EFI}$. Khurana and Tomer [KT24]
show that the converse is also true (below $\lambda$ represents the security
parameter).

######  Fact 1 ([KT24]).

Let $k^{*}(\lambda)\in\mathrm{poly}(\lambda)$. Then a $k^{*}$-imbalanced
$\mathrm{EFI}$ implies quantum commitments.

One-way state generators ($\mathrm{OWSG}$) [MY22a] are quantum generalizations
of one-way functions in which the output $\phi(x)$ (for input
$x\in\\{0,1\\}^{n}$) is a quantum state and the function is difficult to
invert even when multiple copies of the output state, that is
$\phi(x)^{\otimes m}$, is given. Note that for classical one-way functions,
providing many copies of $f(x)$ to the adversary was not changing anything
since the adversary could have made the copies itself. However, the quantum
no-cloning theorem does not allow the adversary to copy quantum states and
hence providing many copies may help the adversary.

We use a definition of $\mathrm{OWSG}$ (see Definition 14) that differs from
the definitions used in [MY22a] and [KT24]. In our definition, the verifier
Ver is an unbounded algorithm and the adversary $A$ is a non-uniform
$\mathrm{QPT}$ algorithm, that is a $\mathrm{QPT}$ algorithm that is provided
a polynomial-size classical advice string. Providing polynomial-size advice
string to adversaries is quite common in classical cryptography [Gol01] and
allows for several reductions to go through. In the definition by [MY22a],
both Ver and $A$ are uniform $\mathrm{QPT}$ algorithms. In the definition by
[KT24], Ver is uniform $\mathrm{QPT}$ and $A$ is a $\mathrm{QPT}$ algorithm
that is provided polynomial-size quantum states as advice. Note that
increasing the power of Ver allows for a larger class of $\mathrm{OWSG}$s and
increasing the power of $A$ allows for a smaller class of $\mathrm{OWSG}$s. In
that sense, our definition is incomparable to that of [MY22a]. An
$\mathrm{OWSG}$ according to [KT24] is also an $\mathrm{OWSG}$ according to
our definition.

[KT24] show that $\mathrm{OWSG}$s with pure-state output imply $\mathrm{EFI}$.
Construction of an $\mathrm{EFI}$ from a mixed-state output $\mathrm{OWSG}$
was left open which we resolve. Our main result is (below $n$ represents the
key-length of the OWSG):

######  Theorem 1.

Let $m=\frac{cn}{\log(n)}$ for some constant $c>0$. An $m$-copy
$\mathrm{OWSG}$ implies a $k^{*}$-imbalanced $\mathrm{EFI}$ for some
$k^{*}(\lambda)\in\mathrm{poly}(\lambda)$.

From Theorem 1 and Fact 1, we get:

######  Corollary 2.

Let $m=\frac{cn}{\log(n)}$ for some constant $c>0$. An $m$-copy
$\mathrm{OWSG}$ implies an $\mathrm{EFI}$.

Combining this with previous works that show secure multi-party computation
from quantum commitments [GLSV21, BCKM21, AQY22] (which are in turn equivalent
to EFI), we get:

######  Corollary 3.

Let $m=\frac{cn}{\log(n)}$ for some constant $c>0$. An $m$-copy
$\mathrm{OWSG}$ implies secure multi-party computation for all
functionalities.

We show the converse to Corollary 2 is also true.

######  Theorem 4.

An $\mathrm{EFI}$ implies a $\mathrm{poly}(n)$-copy $\mathrm{OWSG}$.

Combining the above results we get:

######  Corollary 5.

The following cryptographic primitives are equivalent:

  * •

$\mathrm{poly}(n)$-copy $\mathrm{OWSG}$,

  * •

$O\left(\frac{n}{\log(n)}\right)$-copy $\mathrm{OWSG}$,

  * •

$\mathrm{EFI}$,

  * •

quantum commitments.

A natural question that can be asked at this point is whether an
$o\left(\frac{n}{\log(n)}\right)$-copy $\mathrm{OWSG}$ implies a
$\mathrm{poly}(n)$-copy $\mathrm{OWSG}$ (equivalently $\mathrm{EFI}$)? Cavalar
et al. [CGG+23] show that $o\left(\frac{n}{\log(n)}\right)$-copy pure-state
output $\mathrm{OWSG}$s with statistical security exist unconditionally, which
cannot imply an $\mathrm{EFI}$ (by definition of $\mathrm{EFI}$). This gives
the following corollary.

######  Corollary 6.

$O\left(\frac{n}{\log(n)}\right)$-copy $\mathrm{OWSG}$s are the weakest
$\mathrm{OWSG}$s from which we can get an $\mathrm{EFI}$, equivalently,
commitment schemes.

### Proof idea:

Let $f(\cdot)$ be an $\mathrm{OWF}$ that is hard to invert given $f(X)$ ($X$
represents the input random variable). A hardcore function $g(\cdot)$ for
$f(\cdot)$ is an efficiently computable function such that $f(X)g(X)$ and
$f(X)\otimes U_{|g(X)|}$ are computationally indistinguishable. However, we do
not have the guarantee that $f(X)g(X)$ and $f(X)\otimes U_{|g(X)|}$ are
statistically far apart which is necessary for them to be an $\mathrm{EFI}$
pair.

Håstad, Impagliazzo, Levin and Luby [HILL99] presented a construction of a
classical $\mathrm{PRG}$ from a classical $\mathrm{OWF}$. The idea in [HILL99]
is to first append $HH(X)$ (where $H,H(X)$ are the seed and the output of a
$2$-universal hash function based extractor) to $f(X)$ to increase the amount
of information about $X$ in $f(X)HH(X)$. This (sort of) makes $X\rightarrow
f(X)HH(X)$ an injective function. On appending $HH(X)$, one needs to ensure
that the resultant function remains one-way. For this to happen, one can take
$|H(X)|$ to be around $S_{2}(X|f(X))$ which ensures that $HH(X)$ is nearly
independent of $f(X)$. Here $S_{\alpha}(\cdot)$ represents $\alpha$-Rényi
entropy (see Definition 5). In [HILL99], $|H(X)|$ depended on the number of
preimages of $f(X)$, and hence they needed to condition on the outcome $f(X)$.
They then appended a hardcore function $g(X)$ to $f(X)HH(X)$. Doing this
maintains computational indistinguishability of $f(X)HH(X)g(X)$ from
$f(X)HH(X)\otimes U_{|g(X)|}$. Since $f(X)HH(X)$ carries most information
about $X$ (injectivity), they argued that $f(X)HH(X)g(X)$ and
$f(X)HH(X)\otimes U_{|g(X)|}$ are statistically far apart, thus producing an
$\mathrm{EFI}$ pair.

In the quantum regime, this approach runs into an obvious issue that one
cannot condition on a quantum state. [KT24] circumvent this by measuring the
output state using efficient shadow tomography (which preserves expectation
values for exponentially many observables). They then get a classical output
which allows them to proceed with arguments along the lines of [HILL99].
However they face an additional issue: after conditioning on the measurement
outcome, the probability distribution on the preimages may not be uniform.
They overcome this using novel arguments. Finally, they show that a pure-state
$\mathrm{OWSG}$ implies commitments. Due to the properties needed for known
methods for efficient shadow tomography (requiring some norm bounds on
states), their argument could only go through for pure-state $\mathrm{OWSG}$s.

Unlike [HILL99] and [KT24], our proof does not go via measuring the output
state of the $\mathrm{OWSG}$ and works for mixed-state $\mathrm{OWSG}$s.
Following [HILL99], we wish to append $HH(X)$ to the combined input-output
state $XQ^{i}$ of an $m$-copy $\mathrm{OWSG}$ for some $i\in[m]$ (here $i$
represents the number of copies of the output state). Since Ver acts on an
additional copy of the output state, for the resultant state to remain one-
way, we want $HH(X)$ to be independent of $Q^{i+1}$ which means $|H(X)|$
should be around $S_{2}(X|Q^{i+1})$. However, we also need $|H(X)|$ to be
around $S_{2}(X|Q^{i})$ so that $Q^{i}HH(X)$ carries almost all the
information about $X$. To do this we find an $i^{*}\in[m]$ such that
$S_{2}(X|Q^{i^{*}})$ and $S_{2}(X|Q^{i^{*}+1})$ are at most $O(\log n)$ apart,
which we can do for $m\in O(\frac{n}{\log(n)})$. We cannot handle a larger
difference between $S_{2}(X|Q^{i^{*}})$ and $S_{2}(X|Q^{i^{*}+1})$ since this
difference has to be compensated by the hardcore function $g(\cdot)$ whose
output length is at most $O(\log n)$.

We extensively use properties of $\alpha$-Rényi entropies, which are
generalizations of Shannon and von Neumann entropies and are widely used in
information theory, especially for one-shot tasks. A crucial information-
theoretic tool that we use is the Chain-rule for Rényi entropies shown by
Dupuis [Dup15]. This however requires $XQ^{i^{*}}$ to be (largely) flat. A
state is called flat if all non-zero eigenvalues are the same. An important
property that we use in our proof is that $\alpha$-Rényi entropies of flat
states are the same for any $\alpha\in[0,\infty]$.

In [HILL99], the input $X$ was uniform and hence $Xf(X)$ was already a flat
distribution. In our case $XQ^{i^{*}}$ may not be automatically flat and we
need to do extra work to flatten it. We introduce a classical (non-uniformly
generated) register $J$ that we append to $XQ^{i^{*}}$ such that conditioned
on $J$, $XQ^{i^{*}}$ is (largely) flat. We then append another classical
register $B$ such that the combined state $XQ^{i^{*}}JB$ is (largely) flat. We
note that even though the construction of $J$ and $B$ is non-uniform, they are
required only during the analysis. In the final construction of the imbalanced
$\mathrm{EFI}$ pair, we trace out $J$ and $B$, and hence it is uniform. In
classical information theory, the idea of flattening a probability
distribution in an extended space, finds its origins for example in the well-
known correlated-sampling protocol [Hol07]. In quantum information theory, the
analogous idea of flattening a quantum state (via the so-called ”brothers”
extension) has been used for example in [AJM+16, AJ22, AFJ24].

We then append $g(X)$ to $XQ^{i^{*}}JB$ to obtain $\tau_{0}$ and append
$U_{|g(X)|}$ to $XQ^{i^{*}}JB$ to obtain $\tau_{1}$. We show that $\tau_{0}$
and $\tau_{1}$ are computationally indistinguishable and have $O(\log n)$
difference in their von Neumann entropies. At this point, both $\tau_{0}$ and
$\tau_{1}$ are non-uniformly generated. We use them to create a pair of states
$\rho_{0}$ and $\rho_{1}$ such that they are computationally indistinguishable
and have $1/\mathrm{poly}(n)$ difference in their von Neumann entropies. At
this point, $\rho_{0}$ is uniformly generated, however, $\rho_{1}$ is still
non-uniformly generated. We then take multiple copies of them to amplify their
entropy difference and apply a quantum extractor on them to get an imbalanced
$\mathrm{EFI}$ pair with one of the outputs being the maximally-mixed state.
We then use Fact 1 [KT24] that gives an $\mathrm{EFI}$ from an imbalanced
$\mathrm{EFI}$, thus completing our proof.

Note that our construction, when applied to the classical case, provides an
alternate to the construction provided by [HILL99] to obtain a classical
$\mathrm{PRG}$ from a classical $\mathrm{OWF}$. Since we do not argue
conditioned on the output $f(x)$, our construction and analysis is arguably
simpler and may be of independent interest.

### Organization

In Section 2 we introduce some information-theoretic and computation-theoretic
preliminaries, definitions, and facts that we will need later for our proofs.
In Section 3, we present our construction of an imbalanced $\mathrm{EFI}$ from
an $\mathrm{OWSG}$ and show the reverse direction in Section 4.

##  2 Preliminaries

In this section, we present some notation, definitions and facts that we will
need later for our proofs. For some of the facts, we provide proofs for
completeness (although the proofs for these may already exist in the
literature).

### Notation

  * •

$[n]$ represents the set $\\{1,2,\dots n\\}$.

  * •

For any $i\in\mathbb{N}$, $Q^{i}$ represents $Q_{1}Q_{2}\dots Q_{i}$.

  * •

$\mathbb{1}(\cdot)$ represents the indicator function.

  * •

For $t\in\mathbb{N}$, $U_{t}$ represents the uniform distribution on
$\\{0,1\\}^{t}$.

  * •

For a register $A$, we let $|A|$ represent the number of qubits in $A$.
Similarly, for a binary string $s$, we let $|s|$ represent the number of bits
in $s$.

  * •

$\lambda\in\mathbb{N}$ represents the security parameter and is provided in
unary ($1^{\lambda}$) to algorithms.

  * •

By a $\mathrm{QPT}$ algorithm we mean a quantum polynomial-time algorithm. By
a non-uniform $\mathrm{QPT}$ algorithm (or adversary), we mean a
$\mathrm{QPT}$ algorithm (or adversary) with a polynomial-size advice binary
string (in other words a quantum polynomial-size circuit).

  * •

If a set of registers (say $A,B,C$) are from the state $\rho$, we represent
them as

$ABC_{\rho}=\rho^{ABC}.$

  * •

For a cq-state (with $X$ classical)

$\rho^{XQ}=\sum_{x}\Pr(X=x)\cdot\ket{x}\\!\\!\bra{x}\otimes\rho^{Q}_{x},$

and a function $f(x)$, we define

$\rho^{XFQ}{\text{}:=}\sum_{x}\Pr(X=x)\cdot\ket{x}\\!\\!\bra{x}\otimes\ket{f(x)}\\!\\!\bra{f(x)}\otimes\rho^{Q}_{x}.$

  * •

$\log(x)$ denotes the binary logarithm of $x$ and $\exp(x)=2^{x}$.

#### Information-theoretic preliminaries

######  Definition 1 ($\ell_{1}$ distance).

For an operator $A$, the $\ell_{1}$ norm is defined as
$||A||_{1}{\text{}:=}\mathrm{Tr}\sqrt{A^{\dagger}A}$. For operators $A,B$,
their $\ell_{1}$ distance is defined as $\left\|A-B\right\|_{1}$. We use
shorthand $A\approx_{\varepsilon}B$ to denote
$\left\|A-B\right\|_{1}\leq\varepsilon$.

######  Definition 2 (Fidelity).

For (quantum) states $\rho,\sigma$,

$F(\rho,\sigma){\text{}:=}||\sqrt{\rho}\sqrt{\sigma}||_{1}.$

######  Definition 3 (Bures metric).

For states $\rho,\sigma$,

$\Delta_{B}(\rho,\sigma){\text{}:=}\sqrt{1-F(\rho,\sigma)}.$

######  Fact 2 ([FvdG99]).

For states $\rho,\sigma$,

$\Delta_{B}^{2}(\rho,\sigma)\leq\frac{\left\|\rho-\sigma\right\|_{1}}{2}\leq\sqrt{2}\Delta_{B}(\rho,\sigma).$

######  Definition 4.

For a state $\rho$, its von Neumann entropy is defined as

$S(\rho){\text{}:=}-\mathrm{Tr}(\rho\log\rho).$

######  Fact 3 (Chain-rule for entropy).

For a state $\rho_{AB}$,

$S(AB)_{\rho}=S(A)_{\rho}+S(B|A)_{\rho}.$

######  Fact 4.

For a cq-state $\rho^{XQ}$ (with $X$ classical),

$S(Q|X)_{\rho}\leq S(Q)_{\rho}\leq S(XQ)_{\rho}\leq S(Q)_{\rho}+|X|.$

###### Proof.

The first inequality follows from Fact 9. For the second inequality consider,

$\displaystyle S(XQ)_{\rho}$ $\displaystyle=S(Q)_{\rho}+S(X|Q)_{\rho}$ (Fact
3) $\displaystyle\geq S(Q)_{\rho}.$ (Fact 12)

The last inequality follows from Fact 3 and Fact 9. ∎

######  Definition 5 (Rényi entropy).

For a state $\rho$, the Rényi entropy of order $\alpha\in(0,1)\cup(1,\infty)$
is given as

$S_{\alpha}(\rho){\text{}:=}\frac{1}{1-\alpha}\log\mathrm{Tr}(\rho^{\alpha}).$

$S_{0},S_{1}$ and $S_{\infty}$ are defined as limits of $S_{\alpha}$ for
$\alpha\rightarrow\\{0,1,\infty\\}$. In particular, $\lim_{\alpha\rightarrow
1}S_{\alpha}(\rho)=S(\rho)$.

If $\\{p_{i}\\}_{i}$ are the eigenvalues of $\rho$, then the Rényi entropy
reduces to

$S_{\alpha}(\rho)=\frac{1}{1-\alpha}\log\left(\sum_{i}p_{i}^{\alpha}\right).$
(1)

######  Definition 6 (Conditional Rényi entropy).

For states $\rho$ and $\sigma$, the ”sandwiched” $\alpha$-Rényi divergence for
$\alpha\in(0,1)\cup(1,\infty)$ is given as

$D_{\alpha}(\rho||\sigma){\text{}:=}\frac{1}{\alpha-1}\log\left(\mathrm{Tr}\left[(\sigma^{\frac{1-\alpha}{2\alpha}}\rho\sigma^{\frac{1-\alpha}{2\alpha}})^{\alpha}\right]\right).$

The corresponding $\alpha$-conditional Rényi entropy is given by

$S_{\alpha}(A|B)_{\rho}{\text{}:=}-\min_{\sigma^{B}}D_{\alpha}(\rho^{AB}||\mathbb{1}^{A}\otimes\sigma^{B}).$

$D_{0},D_{1}$ and $D_{\infty}$ are defined as limits of $D_{\alpha}$ for
$\alpha\rightarrow\\{0,1,\infty\\}$.

######  Fact 5 ([Tom16]).

The sandwiched $\alpha$-Rényi divergence as $\alpha\rightarrow\infty$ becomes

$D_{\infty}(\rho||\sigma)=\min\\{\lambda:\rho\leq 2^{\lambda}\sigma\\}.$

######  Fact 6 (Data processing).

Let $\rho,\sigma$ be states and $\Phi$ be a CPTP map. Then,

$\Delta_{B}(\Phi(\rho),\Phi(\sigma))\leq\Delta_{B}(\rho,\sigma).$

The above also holds for the $\ell_{1}$ distance. For all
$\alpha\geq\frac{1}{2}$ [Tom16],

$D_{\alpha}(\Phi(\rho)||\Phi(\sigma))\leq D_{\alpha}(\rho||\sigma).$

######  Fact 7 ([KW24]).

For all $\alpha\in[\frac{1}{2},1)\cup(1,\infty)$ and states
$\rho_{1},\rho_{2},\sigma$,

$D_{\alpha}(\rho_{1}\otimes\sigma||\rho_{2}\otimes\sigma)=D_{\alpha}(\rho_{1}||\rho_{2}).$

######  Fact 8 (Monotonicity of Rényi entropy [Tom16]).

$\alpha$-Rényi entropy (and $\alpha$-conditional Rényi entropy) is
monotonically decreasing with increasing $\alpha$.

######  Fact 9 ([Tom16], eqs. (5.41) and (5.96)).

For a cq-state $\rho^{ABC}$ (with $C$ classical) and all
$\alpha\in[\frac{1}{2},\infty]$,

$S_{\alpha}(A|B)_{\rho}-|C|\leq S_{\alpha}(A|BC)_{\rho}\leq
S_{\alpha}(A|B)_{\rho}\leq|A|.$

Note: $C$ being classical is needed only for the first inequality.

######  Fact 10 ([Tom16]).

Let
$\rho^{XAB}=\sum_{x}p_{x}\cdot\ket{x}\\!\\!\bra{x}^{X}\otimes\rho^{AB}_{x}$ be
a cq-state. For all $\alpha\in(0,1)\cup(1,\infty)$,

$S_{\alpha}(A|BX)_{\rho}=\frac{\alpha}{1-\alpha}\log\left(\sum_{x}p_{x}\exp{\left(\frac{1-\alpha}{\alpha}S_{\alpha}(A|B)_{\rho_{x}}\right)}\right).$

######  Fact 11 ([BCR11] and [BJL23]).

For a state $\sigma_{AB}$,

$\sigma_{AB}\leq 2^{|B|}(\sigma_{A}\otimes\mathbb{1}_{B}).$

For a cq-state $\sigma_{XB}$ (with $X$ classical),

$\sigma_{XB}\leq\sigma_{X}\otimes\mathbb{1}_{B},$
$\sigma_{XB}\leq\mathbb{1}_{X}\otimes\sigma_{B}.$

######  Fact 12.

Let $\rho^{XQ}$ be a cq-state (with $X$ classical). Then
$S_{\alpha}(X|Q)_{\rho}\geq 0$ for $\alpha\in[0,\infty]$.

###### Proof.

Consider,

$\displaystyle S_{\alpha}(X|Q)_{\rho}$ $\displaystyle\geq
S_{\infty}(X|Q)_{\rho}$ (Fact 8)
$\displaystyle=-\min_{\sigma_{B}}D_{\infty}(\rho_{XQ}||\mathbb{1}_{X}\otimes\sigma_{Q})$
$\displaystyle\geq-D_{\infty}(\rho_{XQ}||\mathbb{1}_{X}\otimes\rho_{Q})$
$\displaystyle\geq 0.$ (Facts 5 and 11)

∎

######  Definition 7 (cq-Markov-chain).

We call a cq-state of the form
$\rho^{AXB}=\sum_{x}p_{x}\cdot\rho^{A}_{x}\otimes\ket{x}\\!\\!\bra{x}^{X}\otimes\rho^{B}_{x}$,
a cq-Markov-chain (with $X$ classical), denoted $(A-X-B)_{\rho}$.

The following is easy to see.

######  Fact 13.

Let $\rho^{AXB}$ be a cq-Markov-chain $(A-X-B)_{\rho}$. There exists a CPTP
recovery map $\Phi:X\rightarrow XB$ such that $\Phi(\rho^{AX})=\rho^{AXB}$.

######  Fact 14.

Let $\rho^{AXB}$ be a cq-Markov-chain $(A-X-B)_{\rho}$. Then,

$\rho^{AXB}\leq 2^{|X|}\cdot\rho^{A}\otimes\Phi(U_{|X|}),$

where $\Phi$ is the recovery CPTP map from Fact 13.

###### Proof.

From Fact 11

$\rho^{AX}\leq 2^{|X|}\cdot\rho^{A}\otimes U_{|X|}.$

From Fact 6 and Fact 13 we get,

$\rho^{AXB}=\Phi(\rho^{AX})\leq 2^{|X|}\cdot\rho^{A}\otimes\Phi(U_{|X|}).\qed$

######  Fact 15.

Let $\rho^{AXB}$ be a cq-Markov-chain $(A-X-B)_{\rho}$. Then,

$S(ABX)_{\rho}=S(X)_{\rho}+S(A|X)_{\rho}+S(B|X)_{\rho},$

Let $A=A_{1}A_{2}$. For all $\alpha\in[\frac{1}{2},1)\cup(1,\infty)$,

$S_{\alpha}(A_{1}|A_{2}X)_{\rho}=S_{\alpha}(A_{1}|A_{2}XB)_{\rho}.$

###### Proof.

Below all quantities are considered in $\rho$. For the first equality consider

$\displaystyle S(ABX)$ $\displaystyle=S(X)+S(AB|X)$ (Fact 3)
$\displaystyle=S(X)+S(A|X)+S(B|X).$ ($(A-X-B)_{\rho}$)

For the second equality consider,

$\displaystyle S_{\alpha}(A_{1}|A_{2})_{\rho_{x}}$ $\displaystyle\geq
S_{\alpha}(A_{1}|A_{2}B)_{\rho_{x}}$ (Fact 9)
$\displaystyle=-\min_{\sigma^{A_{2}B}}D_{\alpha}(\rho^{A_{1}A_{2}B}_{x}||\mathbb{1}^{A_{1}}\otimes\sigma^{A_{2}B})$
$\displaystyle=-\min_{\sigma^{A_{2}B}}D_{\alpha}(\rho^{A_{1}A_{2}}_{x}\otimes\rho^{B}_{x}||\mathbb{1}^{A_{1}}\otimes\sigma^{A_{2}B})$
($(A_{1}A_{2}-X-B)_{\rho}$)
$\displaystyle\geq-\min_{\sigma^{A_{2}}}D_{\alpha}(\rho^{A_{1}A_{2}}_{x}\otimes\rho^{B}_{x}||\mathbb{1}^{A_{1}}\otimes\sigma^{A_{2}}\otimes\rho^{B}_{x})$
$\displaystyle=-\min_{\sigma^{A_{2}}}D_{\alpha}(\rho^{A_{1}A_{2}}_{x}||\mathbb{1}^{A_{1}}\otimes\sigma^{A_{2}})$
(Fact 7) $\displaystyle=S_{\alpha}(A_{1}|A_{2})_{\rho_{x}}.$

This along with Fact 10 gives

$\displaystyle S_{\alpha}(A_{1}|A_{2}XB)_{\rho}$
$\displaystyle=\frac{\alpha}{1-\alpha}\log\left(\sum_{x}p(x)\exp\left(\frac{1-\alpha}{\alpha}S_{\alpha}(A_{1}|A_{2}B)_{\rho_{x}}\right)\right)$
$\displaystyle=\frac{\alpha}{1-\alpha}\log\left(\sum_{x}p(x)\exp\left(\frac{1-\alpha}{\alpha}S_{\alpha}(A_{1}|A_{2})_{\rho_{x}}\right)\right)$
$\displaystyle=S_{\alpha}(A_{1}|A_{2}X)_{\rho}.\qed$

######  Definition 8 (Flat state).

A distribution $P$ is said to be flat if all non-zero probabilities are the
same. A quantum state $\rho$ is said to be flat if the probability
distribution formed by its eigenvalues is flat. From Definition 5, we see that
for a flat state $\rho$ and any $\alpha,\beta\in[0,\infty]$,
$S_{\alpha}(\rho)=S_{\beta}(\rho)$.

######  Definition 9 ($2$-flat state).

Let $p_{max}$ and $p_{min}$ be the maximum and minimum non-zero probability
values of the distribution $P$. $P$ is said to be a $2$-flat distribution if

$\frac{p_{max}}{p_{min}}\leq 2.$

A quantum state $\rho$ is said to be $2$-flat if the probability distribution
formed by its eigenvalues is $2$-flat. From Definition 5, we see that for a
state $\rho$,

$S_{\infty}(\rho)=\log\left(\frac{1}{p_{max}}\right)\text{ and
}S_{0}(\rho)\leq\log\left(\frac{1}{p_{min}}\right).$

From Fact 8, we see that for a $2$-flat state $\rho$, for all
$\alpha,\beta\in[0,\infty],$

$|S_{\alpha}(\rho)-S_{\beta}(\rho)|\leq
S_{0}(\rho)-S_{\infty}(\rho)\leq\log\left(\frac{p_{max}}{p_{min}}\right)\leq
1.$ (2)

######  Fact 16 (Chain-rule for sandwiched Rényi entropies [Dup15]).

Let $\alpha,\beta,\gamma\in(0,1)\cup(1,\infty)$ be such that
$\frac{\alpha}{\alpha-1}=\frac{\beta}{\beta-1}+\frac{\gamma}{\gamma-1}$ and
$(\alpha-1)(\beta-1)(\gamma-1)<1$. For a state $\rho$,

$S_{\alpha}(AB|C)_{\rho}\leq S_{\beta}(A|BC)_{\rho}+S_{\gamma}(B|C)_{\rho}.$

######  Fact 17 (Fannes’ inequality [NC10]).

For states $\rho$ and $\sigma$,

$|S(\rho)-S(\sigma)|\leq\log(d)\left\|\rho-\sigma\right\|_{1}+\frac{1}{e}.$

Here $d$ is the dimension of the Hilbert space of $\rho$ (and $\sigma$).

######  Fact 18 (Extractor [Ren06]).

Let $X\in\\{0,1\\}^{n}$ and

$\tau^{XQ}=\sum_{x}\Pr(X=x)\cdot\ket{x}\\!\\!\bra{x}^{X}\otimes\tau^{Q}_{x},$

be a cq-state. Let $l=S_{2}(X|Q)_{\tau}$ and $s=O(n)$. There exists extractor

$\mathsf{Ext}:\\{0,1\\}^{n}\times\\{0,1\\}^{s}\rightarrow\\{0,1\\}^{l},$

such that for all $l^{\prime}\leq l$,

$QHH^{l^{\prime}}(X)_{\tau}\approx_{2^{-(l-l^{\prime})/2}}Q_{\tau}\otimes
U_{s}\otimes U_{l^{\prime}}$

where

$\tau^{XHH(X)Q}=\sum_{x,h}\Pr(X=x)\cdot
2^{-s}\cdot\ket{x,h,\mathsf{Ext}(x,h)}\\!\\!\bra{x,h,\mathsf{Ext}(x,h)}\otimes\tau^{Q}_{x},$

and $H^{l^{\prime}}(X)$ represents the $l^{\prime}$-bit prefix of $H(X)$.

######  Fact 19 (Uhlmann’s Theorem [Uhl76]).

Let $\rho_{A},\sigma_{A}$ be states. Let $\rho_{AB}$ be a purification of
$\rho_{A}$ and $\sigma_{AC}$ be a purification of $\sigma_{A}$. There exists
an isometry $V$ such that,

$\Delta_{B}(\ket{\rho}\\!\\!\bra{\rho}_{AB},\ket{\theta}\\!\\!\bra{\theta}_{AB})=\Delta_{B}(\rho_{A},\sigma_{A}),$

where $\ket{\theta}_{AB}=(\mathbb{1}_{A}\otimes V)\ket{\sigma}_{AC}$.

######  Fact 20 (Distance preserving extension).

Let $\rho_{AB},\sigma_{A}$ be states. There exists an extension $\theta_{AB}$
of $\sigma_{A}$, that is $\mathrm{Tr}_{B}\theta_{AB}=\sigma_{A}$, such that,

$\Delta_{B}(\rho_{AB},\theta_{AB})=\Delta_{B}(\rho_{A},\sigma_{A}).$

###### Proof.

Let $\rho_{ABR}$ be a purification of $\rho_{AB}$. Let $\sigma_{AC}$ be a
purification of $\sigma_{A}$. From Uhlmann’s Theorem (Fact 19), there exists
an isometry $V$ such that $\ket{\theta}_{ABR}=(\mathbb{1}_{A}\otimes
V)\ket{\sigma}_{AC}$ and

$\Delta_{B}(\rho_{ABR},\theta_{ABR})=\Delta_{B}(\rho_{A},\sigma_{A}).$

From the data-processing inequality (Fact 6), we get

$\Delta_{B}(\rho_{A},\theta_{A})\leq\Delta_{B}(\rho_{AB},\theta_{AB})\leq\Delta_{B}(\rho_{ABR},\theta_{ABR})=\Delta_{B}(\rho_{A},\sigma_{A}).$

This shows the desired by noting that $\theta_{A}=\sigma_{A}$. ∎

######  Fact 21 ([TH13]).

For a state $\rho$ on $n$-qubits,

$S_{0}^{\varepsilon}(\rho^{\otimes t})\leq t\cdot
S(\rho)+O(\sqrt{tn})\Phi^{-1}(\varepsilon)+O(\log(n)).$
$S_{\infty}^{\varepsilon}({\rho}^{\otimes t})\geq t\cdot
S({\rho})-O(\sqrt{tn})\Phi^{-1}(\varepsilon)+O(\log(n)).$

Here $\Phi(x)=\int_{-\infty}^{x}\frac{e^{-t^{2}/2}}{\sqrt{2\pi}}dt.$

######  Fact 22 ([AHJ20]).

For the function
$\Phi(x)=\int_{-\infty}^{x}\frac{e^{-t^{2}/2}}{\sqrt{2\pi}}dt$, and
$\varepsilon\leq\frac{1}{2}$,

$|\Phi^{-1}(\varepsilon)|\leq\sqrt{2\log\frac{1}{2\varepsilon}}.$

######  Fact 23 (Quantum extractor [AJ22], Theorem 2).

Let $\psi_{R}$ be a state on $n$-qubits, $\varepsilon>0$ and
$s=4n-S_{\infty}^{\varepsilon}(\psi_{R})+O(\log\left(\frac{1}{\varepsilon}\right))$.
There exists a unitary $G$ such that (below $S$ represents a register on
$s-3n$ qubits),

$\left\|\mathrm{Tr}_{S}G(\psi_{R}\otimes\ket{0}\\!\\!\bra{0}\otimes
U_{s})G^{\dagger}-U_{4n+1}\right\|_{1}\leq\varepsilon.$

This gives a quantum extractor with seed length $s$ and output length $4n+1$:

$\mathsf{Ext}_{Q}(\psi_{R},U_{s})=\mathrm{Tr}_{S}G(\psi_{R}\otimes\ket{0}\\!\\!\bra{0}\otimes
U_{s})G^{\dagger}.$

In addition, for any $\delta>0$,

$S_{0}^{\delta}(\mathsf{Ext}_{Q}(\psi_{R},U_{s}))\leq
S^{\delta}_{0}(\psi_{R})+s.$

#### Computation-theoretic preliminaries

######  Definition 10 ($\mathsf{negl}$ function).

We call a function $\mu:\mathbb{N}\rightarrow\mathbb{R}^{+}$ negligible if for
every positive polynomial $p(\cdot)$, there exists an $N\in\mathbb{N}$ such
that for all $\lambda>N$, $\mu(\lambda)<\frac{1}{p(\lambda)}$. We let
$\mu(\lambda)=\mathsf{negl}(\lambda)$ represent that $\mu(\lambda)$ is a
negligible function in $\lambda$.

######  Definition 11 (noticeable function).

We call a function $\mu:\mathbb{N}\rightarrow\mathbb{R}^{+}$ noticeable if
there exists a positive polynomial $p(\cdot)$ and an $N\in\mathbb{N}$ such
that for all $\lambda>N$, $\mu(\lambda)>\frac{1}{p(\lambda)}$.

######  Definition 12 ($\mathrm{poly}$).

We let $\mathrm{poly}(\lambda)$ denote the class of all positive polynomials
in $\lambda$.

######  Definition 13 (Computationally indistinguishable).

We say two ensemble of states
$\\{\rho_{\lambda},\sigma_{\lambda}\\}_{\lambda\in\mathbb{N}}$ are
computationally indistinguishable, denoted as
$\rho\approx_{\mathsf{negl}_{C}}\sigma$, if for every non-uniform
$\mathrm{QPT}$ adversary $A$,

$\Big{|}\Pr[A(1^{\lambda},\rho_{\lambda})=1]-\Pr[A(1^{\lambda},\sigma_{\lambda})=1]\Big{|}=\mathsf{negl}(\lambda).$

Morimae and Yamakawa [MY22a] have defined a quantum one-way state generator.
We use the following definition which differs from theirs in two points. The
algorithm Ver and the adversary A in their definition are $\mathrm{QPT}$
algorithms, whereas in our definition Ver is an unbounded algorithm and
adversary A is a non-uniform $\mathrm{QPT}$ algorithm.

######  Definition 14 (Quantum one-way state generator).

An $m$-copy quantum one-way state generator ($\mathrm{OWSG}$) is a set of
algorithms:

  1. 1.

$\textsc{KeyGen}(1^{\lambda})\rightarrow x$: It is a $\mathrm{QPT}$ algorithm
that on input the security parameter, outputs a classical key
$x\in\\{0,1\\}^{n}$.

  2. 2.

$\textsc{StateGen}(1^{\lambda},x)\rightarrow\phi_{x}$: It is a $\mathrm{QPT}$
algorithm that takes as input the security parameter and $x\in\\{0,1\\}^{n}$
and outputs a quantum state $\phi_{x}$. In other words,
$\textsc{StateGen}(1^{\lambda},x)=\phi_{x}$ .

  3. 3.

$\textsc{Ver}(x^{\prime},\phi_{x})\rightarrow\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}/\bot:$
It is an algorithm that on input a string $x^{\prime}$ and $\phi_{x}$ gives as
output $\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}$
or $\bot$.

We require the following correctness and security conditions to hold.

Correctness:

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(x,\phi_{x}):x\leftarrow\textsc{KeyGen}(1^{\lambda}),\phi_{x}\leftarrow\textsc{StateGen}(1^{\lambda},x)]\geq
1-\mathsf{negl}(\lambda).$

Security:

For any non-uniform $\mathrm{QPT}$ adversary $A$ (with running time in
$\mathrm{poly}(\lambda)$),

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(x^{\prime},\phi_{x}):x\leftarrow\textsc{KeyGen}(1^{\lambda}),\phi_{x}\leftarrow\textsc{StateGen}(1^{\lambda},x),x^{\prime}\leftarrow
A(1^{\lambda},\phi_{x}^{\otimes m})]=\mathsf{negl}(\lambda).$

We call the state

$\tau^{XQ^{m}}=\sum_{x\in\\{0,1\\}^{n}}\Pr(X=x)_{\tau}\cdot\ket{x}\\!\\!\bra{x}\otimes\phi_{x}^{\otimes
m},$ (3)

an $m$-copy one-way state and the function $x\rightarrow\phi_{x}^{\otimes m}$
an $m$-copy quantum one-way function. For a non-uniform $\mathrm{QPT}$
adversary $A$, security implies that $\forall i\in[m]$,

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A(1^{\lambda},\tau^{Q^{i}}),\tau^{Q_{i+1}})]=\mathsf{negl}(\lambda).$

######  Definition 15 (EFI [BCQ23]).

An $\mathrm{EFI}$ is a $\mathrm{QPT}$ algorithm
$\textsc{StateGen}(b,1^{\lambda})\rightarrow\rho_{b}$ that, on input
$b\in\\{0,1\\}$ and the security parameter $\lambda$, outputs a quantum state
$\rho_{b}$ such that the following conditions are satisfied.

  1. 1.

$\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$.

  2. 2.

$\rho_{0}$ and $\rho_{1}$ are statistically distinguishable with noticeable
advantage. In other words, $\frac{1}{2}\left\|\rho_{0}-\rho_{1}\right\|_{1}$
is a noticeable function in $\lambda$.

We call $(\rho_{0},\rho_{1})$ an $\mathrm{EFI}$ pair.

######  Fact 24 ([MY22b]).

$\mathrm{EFI}$ with noticeable advantage in statistical distinguishability are
equivalent to $\mathrm{EFI}$ with $1-\mathsf{negl}(\lambda)$ advantage.

######  Definition 16 ($s^{*}$-imbalanced EFI [KT24]).

Let $s^{*}(\lambda):\mathbb{N}\rightarrow\mathbb{N}$ be a function. An
$s^{*}$-imbalanced $\mathrm{EFI}$ is a $\mathrm{QPT}$ algorithm
EFI${}_{s}(1^{\lambda},b)\rightarrow\rho_{b}(s)$ that obtains advice string
$s$ and, on input $b\in\\{0,1\\}$ and security parameter $\lambda$, outputs a
state $\rho_{b}(s)$ such that:

  1. 1.

For all $s\leq s^{*}(\lambda)$:
$\rho_{0}(s)\approx_{\mathsf{negl}_{C}}\rho_{1}(s)$.

  2. 2.

For all $s\geq s^{*}(\lambda)$: $\rho_{0}(s)$ and $\rho_{1}(s)$ are
statistically distinguishable with noticeable advantage. That is
$\frac{1}{2}\left\|\rho_{0}(s)-\rho_{1}(s)\right\|_{1}$ is a noticeable
function in $\lambda$.

######  Fact 25 ([KT24]).

Let $s^{*}(\lambda)\in\mathrm{poly}(\lambda)$. Then $s^{*}$-imbalanced
$\mathrm{EFI}$ imply quantum commitments.

######  Fact 26 ([BCQ23]).

Quantum commitments are equivalent to $\mathrm{EFI}$.

######  Fact 27 ([Gol01]).

Let $f$ be a classical one-way function. Define $h(x,r)=(f(x),r)$ where
$x\in\\{0,1\\}^{n}$ and $r\in\\{0,1\\}^{2n}$. For any constant $c>0$, there
exists an efficiently computable hardcore function $g(x,r)$, with
$|g(x,r)|=c\log(n)$, such that $g(x,r)$ is a hardcore function of $h$. In
other words,

$f(U_{n})R~{}g(U_{n},R)\approx_{\mathsf{negl}_{C}}f(U_{n})\otimes
U_{2n}\otimes U_{c\log(n)}.$

######  Fact 28 (Quantum hardcore function).

Let $X\in\\{0,1\\}^{n},m\in\mathrm{poly}(n)$ and $\tau^{XQ^{m}}$ be an
$m$-copy one-way state (see Definition 14). For any constant $c>0$, there
exists an efficiently computable hardcore function $g(x,r)$ for $|r|=2n$ and
$|g(x,r)|=c\log(n)$ such that

$Q^{m}R~{}g(X,R)_{\tau}\approx_{\mathsf{negl}_{C}}Q^{m}_{\tau}\otimes
U_{2n}\otimes U_{c\log(n)}.$

###### Proof.

(Sketch) The proof of Fact 27 reduces to the existence of hardcore predicates
for classical one-way functions. Goldreich-Levin with quantum advice ([AC02])
gives the existence of hardcore predicate for quantum one-way functions also
and hence, the proof of this claim follows along similar lines as Fact 27. ∎

######  Fact 29.

Let $\rho_{0}$ and $\rho_{1}$ be states generatable by a non-uniform
$\mathrm{QPT}$ algorithm. If $\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$,
then $\rho_{0}^{\otimes t}\approx_{\mathsf{negl}_{C}}\rho_{1}^{\otimes t}$ for
any $t\in\mathrm{poly}(\lambda)$ where $\lambda$ is the security parameter.

###### Proof.

This follows using a standard hybrid argument. Assume for contradiction that
there exists a non-uniform $\mathrm{QPT}$ adversary $A$ such that for
infinitely many $\lambda$ and a positive polynomial $p(\cdot)$,

$\Big{|}\Pr[A(1^{\lambda},\rho_{0}^{\otimes
t})=1]-\Pr[A(1^{\lambda},\rho_{1}^{\otimes
t})=1]\Big{|}\geq\frac{1}{p(\lambda)}.$

We define a series of hybrids $H_{0},H_{1}\dots H_{t}$ where
$H_{i}=\rho_{0}^{\otimes t-i}\otimes\rho_{1}^{\otimes i}$. Then

$\displaystyle\frac{1}{p(\lambda)}$
$\displaystyle\leq\Big{|}\Pr[A(1^{\lambda},\rho_{0}^{\otimes
t})=1]-\Pr[A(1^{\lambda},\rho_{1}^{\otimes t})=1]\Big{|}$
$\displaystyle=\Big{|}\Pr[A(1^{\lambda},H_{0})=1]-\Pr[A(1^{\lambda},H_{t})=1]\Big{|}$
$\displaystyle\leq\sum_{i\in[t]}\Big{|}\Pr[A(1^{\lambda},H_{i-1})=1]-\Pr[A(1^{\lambda},H_{i})=1]\Big{|}.$
(By triangle-inequality)

Thus, there exists a $j\in[t]$ for which

$\Big{|}\Pr[A(1^{\lambda},H_{j-1})=1]-\Pr[A(1^{\lambda},H_{j})=1]\Big{|}\geq\frac{1}{p(\lambda)\cdot
t}\geq\frac{1}{q(\lambda)},$ (4)

for some positive polynomial $q(\cdot)$ because $t\in\mathrm{poly}(\lambda)$.

Using non-uniform $\mathrm{QPT}$ adversary $A$, we now create a non-uniform
adversary $A^{\prime}$ to distinguish between $\rho_{0}$ and $\rho_{1}$ as
follows:

$A^{\prime}(1^{\lambda},\rho_{c})$:

  * •

$A^{\prime}$ takes as input a state $\rho_{c}$ for $c\in\\{0,1\\}$ along with
the security parameter $\lambda$.

  * •

$A^{\prime}$ takes as (non-uniform) advice $j\in[t]$.

  * •

$A^{\prime}$ returns $A(1^{\lambda},\rho_{0}^{\otimes
t-j}\otimes\rho_{c}\otimes\rho_{1}^{\otimes j-1})$.

Since $\rho_{0}$ and $\rho_{1}$ are generatable by non-uniform $\mathrm{QPT}$
algorithms, adversary $A^{\prime}$ is also non-uniform $\mathrm{QPT}$. From
eq. 4, we get that for infinitely many $\lambda$

$\Big{|}\Pr[A^{\prime}(1^{\lambda},\rho_{0})=1]-\Pr[A^{\prime}(1^{\lambda},\rho_{1})=1]\Big{|}=\Big{|}\Pr[A(1^{\lambda},H_{j-1})=1]-\Pr[A(1^{\lambda},H_{j})=1]\Big{|}\geq\frac{1}{q(\lambda)}.$

This contradicts the fact that $\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$.
Hence, the desired statement follows. ∎

######  Fact 30.

Let $\sigma$ be a state generatable by a non-uniform $\mathrm{QPT}$ algorithm.
Let $\rho_{0}$ and $\rho_{1}$ be states such that
$\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$. Let

$\kappa_{0}=p\sigma+(1-p)\rho_{0}~{},~{}\kappa_{1}=p\sigma+(1-p)\rho_{1}.$

For any $p\in[0,1]$, $\kappa_{0}\approx_{\mathsf{negl}_{C}}\kappa_{1}.$

###### Proof.

Assume for contradiction that there exists a non-uniform $\mathrm{QPT}$
adversary $A$ such that for infinitely many $\lambda$ and a positive
polynomial $q(\cdot)$,

$\Big{|}\Pr[A(1^{\lambda},\kappa_{0})=1]-\Pr[A(1^{\lambda},\kappa_{1})=1]\Big{|}\geq\frac{1}{q(\lambda)}.$
(5)

We now create a non-uniform adversary $A^{\prime}$ as follows:

$A^{\prime}(1^{\lambda},\rho_{c})$:

  * •

$A^{\prime}$ takes as input a state $\rho_{c}$ for $c\in\\{0,1\\}$ along with
the security parameter $\lambda$.

  * •

$A^{\prime}$ receives (non-uniform) advice $p$ in the form of its binary
encoding in polynomially many bits (in $\lambda$)111The exponentially small
error in the specification of $p$ can be easily incorporated in the proof,
however, we do not do that explicitly for the ease of presentation..

  * •

$A^{\prime}$ creates the state $\tau=p\sigma+(1-p)\rho_{c}$ and returns
$A(1^{\lambda},\tau)$222This is equivalent to creating the state $\sigma$ in
another register, tossing a $p$-biased coin and outputting
$A(1^{\lambda},\sigma)$ or $A(1^{\lambda},\rho_{c})$ depending on the outcome
of the coin..

Since $\sigma$ is generatable by non-uniform $\mathrm{QPT}$ algorithm,
adversary $A^{\prime}$ is also non-uniform $\mathrm{QPT}$. From eq. 5, we get
that for infinitely many $\lambda$

$\Big{|}\Pr[A^{\prime}(1^{\lambda},\rho_{0})=1]-\Pr[A^{\prime}(1^{\lambda},\rho_{1})=1]\Big{|}=\Big{|}\Pr[A(1^{\lambda},\kappa_{0})=1]-\Pr[A(1^{\lambda},\kappa_{1})=1]\Big{|}\geq\frac{1}{q(\lambda)}.$

This contradicts the fact that $\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$.
Hence, the desired statement follows. ∎

######  Fact 31.

Let $\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$ and $B$ be a non-uniform
$\mathrm{QPT}$ algorithm. Then
$B(\rho_{0})\approx_{\mathsf{negl}_{C}}B(\rho_{1})$.

###### Proof.

Assume for contradiction that there exists a non-uniform $\mathrm{QPT}$
algorithm $A$ and a positive polynomial $p(\cdot)$ such that for infinitely
many $\lambda$,

$\Big{|}\Pr[A(1^{\lambda},B(\rho_{0}))=1]-\Pr[A(1^{\lambda},B(\rho_{1}))=1]\Big{|}\geq\frac{1}{p(\lambda)}.$

We now create a non-uniform adversary $A^{\prime}$ to distinguish between
$\rho_{0}$ and $\rho_{1}$ as follows:

  * •

$A^{\prime}$ takes as input the security parameter $\lambda$ and state
$\rho_{b}$ (for $b\in\\{0,1\\}$).

  * •

$A^{\prime}$ returns $A(1^{\lambda},B(\rho_{b}))$.

Consider,

$\displaystyle\Big{|}\Pr[A^{\prime}(1^{\lambda},\rho_{0})=1]-\Pr[A^{\prime}(1^{\lambda},\rho_{1})=1]\Big{|}$
$\displaystyle=\Big{|}\Pr[A(1^{\lambda},B(\rho_{0}))=1]-\Pr[A(1^{\lambda},B(\rho_{1}))=1]\Big{|}$
$\displaystyle\geq\frac{1}{p(\lambda)}.$

This is a contradiction. ∎

##  3 An $\mathrm{OWSG}$ implies an $\mathrm{EFI}$

######  Theorem 7.

Let $m=\frac{cn}{\log(n)}$ for some constant $c>0$ where $n$ is the key-length
of the $\mathrm{OWSG}$. An $m$-copy $\mathrm{OWSG}$ (see Definition 14)
implies a $k^{*}$-imbalanced $\mathrm{EFI}$ (see Definition 16) for some
$k^{*}(\lambda)\in\mathrm{poly}(\lambda)$.

###### Proof.

Let $c^{\prime}=\frac{1}{c}$. Let $\mathsf{Ext}$ be the extractor from Fact 18
and $\mathsf{Ext}_{Q}$ be the quantum extractor from Fact 23. Let $i^{*}$ be
from Claim 1 and the total number of qubits in $\tau^{XQ^{i^{*}}}$ be at most
$n^{c^{\prime\prime}}$ for some constant $c^{\prime\prime}>0$. Let $g(\cdot)$
be the quantum hardcore function from Fact 28 with output size
$(30+4c^{\prime\prime}+c^{\prime})\log(n)$. Let $l_{i^{*}}$ be from Claim 5
and $\tau_{1}(i^{*},l_{i^{*}})$ be from Claim 8.

EFI${}_{k}(1^{\lambda},b)$: 1. The algorithm takes as input the security
parameter $\lambda$ and a bit $b$. 2. It also has access to an $m$-copy
$\mathrm{OWSG}$ with key-length $n$ that generates the one-way state
$\tau^{XQ^{m}}$. 3. For all $i\in[m],l\in[n]$ define,
${\tau_{0}(i,l)}{\text{}:=}Q^{i}HH^{l}(X)Rg(X,R)_{\tau}.$
$\rho_{0}(\tau){\text{}:=}\sum_{i=1}^{m}\sum_{l=1}^{n}\frac{1}{mn}\ket{i,l}\\!\\!\bra{i,l}\otimes{\tau_{0}(i,l)}.$
4. Let $n_{0}\in\mathrm{poly}(\lambda)$ be the number of qubits in
$\rho_{0}(\tau)$ and
$t_{0}=\max(n,\lambda),~{}t=t_{0}^{7},~{}s_{Q}(k)=4n_{0}t-k+O(\log(t_{0})).$
5. If $b=0$, output $\mathsf{Ext}_{Q}(\rho_{0}(\tau)^{\otimes
t},U_{s_{Q}(k)}).$ 6. If $b=1$, output $U_{4n_{0}t+1}$.

Figure 1: $k^{*}$-imbalanced $\mathrm{EFI}$

The $k^{*}$-imbalanced $\mathrm{EFI}$ is given in Figure 1 where $k^{*}$ is
defined as follows. Define,

$\rho_{1}(\tau){\text{}:=}\sum_{j=1}^{m}\sum_{l=1}^{n}\mathbb{1}(j\neq
i^{*}\text{ or }l\neq
l_{i^{*}})\cdot\frac{1}{mn}\ket{j,l}\\!\\!\bra{j,l}\otimes\tau_{0}(j,l)+\frac{1}{mn}\ket{i^{*},l_{i^{*}}}\\!\\!\bra{{i^{*}},l_{i^{*}}}\otimes\tau_{1}(i^{*},l_{i^{*}}),$
$t_{0}{\text{}:=}\max(n,\lambda),~{}t{\text{}:=}t_{0}^{7},~{}k^{*}(\lambda){\text{}:=}S_{\infty}^{\varepsilon}({\rho}_{1}(\tau)^{\otimes
t}).$

From Claim 8, since
$\tau_{0}({i^{*}},l_{i^{*}})\approx_{\mathsf{negl}_{C}}\tau_{1}({i^{*}},l_{i^{*}})$,
we get $\rho_{0}(\tau)\approx_{\mathsf{negl}_{C}}\rho_{1}(\tau)$ (Fact 30).
Consider,

$\displaystyle S(\rho_{1}(\tau))-S(\rho_{0}(\tau))$
$\displaystyle=\frac{1}{mn}\left[S(\tau_{1}({i^{*}},l_{i^{*}}))-S(\tau_{0}({i^{*}},l_{i^{*}}))\right]$
(Fact 3) $\displaystyle\geq\frac{(8\log(n)-5)}{n^{2}}.$ (Claim 8) (6)

Using Fact 21 and Fact 22 and setting $\varepsilon=2^{-\log^{2}(\lambda)}$, we
get

$S_{0}^{\varepsilon}(\rho_{0}(\tau)^{\otimes t})\leq t\cdot
S(\rho_{0}(\tau))+O(\sqrt{tn})\log(\lambda),$
$S_{\infty}^{\varepsilon}({\rho}_{1}(\tau)^{\otimes t})\geq t\cdot
S({\rho}_{1}(\tau))-O(\sqrt{tn})\log(\lambda).$

Since $t_{0}=\max(n,\lambda)$ and $t=t_{0}^{7}$, we get

$S_{\infty}^{\varepsilon}({\rho}_{1}(\tau)^{\otimes
t})-S_{0}^{\varepsilon}(\rho_{0}(\tau)^{\otimes t})\geq
t_{0}^{5}\cdot(8\log(n)-5)-O(t_{0}^{4}\log(t_{0}))\geq t_{0}^{5}.$ (7)

Note that

$\displaystyle k^{*}(\lambda)$
$\displaystyle=S_{\infty}^{\varepsilon}({\rho}_{1}(\tau)^{\otimes t})$
$\displaystyle\leq n_{0}t\in\mathrm{poly}(\lambda).$ (Fact 9)

Define,

$\sigma_{0}(k,\tau){\text{}:=}\mathsf{Ext}_{Q}(\rho_{0}(\tau)^{\otimes
t},U_{s_{Q}(k)}),$
$\sigma_{1}(k,\tau){\text{}:=}\mathsf{Ext}_{Q}(\rho_{1}(\tau)^{\otimes
t},U_{s_{Q}(k)}).$

  1. 1.

When $k\leq k^{*}(\lambda)$:

From Fact 23, we see that if $k\leq k^{*}(\lambda)$, we get

$\sigma_{1}(k,\tau)=\mathsf{Ext}_{Q}({\rho}_{1}(\tau)^{\otimes
t},U_{s_{Q}(k)})\approx_{\mathsf{negl}(\lambda)}U_{4n_{0}t+1}.$ (8)

Since $\rho_{0}(\tau)\approx_{\mathsf{negl}_{C}}\rho_{1}(\tau)$, Fact 29, Fact
31 and eq. 8 gives us
$\sigma_{0}(k,\tau)\approx_{\mathsf{negl}_{C}}U_{4n_{0}t+1}$ for all $k\leq
k^{*}(\lambda)$.

  2. 2.

When $k\geq k^{*}(\lambda)$:

From eq. 7, $S_{0}^{\varepsilon}(\rho_{0}(\tau)^{\otimes t})\leq
k^{*}(\lambda)-t_{0}^{5}$. Using Fact 23, we get

$S_{0}^{\varepsilon}(\sigma_{0}(k,\tau))\leq
k^{*}(\lambda)+4n_{0}t-k+O(\log(t_{0}))-t_{0}^{5}\leq
4n_{0}t-t_{0}^{5}+O(\log(t_{0})).$

Thus, we get

$\left\|\sigma_{0}(k,\tau)-U_{4n_{0}t+1}\right\|_{1}\geq
1-\mathsf{negl}(\lambda).$

We see that for $k\leq k^{*}(\lambda)$, we get computational
indistinguishability of $\sigma_{0}(k,\tau)$ and $U_{4n_{0}t+1}$ and for
$k\geq k^{*}(\lambda)$, we get statistical difference between
$\sigma_{0}(k,\tau)$ and $U_{4n_{0}t+1}$. Thus, we get a $k^{*}$-imbalanced
$\mathrm{EFI}$ where EFI${}_{k}(1^{\lambda},0)=\sigma_{0}(k,\tau)$ and
EFI${}_{k}(1^{\lambda},1)=U_{4n_{0}t+1}$. ∎

######  Claim 1.

There exists an $i^{*}\in[m]$ such that

$S_{2}(X|Q^{i^{*}})_{\tau}-S_{2}(X|Q^{{i^{*}}+1})_{\tau}\leq
c^{\prime}\log(n).$

###### Proof.

Consider,

$\displaystyle\sum_{i=0}^{m-1}\left(S_{2}(X|Q^{i})_{\tau}-S_{2}(X|Q^{i+1})_{\tau}\right)$
$\displaystyle=S_{2}(X)_{\tau}-S_{2}(X|Q^{m})_{\tau}$ $\displaystyle\leq
S_{2}(X)_{\tau}$ (Fact 12) $\displaystyle\leq n.$ (Fact 9)

Since $m=cn/\log(n)$, there exists $i^{*}\in[m]$ such that

$S_{2}(X|Q^{i^{*}})_{\tau}-S_{2}(X|Q^{i^{*}+1})_{\tau}\leq\frac{\log(n)}{c}=c^{\prime}\log(n).\qed$

#### Flattening using ”Brothers” extension

Consider the spectral decomposition of the state $\tau^{XQ^{i^{*}}}$.

$XQ^{i^{*}}_{\tau}=\sum_{k}p_{k}\ket{e_{k}}\\!\\!\bra{e_{k}}^{XQ^{i^{*}}}.$
(9)

We append a classical register $J$ to $XQ^{i^{*}}_{\tau}$ as follows:

$\displaystyle XQ^{i^{*}}J_{\tau}$
$\displaystyle=\sum_{k}p_{k}\ket{e_{k}}\\!\\!\bra{e_{k}}^{XQ^{i^{*}}}\otimes\ket{j_{k}}\\!\\!\bra{j_{k}}^{J},$
(10)

where $j_{k}=r$ if $p_{k}\in\Big{(}\frac{1}{2^{r}},\frac{1}{2^{r-1}}\Big{]}$
for $r\in[n^{5+c^{\prime\prime}}]$ and $j_{k}=0$ otherwise. Here
$|J|\leq(5+c^{\prime\prime})\log(n)+1$. Let
$\gamma=2^{-n^{5+c^{\prime\prime}}}$. We now append another classical register
$B$ (for brothers) as follows where $|B|\leq n^{5+c^{\prime\prime}}$:

  * •

For $j_{k}\neq 0$, $B=U_{n^{5+c^{\prime\prime}}-j_{k}}.$

  * •

For $j_{k}=0$, we do the following. Let $\Pr(J=0)_{\tau}=q_{0}$.

    * –

If $q_{0}\geq{\gamma}$, we set
$B=U_{\lfloor\log(\frac{q_{0}}{\gamma})\rfloor}$.

    * –

Otherwise we just make 1 brother. That is, $B=\ket{0}\\!\\!\bra{0}.$

We call the the resultant state $XQ^{i^{*}}JB_{\tau}$. Note that the marginal
state on the registers $XQ^{m}$ in the extended state remains the same as in
the starting state.

From our construction, since the distribution of $B$ depends only on the value
of the register $J$, we have the following Markov-chain $(XQ^{m}-J-B)_{\tau}$
(see Definition 7). This implies

$(XQ^{i^{*}+1}-J-B)_{\tau}.$ (11)

######  Claim 2.

In the state $XQ^{i^{*}}JB_{\tau}$,

$S(XQ^{i^{*}}JB)_{\tau}\leq
S_{2}(X|Q^{i^{*}}JB)_{\tau}+S(Q^{i^{*}}JB)_{\tau}+2.$

###### Proof.

From the construction, in the state $XQ^{i^{*}}JB_{\tau}$, all the eigenvalues
lie between $(\gamma,2\gamma]$ except for $J=0$. We now create another state
$XQ^{i^{*}}JB_{\tau^{\prime}}$ from $XQ^{i^{*}}JB_{\tau}$ as follows. When
$j_{k}=0$, we map all the corresponding eigenvalues $p_{k}\leq\gamma$ to the
same eigenvector $\ket{0}$. Notice that since we are merging eigenvalues
corresponding to different eigenvectors (in $\tau$) to the same eigenvector
$\ket{0}$ in $\tau^{\prime}$ for $J=0$, the Rényi entropy of the new state
$\tau^{\prime}$ can only decrease because of this redistribution. That is,

$\displaystyle S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\tau}$ $\displaystyle\geq
S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\tau^{\prime}}.$ (12)

Consider the case when $q_{0}\geq\gamma$, we see that the resultant state
$\tau^{\prime}$ is $2$-flat. We also get

$\left\|{XQ^{i^{*}}JB}_{\tau}-{XQ^{i^{*}}JB}_{\tau^{\prime}}\right\|_{1}\leq\frac{2^{n^{c^{\prime\prime}}}}{2^{n^{5+c^{\prime\prime}}}}=\mathsf{negl}(n).$

Thus,

$\displaystyle S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\tau}$ $\displaystyle\geq
S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\tau^{\prime}}$ $\displaystyle\geq
S(XQ^{i^{*}}JB)_{\tau^{\prime}}-1$ ($\tau^{\prime}$ is $2$-flat)
$\displaystyle\geq S(XQ^{i^{*}}JB)_{\tau}-1-\mathsf{negl}(n)-\frac{1}{e}$
(Fact 17) $\displaystyle\geq S(XQ^{i^{*}}JB)_{\tau}-2.$

Now consider the case when $q_{0}<\gamma$. Let the eigenvalues of
$XQ^{i^{*}}JB_{\tau^{\prime}}$ be $q_{0}=p_{0}\leq p_{1}\leq p_{2}\dots$. Then
all values other than $p_{0}$ are at least $\gamma$. Let us create a new
(unnormalized) state $\widetilde{\tau}$ such that the eigenvectors are the
same as $\tau^{\prime}$ but for the eigenvalues, we replace $p_{0}$ with
$\gamma$ and keep the rest of the eigenvalues $p_{1},p_{2}\dots$ same. From
monotonicity of $\log$ and the fact that $(1-\alpha)<0$ for
$\alpha=\frac{4}{3}$, we get

$\displaystyle S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\widetilde{\tau}}\leq
S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{{\tau}^{\prime}}.$ (13)

We now renormalise the state $\widetilde{\tau}$ to get state
$\widetilde{\tau}^{\prime}$. This gives eigenvalues
$p_{0}^{\prime},p_{1}^{\prime}\dots$ where
$p_{0}^{\prime}=\frac{\gamma}{1+\gamma-p_{0}}$ and for $j\neq
0,p_{j}^{\prime}=\frac{p_{j}}{1+\gamma-p_{0}}$. The construction gives that
$(XQ^{i^{*}}JB)_{\widetilde{\tau}^{\prime}}$ is a $2$-flat state that is
$\mathsf{negl}(n)$ close to $(XQ^{i^{*}}JB)_{{\tau}}$. We get

$\displaystyle
S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\widetilde{\tau}^{\prime}}=S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\widetilde{\tau}}+4\log(1+\gamma-
p_{0}).$ (14)

Combining the eqs. 12, 13 and 14, we get

$\displaystyle S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{{\tau}}$ $\displaystyle\geq
S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\widetilde{\tau}^{\prime}}-4\log(1+\gamma-
p_{0})$ $\displaystyle\geq
S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\widetilde{\tau}^{\prime}}-8(\gamma-p_{0})$
($\log(1+x)\leq 2x$ for all $x\in\mathbb{R}^{+}$) $\displaystyle\geq
S(XQ^{i^{*}}JB)_{\widetilde{\tau}^{\prime}}-1-8(\gamma-p_{0})$
($\widetilde{\tau}^{\prime}$ is $2$-flat) $\displaystyle\geq
S(XQ^{i^{*}}JB)_{\tau}-1-\mathsf{negl}(n)-\frac{1}{e}-8(\gamma-p_{0})$ (Fact
17) $\displaystyle\geq S(XQ^{i^{*}}JB)_{\tau}-2.$

Thus in both cases, we get the same inequality. Now we use Fact 16 with
$A\leftarrow X,B\leftarrow Q^{i^{*}}JB,\alpha=\frac{4}{3},\beta=2,\gamma=2$
and $C$ as an empty register to get,

$\displaystyle S_{\frac{4}{3}}(XQ^{i^{*}}JB)_{\tau}$ $\displaystyle\leq
S_{2}(X|Q^{i^{*}}JB)_{\tau}+S_{2}(Q^{i^{*}}JB)_{\tau}$ $\displaystyle\leq
S_{2}(X|Q^{i^{*}}JB)_{\tau}+S(Q^{i^{*}}JB)_{\tau}.$ (Fact 8)

Combining the above equations, we get

$S(XQ^{i^{*}}JB)_{\tau}\leq
S_{2}(X|Q^{i^{*}}JB)_{\tau}+S(Q^{i^{*}}JB)_{\tau}+2.\qed$

######  Claim 3.

$S_{2}(X|Q^{i^{*}}JB)_{\tau}-S_{2}(X|Q^{{i^{*}}+1}JB)_{\tau}\leq(5+c^{\prime\prime}+c^{\prime})\log(n)+1.$

###### Proof.

Consider,

$\displaystyle S_{2}(X|Q^{i^{*}}JB)_{\tau}$ $\displaystyle\leq
S_{2}(X|Q^{i^{*}})_{\tau}$ (Fact 9) $\displaystyle\leq
S_{2}(X|Q^{{i^{*}}+1})_{\tau}+c^{\prime}\log(n)$ (Claim 1) $\displaystyle\leq
S_{2}(X|Q^{{i^{*}}+1}J)_{\tau}+|J|+c^{\prime}\log(n)$ (Fact 9)
$\displaystyle\leq
S_{2}(X|Q^{{i^{*}}+1}J)_{\tau}+(5+c^{\prime\prime})\log(n)+1+c^{\prime}\log(n)$
($|J|\leq(5+c^{\prime\prime})\log(n)+1$)
$\displaystyle=S_{2}(X|Q^{{i^{*}}+1}JB)_{\tau}+(5+c^{\prime\prime}+c^{\prime})\log(n)+1.$
(eq. 11 and Fact 15)

∎

######  Claim 4.

$XQ^{i^{*}}JB_{\tau}$ is a one-way state.

###### Proof.

Let us assume for contradiction that $XQ^{i^{*}}JB_{\tau}$ is not a one-way
state. Then there exists a non-uniform $\mathrm{QPT}$ algorithm $A$ and a
positive polynomial $p(\cdot)$ such that for infinitely many $\lambda$,

$\delta_{\lambda}{\text{}:=}\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A(1^{\lambda},\tau^{Q^{i^{*}}JB}),\tau^{Q_{i^{*}+1}})]\geq\frac{1}{p(\lambda)}.$
(15)

Since $(Q^{i^{*}+1}-J-B)_{\tau}$, using Fact 14, we get

$\displaystyle Q^{i^{*}+1}JB_{\tau}$ $\displaystyle\leq 2^{|J|}\cdot
Q^{{i^{*}}+1}_{\tau}\otimes\Phi(U_{|J|}),$

where $\Phi:J\rightarrow JB$ is the CPTP recovery map such that
$Q^{i^{*}+1}JB_{\tau}=\Phi(Q^{i^{*}+1}J_{\tau})$. We note that $\Phi$ is a
non-uniform $\mathrm{QPT}$ map (using the binary encoding of
$\\{\Pr(J=j)\\}_{j}$ in polynomially many bits as advice)333The exponentially
small errors in the specifications of probabilities can be easily incorporated
in the proof, however, we do not do that explicitly for the ease of
presentation.. Thus, we have

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A(1^{\lambda},Q^{i^{*}}_{\tau}\otimes\Phi(U_{|J|})),\tau^{Q_{i^{*}+1}})]\geq\frac{1}{p(\lambda)}\cdot\frac{1}{2^{|J|}.}$
(16)

We now construct a non-uniform adversary $A^{\prime}$ as follows.

$A^{\prime}(1^{\lambda},Q^{i^{*}}_{\tau})$:

  1. 1.

$A^{\prime}$ takes as input $Q^{i^{*}}_{\tau}$ along with the security
parameter $\lambda$.

  2. 2.

$A^{\prime}$ appends $\Phi(U_{|J|})$ to $Q^{i^{*}}_{\tau}$.

  3. 3.

$A^{\prime}$ returns $A(1^{\lambda},Q^{i^{*}}_{\tau}\otimes\Phi(U_{|J|}))$.

From eqs. 15 and 16, using $|J|\leq(5+c^{\prime\prime})\log(n)+1$, we see that
for infinitely many $\lambda$,

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A^{\prime}(1^{\lambda},\tau^{Q^{i^{*}}}),\tau^{Q_{i^{*}+1}})]\geq\frac{1}{p(\lambda)\cdot
2n^{5+c^{\prime\prime}}}.$

Since $n\in\mathrm{poly}(\lambda)$ (because of efficiency of the
$\mathrm{OWSG}$), this contradicts that $\tau^{XQ^{i^{*}}}$ is a one-way
state. Thus, $XQ^{i^{*}}JB_{\tau}$ is a one-way state. ∎

######  Claim 5.

Let

$l_{i^{*}}{\text{}:=}S_{2}(X|Q^{{i^{*}}+1}JB)_{\tau}-(12+2c^{\prime\prime})\log(n).$

Then $XQ^{i^{*}}JBHH^{l_{i^{*}}}(X)_{\tau}$ is a one-way state.

###### Proof.

Let us assume for contradiction that $XQ^{i^{*}}JBHH^{l_{i^{*}}}(X)_{\tau}$ is
not a one-way state. Then there exists a non-uniform $\mathrm{QPT}$ algorithm
$A$ and a positive polynomial $p(\cdot)$, such that for infinitely many
$\lambda$,

$\delta_{\lambda}{\text{}:=}\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A(1^{\lambda},\tau^{Q^{i^{*}}JBHH^{l_{i^{*}}}(X)}),\tau^{Q_{i^{*}+1}})]\geq\frac{1}{p(\lambda)}.$
(17)

Let $l^{\prime}=l_{i^{*}}-4\log(\frac{4}{\delta_{\lambda}})$. From Fact 18, we
get

$Q^{i^{*}+1}JBHH^{l^{\prime}}(x)_{\tau}\approx_{{\delta_{\lambda}^{2}/16}}Q^{i^{*}+1}JB_{\tau}\otimes
U_{s}\otimes U_{l^{\prime}}.$ (18)

From Fact 20 (using $\rho_{A}\leftarrow
Q^{i^{*}+1}JBHH^{l^{\prime}}(X)_{\tau},\rho_{AB}\leftarrow
Q^{i^{*}+1}JBHH^{l_{i^{*}}}(X)_{\tau}$ and $\sigma_{A}\leftarrow
Q^{i^{*}+1}JB_{\tau}\otimes U_{s}\otimes U_{l^{\prime}}$ ), we get an
extension $\theta_{AB}$ of $\sigma_{A}$ such that

$\displaystyle\left\|\rho_{AB}-\theta_{AB}\right\|_{1}$ $\displaystyle\leq
2\sqrt{2}\cdot\Delta_{B}(\rho_{AB},\theta_{AB})$ (Fact 2)
$\displaystyle=2\sqrt{2}\cdot\Delta_{B}(\rho_{A},\sigma_{A})$
$\displaystyle\leq\frac{\delta_{\lambda}}{2}.$ (eq. 18 and Fact 2)

Hence,

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A(1^{\lambda},\theta^{Q^{i^{*}}JBHH^{l_{i^{*}}}(X)}),\theta^{Q_{i^{*}+1}})]\geq\delta_{\lambda}-\frac{\delta_{\lambda}}{{2}}\geq\frac{\delta_{\lambda}}{2}.$

From Fact 11, we have

$\displaystyle\theta\leq
2^{8\log\left(\frac{4}{\delta_{\lambda}}\right)}Q^{i^{*}+1}JB_{\tau}\otimes
U_{s}\otimes U_{l_{i^{*}}}.$

Thus,

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A(1^{\lambda},{Q^{i^{*}}JB_{\tau}\otimes
U_{s}\otimes
U_{l_{i^{*}}}}),\tau^{Q_{i^{*}+1}})]\geq\frac{\delta_{\lambda}}{2}\cdot\left(\frac{\delta_{\lambda}}{4}\right)^{8}.$
(19)

We now construct a non-uniform adversary $A^{\prime}$ as follows.

$A^{\prime}(1^{\lambda},Q^{i^{*}}JB_{\tau})$:

  1. 1.

$A^{\prime}$ takes as input $Q^{i^{*}}JB_{\tau}$ along with the security
parameter $\lambda$.

  2. 2.

$A^{\prime}$ takes as (non-uniform) advice $l_{i^{*}}$.

  3. 3.

$A^{\prime}$ appends $U_{s}\otimes U_{l_{i^{*}}}$ to $Q^{i^{*}}JB_{\tau}$.

  4. 4.

$A^{\prime}$ returns $A(1^{\lambda},Q^{{i^{*}}}JB_{\tau}\otimes U_{s}\otimes
U_{l_{i^{*}}})$.

From eqs. 17 and 19, we see that for infinitely many $\lambda$,

$\Pr[\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A^{\prime}(1^{\lambda},\tau^{Q^{i^{*}}JB}),\tau^{Q_{i^{*}+1}})]\geq\frac{1}{2^{17}\cdot
p(\lambda)^{9}}.$

This contradicts that $\tau^{XQ^{i^{*}}JB}$ is a one-way state (Claim 4).
Thus, $XQ^{i^{*}}JBHH^{l_{i^{*}}}(X)_{\tau}$ is a one-way state. ∎

######  Claim 6.

There exists a function
$g:\\{0,1\\}^{n}\times\\{0,1\\}^{2n}\rightarrow\\{0,1\\}^{(30+4c^{\prime\prime}+c^{\prime})\log(n)}$
such that

$\tau^{\prime}_{0}({i^{*}},l_{i^{*}})\approx_{\mathsf{negl}_{C}}\tau^{\prime}_{1}({i^{*}},l_{i^{*}}),$

where:

$\tau^{\prime}_{0}({i^{*}},l)=Q^{i^{*}}JBHH^{l}(X)Rg(X,R)_{\tau}.$
$\tau^{\prime}_{1}({i^{*}},l)=Q^{i^{*}}JBHH^{l}(X)_{\tau}\otimes U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)}.$

###### Proof.

From Claim 5, $XQ^{i^{*}}JBHH^{l_{i^{*}}}(X)_{\tau}$ is a one-way state. The
claim now follows by taking $g(\cdot)$ as the quantum hardcore function from
Fact 28. ∎

######  Claim 7.

$S(\tau^{\prime}_{1}(i^{*},l_{i^{*}}))-S(\tau^{\prime}_{0}(i^{*},l_{i^{*}}))\geq(13+c^{\prime\prime})\log(n)-4.$

###### Proof.

Fact 18 gives

$Q^{i^{*}+1}JBHH^{l_{i^{*}}}(X)_{\tau}\approx_{2^{-{(6+c^{\prime\prime})}\log(n)}}Q^{i^{*}+1}JB_{\tau}\otimes
U_{s}\otimes U_{l_{i^{*}}}.$

On tracing out $Q_{i^{*}+1}$, we have

$Q^{i^{*}}JBHH^{l_{i^{*}}}(X)_{\tau}\approx_{2^{-(6+c^{\prime\prime})\log(n)}}Q^{i^{*}}JB_{\tau}\otimes
U_{s}\otimes U_{l_{i^{*}}}.$ (20)

Let

$\widetilde{\tau}_{1}({i^{*}},l_{i^{*}})=Q^{i^{*}}JB_{\tau}\otimes
U_{s}\otimes U_{l_{i^{*}}}\otimes U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)}.$
$\displaystyle\left\|\tau^{\prime}_{1}({i^{*}},l_{i^{*}})-\widetilde{\tau}_{1}({i^{*}},l_{i^{*}})\right\|_{1}$
$\displaystyle=\left\|Q^{i^{*}}JBHH^{l_{i^{*}}}(X)_{\tau}\otimes U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)}-Q^{i^{*}}JB_{\tau}\otimes
U_{s}\otimes U_{l_{i^{*}}}\otimes U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)}\right\|_{1}$
$\displaystyle=\left\|Q^{i^{*}}JBHH^{l_{i^{*}}}(X)_{\tau}-Q^{i^{*}}JB_{\tau}\otimes
U_{s}\otimes U_{l_{i^{*}}}\right\|_{1}$
$\displaystyle\leq\frac{1}{n^{6+c^{\prime\prime}}}.\hskip 56.9055pt\hskip
56.9055pt\hskip 56.9055pt\hskip 56.9055pt\hskip 56.9055pt\mbox{(eq.
\ref{eq*:hash_traced_out})}$

From Fact 17, we get (here $\log(d)$ is the number of qubits in
$\tau^{\prime}_{0}({i^{*}},l_{i^{*}})$)

$|S(\tau^{\prime}_{1}({i^{*}},l_{i^{*}}))-S(\widetilde{\tau}_{1}({i^{*}},l_{i^{*}}))|\leq\log(d)\left\|\tau^{\prime}_{1}({i^{*}},l_{i^{*}})-\widetilde{\tau}_{1}({i^{*}},l_{i^{*}})\right\|_{1}+\frac{1}{e}\leq\frac{O(n^{5+c^{\prime\prime}})}{n^{6+c^{\prime\prime}}}+\frac{1}{e}\leq
1.$ (21)

Consider,

$\displaystyle S(\tau^{\prime}_{0}({i^{*}},l_{i^{*}}))$
$\displaystyle=S(Q^{i^{*}}JBHH^{l_{i^{*}}}(X)Rg(X,R))_{\tau}$
$\displaystyle\leq S(XQ^{i^{*}}JBHH^{l_{i^{*}}}(X)Rg(X,R))_{\tau}$ (Fact 4)
$\displaystyle=S(XQ^{i^{*}}JBHR)_{\tau}$ (since $h^{l_{i^{*}}}(x),g(x,r)$ are
functions of $x,h,r$) $\displaystyle=S(XQ^{i^{*}}JB\otimes U_{s}\otimes
U_{2n})_{\tau}$ $\displaystyle=S(XQ^{i^{*}}JB)_{\tau}+s+2n.$ (22)

Consider,

$\displaystyle S(\widetilde{\tau}_{1}({i^{*}},l_{i^{*}}))$
$\displaystyle=S(Q^{i^{*}}JB)_{\tau}+s+l_{i^{*}}+2n+(30+4c^{\prime\prime}+c^{\prime})\log(n)$
$\displaystyle=S(Q^{i^{*}}JB)_{\tau}+s+S_{2}(X|Q^{{i^{*}}+1}JB)_{\tau}-(12+2c^{\prime\prime})\log(n)+2n+(30+4c^{\prime\prime}+c^{\prime})\log(n)$
$\displaystyle\geq
S(Q^{i^{*}}JB)_{\tau}+s+S_{2}(X|Q^{i^{*}}JB)_{\tau}-1-(5+c^{\prime\prime}+c^{\prime})\log(n)+2n+(18+2c^{\prime\prime}+c^{\prime})\log(n)$
$\displaystyle=S(Q^{i^{*}}JB)_{\tau}+s+2n+S_{2}(X|Q^{i^{*}}JB)_{\tau}+(13+c^{\prime\prime})\log(n)-1$
$\displaystyle\geq
S(XQ^{i^{*}}JB)_{\tau}+s+2n+(13+c^{\prime\prime})\log(n)-3.$ (23)

The first and second inequalities follow from Claim 3 and Claim 2
respectively. Combining eqs. 21, 22 and 23, we get

$S({\tau^{\prime}}_{1}(i^{*},l_{i^{*}}))-S(\tau^{\prime}_{0}(i^{*},l_{i^{*}}))\geq(13+c^{\prime\prime})\log(n)-4.\qed$

######  Claim 8.

Define for all $i\in[m]$ and $l\in[n]$ :

$\tau_{0}(i,l){\text{}:=}\mathrm{Tr}_{JB}(\tau^{\prime}_{0}(i,l))=Q^{i}HH^{l}(X)Rg(X,R)_{\tau}.$
$\tau_{1}(i,l){\text{}:=}\mathrm{Tr}_{JB}(\tau^{\prime}_{1}(i,l))=Q^{i}HH^{l}(X)_{\tau}\otimes
U_{2n}\otimes U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)}.$

Then,

$\tau_{0}(i^{*},l_{i^{*}})\approx_{\mathsf{negl}_{C}}\tau_{1}(i^{*},l_{i^{*}}).$
$S({\tau}_{1}(i^{*},l_{i^{*}}))-S(\tau_{0}(i^{*},l_{i^{*}}))\geq 8\log(n)-5.$

###### Proof.

From Claim 6, we have

$\tau^{\prime}_{0}(i^{*},l_{i^{*}})\approx_{\mathsf{negl}_{C}}\tau^{\prime}_{1}(i^{*},l_{i^{*}}).$

On tracing out $J$ and $B$ and using Fact 31, we get

$\tau_{0}(i^{*},l_{i^{*}})\approx_{\mathsf{negl}_{C}}\tau_{1}(i^{*},l_{i^{*}}).$

Consider,

$\displaystyle S({\tau}^{\prime}_{0}(i^{*},l_{i^{*}}))$
$\displaystyle=S(Q^{i^{*}}JBHH^{l_{i^{*}}}(X)Rg(X,R))_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}$
$\displaystyle=S(J)_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}+S(Q^{i^{*}}HH^{l_{i^{*}}}(X)Rg(X,R)|J)_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}+S(B|J)_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}$
(Fact 15)
$\displaystyle=S(Q^{i^{*}}JHH^{l_{i^{*}}}(X)Rg(X,R))_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}+S(B|J)_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}$
(Fact 3) $\displaystyle\geq
S({\tau_{0}(i^{*},l_{i^{*}})})+S(B|J)_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}.$
(Fact 4) (24)

Similarly,

$\displaystyle S({\tau}^{\prime}_{1}(i^{*},l_{i^{*}}))$
$\displaystyle=S(Q^{i^{*}}JBHH^{l_{i^{*}}}(X)\otimes U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)})_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}$
$\displaystyle=S(J)_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}+S(Q^{i^{*}}HH^{l_{i^{*}}}(X)\otimes
U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)}|J)_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}+S(B|J)_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}$
(Fact 15) $\displaystyle=S(Q^{i}JHH^{l_{i^{*}}}(X)\otimes U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)})_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}+S(B|J)_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}$
(Fact 3) $\displaystyle\leq S(Q^{i}HH^{l_{i^{*}}}(X)\otimes U_{2n}\otimes
U_{(30+4c^{\prime\prime}+c^{\prime})\log(n)})_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}+|J|+S(B|J)_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}$
(Fact 3) $\displaystyle\leq
S({\tau_{1}(i^{*},l_{i^{*}})})+S(B|J)_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}+(5+c^{\prime\prime})\log(n)+1.$
(25)

From the definitions of $\tau^{\prime}_{0}(i^{*},l_{i^{*}})$ and
$\tau^{\prime}_{1}(i^{*},l_{i^{*}})$, we see that the joint distribution of
$XQ^{i^{*}}BJHH^{l_{i^{*}}}(X)$ is same in both
$\tau^{\prime}_{0}(i^{*},l_{i^{*}})$ and $\tau^{\prime}_{1}(i^{*},l_{i^{*}})$
and hence

$S(B|J)_{\tau^{\prime}_{0}(i^{*},l_{i^{*}})}=S(B|J)_{\tau^{\prime}_{1}(i^{*},l_{i^{*}})}.$

Combining eqs. 24 and 25 and Claim 7, we get

$S({\tau}_{1}(i^{*},l_{i^{*}}))-S(\tau_{0}(i^{*},l_{i^{*}}))\geq
8\log(n)-5.\qed$

##  4 An $\mathrm{EFI}$ implies an $\mathrm{OWSG}$

######  Theorem 8.

An $\mathrm{EFI}$ implies a $\mathrm{poly}(n)$-copy $\mathrm{OWSG}$.

###### Proof.

Suppose we have an $\mathrm{EFI}$ pair $(\rho_{0},\rho_{1})$. Then,
$\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$. From Fact 24, we can also
assume without loss of generality that
$\frac{1}{2}\left\|\rho_{0}-\rho_{1}\right\|_{1}\geq
1-\mathsf{negl}(\lambda)$.

We create an $\mathrm{OWSG}$ as follows:

  1. 1.

$\textsc{KeyGen}(1^{\lambda})\rightarrow x$ : $x\leftarrow U_{n}$ for
$n=\lambda$.

  2. 2.

$\textsc{StateGen}(1^{\lambda},x)\rightarrow\phi_{x}:\phi_{x}=\rho_{x_{1}}\otimes\rho_{x_{2}}\dots\rho_{x_{n}}$
where $x_{i}$ represents the $i^{th}$-bit of $x$.

  3. 3.

$\textsc{Ver}(x^{\prime},\phi_{x})\rightarrow\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}/\bot:$
Let $\\{\pi_{0},\pi_{1}\\}$ be the optimal distinguisher for $\rho_{0}$ and
$\rho_{1}$. Ver measures $\phi_{x}$ according to the projectors
$\\{\pi_{x^{\prime}_{1}}\otimes\pi_{x^{\prime}_{2}}\dots\pi_{x^{\prime}_{n}},\mathbb{1}-\pi_{x^{\prime}_{1}}\otimes\pi_{x^{\prime}_{2}}\dots\pi_{x^{\prime}_{n}}\\}$.
It outputs
$\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}$ if the
first result is obtained and outputs $\perp$ otherwise.

We know that since $\pi_{0},\pi_{1}$ are the optimal distinguishers and
$\frac{1}{2}\left\|\rho_{0}-\rho_{1}\right\|_{1}\geq
1-\mathsf{negl}(\lambda)$, we have the following:

$\mathrm{Tr}(\pi_{0}\rho_{0})\geq
1-\mathsf{negl}(\lambda)~{},~{}\mathrm{Tr}(\pi_{1}\rho_{1})\geq
1-\mathsf{negl}(\lambda),$
$\mathrm{Tr}(\pi_{1}\rho_{0})=\mathsf{negl}(\lambda)~{},~{}\mathrm{Tr}(\pi_{0}\rho_{1})=\mathsf{negl}(\lambda).$

#### Correctness:

From the union bound, we get

$\Pr(\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(x,\phi_{x}))\geq
1-n\cdot\mathsf{negl}(\lambda)\geq 1-\mathsf{negl}(\lambda).$ (26)

The above gives us the correctness condition required for an $\mathrm{OWSG}$.

#### Security:

We see that for any $x^{\prime}\neq x$,

$\Pr(\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(x^{\prime},\phi_{x}))=\mathsf{negl}(\lambda).$
(27)

Let $X\leftarrow U_{n}$. Assume for contradiction that there exists a non-
uniform $\mathrm{QPT}$ adversary $A$ and $t\in\mathrm{poly}(n)$ such that

$\displaystyle\Pr(\ThisStyle{\abovebaseline[0pt]{\scalebox{-1.0}{$\SavedStyle\perp$}}}\leftarrow\textsc{Ver}(A(1^{\lambda},\phi_{X}^{\otimes
t}),\phi_{X}))\geq\frac{1}{q(n)},$

for some positive polynomial $q(\cdot)$. Let
$A(1^{\lambda},\rho_{X_{1}}^{\otimes t}\otimes\rho_{X_{2}}^{\otimes
t}\dots\rho_{X_{n}}^{\otimes t})=X^{\prime}$. Combining the above with eqs. 26
and 27 gives us

$\Pr(X^{\prime}=X)=\Pr(A(1^{\lambda},\phi_{X}^{\otimes
t})=X)\geq\frac{1}{2q(n)}.$ (28)

We also have

$\Pr(X^{\prime}=X)=\prod_{i=1}^{n}\Pr(X_{i}^{\prime}=X_{i}|X^{\prime}_{[i-1]}=X_{[i-1]}).$

Since $\Pr(X^{\prime}=X)\geq\frac{1}{2q(n)}$, there exists an $i\in[n]$ such
that

$\Pr(X_{i}^{\prime}=X_{i}|X^{\prime}_{[i-1]}=X_{[i-1]})\geq\frac{3}{4}.$ (29)

We now construct a non-uniform adversary $A^{\prime}$ as described below. Let
$B\leftarrow U_{1}$.

$A^{\prime}(1^{\lambda},\rho_{B}^{\otimes t})$:

  1. 1.

$A^{\prime}$ takes as input $t$-copies of the state $\rho_{B}$ along with the
security parameter $\lambda$. It also has access to an $\mathrm{EFI}$ that
generates the $\mathrm{EFI}$ pair $(\rho_{0},\rho_{1})$.

  2. 2.

$A^{\prime}$ takes as advice $i$ from eq. 29.

  3. 3.

$A^{\prime}$ generates $X_{1}\dots X_{i-1}X_{i+1}\dots X_{n}$ each drawn i.i.d
from $U_{1}$.

  4. 4.

$A^{\prime}$ sets $X^{\prime}=A(1^{\lambda},\rho_{X_{1}}^{\otimes
t}\otimes\dots\rho_{X_{i-1}}^{\otimes t}\otimes\rho_{B}^{\otimes
t}\otimes\rho_{X_{i+1}}^{\otimes t}\dots\rho_{X_{n}}^{\otimes t})$.

  5. 5.

$A^{\prime}$ checks if $X_{[i-1]}^{\prime}=X_{[i-1]}$.

     * •

If $X_{[i-1]}^{\prime}=X_{[i-1]}$, then $A^{\prime}$ outputs $X^{\prime}_{i}$.

     * •

Otherwise, $A^{\prime}$ outputs a random bit $U_{1}$.

Define $X=X_{1}\dots X_{i-1}BX_{i+1}\dots X_{n}$. Note that $X\leftarrow
U_{n}$. From the above construction, we get

$\displaystyle\Pr(A^{\prime}(1^{\lambda},\rho_{B}^{\otimes t})=B)$
$\displaystyle=\Pr(X^{\prime}_{[i-1]}=X_{[i-1]}).\Pr(X^{\prime}_{i}=B|X^{\prime}_{[i-1]}=X_{[i-1]})+\Pr(X^{\prime}_{[i-1]}\neq
X_{[i-1]}).\frac{1}{2}.$

From eq. 28 we have $\Pr(X^{\prime}=X)\geq\frac{1}{2q(n)}$ which gives
$\Pr(X^{\prime}_{[i-1]}=X_{[i-1]})\geq\frac{1}{2q(n)}$. Combining this with
eq. 29, we get

$\displaystyle\Pr(A^{\prime}(1^{\lambda},\rho_{B}^{\otimes
t})=B)\geq\frac{1}{2}+\frac{1}{8q(n)},$ $\displaystyle\Rightarrow~{}$
$\displaystyle\frac{1}{2}\Pr(A^{\prime}(1^{\lambda},\rho_{0}^{\otimes
t})=0)+\frac{1}{2}\Pr(A^{\prime}(1^{\lambda},\rho_{1}^{\otimes
t})=1)\geq\frac{1}{2}+\frac{1}{8q(n)},$ $\displaystyle\Rightarrow~{}$
$\displaystyle\frac{1}{2}\Pr(A^{\prime}(1^{\lambda},\rho_{0}^{\otimes
t})=0)+\frac{1}{2}\left(1-\Pr(A^{\prime}(1^{\lambda},\rho_{1}^{\otimes
t})=0)\right)\geq\frac{1}{2}+\frac{1}{8q(n)},$ $\displaystyle\Rightarrow~{}$
$\displaystyle\Pr(A^{\prime}(1^{\lambda},\rho_{0}^{\otimes
t})=0)-\Pr(A^{\prime}(1^{\lambda},\rho_{1}^{\otimes
t})=0)\geq\frac{1}{4q(n)}.$

This along with Fact 29 contradicts that
$\rho_{0}\approx_{\mathsf{negl}_{C}}\rho_{1}$. ∎

## Acknowledgements

R.B. would like to thank Upendra Kapshikar and Sayantan Chakraborty for useful
discussions. R.J. would like to thank Fang Song for pointing the reference
[CGG+23]. The work of R.J. is supported by the NRF grant NRF2021-QEP2-02-P05
and the Ministry of Education, Singapore, under the Research Centres of
Excellence program. This work was done in part while R.J. was visiting the
Simons Institute for the Theory of Computing, Berkeley, CA, USA. R.B. is
supported by the Singapore Ministry of Education and the National Research
Foundation through the core grants of the Centre for Quantum Technologies.

## References

  * [AC02] Mark Adcock and Richard Cleve.  A Quantum Goldreich-Levin Theorem with Cryptographic Applications.  In Helmut Alt and Afonso Ferreira, editors, STACS 2002, pages 323–334, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
  * [AFJ24] Itai Arad, Raz Firanko, and Rahul Jain.  Area law for the maximally mixed ground state in degenerate 1D gapped systems.  ACM Symposium on Theory of Computing (STOC), 2024.
  * [AHJ20] Anurag Anshu, Min-Hsiu Hsieh, and Rahul Jain.  Noisy Quantum State Redistribution With Promise and the Alpha-Bit.  IEEE Transactions on Information Theory, 66(12):7772–7786, 2020.
  * [AJ22] Anurag Anshu and Rahul Jain.  Efficient methods for one-shot quantum communication.  npj Quantum Information, 8(1), August 2022.
  * [AJM+16] Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, and Penghui Yao.  New One Shot Quantum Protocols With Application to Communication Complexity.  IEEE Transactions on Information Theory, 62(12):7566–7577, December 2016.
  * [AQY22] Prabhanjan Ananth, Luowen Qian, and Henry Yuen.  Cryptography from Pseudorandom Quantum States.  In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 208–236, Cham, 2022. Springer Nature Switzerland.
  * [BB84] Charles Bennett and Gilles Brassard.  Quantum Cryptography: Public Key Distribution and Coin Tossing.  Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, pages 175–179, Dec 1984.
  * [BCKM21] James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma.  One-Way Functions Imply Secure Computation in a Quantum World.  In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 467–496, Cham, 2021. Springer International Publishing.
  * [BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian.  On the Computational Hardness Needed for Quantum Cryptography.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:21, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [BCR11] Mario Berta, Matthias Christandl, and Renato Renner.  The Quantum Reverse Shannon Theorem Based on One-Shot Information Theory.  Communications in Mathematical Physics, 306(3):579–615, August 2011.
  * [BJL23] Naresh Goud Boddu, Rahul Jain, and Han-Hsuan Lin.  On relating one-way classical and quantum communication complexities.  Quantum, 7:1010, May 2023.
  * [CGG+23] Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu, and Angelos Pelecanos.  On the Computational Hardness of Quantum One-Wayness, 2023.
  * [Dup15] Frédéric Dupuis.  Chain rules for quantum Rényi entropies.  Journal of Mathematical Physics, 56(2):022203, February 2015.
  * [Eke91] Artur K. Ekert.  Quantum cryptography based on Bell’s theorem.  Phys. Rev. Lett., 67:661–663, Aug 1991.
  * [FvdG99] C.A. Fuchs and J. van de Graaf.  Cryptographic distinguishability measures for quantum-mechanical states.  IEEE Transactions on Information Theory, 45(4):1216–1227, 1999.
  * [GLSV21] Alex B. Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan.  Oblivious Transfer Is in MiniQCrypt.  In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, pages 531–561, Cham, 2021. Springer International Publishing.
  * [Gol90] Oded Goldreich.  A note on computational indistinguishability.  Information Processing Letters, 34(6):277–281, 1990.
  * [Gol01] Oded Goldreich.  Foundations of Cryptography.  Cambridge University Press, 2001.
  * [HILL99] Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby.  A Pseudorandom Generator from any One-way Function.  SIAM Journal on Computing, 28(4):1364–1396, 1999.
  * [Hol07] Thomas Holenstein.  Parallel repetition: simplifications and the no-signaling case.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 411–419, New York, NY, USA, 2007. Association for Computing Machinery.
  * [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song.  Pseudorandom Quantum States.  In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, pages 126–152, Cham, 2018. Springer International Publishing.
  * [KQST23] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal.  Quantum Cryptography in Algorithmica.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1589–1602, New York, NY, USA, 2023. Association for Computing Machinery.
  * [Kre21] William Kretschmer.  Quantum Pseudorandomness and Classical Complexity.  Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
  * [KT24] Dakshita Khurana and Kabir Tomer.  Commitments from Quantum One-Wayness.  ACM Symposium on Theory of Computing (STOC), 2024.
  * [KW24] Sumeet Khatri and Mark M. Wilde.  Principles of Quantum Communication Theory: A Modern Approach, 2024.
  * [LC97] Hoi-Kwong Lo and H. F. Chau.  Is Quantum Bit Commitment Really Possible?  Phys. Rev. Lett., 78:3410–3413, Apr 1997.
  * [Lo97] Hoi-Kwong Lo.  Insecurity of quantum secure computations.  Phys. Rev. A, 56:1154–1162, Aug 1997.
  * [May97] Dominic Mayers.  Unconditionally Secure Quantum Bit Commitment is Impossible.  Phys. Rev. Lett., 78:3414–3417, Apr 1997.
  * [MY22a] Tomoyuki Morimae and Takashi Yamakawa.  One-Wayness in Quantum Cryptography.  Cryptology ePrint Archive, Paper 2022/1336, 2022.  https://eprint.iacr.org/2022/1336.
  * [MY22b] Tomoyuki Morimae and Takashi Yamakawa.  Quantum Commitments and Signatures Without One-Way Functions, page 269–295.  Springer Nature Switzerland, 2022.
  * [NC10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * [Ren06] Renato Renner.  Security of Quantum Key Distribution.  PhD thesis, 2006.
  * [TH13] Marco Tomamichel and Masahito Hayashi.  A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks.  IEEE Transactions on Information Theory, 59(11):7693–7710, November 2013.
  * [Tom16] Marco Tomamichel.  Quantum Information Processing with Finite Resources.  Springer International Publishing, 2016.
  * [Uhl76] A. Uhlmann.  The “transition probability” in the state space of a*-algebra. reports on mathematical physics.  Rep. Math. Phys., 1976.
  * [Yan22] Jun Yan.  General Properties of Quantum Bit Commitments.  In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, pages 628–657, Cham, 2022. Springer Nature Switzerland.