# Exponential Quantum One-Wayness and EFI Pairs

Giulio Malavolta  Bocconi University, Milan, Italy
<EMAIL_ADDRESS>Max Planck Institute for Security and Privacy,
Bochum, Germany Tomoyuki Morimae  Yukawa Institute for Theoretical Physics,
Kyoto University, Kyoto, Japan
<EMAIL_ADDRESS>Michael Walter  Faculty of Computer
Science, Ruhr University Bochum, Bochum, Germany
<EMAIL_ADDRESS>Takashi Yamakawa  NTT Social Informatics Laboratories,
Tokyo, Japan
<EMAIL_ADDRESS>NTT Research Center for Theoretical Quantum
Information, Atsugi, Japan Yukawa Institute for Theoretical Physics, Kyoto
University, Kyoto, Japan
<EMAIL_ADDRESS>
###### Abstract

In classical cryptography, one-way functions are widely considered to be the
minimal computational assumption. However, when taking quantum information
into account, the situation is more nuanced. There are currently two major
candidates for the minimal assumption: the _search_ quantum generalization of
one-way functions are one-way state generators (OWSG), whereas the
_decisional_ variant are EFI pairs. A well-known open problem in quantum
cryptography is to understand how these two primitives are related. A recent
breakthrough result of Khurana and Tomer (STOC’24) shows that OWSGs imply EFI
pairs, for the restricted case of pure states.

In this work, we make progress towards understanding the general case. To this
end, we define the notion of _inefficiently-verifiable one-way state
generators_ (IV-OWSGs), where the verification algorithm is not required to be
efficient, and show that these are precisely equivalent to EFI pairs, with an
exponential loss in the reduction. Significantly, this equivalence holds also
for _mixed_ states. Thus our work establishes the following relations among
these fundamental primitives of quantum cryptography:

$\text{(mixed) OWSGs}\implies\text{(mixed) IV-
OWSGs}\equiv_{\text{exp}}\text{EFI pairs},$

where $\equiv_{\text{exp}}$ denotes equivalence up to exponential security of
the primitives.

##  1 Introduction

The existence of one-way functions (OWFs) is widely regarded as the minimal
assumption in classical cryptography. This is because almost all primitives
imply OWFs and furthermore OWFs are in fact equivalent to many foundational
primitives, such as secret-key encryption (SKE), commitments, zero-knowledge,
pseudorandom generators (PRGs), pseudorandom functions (PRFs), and digital
signatures [LR86, IL89, ILL89]. However, recent works have suggested that OWFs
may _not_ be the minimal assumption when bringing quantum information into the
picture. Instead, several candidate “minimal” primitives have been proposed
that are potentially weaker than OWFs [Kre21, KQST23, LMW23], yet still enable
many useful applications, such as private-key quantum money, SKE, commitments,
multiparty computations, and digital signatures [JLS18, MY22b, AQY22, BCQ23,
Yan22].

In this work, we consider two major candidates that have emerged in this
recent line of research: _one-way state generators (OWSGs)_ and _EFI pairs_.
OWSGs were introduced in [MY22b, MY22a] as a _search_ quantum generalization
of OWFs. Formally, a OWSG consists of a triple
$(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Ver})$ of quantum polynomial-time
(QPT) algorithms, where $\mathsf{KeyGen}(1^{\lambda})\to k$ is the key
generation algorithm (keys are classical), $\mathsf{StateGen}(k)\to\phi_{k}$
takes a key as input and generates a quantum state, and
$\mathsf{Ver}(k^{\prime},\phi)\to\\{\top,\bot\\}$ is a verification algorithm
that takes a bit string $k^{\prime}$ and a quantum state $\phi$ as input. The
security of a OWSG requires that no QPT adversary $\mathcal{A}$ can find a
“preimage” of $\phi_{k}$ with non-negligible probability, that is,

$\displaystyle\Pr\left[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\phi_{k}\leftarrow\mathsf{StateGen}(k),k^{\prime}\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t})\right]\approx 0$

for any polynomial number $t=t(\lambda)$ of copies. This can be considered as
a quantum analogue of the one-wayness of OWFs.

On the other hand, EFI pairs [BCQ23] are a _decisional_ quantum generalization
of OWFs. Formally, an EFI pair consists of a QPT algorithm that on input
$1^{\lambda}$ generates two (mixed) quantum states $\xi_{0}$ and $\xi_{1}$
which are statistically far but computationally indistinguishable. As such,
EFI pairs are a quantum generalization of EFIDs, which are pairs of
efficiently samplable classical distributions that are statistically
distinguishable but computationally indistinguishable, a primitive that is
equivalent to OWFs [Gol90].

Given that both of these quantum primitives generalize the same object in
classical cryptography, it is natural to ask about their relation. A recent
breakthrough result [KT23] shows that OWSGs imply EFI pairs provided the
outputs of $\mathsf{StateGen}$ are _pure_ states. The general case where the
outputs of $\mathsf{StateGen}$ are _mixed states_ , as well as the reverse
direction of the implication, remain open.

###  1.1 Our Results

In this work, we make progress towards understanding the relation between
OWSGs and EFI pairs. First, we define a weaker notion of OWSGs, wherein the
verification algorithm $\mathsf{Ver}$ is not required to be efficient. We
refer to this primitive as _inefficiently-verifiable one-way state generators
(IV-OWSGs)_. Then, as the main technical contribution of our work, we show
that IV-OWSGs and EFI pairs are equivalent, but with an exponential loss in
the reduction. That is, our work establishes the following relations amongst
these fundamental primitives in quantum cryptography:

$\text{(mixed) OWSGs}\implies\text{(mixed) IV-
OWSGs}\equiv_{\text{exp}}\text{EFI pairs}$

where $\equiv_{\text{exp}}$ means equivalence with an exponential loss for the
implication from the left to right (but only with a polynomial loss for the
other direction) and we write “(mixed)” to stress that all our results hold in
the general case that the $\mathsf{StateGen}$ of OWSGs returns mixed states.
The first implication is clear. That EFI pairs imply (mixed) IV-OWSGs follows
using known facts in quantum cryptography (Theorem 4.3), and the reduction
does not incur any loss. Our main technical contribution is to prove that IV-
OWSGs imply EFI pairs with an exponential security loss (Theorem 5.2).
Crucially, all our results hold in the general setting where the
$\mathsf{StateGen}$ of OWSGs is allowed to generate mixed states. In contrast,
the recent breakthrough [KT23] only considered _pure_ states (but their
reduction has a polynomial loss, so the results are incomparable). Our proof
follows a different route, and makes crucial use of Aaronson’s shadow
tomography algorithm [Aar19].

Using known implications from the literature [BCQ23], a consequence of our
work is that (mixed) OWSGs with exponential security imply a number of
primitives in cryptography, such as non-interactive commitments, quantum
computational zero knowledge, oblivious transfer, and general multiparty
computation. At a more conceptual level, our work also sheds some light on the
relation between OWSGs and EFI pairs: For instance, if one were able to show
the outstanding implication that EFI pairs $\implies$ OWSGs (with a polynomial
reduction), one would automatically obtain a generic conversion that turns any
exponentially secure OWSGs with _inefficient_ verification into one with
_efficient_ verification, which would perhaps be surprising.

###  1.2 Proof Outline

We give here a brief overview of the proof of our main technical contribution,
namely that IV-OWSGs imply EFI pairs. It is well-known that EFI pairs are
equivalent to canonical quantum bit commitments [Yan22], and therefore our
goal is to construct commitments from IV-OWSGs. Consider an arbitrary IV-OWSG
$(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Ver})$. We construct a non-
interactive bit commitment scheme in the canonical form of [Yan22] as follows.
A commitment to $0$ is a state

$\displaystyle\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}}\coloneqq\sum_{k}\sum_{h\in\mathcal{H}}\sqrt{\frac{\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]}{|\mathcal{H}|}}\ket{k,\mathrm{junk}_{k},h}_{\mathbf{C}_{1}}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}$

whereas a commitment to $1$ is a state

$\displaystyle\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}}\coloneqq\sum_{k}\sum_{h\in\mathcal{H}}\sqrt{\frac{\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]}{|\mathcal{H}|}}\ket{k,\mathrm{jun}k_{k},h}_{\mathbf{C}_{1}}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{k}_{\mathbf{R}_{3}}$

where $t=t(\lambda)$ is a certain polynomial specified later, $\mathcal{H}$ is
a family of pairwise-independent hash functions, $\ket{\mathrm{junk}_{k}}$ is
the state of the non-output registers in a unitary realization of the
$\mathsf{KeyGen}$ algorithm,111Without loss of generality, the
$\mathsf{KeyGen}$ algorithm takes the following form: apply a QPT unitary to
generate a superposition
$\sum_{k}\sqrt{\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]}\ket{k}\ket{\mathrm{junk}_{k}}$,
measure the first register, and output the measurement result.  and
$\ket{\Phi_{k}}$ is a purification of the output of the $\mathsf{StateGen}(k)$
algorithm.222 Without loss of generality, $\mathsf{StateGen}$ takes the
following form: on input $k$, apply a QPT unitary $U_{k}$ on $\ket{0...0}$ to
generate a pure state
$\ket{\Phi_{k}}_{\mathbf{A},\mathbf{B}}=U_{k}|0...0\rangle$ and output the
first register $\mathbf{A}$, which is in state
$\phi_{k}=\mathrm{Tr}_{\mathbf{B}}(\ket{\Phi_{k}}\\!\\!\bra{\Phi_{k}})$. Then
the $\mathbf{A}$ registers of $\ket{\Phi_{k}^{\otimes t}}$ make up
$\mathbf{R}_{2}$, while the $\mathbf{B}$ registers make up $\mathbf{C}_{2}$.
One should think of $\mathbf{C}\coloneqq(\mathbf{C}_{1},\mathbf{C}_{2})$ as
the commitment register and of
$\mathbf{R}\coloneqq(\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{R}_{3})$ as the
reveal register. It is clear that both $\ket{\psi_{0}}$ and $\ket{\psi_{1}}$
can be efficiently generated.

Computational binding is shown with a reduction to the exponential one-wayness
of IV-OWSG: Assuming that there exists an efficient algorithm that converts
$\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}}$ into
$\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}}$ by acting only on $\mathbf{R}$, we
can obtain an algorithm that computes $k$ from $h$, $h(k)$, and
$\phi_{k}^{\otimes t}=\mathrm{Tr}_{\mathbf{C}_{2}}(\ket{\Phi_{k}^{\otimes
t}}\\!\\!\bra{\Phi_{k}^{\otimes t}})$. By randomly guessing $h(k)$, we can use
it to break the security of IV-OWSG with an exponential security loss of
$2^{|h(k)|}$ where $|h(k)|$ is the output length of $h$.

To show statistical hiding, it suffices to construct an (inefficient) unitary
on $\mathbf{R}$ that turns $\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}}$ into
$\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}}$ with a sufficiently good
approximation. To this end consider the following procedure:

  1. 1.

Apply shadow tomography [Aar19] to list all $k^{\prime}$ that are accepted by
$\mathsf{Ver}(\cdot,\phi_{k})$ with a sufficiently large probability.

  2. 2.

In this list, find $k^{*}$ such that $h(k)=h(k^{*})$. If there is a single
such $k^{*}$, output it. Otherwise, output $\bot$.

Intuitively, this algorithm outputs the true key $k$ with probability at least
$1/2-{\mathsf{negl}}(\lambda)$, because the list obtained by the shadow
tomography contains $k$ except for a negligible probability and because we set
the output length of $h$ appropriately so that, with probability at least
$1/2$, $h^{-1}(h(k))$ intersects the list in a single element. By running this
algorithm coherently, we get an (inefficient) unitary on $\mathbf{R}$ that
maps $\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}}$ close to
$\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}}$. Thus Uhlmann’s theorem implies that
the trace distance between
$\mathrm{Tr}_{\mathbf{R}}(\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}})$ and
$\mathrm{Tr}_{\mathbf{R}}(\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}})$ is small.
This shows statistical hiding.

###  1.3 Paper Outline

Section 2 is for preliminaries where some notations and basic definitions are
given. In Section 3, we define the new notion of IV-OWSGs. In Section 4, we
show that EFI pairs imply IV-OWSGs, unconditionally and without any loss. In
Section 5, we show that EFI pairs can be constructed from exponentially-secure
IV-OWSGs, with an exponential loss.

##  2 Preliminaries

###  2.1 Basic Notations

We use notation that is standard in quantum computing and cryptography. We use
$\lambda$ as the security parameter. The notation $[n]$ refers to the set
$\\{1,2,...,n\\}$. For any set $S$, $x\leftarrow S$ means that an element $x$
is sampled uniformly at random from the set $S$. For an algorithm $A$,
$y\leftarrow A(x)$ means that the algorithm outputs $y$ on input $x$. For a
set $S$, $|S|$ denotes its cardinality. We write ${\mathsf{negl}}$ to denote a
negligible function and ${\mathsf{poly}}$ to mean a polynomial function. QPT
stands for quantum polynomial-time. Any binary (2-outcome) quantum measurement
can be described by a POVM element $E$, which is an operator such that both
$E$ and $I-E$ are positive semidefinite. Quantum registers are denoted by bold
font (e.g., $\mathbf{A}$ and $\mathbf{B}$). We write
$\mathrm{Tr}_{\mathbf{B}}(\rho_{\mathbf{A},\mathbf{B}})$ for the partial trace
over the register $\mathbf{B}$ of the bipartite state
$\rho_{\mathbf{A},\mathbf{B}}$. The notation $I_{\mathbf{A}}$ denotes the
identity operator on register $\mathbf{A}$. For any two quantum states $\rho$
and $\sigma$, their fidelity is
$F(\rho,\sigma)\coloneqq(\mathrm{Tr}\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}})^{2}$
and their trace distance is
$\mathsf{TD}(\rho,\sigma)\coloneqq\frac{1}{2}\|\rho-\sigma\|_{1}$.

###  2.2 Computational Model for Adversaries

Throughout the paper, we treat adversaries as _non-uniform_ QPT machine with
_quantum_ advice. However, all of our results extend to the uniform setting in
a straightforward manner.

###  2.3 Pairwise-Independent Hash Family

We recall the definition of pairwise independence.

###### Definition 2.1 (Pairwise-Independent Hash Family).

A family $\mathcal{H}=\\{h:\mathcal{X}\to\mathcal{Y}\\}$ of functions is
called a _pairwise-independent hash family_ if, for any two $x\neq
x^{\prime}\in\mathcal{X}$ and any two $y,y^{\prime}\in\mathcal{Y}$,

$\Pr_{h\leftarrow\mathcal{H}}[h(x)=y\wedge
h(x^{\prime})=y^{\prime}]=\frac{1}{|\mathcal{Y}|^{2}}.$

###  2.4 Shadow Tomography

The shadow tomography problem asks to predict a large number of measurement
outcomes from copies of a quantum state. More formally:

###### Definition 2.2 (Shadow Tomography Problem [Aar19, Problem 1]).

Given $t$ copies of an unknown $d$-dimensional (possibly mixed) quantum state
$\rho$, as well as known binary measurements given by POVM elements
$E_{1},\dots,E_{M}$, output numbers $b_{1},\dots,b_{M}\in[0,1]$ such that

$|b_{j}-\mathrm{Tr}(E_{j}\rho)|\leq\varepsilon$

for all $j$, with success probability at least $1-\omega$.

The following theorem from Aaronson provides a bound on the number of copies
of the state needed to solve this problem.

###### Theorem 2.3 ([Aar19, Theorem 2]).

The shadow tomography problem is solvable with

$t=\tilde{O}\left(\frac{\log\frac{1}{\omega}}{\varepsilon^{4}}\cdot\log^{4}M\cdot\log
d\right),$

where the $\tilde{O}$ hides a ${\mathsf{poly}}(\log\log M,\log\log
d,\log\frac{1}{\epsilon})$ factor.

###  2.5 EFI Pairs and Quantum Bit Commitments

EFI pairs are pairs of efficiently generatable quantum states that are
statistically far, yet computationally indistinguishable. They were introduced
in [BCQ23].

###### Definition 2.4 (EFI Pair [BCQ23]).

An _EFI pair_ is a family $\\{\xi_{\lambda,b}\\}_{\lambda\in\mathbb{N},\
b\in\\{0,1\\}}$ of (mixed) quantum states that satisfies the following
conditions:

  * •

(Efficiently Generatable) There is a uniform QPT algorithm that generates
$\xi_{\lambda,0}$ and $\xi_{\lambda,1}$ on input $1^{\lambda}$.

  * •

(Statistically Far) It holds that
$\mathsf{TD}(\xi_{\lambda,0},\xi_{\lambda,1})\geq 1/{\mathsf{poly}}(\lambda)$.

  * •

(Computationally Indistinguishable) For any non-uniform QPT distinguisher
$\mathcal{A}$, there exists a negligible function ${\mathsf{negl}}$ such that

$\displaystyle\left|\Pr[\mathcal{A}(1^{\lambda},\xi_{\lambda,0})=1]-\Pr[\mathcal{A}(1^{\lambda},\xi_{\lambda,1})=1]\right|\leq{\mathsf{negl}}(\lambda).$

It is known that EFI pairs exist if and only if quantum bit commitments exist.
We define canonical quantum bit commitments following [Yan22].

###### Definition 2.5 (Canonical Quantum Bit Commitments [Yan22]).

A _canonical quantum bit commitment scheme_ consists of a family
$\\{Q_{0}(\lambda),Q_{1}(\lambda)\\}_{\lambda\in\mathbb{N}}$ of uniform QPT
unitaries. Each acts on two registers $\mathbf{C}$ (called the _commitment
register_) and $\mathbf{R}$ (called the _reveal register_). In the rest of the
paper, we often omit $\lambda$ and simply write $Q_{0}$ and $Q_{1}$ to mean
$Q_{0}(\lambda)$ and $Q_{1}(\lambda)$. We define two properties that can be
satisfied by canonical quantum bit commitments:

  * •

(Hiding) The scheme is _computationally (resp. statistically)
$\epsilon$-hiding_ if for any non-uniform QPT (resp. for any unbounded)
adversary $\mathcal{A}$, it holds that

$\displaystyle\left|\Pr\left[1\leftarrow\mathcal{A}\Bigl{(}1^{\lambda},\mathrm{Tr}_{\mathbf{R}}\bigl{(}(Q_{0}\ket{0}\\!\\!\bra{0}Q_{0}^{\dagger})_{\mathbf{C},\mathbf{R}}\bigr{)}\Bigr{)}\right]-\Pr\left[1\leftarrow\mathcal{A}\Bigl{(}1^{\lambda},\mathrm{Tr}_{\mathbf{R}}\bigl{(}(Q_{1}\ket{0}\\!\\!\bra{0}Q_{1}^{\dagger})_{\mathbf{C},\mathbf{R}}\bigr{)}\Bigr{)}\right]\right|\leq\epsilon(\lambda).$

We say that the scheme is _computationally (resp. statistically) hiding_ if
$\epsilon$ is negligible.

  * •

(Binding) The scheme is _computationally (resp. statistically)
$\delta$-binding_ if for any polynomial-size register $\mathbf{Z}$ and for any
non-uniform QPT (resp. for any unbounded) unitary $U_{\mathbf{R},\mathbf{Z}}$,
it holds that

$\displaystyle\left\|\bigl{(}(\bra{0}Q_{1}^{\dagger})_{\mathbf{C},\mathbf{R}}\otimes
I_{\mathbf{Z}}\bigr{)}\bigl{(}I_{\mathbf{C}}\otimes
U_{\mathbf{R},\mathbf{Z}}\bigr{)}\bigl{(}(Q_{0}\ket{0})_{\mathbf{C},\mathbf{R}}\otimes
I_{\mathbf{Z}}\bigr{)}\right\|\leq\delta(\lambda).$

We say that the scheme is _computationally (resp. statistically) binding_ if
$\delta$ is negligible.

Note that _statistical_ $\epsilon$-hiding can also be defined in terms of the
trace distance, as follows:

$\displaystyle\mathsf{TD}\Bigl{(}\mathrm{Tr}_{\mathbf{R}}\bigl{(}(Q_{0}\ket{0}\\!\\!\bra{0}Q_{0}^{\dagger})_{\mathbf{C},\mathbf{R}}\bigr{)},\mathrm{Tr}_{\mathbf{R}}\bigl{(}(Q_{1}\ket{0}\\!\\!\bra{0}Q_{1}^{\dagger})_{\mathbf{C},\mathbf{R}}\bigr{)}\Bigr{)}\leq\epsilon(\lambda).$
(2.1)

The following lemma is an immediate consequence of Uhlmann’s theorem.

###### Lemma 2.6.

EFI pairs exist if and only if there exists a canonical quantum bit commitment
scheme that is computationally hiding and statistically
$(1-1/{\mathsf{poly}}(\lambda))$-binding.333A very recent work [BQSY23] shows
that canonical quantum bit commitment schemes that satisfy computational
hiding and _computational_ $(1-1/{\mathsf{poly}}(\lambda))$-binding are
sufficient for constructing EFI pairs. We do not need this result.

It is known that binding and hiding of canonical quantum bit commitments can
be traded for each other [CLS01, Yan22, HMY23, GJMZ23]. In particular, the
following result was shown in [HMY23] (see also [HKNY23]).

###### Lemma 2.7 (Flavor Conversion for Quantum Bit Commitments [HMY23]).

If there exists a canonical quantum bit commitment scheme that is
statistically $\epsilon$-hiding and computationally binding, then there also
exists one that is computationally hiding and statistically
$\sqrt{\epsilon}$-binding.

Combining Lemmata 2.6 and 2.7, we obtain the following corollary.

###### Corollary 2.8.

If there exists a canonical quantum bit commitment scheme that is
statistically $(1-1/{\mathsf{poly}}(\lambda))$-hiding and computationally
binding, then EFI pairs exist.

##  3 Inefficiently-Verifiable One-Way State Generators (IV-OWSGs)

In this section, we define IV-OWSGs and the notion of exponential security. We
first recall the definition of OWSGs.444The original OWSGs introduced in
[MY22b] were defined to have pure state outputs, but this was later
generalized to allow for mixed state outputs [MY22a].

###### Definition 3.1 (OWSGs [MY22b, MY22a]).

A _one-way state generator (OWSG)_ is a triple
$(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Ver})$ of uniform QPT algorithms
with the following syntax:

  * •

$\mathsf{KeyGen}(1^{\lambda})\to k$: On input the security parameter
$\lambda$, this algorithm outputs a key $k\in\\{0,1\\}^{\lambda}$.

  * •

$\mathsf{StateGen}(k)\to\phi_{k}$: On input $k$, this algorithm outputs the
(possibly mixed) quantum state $\phi_{k}$.

  * •

$\mathsf{Ver}(k^{\prime},\phi)\to\\{\top,\bot\\}$: On input a bit string
$k^{\prime}$ and a quantum state $\phi$, this algorithm outputs $\top$ or
$\bot$.

We require the following two properties to hold.

  * •

(Correctness) There exists a negligible function ${\mathsf{negl}}$ such that:

$\displaystyle\Pr\left[\top\leftarrow\mathsf{Ver}(k,\phi_{k})\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
\phi_{k}\leftarrow\mathsf{StateGen}(k)\right]\geq 1-{\mathsf{negl}}(\lambda).$

  * •

(Security) For any non-uniform QPT adversary $\mathcal{A}$ and any polynomial
$t=t(\lambda)$, there exists a negligible function ${\mathsf{negl}}$ such that

$\displaystyle\Pr\left[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
\phi_{k}\leftarrow\mathsf{StateGen}(k),\
k^{\prime}\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t(\lambda)})\right]\leq{\mathsf{negl}}(\lambda).$

Now we introduce a new variant of OWSGs where we allow $\mathsf{Ver}$ to be
inefficient.

###### Definition 3.2 (IV-OWSGs).

An _inefficiently-verifiable one-way state generator (IV-OWSG)_ is defined
like a OWSG, except that the algorithm $\mathsf{Ver}$ is allowed to be
inefficient (need not be QPT).

We will also consider exponential security as defined below. The definition
applies to both OWSGs and IV-OWSGs.

###### Definition 3.3 (Exponential security of (IV-)OWSGs).

For a function $\delta\colon\mathbb{N}\to\mathbb{R}$, we say that an OWSG or
IV-OWSG is _$\delta$ -exponentially secure_ if

$\displaystyle\Pr\left[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
\phi_{k}\leftarrow\mathsf{StateGen}(k),\
k^{\prime}\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t(\lambda)})\right]\leq 2^{-\delta(\lambda)}$

for any non-uniform QPT adversary $\mathcal{A}$, any polynomial
$t=t(\lambda)$, and a large enough $\lambda$, possibly depending on the
adversary.

##  4 EFI Pairs Imply IV-OWSGs

In this section, we show that the existence of EFI pairs implies the existence
of IV-OWSGs, unconditionally and without any loss. For our proof, it will be
useful to recall the notion of secretly-verifiable and statistically-
invertible one-way state generators (SV-SI-OWSGs) as introduced in [MY22a].

###### Definition 4.1 (SV-SI-OWSGs [MY22a]).

A _secretly-verifiable and statistically-invertible one-way state generator
(SV-SI-OWSG)_ consists of a pair $(\mathsf{KeyGen},\mathsf{StateGen})$ of
uniform QPT algorithms with the following syntax.

  * •

$\mathsf{KeyGen}(1^{\lambda})\to k:$ On input the security parameter
$\lambda$, this algorithm outputs a key $k\in\\{0,1\\}^{\lambda}$.

  * •

$\mathsf{StateGen}(k)\to\phi_{k}:$ On input $k$, this algorithm outputs a
(possibly mixed) quantum state $\phi_{k}$.

We require the following two properties to hold:

  * •

(Statistical Invertibility) There exists a (not necessarily efficient) POVM
$\\{\Pi_{k}\\}_{k\in\\{0,1\\}^{\lambda}}$ such that
$\mathrm{Tr}(\Pi_{k}\phi_{k})\geq 1-{\mathsf{negl}}(\lambda)$ and
$\mathrm{Tr}(\Pi_{k^{\prime}}\phi_{k})\leq{\mathsf{negl}}(\lambda)$ for any
two keys $k\neq k^{\prime}$.

  * •

(Computational Non-Invertibility) For any non-uniform QPT adversary
$\mathcal{A}$ and any polynomial $t=t(\lambda)$, there exists a negligible
function ${\mathsf{negl}}$ such that

$\displaystyle\Pr[k\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t(\lambda)}):k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\phi_{k}\leftarrow\mathsf{StateGen}(k)]\leq{\mathsf{negl}}(\lambda).$

The following result was proved in the same paper.

###### Lemma 4.2 ([MY22a, Theorem 7.8]).

If EFI pairs exist, then SV-SI-OWSGs exist.

We are now ready to state and prove the main theorem of this section.

###### Theorem 4.3.

If EFI pairs exist, then IV-OWSGs exist.

###### Proof.

In view of Lemma 4.2 it suffices to show the existence of an IV-OWSG from a
SV-SI-OWSG. Let us thus assume that a SV-SI-OWSG
$(\mathsf{SVSI}.\mathsf{KeyGen},\allowbreak\mathsf{SVSI}.\mathsf{StateGen})$
exists. We construct an IV-OWSG
$(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Ver})$ as follows:

  * •

$\mathsf{KeyGen}(1^{\lambda})\to k:$ Run
$k\leftarrow\mathsf{SVSI}.\mathsf{KeyGen}(1^{\lambda})$ and output $k$.

  * •

$\mathsf{StateGen}(k)\to\phi_{k}:$ Run
$\phi_{k}\leftarrow\mathsf{SVSI}.\mathsf{StateGen}(k)$ and output $\phi_{k}$.

  * •

$\mathsf{Ver}(k^{\prime},\phi)\to\top/\bot:$ Measure $\phi$ with the POVM
$\\{\Pi_{k}\\}_{k\in\\{0,1\\}^{\lambda}}$ that exists by the statistical
invertibility. If the outcome is $k^{\prime}$ then output $\top$. Otherwise,
output $\bot$.

Correctness follows as an immediate consequence of the statistical
invertibility of the SV-SI-OWSG.

We now prove security. Let $\mathcal{A}$ be an arbitrary non-uniform QPT
algorithm and $t=t(\lambda)$ a polynomial. Then it holds that,

$\displaystyle\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k}):k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\phi_{k}\leftarrow\mathsf{StateGen}(k),k^{\prime}\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t})]$
$\displaystyle=\sum_{k}\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]\sum_{k^{\prime}}\Pr[k^{\prime}\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t})]\cdot\mbox{Tr}(\Pi_{k^{\prime}}\phi_{k})$
$\displaystyle=\sum_{k}\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]\Pr[k\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t})]\cdot\mbox{Tr}(\Pi_{k}\phi_{k})$
$\displaystyle\quad+\sum_{k}\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]\sum_{k^{\prime}\neq
k}\Pr[\alpha\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t})]\cdot\mbox{Tr}(\Pi_{k^{\prime}}\phi_{k})$
$\displaystyle\leq\sum_{k}\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]\Pr[k\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t})]$
$\displaystyle\quad+\sum_{k}\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]\sum_{\alpha\neq
k}\Pr[\alpha\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t})]\cdot{\mathsf{negl}}(\lambda)$
$\displaystyle\leq{\mathsf{negl}}(\lambda),$

where the first inequality follows by upper bounding
$\mbox{Tr}(\Pi_{k}\phi_{k})\leq 1$ and using the statistical invertibility of
the SV-SI-OWSG, and the second inequality uses the computational non-
invertibility of the SV-SI-OWSG. ∎

##  5 Exponentially-Secure IV-OWSGs Imply EFI Pairs

In this section, we show our main result, namely, the construction of EFI
pairs from exponentially-secure IV-OWSGs. Before stating our main theorem, we
first prove a useful lemma.

###### Lemma 5.1.

Let $(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Ver})$ be a
$\delta$-exponentially-secure IV-OWSG for some $\delta=\delta(\lambda)$. Let
$p=p(\lambda)$ be an arbitrary polynomial, and define for any $\lambda$ and
for any $k\in\\{0,1\\}^{\lambda}$,

$\displaystyle G_{k}\coloneqq
G_{k}(\lambda)\coloneqq\left\\{k^{\prime}\in\\{0,1\\}^{\lambda}\;:\;\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})]\geq
1-\frac{1}{p(\lambda)}\right\\}.$

Suppose that $r=r(\lambda)$ is a function that satisfies
$\delta(\lambda)+r(\lambda)\geq C\lambda$ for some constant $C>1$. Then there
exists a negligible function ${\mathsf{negl}}(\lambda)$ such that the
following holds:

$\displaystyle\Pr\left[1\leq\lvert G_{k}\rvert\leq
2^{r}\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\geq\Pr\left[k\in
G_{k}\wedge\lvert G_{k}\rvert\leq
2^{r}\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\geq
1-{\mathsf{negl}}(\lambda),$

###### Proof.

The correctness of the IV-OWSG implies that

$\displaystyle\Pr\left[\lvert
G_{k}\rvert<1:k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\leq
1-\Pr\left[k\in
G_{k}:k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\leq{\mathsf{negl}}(\lambda).$

It remains to show that the upper bound $\lvert G_{k}\rvert\leq 2^{r}$ holds
for all but a negligible fraction of $k$ as well. To this end we consider the
following trivial attack against the IV-OWSG:555It works even for $t=0$. On
input $\phi_{k}^{\otimes t}$, ignore the state, sample
$k^{\prime}\leftarrow\\{0,1\\}^{\lambda}$, and output $k^{\prime}$. By the
$\delta$-exponential security of the IV-OWSG, the winning probability of this
attack is at most

$\displaystyle\Pr\left[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
\phi_{k}\leftarrow\mathsf{StateGen}(k),\
k^{\prime}\leftarrow\\{0,1\\}^{\lambda}\right]\leq 2^{-\delta(\lambda)}.$

In other words:

$\displaystyle\sum_{k,k^{\prime}}\Pr[k]2^{-\lambda}\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})]\leq
2^{-\delta(\lambda)},$ (5.1)

where $\Pr[k]\coloneqq\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]$. Let us
define the set of keys for which the desired bound is not satisfied

$\displaystyle T\coloneqq
T(\lambda)\coloneqq\left\\{k\in\\{0,1\\}^{\lambda}\;:\;|G_{k}|>2^{r(\lambda)}\right\\}.$

Then we can rewrite Equation 5.1 as follows:

$\displaystyle 2^{-{\delta(\lambda)}}$
$\displaystyle\geq\sum_{k,k^{\prime}}\Pr[k]2^{-\lambda}\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})]$
$\displaystyle\geq\sum_{k\in T}\Pr[k]\sum_{k^{\prime}\in
G_{k}}2^{-\lambda}\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})]$
$\displaystyle\geq\sum_{k\in T}\Pr[k]\ \lvert G_{k}\rvert\
2^{-\lambda}\left(1-\frac{1}{p(\lambda)}\right)$ $\displaystyle\geq\sum_{k\in
T}\Pr[k]\ 2^{r(\lambda)}\ 2^{-\lambda}\left(1-\frac{1}{p(\lambda)}\right).$

Rearranging, we obtain that

$\displaystyle\Pr\left[\lvert
G_{k}\rvert>2^{r(\lambda)}:k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]=\sum_{k\in
T}\Pr[k],$

which is negligible since $\delta(\lambda)+r(\lambda)\geq C\lambda$, for some
$C>1$. ∎

We are now ready to show the main theorem of this section.

###### Theorem 5.2.

For any constant $D>0$ the following holds. If $\delta$-exponentially secure
IV-OWSGs exist with $\delta(\lambda)\geq(0.5+D)\lambda$, then EFI pairs exist.

###### Proof.

Assume that an IV-OWSG $(\mathsf{KeyGen},\mathsf{StateGen},\mathsf{Ver})$
exists. By Corollary 2.8, it suffices to show that there exists a canonical
quantum bit commitment scheme that is statistically
$(1-1/{\mathsf{poly}}(\lambda))$-hiding and computationally binding. To
prepare the construction of the bit commitment scheme, we make the following
structural observations:

  * •

Without loss of generality, we may assume that the $\mathsf{KeyGen}$ algorithm
applies a QPT unitary to generate a superposition
$\sum_{k}\sqrt{\Pr[k]}\ket{k}\ket{\mathrm{junk}_{k}}$, measures the first
register, and outputs the result.

  * •

Similarly, we can assume that the $\mathsf{StateGen}(k)$ algorithm applies a
QPT unitary to generate a pure state $\ket{\Phi_{k}}_{\mathbf{A},\mathbf{B}}$
and outputs the register $\mathbf{A}$, which is in state
$\phi_{k}=\mathrm{Tr}_{\mathbf{B}}(\ket{\Phi_{k}}\\!\\!\bra{\Phi_{k}}_{\mathbf{A},\mathbf{B}})$.

Let $\mathcal{H}\coloneqq\\{h:\mathcal{X}\to\mathcal{Y}\\}$ be a family of
pairwise independent hash functions such that
$\mathcal{X}\coloneqq\\{0,1\\}^{\lambda}$ and
$\mathcal{Y}\coloneqq\\{1,\dots,2\lfloor 2^{r(\lambda)}\rfloor\\}$, where
$r(\lambda)\coloneqq(0.5+\frac{D}{2})\lambda$. Let us also denote by
$t(\lambda)$ a polynomial that will be chosen later in the proof. Then we can
define the following two states, which we shall think of being the commitments
of $0$ and $1$, respectively:

$\displaystyle\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}}$
$\displaystyle\coloneqq\sum_{k}\sum_{h\in\mathcal{H}}\sqrt{\frac{\Pr[k]}{|\mathcal{H}|}}\ket{k,\mathrm{junk}_{k},h}_{\mathbf{C}_{1}}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}$
$\displaystyle\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}}$
$\displaystyle\coloneqq\sum_{k}\sum_{h\in\mathcal{H}}\sqrt{\frac{\Pr[k]}{|\mathcal{H}|}}\ket{k,\mathrm{junk}_{k},h}_{\mathbf{C}_{1}}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{k}_{\mathbf{R}_{3}},$

where $\Pr[k]\coloneqq\Pr[k\leftarrow\mathsf{KeyGen}(1^{\lambda})]$. We denote
by $\mathbf{C}\coloneqq(\mathbf{C}_{1},\mathbf{C}_{2})$ the commitment
register and by
$\mathbf{R}\coloneqq(\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{R}_{3})$ the reveal
register. Note that
$\mathbf{C}_{2}\coloneqq(\mathbf{B}_{1},\dots,\mathbf{B}_{t})$ and
$\mathbf{R}_{2}\coloneqq(\mathbf{A}_{1},\dots,\mathbf{A}_{t})$, where the
$j$-th copy of $\ket{\Phi_{k}}$ lives on registers
$\mathbf{A}_{j},\mathbf{B}_{j}$. By construction, both $\ket{\psi_{0}}$ and
$\ket{\psi_{1}}$ can be generated by QPT unitaries. In the following we show
that the scheme is statistically $(1-1/{\mathsf{poly}}(\lambda))$-hiding and
computationally binding.

#### Computational binding.

Towards a contradiction, we assume that our construction is not
computationally binding. This means that there exists a polynomial
$q=q(\lambda)$, an advice quantum state $\ket{\tau}_{\mathbf{Z}}$ on a
polynomially-sized register $\mathbf{Z}$, and a non-uniform QPT unitary $U$
acting on $\mathbf{R}$ and $\mathbf{Z}$ such that

$\displaystyle\|\bra{\psi_{1}}_{\mathbf{C},\mathbf{R}}(I_{\mathbf{C}}\otimes
U_{\mathbf{R},\mathbf{Z}})(\ket{\psi_{0}}_{\mathbf{C},\mathbf{R}}\otimes\ket{\tau}_{\mathbf{Z}})\|^{2}\geq\frac{1}{q(\lambda)}$

for infinitely many $\lambda$. This means that, abbreviating $t=t(\lambda)$,

$\displaystyle\frac{1}{q(\lambda)}$
$\displaystyle\leq\left\|\sum_{k,h}\frac{\Pr[k]}{|\mathcal{H}|}\bra{h,h(k)}_{\mathbf{R}_{1}}\bra{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle\leq\left(\sum_{k,h}\frac{\Pr[k]}{|\mathcal{H}|}\left\|\bra{h,h(k)}_{\mathbf{R}_{1}}\bra{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|\right)^{2}$
$\displaystyle\leq\sum_{k,h}\frac{\Pr[k]}{|\mathcal{H}|}\left\|\bra{h,h(k)}_{\mathbf{R}_{1}}\bra{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle\leq\sum_{k,h}\frac{\Pr[k]}{|\mathcal{H}|}\left\|\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle\leq\sum_{k\in
G,h}\frac{\Pr[k]}{|\mathcal{H}|}\left\|\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle+\sum_{k\notin
G,h}\frac{\Pr[k]}{|\mathcal{H}|}\left\|\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle\leq\sum_{k\in
G,h}\frac{\Pr[k]}{|\mathcal{H}|}\left\|\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}+{\mathsf{negl}}(\lambda).$
(5.2)

Here, in the second inequality we have used the triangle inequality, and in
the third inequality we have used Jensen’s inequality. $G$ is a set defined as

$\displaystyle
G\coloneqq\left\\{k\in\\{0,1\\}^{\lambda}:\Pr[\top\leftarrow\mathsf{Ver}(k,\phi_{k})]\geq\frac{1}{2}\right\\}.$
(5.3)

Due to the correctness of the IV-OWSG, we have $\sum_{k\not\in
G}\Pr[k]\leq{\mathsf{negl}}(\lambda)$.

From such $\ket{\tau}$ and $U$, we can construct a non-uniform QPT adversary
$\mathcal{A}$ that breaks the security of the IV-OWSG as follows:

  1. 1.

The algorithm gets as input the $\mathbf{R}_{2}$ register of
$\ket{\Phi_{k}^{\otimes t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}$ and the
$\mathbf{Z}$ register containing the advice state $\ket{\tau}_{\mathbf{Z}}$.

  2. 2.

Choose $h\leftarrow\mathcal{H}$. Choose $y\leftarrow\mathcal{Y}$.

  3. 3.

Apply $(I_{\mathbf{C}_{2}}\otimes U_{\mathbf{R},\mathbf{Z}})$ on
$\ket{h,y}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}$.

  4. 4.

Measure the register $\mathbf{R}_{3}$ in the computational basis, and output
the result.

The probability that $\mathcal{A}$ outputs $k$ and $k\in G$ can then be lower
bounded as

$\displaystyle\Pr\left[k\in G\wedge
k\leftarrow\mathcal{A}(1^{\lambda},\phi_{k}^{\otimes
t(\lambda)})\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
\phi_{k}\leftarrow\mathsf{StateGen}(k)\right]$ $\displaystyle=\sum_{k\in
G}\Pr[k]\sum_{h,y}\frac{1}{|\mathcal{H}|\cdot|\mathcal{Y}|}\left\|\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,y}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle=\sum_{k\in
G,h}\frac{\Pr[k]}{|\mathcal{H}|}\sum_{y}\frac{1}{2\lfloor
2^{r(\lambda)}\rfloor}\left\|\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{2}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,y}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle\geq\sum_{k\in G,h}\frac{\Pr[k]}{|\mathcal{H}|}\frac{1}{2\lfloor
2^{r(\lambda)}\rfloor}\left\|\bra{k}_{\mathbf{R}_{3}}(I_{\mathbf{C}_{3}}\otimes
U_{\mathbf{R},\mathbf{Z}})\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0...0}_{\mathbf{R}_{3}}\ket{\tau}_{\mathbf{Z}}\right\|^{2}$
$\displaystyle\geq\frac{1}{4q(\lambda)\lfloor 2^{r(\lambda)}\rfloor},$

where the first inequality is obtained by only keeping the term $y=h(k)$, and
the last inequality is from Equation 5.2. Hence, the probability that
$\mathcal{A}$ wins is lowerbounded by $\frac{1}{8q(\lambda)\lfloor
2^{r(\lambda)}\rfloor}$.

We claim that this is larger than $2^{-\delta(\lambda)}$, in contradiction to
the $\delta$-exponential security of the IV-OWSG. Indeed, we have

$\displaystyle\frac{1}{8q(\lambda)\lfloor
2^{r(\lambda)}\rfloor}-\frac{1}{2^{\delta(\lambda)}}=\frac{2^{\delta(\lambda)}-8q(\lambda)\lfloor
2^{r(\lambda)}\rfloor}{8q(\lambda)2^{\delta(\lambda)}\lfloor
2^{r(\lambda)}\rfloor}\geq\frac{2^{\delta(\lambda)}-8q(\lambda)2^{r(\lambda)}}{8q(\lambda)2^{\delta(\lambda)}\lfloor
2^{r(\lambda)}\rfloor}\geq\frac{2^{(0.5+D)\lambda}-8q(\lambda)2^{(0.5+\frac{D}{2})\lambda}}{8q(\lambda)2^{\delta(\lambda)}\lfloor
2^{r(\lambda)}\rfloor}>0$

for infinitely many $\lambda$. Thus we have obtained the desired
contradiction, and we may conclude that our bit commitment scheme is
computationally binding.

#### Statistical hiding.

We first describe an (inefficient) algorithm that, given
$\ket{h,h(k)}_{\mathbf{R}_{1}}$ and the $\mathbf{R}_{2}$ register of
$\ket{\Phi_{k}^{\otimes t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}$, for
$k\leftarrow\mathsf{KeyGen}(1^{\lambda})$ and $h\leftarrow\mathcal{H}$,
outputs the key $k$ with not too small probability:

  1. 1.

Apply the shadow tomography procedure on the $\mathbf{R}_{2}$ register of
$\ket{\Phi_{k}^{\otimes t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}$ to
obtain an estimate $b_{k^{\prime}}$ of
$\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})]$ with additive error
$\varepsilon=1/8$ for all $k^{\prime}\in\\{0,1\\}^{\lambda}$, with failure
probability at most $\omega=2^{-\lambda}$. Compute the list
$\mathcal{L}\coloneqq\\{k^{\prime}\in\\{0,1\\}^{\lambda}:b_{k^{\prime}}\geq
3/4\\}$.

  2. 2.

Read $(h,h(k))$ from $\mathbf{R}_{1}$. Compute $h(k^{\prime})$ for each
$k^{\prime}$ in the list $\mathcal{L}$. If there is only a single $k^{*}$ in
the list such that $h(k^{*})=h(k)$, output $k^{*}$. Otherwise, output $\bot$.

By Theorem 2.3, the first step is possible if we choose $t(\lambda)$ to be a
large enough polynomial. Then, with probability at least
$1-\omega=1-{\mathsf{negl}}(\lambda)$, the list $\mathcal{L}$ computed in the
first step satisfies

$\displaystyle\left\\{k^{\prime}\in\\{0,1\\}^{\lambda}:\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})]\geq\frac{7}{8}\right\\}\subseteq\mathcal{L}\subseteq
G_{k},$ (5.4)

where
$G_{k}=\left\\{k^{\prime}\in\\{0,1\\}^{\lambda}:\Pr[\top\leftarrow\mathsf{Ver}(k^{\prime},\phi_{k})]\geq\frac{1}{2}\right\\}$
is the set defined in Lemma 5.1. By the correctness of the IV-OWSG, it holds
that, except for a negligible fraction of $k$,
$\Pr[\top\leftarrow\mathsf{Ver}(k,\phi_{k})]\geq\frac{7}{8}$ holds for
sufficiently large $\lambda$, in which case the first inclusion implies that
$k\in\mathcal{L}$. This means that we have

$\displaystyle\Pr\left[k\in\mathcal{L}\subseteq
G_{k}:k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\geq
1-{\mathsf{negl}}(\lambda).$ (5.5)

We claim that the second step will return $k$ with not too small probability.
To see this, we first note that for any fixed set
$G\subseteq\\{0,1\\}^{\lambda}$ and for any fixed $x\in G$, it holds that

$\displaystyle\Pr_{h\leftarrow\mathcal{H}}\left[\lvert G\cap
h^{-1}(h(x))\rvert=1\right]$
$\displaystyle=1-\Pr_{h\leftarrow\mathcal{H}}\left[\bigvee_{x^{\prime}\in
G,x^{\prime}\neq x}h(x^{\prime})=h(x)\right]$ $\displaystyle\geq
1-\sum_{x^{\prime}\in G,x^{\prime}\neq
x}\Pr_{h\leftarrow\mathcal{H}}\left[h(x^{\prime})=h(x)\right]=1-\frac{|G|-1}{|\mathcal{Y}|}$

due to the pairwise independence of the family of hash functions and the union
bound. Thus,

$\displaystyle\quad\Pr\left[\mathcal{L}\cap
h^{-1}(h(k))=\\{k\\}:k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
h\leftarrow\mathcal{H}\right]$ $\displaystyle=\Pr\left[\lvert\mathcal{L}\cap
h^{-1}(h(k))\rvert=1,\
k\in\mathcal{L}\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
h\leftarrow\mathcal{H}\right]$ $\displaystyle\geq\Pr\left[\lvert G_{k}\cap
h^{-1}(h(k))\rvert=1,\ k\in\mathcal{L}\subseteq
G_{k}\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\
h\leftarrow\mathcal{H}\right]$
$\displaystyle\geq\Pr_{h\leftarrow\mathcal{H}}\left[\lvert G_{k}\cap
h^{-1}(h(k))\rvert=1,\ k\in
G_{k}\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\left(1-{\mathsf{negl}}(\lambda)\right)$
$\displaystyle\geq\Pr_{h\leftarrow\mathcal{H}}\left[\lvert G_{k}\cap
h^{-1}(h(k))\rvert=1,\ k\in G_{k},\ |G_{k}|\leq
2^{r(\lambda)}\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\left(1-{\mathsf{negl}}(\lambda)\right)$
$\displaystyle\geq\Pr_{h\leftarrow\mathcal{H}}\left[\lvert G_{k}\cap
h^{-1}(h(k))\rvert=1\;:\;k\leftarrow\mathsf{KeyGen}(1^{\lambda}),\ k\in
G_{k},\ |G_{k}|\leq
2^{r(\lambda)}\right]\left(1-{\mathsf{negl}}(\lambda)\right)^{2}$
$\displaystyle\geq\left(1-\frac{2^{r(\lambda)}-1}{2\lfloor
2^{r(\lambda)}\rfloor}\right)\left(1-{\mathsf{negl}}(\lambda)\right)\geq\frac{1}{2}-{\mathsf{negl}}(\lambda),$

where the second inequality uses Equation 5.5 and the fact that $h$ and
$\mathcal{L}$ are independent conditioned on $k$, the fourth inequality uses
Lemma 5.1, and the last line follows from the bound derived above. We conclude
that the algorithm returns the correct key with probability at least
$\frac{1}{2}-{\mathsf{negl}}(\lambda)$.

We may summarize the above as saying that there exists an (inefficient) POVM
measurement
$\\{\Pi_{\mathbf{R}_{1},\mathbf{R}_{2}}^{(\alpha)}\\}_{\alpha\in\\{0,1\\}^{\lambda}\cup\\{\bot\\}}$
such that

$\sum_{k}\sum_{h\in\mathcal{H}}\frac{\Pr[k]}{|\mathcal{H}|}\bra{h,h(k)}_{\mathbf{R}_{1}}\bra{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\Pi_{\mathbf{R}_{1},\mathbf{R}_{2}}^{(k)}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\geq\frac{1}{2}-{\mathsf{negl}}(\lambda).$
(5.6)

This implies that there is an (inefficient) unitary
$U_{\mathbf{G},\mathbf{Z}}$ that sends
$\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}}\ket{0}_{\mathbf{Z}}$ to a state with
not too small overlap with
$\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}}\ket{0}_{\mathbf{Z}}$. To see this,
choose a unitary $V_{\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{Z}}$ that extends
the Naimark dilation
$V_{\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{Z}}\ket{0}_{\mathbf{Z}}=\sum_{\alpha}(\Pi_{\mathbf{R}_{1},\mathbf{R}_{2}}^{(\alpha)})^{1/2}\otimes\ket{\alpha}_{\mathbf{Z}}$
of the POVM measurement, and define $U_{\mathbf{G},\mathbf{Z}}\coloneqq
V_{\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{Z}}^{\dagger}{\mathrm{CNOT}}_{\mathbf{Z}\to\mathbf{R}_{3}}V_{\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{Z}}$.
Then it holds that

$\displaystyle\quad\bra{\psi_{1}}_{\mathbf{R},\mathbf{C}}\bra{0}_{\mathbf{Z}}U_{\mathbf{R},\mathbf{Z}}\ket{\psi_{0}}_{\mathbf{R},\mathbf{C}}\ket{0}_{\mathbf{Z}}$
$\displaystyle=\sum_{k}\sum_{h\in\mathcal{H}}\frac{\Pr[k]}{|\mathcal{H}|}\bra{h,h(k)}_{\mathbf{R}_{1}}\bra{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\bra{k}_{\mathbf{R}_{3}}\bra{0}_{\mathbf{Z}}U_{\mathbf{R},\mathbf{Z}}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\ket{0}_{\mathbf{R}_{3}}\ket{0}_{\mathbf{Z}}$
$\displaystyle=\sum_{k}\sum_{h\in\mathcal{H}}\frac{\Pr[k]}{|\mathcal{H}|}\sum_{\alpha,\beta}\bra{h,h(k)}_{\mathbf{R}_{1}}\bra{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\sqrt{\Pi_{\mathbf{R}_{1},\mathbf{R}_{2}}^{(\alpha)}}\bra{\alpha,k}_{\mathbf{Z},\mathbf{R}_{3}}{\mathrm{CNOT}}_{\mathbf{Z}\to\mathbf{R}_{3}}\ket{\beta,0}_{\mathbf{Z},\mathbf{R}_{3}}$
$\displaystyle\qquad\qquad\qquad\qquad\quad\sqrt{\Pi_{\mathbf{R}_{1},\mathbf{R}_{2}}^{(\beta)}}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}$
$\displaystyle=\sum_{k}\sum_{h\in\mathcal{H}}\frac{\Pr[k]}{|\mathcal{H}|}\bra{h,h(k)}_{\mathbf{R}_{1}}\bra{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}\Pi_{\mathbf{R}_{1},\mathbf{R}_{2}}^{(k)}\ket{h,h(k)}_{\mathbf{R}_{1}}\ket{\Phi_{k}^{\otimes
t(\lambda)}}_{\mathbf{C}_{2},\mathbf{R}_{2}}$
$\displaystyle\geq\frac{1}{2}-{\mathsf{negl}}(\lambda),$

where the last step is due to Equation 5.6. Hence

$\displaystyle\left|\bra{\psi_{1}}_{\mathbf{R},\mathbf{C}}\bra{0}_{\mathbf{Z}}U_{\mathbf{R},\mathbf{Z}}\ket{\psi_{1}}_{\mathbf{R},\mathbf{C}}\ket{0}_{\mathbf{Z}}\right|^{2}\geq\frac{1}{4}-{\mathsf{negl}}(\lambda).$

By Uhlmann’s theorem, it follows that the reduced states
$\rho_{b}\coloneqq\mathrm{Tr}_{\mathbf{R}}(\ket{\psi_{b}}\\!\\!\bra{\psi_{b}}_{\mathbf{R},\mathbf{C}})$
have fidelity

$F(\rho_{0},\rho_{1})\geq\frac{1}{4}-{\mathsf{negl}}(\lambda),$

and hence their trace distance is at most

$\mathsf{TD}(\rho_{0},\rho_{1})\leq\sqrt{\frac{3}{4}}+{\mathsf{negl}}(\lambda).$

In view of Equation 2.1 this implies that the scheme is statistically
$(\sqrt{\frac{3}{4}}+{\mathsf{negl}}(\lambda))$-hiding, which in particular
means that it is statistically $(1-1/{\mathsf{poly}}(\lambda))$-hiding. This
completes the proof of Theorem 5.2. ∎

### Acknowledgements

GM was supported by the European Research Council through an ERC Starting
Grant (Grant agreement No. 101077455, ObfusQation). GM and MW acknowledge
support by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) under Germany’s Excellence Strategy - EXC 2092 CASA - 390781972.
MW also acknowledges support by the European Research Council through an ERC
Starting Grant (grant agreement No. 101040907, SYMOPTIC), by the NWO through
grant OCENW.KLEIN.267, and by the BMBF through project Quantum Methods and
Benchmarks for Resource Allocation (QuBRA). TM is supported by JST CREST
JPMJCR23I3, JST Moonshot JPMJMS2061-5-1-1, JST FOREST, MEXT QLEAP, the Grant-
in Aid for Transformative Research Areas (A) 21H05183, and the Grant-in-Aid
for Scientific Research (A) No.22H00522.

## References

  * [Aar19] Scott Aaronson.  Shadow tomography of quantum states.  SIAM J. Comput., 49(5):STOC18–368, 2019.
  * [AQY22] Prabhanjan Ananth, Luowen Qian, and Henry Yuen.  Cryptography from pseudorandom quantum states.  LNCS, pages 208–236. Springer, Heidelberg, 2022.
  * [BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian.  On the computational hardness needed for quantum cryptography.  ITCS 2023, 2023.
  * [BQSY23] John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen.  An efficient quantum parallel repetition theorem and applications, 2023.
  * [CLS01] Claude Crépeau, Frédéric Légaré, and Louis Salvail.  How to convert the flavor of a quantum bit commitment.  In Birgit Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 60–77. Springer, Heidelberg, May 2001.
  * [GJMZ23] Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry.  Commitments to quantum states.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1579–1588. ACM, 2023.
  * [Gol90] Oded Goldreich.  A note on computational indistinguishability.  Information Processing Letters 34.6 (1990), pp.277–281., 1990.
  * [HKNY23] Taiga Hiroka, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Robust combiners and universal constructions for quantum cryptography, 2023.
  * [HMY23] Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa.  From the hardness of detecting superpositions to cryptography: Quantum public key encryption and commitments.  LNCS, pages 639–667. Springer, Heidelberg, 2023.
  * [IL89] Russell Impagliazzo and Michael Luby.  One-way functions are essential for complexity based cryptography (extended abstract).  In 30th FOCS, pages 230–235. IEEE Computer Society Press, October / November 1989.
  * [ILL89] Russell Impagliazzo, Leonid A. Levin, and Michael Luby.  Pseudo-random generation from one-way functions (extended abstracts).  In 21st ACM STOC, pages 12–24. ACM Press, May 1989.
  * [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song.  Pseudorandom quantum states.  In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Heidelberg, August 2018.
  * [KQST23] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal.  Quantum cryptography in algorithmica.  STOC, 2023.
  * [Kre21] W. Kretschmer.  Quantum pseudorandomness and classical complexity.  TQC 2021, 2021.
  * [KT23] Dakshita Khurana and Kabir Tomer.  Commitments from quantum one-wayness.  Cryptology ePrint Archive, Paper 2023/1620, 2023.  https://eprint.iacr.org/2023/1620.
  * [LMW23] Alex Lombardi, Fermi Ma, and John Wright.  A one-query lower bound for unitary synthesis and breaking quantum cryptography.  Cryptology ePrint Archive, Paper 2023/1602, 2023.  https://eprint.iacr.org/2023/1602.
  * [LR86] Michael Luby and Charles Rackoff.  Pseudo-random permutation generators and cryptographic composition.  In 18th ACM STOC, pages 356–363. ACM Press, May 1986.
  * [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.  LNCS, pages 269–295. Springer, Heidelberg, 2022.
  * [Yan22] Jun Yan.  General properties of quantum bit commitments (extended abstract).  LNCS, pages 628–657. Springer, Heidelberg, 2022.