include (but not limited to) OWFs, public key encryption, digital signatures,
oblivious transfers indistinguishability obfuscation etc. On the other hand,
we note that it does not capture concrete assumptions such as the hardness of
factoring, discrete-logarithm, LWE etc. unlike game-based assumptions defined
in Definition 7.1. Similarly to game-based assumptions, semantical
cryptographic primitives do not capture knowledge-type assumptions or zero-
knowledge proofs (with non-black-box zero-knowledge).

Next, we define secure implementation relative to oracles following [RTV04].

###### Definition 7.11 (Secure implementation relative to oracles [RTV04,
Definition 2.2]).

A quantumly-secure implementation of primitive $\mathtt{P}$ exists relative to
an oracle $O$ if there exists an implementation of $f$ of $\mathtt{P}$ which
is computable by a PPT oracle machine with access to $O$ and such that no QPT
oracle machine with access to $O$ $\mathtt{P}$-breaks $f$.

######  Remark 7.12 (Example).

A quantumly-secure implementation of OWFs and collision-resistant hash
functions exists relative to a random oracle [BBBV97, Zha15]. [HY20]
implicitly proves that quantumly-secure implementation of trapdoor-
permutations exist relative to a classical oracle. We believe that we can
prove similar statements for most cryptographic primitives by appropriately
defining oracles.

Now, we are ready to state the formal version of Theorem 1.9.

###### Theorem 7.13.

Suppose that a semantical cryptographic primitive
$\mathtt{P}=(F_{\mathtt{P}},R_{\mathtt{P}})$ has a quantumly-secure
implementation relative to a classical oracle. Then there is a randomized
classical oracle relative to which two-round AI-IV-PoQ do not exist but a
quantumly-secure implementation of $\mathtt{P}$ exists.

######  Remark 7.14.

If we assume that a quantumly-secure implementation of a semantical
cryptographic primitive $\mathtt{P}$ exists in the unrelativized world, then
the assumption of the theorem is trivially satisfied relative to a trivial
oracle that does nothing. Thus, the above theorem can be understood as a
negative result on constructing two-round AI-IV-PoQ from any primitive whose
quantumly-secure implementation is believed to exist.

###### Proof.

Let $f$ be a quantumly-secure implementation of $\mathtt{P}$ relative to a
classical oracle $O$. Let $Q^{O}$ be a randomized oracle that takes a
description of an $n$-qubit input quantum circuit $C^{O}$ with $O$-gates and a
classical string $x\in\\{0,1\\}^{n}$ as input and returns a classical string
according to the distribution of $C^{O}(x)$. We prove that AI-IV-PoQ do not
exist but $f$ is a quantumly-secure implementation relative to oracles
$(O,C^{O})$.

Let $\Pi=(\mathcal{P},\mathcal{V}=(\mathcal{V}_{1},\mathcal{V}_{2}))$ be an
AI-IV-PoQ that satisfies $s$-soundness relative to $(O,Q^{O})$. Since $Q^{O}$
is simulatable in QPT with oracle access to $O$, given the auxiliary input
$\sigma$, one can generate a description of quantum circuit $C^{O}$ with
$O$-gates that simulates $\mathcal{P}^{O,Q^{O}}(\sigma)$ in a classical
polynomial time. Then let us consider a classical cheating prover
$\mathcal{P}^{*}$ relative to the oracles $(O,R^{O})$ that works as follows:
Receiving the auxiliary input $\sigma$ and the first-round message $m_{1}$
from the external verifier, $\mathcal{P}^{*}$ generates the above quantum
circuit $C^{O}$, queries $(C^{O},m_{1})$ to the oracle $Q^{O}$ to receive the
response $m_{2}$, and send $m_{2}$ to the external verifier. Clearly,
$\mathcal{P}^{*}$ passes the verification with the same probability as
$\mathcal{P}$ does. Therefore, $\Pi$ cannot satisfy $c$-soundness for any
$c<s$. This means that there is no AI-IV-PoQ relative to $(O,Q^{O})$.

On the other hand, if $f$ is not a quantumly-secure implementation of
$\mathtt{P}$ relative to $(O,R^{O})$, then there is a QPT oracle-aided machine
$M$ such that $(f,M^{O,Q^{O}})\in R_{\mathtt{P}}$. Again, since $Q^{O}$ is
simulatable in QPT with oracle access to $O$, there is a QPT oracle-aided
machine $\widetilde{M}$ such that $M^{O,Q^{O}}$ and $\widetilde{M}^{O}$ induce
the same output distributions. Since $\mathtt{P}$ is semantical, we have
$(f,\widetilde{M}^{O})\in R_{\mathtt{P}}$. This contradicts the assumption
that $f$ is a quantumly-secure implementation of $\mathtt{P}$ relative to $O$.
Therefore, $f$ is a quantumly-secure implementation of $\mathtt{P}$ relative
to $(O,R^{O})$.

∎

##  8 Variants of PoQ from QE-OWFs

###### Definition 8.1 (QE-OWFs).

A function $f:\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ is a (classically-secure)
quantum-evaluation OWF (QE-OWF) if the following two properties are satisfied.

  * •

There exists a QPT algorithm $\mathsf{QEval}$ such that
$\Pr[f(x)\leftarrow\mathsf{QEval}(x)]\geq 1-2^{-|x|}$ for all
$x\in\\{0,1\\}^{*}$.232323Actually the threshold can be any value larger than
1/2, because the amplification is possible.

  * •

For any PPT adversary $\mathcal{A}$, there exists a negligible function
${\mathsf{negl}}$ such that for any $\lambda$,

$\Pr[f(x^{\prime})=f(x):x^{\prime}\leftarrow\mathcal{A}(1^{\lambda},f(x)),x\leftarrow\\{0,1\\}^{\lambda}]\leq{\mathsf{negl}}(\lambda).$
(142)

######  Remark 8.2.

It is usually useless to consider OWFs whose evaluation algorithm is QPT but
the security is against PPT adversaries. However, for our applications,
classical security is enough. We therefore consider the classically-secure QE-
OWFs, because it only makes our result stronger.

Before explaining our construction of variants of PoQ from QE-OWFs, we point
out that QE-OWFs seems to be weaker than classically-secure and classical-
evaluation OWFs. Let $g$ be a classically-secure and classical-evaluation OWF.
Let $L$ be any language in $\mathbf{BQP}$. From them, we construct the
function $f$ as follows: $f(x,y)\coloneqq L(x)\|g(y)$, where $L(x)=1$ if $x\in
L$ and $L(x)=0$ if $x\notin L$. Then we have the following lemma.

###### Lemma 8.3.

$f$ is QE-OWFs. Moreover, if $\mathbf{BQP}\neq\mathbf{BPP}$, $f$ cannot be
evaluated in classical polynomial-time.

###### Proof.

First, it is clear that there exists a QPT algorithm $\mathsf{QEval}$ such
that for any $x,y$

$\Pr[f(x,y)\leftarrow\mathsf{QEval}(x,y)]\geq 1-2^{-|x\|y|}.$ (143)

Second, let us show the one-wayness of $f$. Assume that it is not one-way.
Then, there exists a PPT adversary $\mathcal{A}$ and a polynomial $p$ such
that

$\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\frac{1}{2^{m}}\sum_{y\in\\{0,1\\}^{m}}\Pr[L(x)=L(x^{\prime})\wedge
g(y)=g(y^{\prime}):(x^{\prime},y^{\prime})\leftarrow\mathcal{A}(L(x)\|g(y))]\geq\frac{1}{p}.$
(144)

From this $\mathcal{A}$, we can construct a PPT adversary $\mathcal{B}$ that
breaks the one-wayness of $g$ as follows.

  1. 1.

On input $g(y)$, sample $x\leftarrow\\{0,1\\}^{n}$ and $b\leftarrow\\{0,1\\}$.

  2. 2.

Run $(x^{\prime},y^{\prime})\leftarrow\mathcal{A}(b\|g(y))$.

  3. 3.

Output $y^{\prime}$.

The probability that $\mathcal{B}$ breaks the one-wayness of $g$ is

$\displaystyle\frac{1}{2^{m}}\sum_{y\in\\{0,1\\}^{m}}\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\frac{1}{2}\sum_{b\in\\{0,1\\}}\sum_{x^{\prime},y^{\prime}}\Pr[(x^{\prime},y^{\prime})\leftarrow\mathcal{A}(b\|g(y))]\delta_{g(y),g(y^{\prime})}$
(145)
$\displaystyle\geq\frac{1}{2}\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\frac{1}{2^{m}}\sum_{y\in\\{0,1\\}^{m}}\sum_{x^{\prime},y^{\prime}}\Pr[(x^{\prime},y^{\prime})\leftarrow\mathcal{A}(L(x)\|g(y))]\delta_{g(y),g(y^{\prime})}$
(146)
$\displaystyle\geq\frac{1}{2}\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\frac{1}{2^{m}}\sum_{y\in\\{0,1\\}^{m}}\sum_{x^{\prime},y^{\prime}}\Pr[(x^{\prime},y^{\prime})\leftarrow\mathcal{A}(L(x)\|g(y))]\delta_{g(y),g(y^{\prime})}\delta_{L(x),L(x^{\prime})}$
(147) $\displaystyle\geq\frac{1}{2p},$ (148)

which is non-negligible.

Finally, it is clear that if there exists a PPT algorithm that computes
$f(x,y)$ for any $x,y$ with probability at least $1-2^{-|x\|y|}$, then the
algorithm can solve $L$, which contradicts $\mathbf{BQP}\neq\mathbf{BPP}$. ∎

Now we show the main result of this section.

###### Theorem 8.4.

If (classically-secure) QE-OWFs exist, then QV-PoQ exist or (classically-
secure and classical-evaluation) infinitely-often OWFs exist.

###### Proof.

Let $f$ be a classically-secure QE-OWF. From the $f$, we construct a QV-PoQ
$(\mathcal{P},\mathcal{V})$ as follows.

  1. 1.

The verifier $\mathcal{V}$ chooses $x\leftarrow\\{0,1\\}^{\lambda}$, and sends
it to the prover $\mathcal{P}$.

  2. 2.

$\mathcal{P}$ runs $y\leftarrow\mathsf{QEval}(x)$, and sends $y$ to
$\mathcal{V}$.

  3. 3.

$\mathcal{V}$ runs $y^{\prime}\leftarrow\mathsf{QEval}(x)$. If $y=y^{\prime}$,
$\mathcal{V}$ outputs $\top$. Otherwise, $\mathcal{V}$ outputs $\bot$.

The $1$-completeness is shown as follows. The probability that $\mathcal{V}$
accepts with the honest prover is

$\displaystyle\frac{1}{2^{\lambda}}\sum_{x}\sum_{y}\Pr[y\leftarrow\mathsf{QEval}(x)]^{2}$
$\displaystyle\geq\frac{1}{2^{\lambda}}\sum_{x}\Pr[f(x)\leftarrow\mathsf{QEval}(x)]^{2}$
(149) $\displaystyle\geq\frac{1}{2^{\lambda}}\sum_{x}(1-2^{-\lambda})^{2}$
(150) $\displaystyle\geq 1-{\mathsf{negl}}(\lambda).$ (151)

If the soundness is also satisfied, then we have a QV-PoQ.

Assume that the soundness is not satisfied. Then there exists a PPT algorithm
$P^{*}$ such that for any polynomial ${\mathrm{poly}}$ such that

$\displaystyle\frac{1}{2^{\lambda}}\sum_{x}\sum_{y}\Pr[y\leftarrow
P^{*}(x)]\Pr[y\leftarrow\mathsf{QEval}(x)]\geq
1-\frac{1}{{\mathrm{poly}}(\lambda)}$ (152)

for infinitely many $\lambda$. Then we have for any polynomial
${\mathrm{poly}}$

$\displaystyle 1-\frac{1}{{\mathrm{poly}}(\lambda)}$
$\displaystyle\leq\frac{1}{2^{\lambda}}\sum_{x}\sum_{y}\Pr[y\leftarrow
P^{*}(x)]\Pr[y\leftarrow\mathsf{QEval}(x)]$ (153)
$\displaystyle=\frac{1}{2^{\lambda}}\sum_{x}\Pr[f(x)\leftarrow
P^{*}(x)]\Pr[f(x)\leftarrow\mathsf{QEval}(x)]$ (154)
$\displaystyle+\frac{1}{2^{\lambda}}\sum_{x}\sum_{y\neq f(x)}\Pr[y\leftarrow
P^{*}(x)]\Pr[y\leftarrow\mathsf{QEval}(x)]$ (155)
$\displaystyle\leq\frac{1}{2^{\lambda}}\sum_{x}\Pr[f(x)\leftarrow
P^{*}(x)]+\frac{1}{2^{\lambda}}\sum_{x}\sum_{y\neq
f(x)}\Pr[y\leftarrow\mathsf{QEval}(x)]$ (156)
$\displaystyle\leq\frac{1}{2^{\lambda}}\sum_{x}\Pr[f(x)\leftarrow
P^{*}(x)]+\frac{1}{2^{\lambda}}\sum_{x}2^{-\lambda}$ (157)

for infinitely many $\lambda$, which gives that for any polynomial
${\mathrm{poly}}$

$\frac{1}{2^{\lambda}}\sum_{x}\Pr[f(x)\leftarrow P^{*}(x)]\geq
1-\frac{1}{{\mathrm{poly}}(\lambda)}$ (158)

for infinitely many $\lambda$. If we write the random seed for $P^{*}$
explicitly, it means that for any polynomial ${\mathrm{poly}}$

$\frac{1}{2^{\lambda+p(\lambda)}}\sum_{x\in\\{0,1\\}^{\lambda}}\sum_{r\in\\{0,1\\}^{p(\lambda)}}\delta_{f(x),P^{*}(x;r)}\geq
1-\frac{1}{{\mathrm{poly}}(\lambda)}$ (159)

for infinitely many $\lambda$, where $p(\lambda)$ is the length of the seed,
and $\delta_{\alpha,\beta}=1$ if $\alpha=\beta$ and it is 0 otherwise. Define
the set

$G\coloneqq\\{(x,r)\in\\{0,1\\}^{\lambda}\times\\{0,1\\}^{p}:f(x)=P^{*}(x;r)\\}.$
(160)

Then, from Equation 159, we have for any polynomial ${\mathrm{poly}}$

$\frac{2^{\lambda+p}-|G|}{2^{\lambda+p}}\leq\frac{1}{{\mathrm{poly}}(\lambda)}$
(161)

for infinitely many $\lambda$.

Define the function $g:(x,r)\to P^{*}(x;r)$. We show that it is a classically-
secure and classical-evaluation infinitely-often distributionally OWF. (For
the definition of distributionally OWFs, see Appendix D.) It is enough because
distributionally OWFs imply OWFs (Lemma D.2). To show it, assume that it is
not. Then, for any polynomial ${\mathrm{poly}}$ there exists a PPT algorithm
$\mathcal{A}$ such that

$\displaystyle\Big{\|}\frac{1}{2^{\lambda+p}}\sum_{x,r}(x,r)\otimes
g(x,r)-\frac{1}{2^{\lambda+p}}\sum_{x,r}\mathcal{A}(g(x,r))\otimes
g(x,r)\Big{\|}_{1}\leq\frac{1}{{\mathrm{poly}}(\lambda)}$ (162)

for infinitely many $\lambda$. Here, we have used quantum notations although
everything is classical, because it is simpler. Moreover, for the notational
simplicity, we omit bras and kets: $(x,r)$ means $|(x,r)\rangle\langle(x,r)|$,
$g(x,r)$ means $|g(x,r)\rangle\langle g(x,r)|$, and $\mathcal{A}(g(x,r))$ is
the (diagonal) density matrix that represents the classical output
distribution of the algorithm $\mathcal{A}$ on input $g(x,r)$.

From the algorithm $\mathcal{A}$, we construct a PPT adversary $\mathcal{B}$
that breaks the distributional one-wayness of $f$ as follows:

  1. 1.

On input $f(x)$, sample $r\leftarrow\\{0,1\\}^{p}$.

  2. 2.

Run $(x^{\prime},r^{\prime})\leftarrow\mathcal{A}(f(x))$.

  3. 3.

Output $x^{\prime}$.

Then for any polynomial ${\mathrm{poly}}$

$\displaystyle\Big{\|}\frac{1}{2^{\lambda}}\sum_{x}x\otimes
f(x)-\frac{1}{2^{\lambda}}\sum_{x}\mathcal{B}(f(x))\otimes f(x)\Big{\|}_{1}$
(163) $\displaystyle=\Big{\|}\frac{1}{2^{\lambda}}\sum_{x}x\otimes
f(x)-\frac{1}{2^{\lambda}}\sum_{x}\frac{1}{2^{p}}\sum_{r}\mbox{Tr}_{R}[\mathcal{A}(f(x))]\otimes
f(x)\Big{\|}_{1}$ (164)
$\displaystyle=\Big{\|}\frac{1}{2^{\lambda}}\sum_{x}\sum_{r}\frac{1}{2^{p}}\mbox{Tr}(r)x\otimes
f(x)-\frac{1}{2^{\lambda}}\sum_{x}\frac{1}{2^{p}}\sum_{r}\mbox{Tr}_{R}[\mathcal{A}(f(x))]\otimes
f(x)\Big{\|}_{1}$ (165)
$\displaystyle\leq\Big{\|}\frac{1}{2^{\lambda}}\sum_{x}\sum_{r}\frac{1}{2^{p}}x\otimes
r\otimes
f(x)-\frac{1}{2^{\lambda}}\sum_{x}\frac{1}{2^{p}}\sum_{r}\mathcal{A}(f(x))\otimes
f(x)\Big{\|}_{1}$ (166)
$\displaystyle=\Big{\|}\frac{1}{2^{\lambda+p}}\sum_{x,r}[x\otimes r\otimes
f(x)-\mathcal{A}(f(x))\otimes f(x)]\Big{\|}_{1}$ (167)
$\displaystyle=\Big{\|}\frac{1}{2^{\lambda+p}}\sum_{(x,r)\in G}[x\otimes
r\otimes f(x)-\mathcal{A}(f(x))\otimes f(x)]$ (168)
$\displaystyle+\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
f(x)-\mathcal{A}(f(x))\otimes f(x)]$ (169)
$\displaystyle+\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]$ (170)
$\displaystyle-\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]\Big{\|}_{1}$ (171)
$\displaystyle=\Big{\|}\frac{1}{2^{\lambda+p}}\sum_{(x,r)\in G}[x\otimes
r\otimes P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]$ (172)
$\displaystyle+\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
f(x)-\mathcal{A}(f(x))\otimes f(x)]$ (173)
$\displaystyle+\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]$ (174)
$\displaystyle-\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]\Big{\|}_{1}$ (175)
$\displaystyle=\Big{\|}\frac{1}{2^{\lambda+p}}\sum_{x,r}[x\otimes r\otimes
P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]$ (176)
$\displaystyle+\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
f(x)-\mathcal{A}(f(x))\otimes f(x)]$ (177)
$\displaystyle-\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}[x\otimes r\otimes
P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]\Big{\|}_{1}$ (178)
$\displaystyle\leq\Big{\|}\frac{1}{2^{\lambda+p}}\sum_{x,r}[x\otimes r\otimes
P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)]\Big{\|}_{1}$ (179)
$\displaystyle+\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}\Big{\|}x\otimes
r\otimes f(x)-\mathcal{A}(f(x))\otimes f(x)\Big{\|}_{1}$ (180)
$\displaystyle+\frac{1}{2^{\lambda+p}}\sum_{(x,r)\notin G}\Big{\|}x\otimes
r\otimes P^{*}(x;r)-\mathcal{A}(P^{*}(x;r))\otimes P^{*}(x;r)\Big{\|}_{1}$
(181) $\displaystyle\leq\frac{1}{{\mathrm{poly}}(\lambda)}$ (182)

for infinitely $\lambda$, which means that $f$ is not distributional one-way.
It contradicts the assumption that $f$ is one-way, because one-wayness implies
distributionally one-wayness. In Equation 164, $R$ is the register of the
state $\mathcal{A}(f(x))$ that contains “the output $r$” of the algorithm
$\mathcal{A}$. The last inequality comes from Equation 162 and Equation 161. ∎

Acknowledgements. We thank Mark Zhandry for pointing out Remark 7.6. TM is
supported by JST Moonshot R`&`D JPMJMS2061-5-1-1, JST FOREST, MEXT QLEAP, the
Grant-in-Aid for Scientific Research (B) No.JP19H04066, the Grant-in Aid for
Transformative Research Areas (A) 21H05183, and the Grant-in-Aid for
Scientific Research (A) No.22H00522.

## References

  * [AA11] Scott Aaronson and Alex Arkhipov.  The computational complexity of linear optics.  In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 333–342. ACM Press, June 2011.
  * [AA14] Scott Aaronson and Andris Ambainis.  The need for structure in quantum speedups.  Theory Comput., 10:133–166, 2014.
  * [AA15] Scott Aaronson and Andris Ambainis.  Forrelation: A problem that optimally separates quantum from classical computing.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 307–316. ACM Press, June 2015.
  * [Aar08] Scott Aaronson.  On perfect completeness for qma.  arXiv:0806.0450, 2008.
  * [Aar10] Scott Aaronson.  BQP and the polynomial hierarchy.  In Leonard J. Schulman, editor, 42nd ACM STOC, pages 141–150. ACM Press, June 2010.
  * [Aar14] Scott Aaronson.  The equivalence of sampling and searching.  Theory of Computing Systems, 55:281–298, 2014.
  * [AC17] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  CCC’17: Proceedings of the 32nd Computational Complexity Conference, 2017\.
  * [ACC+22] Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, and Hendrik Waldner.  Quantum depth in the random oracle model.  arXiv:2210.06454, 2022.
  * [AG19] Scott Aaronson and Sam Gunn.  On the classical hardness of spoofing linear cross-entropy benchmarking.  arXiv:1910.12085, 2019.
  * [AGQY22] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen.  Pseudorandom (function-like) quantum state generators: New definitions and applications.  TCC, 2022.
  * [AQY22] Prabhanjan Ananth, Luowen Qian, and Henry Yuen.  Cryptography from pseudorandom quantum states.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 208–236. Springer, Heidelberg, August 2022.
  * [AR16] Benny Applebaum and Pavel Raykov.  On the relationship between statistical zero-knowledge and statistical randomized encodings.  In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 449–477. Springer, Heidelberg, August 2016.
  * [Bar01] Boaz Barak.  How to go beyond the black-box simulation barrier.  In 42nd FOCS, pages 106–115. IEEE Computer Society Press, October 2001.
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani.  Strengths and weaknesses of quantum computing.  SIAM J. Comput., 26(5):1510–1523, 1997.
  * [BBF13] Paul Baecher, Christina Brzuska, and Marc Fischlin.  Notions of black-box reductions, revisited.  In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part I, volume 8269 of LNCS, pages 296–315. Springer, Heidelberg, December 2013.
  * [BCCT12] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer.  From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again.  In Shafi Goldwasser, editor, ITCS 2012, pages 326–349. ACM, January 2012.
  * [BCM+21] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick.  A cryptographic test of quantumness and certifiable randomness from a single quantum device.  Journal of the ACM, 68(5):31:1–31:47, 2021.
  * [BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian.  On the computational hardness needed for quantum cryptography.  ITCS 2023: 14th Innovations in Theoretical Computer Science, 2023.
  * [BDRV18] Itay Berman, Akshay Degwekar, Ron D. Rothblum, and Prashant Nalini Vasudevan.  Multi-collision resistant hash functions and their applications.  In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 133–161. Springer, Heidelberg, April / May 2018.
  * [BFNV19] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani.  On the complexity and verification of quantum random circuit sampling.  Nature Physics, 15:159–163, 2019.
  * [BGI+12] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang.  On the (im)possibility of obfuscating programs.  Journal of the ACM, 59(2):6:1–6:48, 2012.
  * [BGK18] Sergey Bravyi, David Gosset, and Robert König.  Quantum advantage with shallow circuits.  Science, 362:308–311, 2018.
  * [BGKT20] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel.  Quantum advantage with noisy shallow circuits.  Nature Physics, 16:1040–1045, 2020.
  * [BHKY19] Nir Bitansky, Iftach Haitner, Ilan Komargodski, and Eylon Yogev.  Distributional collision resistance beyond one-way functions.  In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 667–695. Springer, Heidelberg, May 2019.
  * [BJS11] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd.  Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467:459–472, 2011.
  * [BKVV20] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick.  Simpler proofs of quantumness.  In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, June 9-12, 2020, Riga, Latvia, volume 158 of LIPIcs, pages 8:1–8:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [BMS16] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd.  Average-case complexity versus approximate simulation of commuting quantum computations.  Physical Review Letters, 117:080501, 2016.
  * [CD08] Ran Canetti and Ronny Ramzi Dakdouk.  Extractable perfectly one-way functions.  In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, ICALP 2008, Part II, volume 5126 of LNCS, pages 449–460. Springer, Heidelberg, July 2008.
  * [CD09] Ran Canetti and Ronny Ramzi Dakdouk.  Towards a theory of extractable functions.  In Omer Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 595–613. Springer, Heidelberg, March 2009.
  * [CGH04] Ran Canetti, Oded Goldreich, and Shai Halevi.  The random oracle methodology, revisited.  J. ACM, 51(4):557–594, 2004.
  * [CHS05] Ran Canetti, Shai Halevi, and Michael Steiner.  Hardness amplification of weakly verifiable puzzles.  In Joe Kilian, editor, TCC 2005, volume 3378 of LNCS, pages 17–33. Springer, Heidelberg, February 2005.
  * [CX22] Shujiao Cao and Rui Xue.  On constructing one-way quantum state generators, and more.  Cryptology ePrint Archive, Report 2022/1323, 2022.  https://eprint.iacr.org/2022/1323.
  * [Dam92] Ivan Damgård.  Towards practical public key systems secure against chosen ciphertext attacks.  In Joan Feigenbaum, editor, CRYPTO’91, volume 576 of LNCS, pages 445–456. Springer, Heidelberg, August 1992.
  * [DI06] Bella Dubrov and Yuval Ishai.  On the randomness complexity of efficient sampling.  In Jon M. Kleinberg, editor, 38th ACM STOC, pages 711–720. ACM Press, May 2006.
  * [FKM+18] Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Seiichiro Tani, and Shuhei Tamate.  Impossibility of classically simulating one-clean-qubit model with multiplicative error.  Physical Review Letters, 120:200502, 2018.
  * [FR99] Lance Fortnow and John Rogers.  Complexity limitations on quantum computation.  Journal of Computer and System Sciences, 59:240–252, 1999.
  * [GGH+16] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters.  Candidate indistinguishability obfuscation and functional encryption for all circuits.  SIAM J. Comput., 45(3):882–929, 2016.
  * [GL89] Oded Goldreich and Leonid A Levin.  A hard-core predicate for all one-way functions.  In STOC, pages 25–32. ACM, 1989.
  * [GS20] Daniel Grier and Luke Schaeffer.  Interactive shallow Clifford circuits: quantum advantage against $\text{NC}^{1}$ and beyond.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd ACM STOC, pages 875–888. ACM Press, June 2020.
  * [GW11] Craig Gentry and Daniel Wichs.  Separating succinct non-interactive arguments from all falsifiable assumptions.  In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 99–108. ACM Press, June 2011.
  * [HKEG19] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin.  Sample complexity of device-independently certified “quantum supremacy”.  Physical Review Letters, 122:21050, 2019.
  * [HM96] Shai Halevi and Silvio Micali.  Practical and provably-secure commitment schemes from collision-free hashing.  In Neal Koblitz, editor, CRYPTO’96, volume 1109 of LNCS, pages 201–215. Springer, Heidelberg, August 1996.
  * [HNO+09] Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan.  Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function.  SIAM J. Comput., 39(3):1153–1218, 2009.
  * [HT98] Satoshi Hada and Toshiaki Tanaka.  On the existence of 3-round zero-knowledge protocols.  In Hugo Krawczyk, editor, CRYPTO’98, volume 1462 of LNCS, pages 408–423. Springer, Heidelberg, August 1998.
  * [HY20] Akinori Hosoyamada and Takashi Yamakawa.  Finding collisions in a quantum world: Quantum black-box separation of collision-resistance and one-wayness.  In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part I, volume 12491 of LNCS, pages 3–32. Springer, Heidelberg, December 2020.
  * [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.
  * [Jer16] Emil Jerábek.  Integer factoring and modular square roots.  J. Comput. Syst. Sci., 82(2):380–394, 2016.
  * [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.
  * [KLVY22] Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang.  Quantum advantage from any non-local game.  Cryptology ePrint Archive, Paper 2022/400, 2022.  https://eprint.iacr.org/2022/400.
  * [KMCVY22] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao.  Classically verifiable quantum advantage from a computational bell test.  Nature Physics, 2022.
  * [KNY18] Ilan Komargodski, Moni Naor, and Eylon Yogev.  Collision resistant hashing for paranoids: Dealing with multiple collisions.  In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 162–194. Springer, Heidelberg, April / May 2018.
  * [KQST22] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal.  Quantum cryptography in algorithmica.  arXiv:2212.00879, 2022.
  * [Kre21] W. Kretschmer.  Quantum pseudorandomness and classical complexity.  TQC 2021, 2021.
  * [KY18] Ilan Komargodski and Eylon Yogev.  On distributional collision resistant hashing.  In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 303–327. Springer, Heidelberg, August 2018.
  * [LLQ22] Jiahui Liu, Qipeng Liu, and Luowen Qian.  Beating classical impossibility of position verification.  ITCS 2022: 13rd Innovations in Theoretical Computer Science, 2022.
  * [Mah18] Urmila Mahadev.  Classical homomorphic encryption for quantum circuits.  In Mikkel Thorup, editor, 59th FOCS, pages 332–338. IEEE Computer Society Press, October 2018.
  * [Mic00] Silvio Micali.  Computationally sound proofs.  SIAM J. Comput., 30(4):1253–1298, 2000.
  * [Mor17] Tomoyuki Morimae.  Hardness of classically sampling the one-clean-qubit model with constant total variation distance error.  Physical Review A, 96:040302(R), 2017.
  * [MY22a] Tomoyuki Morimae and Takashi Yamakawa.  One-wayness in quantum cryptography.  Cryptology ePrint Archive, Report 2022/1336, 2022.  https://eprint.iacr.org/2022/1336.
  * [MY22b] Tomoyuki Morimae and Takashi Yamakawa.  Quantum commitments and signatures without one-way functions.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 269–295. Springer, Heidelberg, August 2022.
  * [MY23] Tomoyuki Morimae and Takashi Yamakawa.  Proofs of quantumness from trapdoor permutations.  ITCS 2023: 14th Innovations in Theoretical Computer Science (ITCS)., 2023\.
  * [Nao03] Moni Naor.  On cryptographic assumptions and challenges (invited talk).  In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 96–109. Springer, Heidelberg, August 2003.
  * [NOVY93] Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung.  Perfect zero-knowledge arguments for NP can be based on general complexity assumptions (extended abstract).  In Ernest F. Brickell, editor, CRYPTO’92, volume 740 of LNCS, pages 196–214. Springer, Heidelberg, August 1993.
  * [OV08] Shien Jin Ong and Salil P. Vadhan.  An equivalence between zero knowledge and commitments.  In Ran Canetti, editor, TCC 2008, volume 4948 of LNCS, pages 482–500. Springer, Heidelberg, March 2008.
  * [OW93] Rafail Ostrovsky and Avi Wigderson.  One-way fuctions are essential for non-trivial zero-knowledge.  In Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, June 7-9, 1993, Proceedings, pages 3–17. IEEE Computer Society, 1993.
  * [RTV04] Omer Reingold, Luca Trevisan, and Salil P. Vadhan.  Notions of reducibility between cryptographic primitives.  In Moni Naor, editor, TCC 2004, volume 2951 of LNCS, pages 1–20. Springer, Heidelberg, February 2004.
  * [Sho94] Peter W. Shor.  Algorithms for quantum computation: Discrete logarithms and factoring.  In 35th FOCS, pages 124–134. IEEE Computer Society Press, November 1994.
  * [Sta22] StackExchange.  https://math.stackexchange.com/questions/4393348/pairwise-independent-balls-in-bins-probability-of-an-empty-bin.  2022\.
  * [SV03] Amit Sahai and Salil P. Vadhan.  A complete problem for statistical zero knowledge.  J. ACM, 50(2):196–249, 2003.
  * [TD04] B. M. Terhal and D. P. DiVincenzo.  Adaptive quantum computation, constant-depth circuits and arthur-merlin games.  Quant. Inf. Comput., 4(2):134–145, 2004.
  * [Vad06] Salil Vadhan.  An unconditional study of computational zero knowledge.  SIAM J. Comput., 36(4):1160–1214, 2006.
  * [WKST19] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal.  Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.  In Moses Charikar and Edith Cohen, editors, 51st ACM STOC, pages 515–526. ACM Press, June 2019.
  * [YZ22] Takashi Yamakawa and Mark Zhandry.  Verifiable quantum advantage without structure.  FOCS 2022: 63rd IEEE Symposium on Foundations of Computer Science, 2022\.
  * [Zha15] Mark Zhandry.  A note on the quantum collision and set equality problems.  Quantum Inf. Comput., 15(7&8):557–567, 2015.

##  Appendix A Necessity of Assumptions for (AI-/IO-)IV-PoQ

In this appendix, we prove that the existence of AI-IV-PoQ implies
$\mathbf{PP}\neq\mathbf{BPP}$. (Remember that IV-PoQ implies IO-IV-PoQ, and
that IO-IV-PoQ implies AI-IV-PoQ.)

Assume that there is an AI-IV-PoQ. From it, we can construct another AI-IV-PoQ
$(\mathcal{P},\mathcal{V}=(\mathcal{V}_{1},\mathcal{V}_{2}))$ where each
prover’s message is a single bit. Without loss of generality, we can assume
that the first phase of the AI-IV-PoQ runs as follows: For $j=1,2,...,N$, the
prover $\mathcal{P}$ and the verifier $\mathcal{V}_{1}$ repeat the following.

  1. 1.

$\mathcal{P}$ possesses a state $\ket{\psi_{j-1}}$. It applies a unitary
$U_{j}(\alpha_{1},\beta_{1},...,\alpha_{j-1},\beta_{j-1})$ that depends on the
transcript $(\alpha_{1},\beta_{1},...,\alpha_{j-1},\beta_{j-1})$ obtained so
far on the state, and measures a qubit in the computational basis to obtain
the measurement result $\alpha_{j}\in\\{0,1\\}$. $\mathcal{P}$ sends
$\alpha_{j}\in\\{0,1\\}$ to $\mathcal{V}_{1}$. The post-measurement state is
$\ket{\psi_{j}}$.

  2. 2.

$\mathcal{V}_{1}$ does some classical computing and sends a bit string
$\beta_{j}$ to $\mathcal{P}$.

We claim that a PPT prover $\mathcal{P}^{*}$ that queries the
$\verb|#|\mathbf{P}$ oracle can exactly sample from $\mathcal{P}$’s $j$th
output probability distribution $\Pr[\alpha_{j}|\alpha_{j-1},...,\alpha_{1}]$
for each $j\in[N]$. This is shown as follows.

  1. 1.

$\mathcal{P}^{*}$ computes
$\Pr[\alpha_{1}]=\|(|\alpha_{1}\rangle\langle\alpha_{1}|\otimes
I)U_{1}|0...0\rangle\|^{2}$ for each $\alpha_{1}\in\\{0,1\\}$, and samples
$\alpha_{1}$ according to $\Pr[\alpha_{1}]$. Let $\alpha_{1}^{*}\in\\{0,1\\}$
be the result of the sampling. $\mathcal{P}^{*}$ sends $\alpha_{1}^{*}$ to
$\mathcal{V}_{1}$.

  2. 2.

$\mathcal{V}_{1}$ sends $\beta_{1}^{*}$ to $\mathcal{P}^{*}$.

  3. 3.

$\mathcal{P}^{*}$ and $\mathcal{V}_{1}$ repeat the following for
$j=2,3,...,N$.

    1. (a)

$\mathcal{P}^{*}$ computes
$\Pr[\alpha_{j}|\alpha_{j-1}^{*},...,\alpha_{1}^{*}]=\frac{\Pr[\alpha_{j},\alpha_{j-1}^{*},...,\alpha_{1}^{*}]}{\Pr[\alpha_{j-1}^{*},...,\alpha_{1}^{*}]}$
for each $\alpha_{j}\in\\{0,1\\}$, and samples $\alpha_{j}$ according to
$\Pr[\alpha_{j}|\alpha_{j-1}^{*},...,\alpha_{1}^{*}]$. Here,

$\displaystyle\Pr[\alpha_{j},\alpha_{j-1}^{*},...,\alpha_{1}^{*}]$
$\displaystyle=\|(|\alpha_{1}^{*}\rangle\langle\alpha_{1}^{*}|\otimes...\otimes|\alpha_{j-1}^{*}\rangle\langle\alpha_{j-1}^{*}|\otimes|\alpha_{j}\rangle\langle\alpha_{j}|\otimes
I)U_{j}(\alpha_{1}^{*},\beta_{1}^{*},...,\alpha_{j-1}^{*},\beta_{j-1}^{*})...U_{2}(\alpha_{1}^{*},\beta_{1}^{*})U_{1}|0...0\rangle\|^{2}.$
(183)

Let $\alpha_{j}^{*}\in\\{0,1\\}$ be the result of the sampling.
$\mathcal{P}^{*}$ sends $\alpha_{j}^{*}$ to $\mathcal{V}_{1}$.

    2. (b)

$\mathcal{V}_{1}$ sends $\beta_{j}^{*}$ to $\mathcal{P}^{*}$.

It is known that for any QPT algorithm that outputs $z\in\\{0,1\\}^{\ell}$,
the probability $\Pr[z]$ that it outputs $z$ can be computed in classical
deterministic polynomial-time by querying the `#`$\mathbf{P}$ oracle [FR99].
Therefore, $\mathcal{P}^{*}$ can compute $\Pr[\alpha_{1}]$ and
$\Pr[\alpha_{j}|\alpha_{j-1}^{*},...,\alpha_{1}^{*}]$ for any $j=2,3,...,N$.
It is known that a $\verb|#|\mathbf{P}$ function can be computed in classical
deterministic polynomial-time by querying the $\mathbf{PP}$ oracle. Therefore,
if $\mathbf{PP}=\mathbf{BPP}$, $\mathcal{P}^{*}$ is enough to be a PPT
algorithm.

##  Appendix B Omitted Contents in Section 2

###  B.1 Auxiliary-Input Collision-Resistance and
$\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$

We prepare several definitions.

###### Definition B.1 (Auxiliary-input collision-resistant hash functions).

An auxiliary-input collision-resistant hash function is a polynomial-time
computable auxiliary-input function ensemble
$\mathcal{H}\coloneqq\\{h_{\sigma}:\\{0,1\\}^{p(|\sigma|)}\to\\{0,1\\}^{q(|\sigma|)}\\}_{\sigma\in\\{0,1\\}^{*}}$
such that $q(|\sigma|)<p(|\sigma|)$ and for every uniform PPT adversary
$\mathcal{A}$ and polynomial ${\mathrm{poly}}$, there exists an infinite set
$\Lambda\subseteq\\{0,1\\}^{*}$ such that,

$\Pr[h_{\sigma}(x^{\prime})=h_{\sigma}(x):(x,x^{\prime})\leftarrow\mathcal{A}(\sigma)]\leq\frac{1}{{\mathrm{poly}}(|\sigma|)}$
(184)

for all $\sigma\in\Lambda$.

A search problem is specified by a relation
$R\subseteq\\{0,1\\}^{*}\times\\{0,1\\}^{*}$ where one is given
$x\in\\{0,1\\}^{*}$ and asked to find $y\in\\{0,1\\}^{*}$ such that $(x,y)\in
R$. We say that a search problem $R$ is many-one reducible to another search
problem $S$ if there are polynomial-time computable functions $f$ and $g$ such
that $(f(x),y)\in S$ implies $(x,g(x,y))\in R$.

A search problem Weak Pigeon is defined as follows:
$(C,(x,x^{\prime}))\in\text{Weak Pigeon}$ if and only if $C$ represents a
circuit from $\\{0,1\\}^{m}$ to $\\{0,1\\}^{n}$ for $m>n$, $x\neq x^{\prime}$,
and $C(x)=C(x^{\prime})$.

###### Definition B.2 ([Jer16]).

$\mathbf{PWPP}$ is the class of all search problems that are many-one
reducible to Weak Pigeon.

###### Definition B.3 ([Aar10]).

$\mathbf{FBPP}$ is the class of all search problems $R$ for which there exists
a PPT algorithm $\mathcal{A}$ such that for any $x\in\\{0,1\\}^{*}$,

$\displaystyle\Pr[(x,y)\in R:y\leftarrow\mathcal{A}(x)]=1-o(1).$ (185)

The following theorem almost directly follows from the definitions.

###### Theorem B.4.

There exist auxiliary-input collision-resistant hash functions if and only if
$\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$.

###### Proof.

We first show the “if” direction. Toward contradiction, we assume that there
is no auxiliary-input collision-resistant hash function. We consider a
polynomial-time computable auxiliary-input function ensemble
$\mathcal{H}=\\{h_{\sigma}\\}$ defined as follows: if $\sigma$ represents a
circuit $C:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}$ such that $n>m$, then
$h_{\sigma}$ takes $x\in\\{0,1\\}^{n}$ and outputs $C(x)\in\\{0,1\\}^{m}$.
Otherwise, $h_{\sigma}$ is defined arbitrarily, (say, $h_{\sigma}$ is a
constant function that always outputs $0$). By our assumption, this is not an
auxiliary-input collision-resistant hash function, so there is a PPT algorithm
$\mathcal{A}$ and a polynomial ${\mathrm{poly}}$ such that

$\Pr[h_{\sigma}(x^{\prime})=h_{\sigma}(x):(x,x^{\prime})\leftarrow\mathcal{A}(\sigma)]\geq
1/{\mathrm{poly}}(|\sigma|)$ (186)

for all but finitely many $\sigma$. For those $\sigma$, we can amplify the
success probability of $\mathcal{A}$ to $1-o(1)$ by polynomially many times
repetition. This gives a PPT algorithm that solves Weak Pigeon with
probability $1-o(1)$, which contradicts
$\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$. Therefore, the above $\mathcal{H}$
must be an auxiliary-input collision-resistant hash function.

Next, we prove the “only if” direction. Toward contradiction, we assume
$\mathbf{PWPP}\subseteq\mathbf{FBPP}$. This means that there is a PPT
algorithm that solves Weak Pigeon with probability $1-o(1)$ on all instances.
Let $\mathcal{H}=\\{h_{\sigma}\\}$ be an arbitrary polynomial-time computable
auxiliary-input function ensemble. Then we can use the algorithm that solves
Weak Pigeon to find a collision of $h_{\sigma}$ for all auxiliary inputs
$\sigma$ with probability $1-o(1)$. This means that
$\mathcal{H}=\\{h_{\sigma}\\}$ is not an auxiliary-input collision-resistant
hash function. This contradicts the existence of auxiliary-input collision-
resistant hash functions. Thus, we have
$\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$. ∎

###  B.2 Auxiliary-Input Commitments from $\mathbf{SZK}\nsubseteq\mathbf{BPP}$

We prove Theorem 2.17, i.e., we construct constant-round auxiliary-input
statistically-hiding and computationally-binding bit commitments assuming
$\mathbf{SZK}\nsubseteq\mathbf{BPP}$.

First, we recall the definition of instance-dependent commitments.

###### Definition B.5 (Instance-dependent commitment).

Instance-dependent commitments for a promise problem
$(L_{\mathsf{yes}},L_{\mathsf{no}})$ is a family of commitment schemes
$\\{\Pi_{\sigma}\\}_{\sigma\in\\{0,1\\}^{*}}$ such that

  * •

$\Pi_{\sigma}$ is statistically hiding if $\sigma\in L_{\mathsf{yes}}$,

  * •

$\Pi_{\sigma}$ is statistically binding if $\sigma\in L_{\mathsf{no}}$.

###### Theorem B.6 ([OV08]).

For any promise problem $(L_{\mathsf{yes}},L_{\mathsf{no}})\in\mathbf{SZK}$,
there is a constant-round instance-dependent commitments for
$(L_{\mathsf{yes}},L_{\mathsf{no}})$.

Instance-dependent commitments for $\mathbf{SZK}$ directly give auxiliary-
input statistically-hiding and computationally-binding commitments if
$\mathbf{SZK}\nsubseteq\mathbf{BPP}$.

###### Proof of Theorem 2.17.

Fix a $\mathbf{SZK}$-complete promise problem
$(L_{\mathsf{yes}},L_{\mathsf{no}})$. (For example, we can take the
statistical difference problem [SV03].) We regard instance-dependent
commitments for $(L_{\mathsf{yes}},L_{\mathsf{no}})$ as auxiliary-input
commitments where $\Sigma\coloneqq L_{\mathsf{yes}}$. Then correctness and
statistical hiding as auxiliary-input commitments directly follows from those
of instance-dependent commitments noting that they are statistically hiding if
$\sigma\in L_{\mathsf{yes}}$. Suppose that this scheme does not satisfy
computational binding. Then there is a PPT malicious committer
$\mathcal{S}^{*}$ that finds decommitments to both $0$ and $1$ with an
inverse-polynomial probability for all but finitely many $\sigma\in
L_{\mathsf{yes}}$. We can augment it to construct
$\widetilde{\mathcal{S}}^{*}$ that works for all $\sigma\in L_{\mathsf{yes}}$
by letting it find decommitments by brute-force for $\sigma$ for which
$\mathcal{S}^{*}$ fails to find decommitments. Since there are only finitely
many such $\sigma$, $\widetilde{\mathcal{S}}^{*}$ still runs in PPT. On the
other hand, if $\sigma\in L_{\mathsf{no}}$, $\widetilde{\mathcal{S}}^{*}$
cannot find decommitments to $0$ and $1$ except for a negligible probability.
Therefore, we can use $\widetilde{\mathcal{S}}^{*}$ to distinguish elements of
$L_{\mathsf{yes}}$ and $L_{\mathsf{no}}$ with an inverse-polynomial
distinguishing gap. Since $(L_{\mathsf{yes}},L_{\mathsf{no}})$ is
$\mathbf{SZK}$-complete, this means $\mathbf{SZK}\subseteq\mathbf{BPP}$. This
is a contradiction, and thus the above commitment scheme satisfies
computational binding. ∎

##  Appendix C Omitted Proofs for the Completeness

In this appendix, we show that if $\mathcal{P}$ starts Step 5 of Algorithm 4
with the state $\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$, the probability that
$\mathcal{V}_{2}$ outputs $\top$ is
$\frac{1}{2}+\frac{1}{2}\cos^{2}\frac{\pi}{8}$. The proof is the same as that
in [KMCVY22], but for the convenience of readers, we provide it here.

First, the probability that $\mathcal{V}_{1}$ chooses $v_{1}=0$ is 1/2, and in
that case, the honest $\mathcal{P}$ sends correct $x_{0}$ or $x_{1}$, and
therefore $\mathcal{V}_{2}$ outputs $\top$ with probability 1.

Second, the probability that $\mathcal{V}_{1}$ chooses $v_{1}=1$ is 1/2. In
that case, Equation 99 is $\ket{\xi\cdot x_{0}}+(-1)^{d\cdot(x_{0}\oplus
x_{1})}\ket{1\oplus(\xi\cdot x_{1})}$, which is one of the BB84 states
$\\{\ket{0},\ket{1},\ket{+},\ket{-}\\}$. By the straightforward calculations,
we can show that

$\displaystyle\Pr[\eta=0|\ket{0},v_{2}=0]$ (187)
$\displaystyle\Pr[\eta=1|\ket{1},v_{2}=0]$ (188)
$\displaystyle\Pr[\eta=0|\ket{+},v_{2}=0]$ (189)
$\displaystyle\Pr[\eta=1|\ket{-},v_{2}=0]$ (190)
$\displaystyle\Pr[\eta=0|\ket{0},v_{2}=1]$ (191)
$\displaystyle\Pr[\eta=1|\ket{1},v_{2}=1]$ (192)
$\displaystyle\Pr[\eta=1|\ket{+},v_{2}=1]$ (193)
$\displaystyle\Pr[\eta=0|\ket{-},v_{2}=1]$ (194)

are all equal $\cos^{2}\frac{\pi}{8}$. Then, we can confirm that the
probability that

$\displaystyle(\xi\cdot x_{0}\neq\xi\cdot x_{1})\wedge(\eta=\xi\cdot x_{0}),$
(195)

or

$\displaystyle(\xi\cdot x_{0}=\xi\cdot x_{1})\wedge(\eta=v_{2}\oplus
d\cdot(x_{0}\oplus x_{1}))$ (196)

occurs is $\cos^{2}\frac{\pi}{8}$. In fact, if $\xi\cdot x_{0}\neq\xi\cdot
x_{1}$, $\mathcal{P}$’s state is $\ket{0}$ or $\ket{1}$. In that case, the
probability that $\eta=\xi\cdot x_{0}$ is $\cos^{2}\frac{\pi}{8}$ for any
$v_{2}\in\\{0,1\\}$. If $\xi\cdot x_{0}=\xi\cdot x_{1}$, $\mathcal{P}$’s state
is $\ket{+}$ or $\ket{-}$. In that case, the probability that
$\eta=v_{2}\oplus d\cdot(x_{0}\oplus x_{1})$ is $\cos^{2}\frac{\pi}{8}$.

##  Appendix D Distributionally OWFs

###### Definition D.1 (Distributionally OWFs [IL89]).

A polynomial-time-computable function $f:\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ is
distributionally one-way if there exists a polynomial $p$ such that for any
PPT algorithm $\mathcal{A}$ and all sufficiently large $\lambda$, the
statistical difference between
$\\{(x,f(x))\\}_{x\leftarrow\\{0,1\\}^{\lambda}}$ and
$\\{(\mathcal{A}(1^{\lambda},f(x)),f(x))\\}_{x\leftarrow\\{0,1\\}^{\lambda}}$
is greater than $1/p(\lambda)$.

The following result is known.

###### Lemma D.2 ([IL89]).

If distributionally OWFs exist then OWFs exist.