# Quantum Advantage from One-Way Functions

Tomoyuki Morimae  Yukawa Institute for Theoretical Physics, Kyoto University,
Kyoto, Japan
<EMAIL_ADDRESS>Takashi Yamakawa  Yukawa Institute for
Theoretical Physics, Kyoto University, Kyoto, Japan
<EMAIL_ADDRESS>NTT Social Informatics Laboratories,
Tokyo, Japan
<EMAIL_ADDRESS>
###### Abstract

Showing quantum advantage based on weaker and standard classical complexity
assumptions is one of the most important goals in quantum information science.
In this paper, we demonstrate quantum advantage with several basic
assumptions, specifically based on only the existence of classically-secure
one-way functions. We introduce inefficient-verifier proofs of quantumness
(IV-PoQ), and construct it from statistically-hiding and computationally-
binding classical bit commitments. IV-PoQ is an interactive protocol between a
verifier and a quantum polynomial-time prover consisting of two phases. In the
first phase, the verifier is classical probabilistic polynomial-time, and it
interacts with the quantum polynomial-time prover over a classical channel. In
the second phase, the verifier becomes inefficient, and makes its decision
based on the transcript of the first phase. If the quantum prover is honest,
the inefficient verifier accepts with high probability, but any classical
probabilistic polynomial-time malicious prover only has a small probability of
being accepted by the inefficient verifier. In our construction, the
inefficient verifier can be a classical deterministic polynomial-time
algorithm that queries an $\mathbf{NP}$ oracle. Our construction demonstrates
the following results based on the known constructions of statistically-hiding
and computationally-binding commitments from one-way functions or
distributional collision-resistant hash functions:

  * •

If one-way functions exist, then IV-PoQ exist.

  * •

If distributional collision-resistant hash functions exist (which exist if
hard-on-average problems in $\mathbf{SZK}$ exist), then constant-round IV-PoQ
exist.

We also demonstrate quantum advantage based on worst-case-hard assumptions. We
define auxiliary-input IV-PoQ (AI-IV-PoQ) that only require that for any
malicious prover, there exist infinitely many auxiliary inputs under which the
prover cannot cheat. We construct AI-IV-PoQ from an auxiliary-input version of
commitments in a similar way, showing that

  * •

If auxiliary-input one-way functions exist (which exist if
$\mathbf{CZK}\not\subseteq\mathbf{BPP}$), then AI-IV-PoQ exist.

  * •

If auxiliary-input collision-resistant hash functions exist (which is
equivalent to $\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$) or
$\mathbf{SZK}\nsubseteq\mathbf{BPP}$, then constant-round AI-IV-PoQ exist.

Finally, we also show that some variants of PoQ can be constructed from
quantum-evaluation one-way functions (QE-OWFs), which are similar to
classically-secure classical one-way functions except that the evaluation
algorithm is not classical but quantum. QE-OWFs appear to be weaker than
classically-secure classical one-way functions.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Technical Overview
    3. 1.3 Related Works
  2. 2 Preliminaries
    1. 2.1 Basic Notations
    2. 2.2 Pairwise-Independent Hash Family
    3. 2.3 OWFs
    4. 2.4 Commitments
  3. 3 Hashing Lemmas
  4. 4 Inefficient-Verifier Proofs of Quantumness
    1. 4.1 Definitions
    2. 4.2 Strong Soundness
    3. 4.3 Gap Amplification
  5. 5 Coherent Execution of Classical Bit Commitments
  6. 6 Construction of IV-PoQ
    1. 6.1 Completeness
    2. 6.2 Soundness
    3. 6.3 Computational Power of the Inefficient Verifier
  7. 7 Implausibility of Two-Round AI-IV-PoQ
    1. 7.1 Impossibility of Classical Reduction
    2. 7.2 Oracle Separation
  8. 8 Variants of PoQ from QE-OWFs
  9. A Necessity of Assumptions for (AI-/IO-)IV-PoQ
  10. B Omitted Contents in Section 2
    1. B.1 Auxiliary-Input Collision-Resistance and $\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$
    2. B.2 Auxiliary-Input Commitments from $\mathbf{SZK}\nsubseteq\mathbf{BPP}$
  11. C Omitted Proofs for the Completeness
  12. D Distributionally OWFs

##  1 Introduction

Quantum advantage means that quantum computing outperforms classical one for
some computational tasks. Showing quantum advantage based on weaker and
standard classical complexity assumptions is one of the most important goals
in quantum information science.

One approach to demonstrate quantum advantage is the sampling-based one. In
the sampling-based quantum advantage, quantum polynomial-time (QPT) algorithms
can sample certain probability distributions but no classical probabilistic
polynomial-time (PPT) algorithm can. A great merit of the approach is that
relatively simple quantum computing models are enough, such as the Boson
Sampling model [AA11], the IQP model [BJS11], the random circuit model
[BFNV19], and the one-clean-qubit model [FKM+18]. 111The Boson Sampling model
is a quantum computing model that uses non-interacting bosons, such as
photons. The IQP (Instantaneous Quantum Polytime) model is a quantum computing
model where only commuting quantum gates are used. The random circuit model is
a quantum computing model where each gate is randomly chosen. The one-clean-
qubit model is a quantum computing model where the input is $|0\rangle\langle
0|\otimes\frac{I^{\otimes m}}{2^{m}}$. Output probability distributions of
these restricted quantum computing models cannot be sampled by any PPT
algorithm within a constant multiplicative error222We say that the output
probability distribution of a quantum algorithm is sampled by a classical
algorithm within a constant multiplicative error $\epsilon$ if
$|q_{z}-p_{z}|\leq\epsilon p_{z}$ is satisfied for all $z$, where $q_{z}$ is
the probability that the quantum algorithm outputs the bit string $z$, and
$p_{z}$ is the probability that the classical algorithm outputs the bit string
$z$. unless the polynomial-time hierarchy collapses to the third [AA11, BJS11]
or the second level [FKM+18].333[TD04] previously showed that output
probability distributions of constant-depth quantum circuits cannot be sampled
classically unless $\mathbf{BQP}\subseteq\mathbf{AM}$. Their assumption can be
easily improved to the assumption that the polynomial-time hierarchy does not
collapse to the second level. The assumption that the polynomial-time
hierarchy does not collapse is a widely-believed assumption in classical
complexity theory, but one disadvantage of these results is that the
multiplicative-error sampling is unrealistic. The requirement of the
multiplicative-error sampling can be relaxed to that of the constant additive-
error sampling [AA11, BMS16, Mor17, BFNV19],444We say that the output
probability distribution of a quantum algorithm is sampled by a classical
algorithm within a constant additive error $\epsilon$ if
$\sum_{z}|q_{z}-p_{z}|\leq\epsilon$ is satisfied, where $q_{z}$ is the
probability that the quantum algorithm outputs the bit string $z$, and $p_{z}$
is the probability that the classical algorithm outputs the bit string $z$.
but the trade-off is that the underlying classical complexity assumptions
become less standard: some ad-hoc assumptions about average-case
$\verb|#|\mathbf{P}$-hardness of some problems, which were not studied before,
have to be introduced.

Another disadvantage of the sampling-based approach is that it is not known to
be verifiable. For the multiplicative-error case, we do not know how to verify
quantum advantage even with a computationally-unbounded verifier. Also for the
additive-error case, we do not know how to verify the quantum advantage
efficiently. (For example, there is a negative result that suggets that
exponentially-many samples are necessary to verify the correctness of the
sampling [HKEG19].) At least, we can say that if there exists a sampling-based
quantum advantage in the additive-error case, there exists an inefficiently-
verifiable quantum advantage for a certain search problem [Aar14].555[Aar14,
Theorem 21] showed that if there exists an additive-error sampling problem
that is quantumly easy but classically hard, then there exists a search
problem that is quantumly easy but classically hard. The relation of the
search problem is verified inefficiently. Note that the search problem depends
on the time-complexity of the classical adversary, and therefore it is
incomparable to our (AI-)IV-PoQ.

Some inefficiently-verifiable search problems that exhibit quantum advantage
have been introduced. For example, for the random circuit model, [AC17, AG19]
introduced so-called Heavy Output Generation (HOG) and Linear Cross-Entropy
Heavy Output Generation (XHOG) where given a quantum circuit $C$ it is
required to output bit strings that satisfy certain relations about $C$. The
relations can be verified inefficiently. The classical hardnesses of these
problems are, however, based on new assumptions introduced by the authors.
[Aar10] constructed an inefficiently-verifiable search problem (Fourier
Fishing), but its quantum advantage is relative to random oracles. [ACC+22]
constructed another inefficiently-verifiable search problem (Collision
Hashing), but its quantum advantage is also relative to random oracles.

There is another approach of demonstrating quantum advantage where the
verification is efficient, namely, proofs of quantumness (PoQ) [BCM+21]. In
PoQ, we have a QPT prover and a PPT verifier. They interact over a classical
channel, and the verifier finally makes the decision. If the QPT prover
behaves honestly, the verifier accepts with high probability, but for any
malicious PPT prover, the verifier accepts with only small probability. The
simplest way of realizing PoQ is to let the prover solve an $\mathbf{NP}$
problem that is quantumly easy but classically hard, such as factoring
[Sho94]. Such a simplest way is, however, based on specific assumptions that
certain specific problems are hard for PPT algorithms.

The first construction of PoQ based on a general assumption was given in
[BCM+21] where (noisy) trapdoor claw-free functions with the adaptive-
hardcore-bit property666The adaptive-hardcore-bit property very roughly means
that it is hard to find $x_{b}$ ($b\in\\{0,1\\}$) and $d\neq\mathbf{0}$ such
that $f_{0}(x_{0})=f_{1}(x_{1})$ and $d\cdot(x_{0}\oplus x_{1})=0$, given a
claw-free pair $(f_{0},f_{1})$. is assumed. Such functions can be instantiated
with the LWE assumption, for example [BCM+21]. The adaptive-hardcore-bit
property was removed in [KMCVY22], where only trapdoor 2-to-1 collision-
resistant hash functions are assumed. In [MY23], PoQ was constructed from
(full-domain) trapdoor permutations. PoQ can also be constructed from quantum
homomorphic encryptions (QHE) [KLVY22] for a certain class of quantum
operations (such as controlled-Hadamard gates), which can be instantiated with
the LWE assumption [Mah18]. These contructions are interactive, i.e., the
verifier and the prover have to exchange many rounds of messages. Recently, a
non-interactive PoQ has been realized with only random oracles [YZ22]. This
result demonstrates efficiently-verifiable quantum advantage with an
“unstructured” problem for the first time. However, it is known that hardness
relative to a random oracle does not necessarily imply hardness in the
unrelativized world where the random oracle is replaced with a real-world hash
function [CGH04]. Thus, [YZ22] does not give quantum advantage under a
standard assumption in the unrelativized world.

We therefore have the following open problem.

Can we construct PoQ from weaker and standard assumptions, such as the
existence of one-way functions (OWFs)?

Note that this open problem is highly non-trivial even if we give up the
efficient verification. As we have explained, all previous results on
inefficiently-verifiable quantum advantage assume (random) oracles or some ad-
hoc assumptions newly introduced by the authors themselves. It is therefore
highly non-trivial to answer even the following question.

Can we demonstrate inefficiently-verifiable quantum advantage with weaker and
standard assumptions, such as the existence of OWFs?

###  1.1 Our Results

In this paper, we answer the second question affirmatively. We demonstrate
inefficiently-verifiable quantum advantage with several basic assumptions,
specifically based on only the existence of OWFs. To our knowledge, this is
the first time that quantum advantage is shown based only on OWFs. More
precisely, we construct what we call inefficient-verifier proofs of
quantumness (IV-PoQ) from statistically-hiding and computationally-binding
classical bit commitments. IV-PoQ is an interactive protocol between a
verifier and a QPT prover, which is divided into two phases. In the first
phase, the verifier is PPT, and it interacts with the QPT prover over a
classical channel. In the second phase, the verifier becomes inefficient, and
makes the decision based on the transcript of the first phase.777The
inefficient verifier could also take the efficient verifier’s secret
information as input in addition to the transcript. However, without loss of
generality, we can assume that the inefficient verifier takes only the
transcript as input, because we can always modify the protocol of the first
phase in such a way that the efficient verifier sends its secret information
to the prover at the end of the first phase. If the QPT prover is honest, the
inefficient verifier accepts with high probability, but for any PPT malicious
prover, the inefficient verifier accepts with only small probability. The new
notion of IV-PoQ captures both the standard PoQ and inefficiently-verifiable
quantum advantage (including search problems that exhibit quantum advantage).

Our main result is the following:

###### Theorem 1.1.

$(k+6)$-round IV-PoQ exist if statistically-hiding and computationally-binding
classical bit commitments with $k$-round commit phase exist.

A proof of Theorem 1.1 is given in Section 6. Note that we actually need the
statistical hiding property only for the honest receiver, because the receiver
corresponds to the verifier. Moreover, note that in our construction, the
inefficient verifier in the second phase is enough to be a classical
deterministic polynomial-time algorithm that queries the $\mathbf{NP}$ oracle.
(See Section 6.3.)

Because statistically-hiding and computationally-binding classical bit
commitments can be constructed from OWFs [HNO+09], we have the following
result.

###### Theorem 1.2.

IV-PoQ exist if OWFs exist.

Moreover, it is known that constant-round statistically-hiding and
computationally-binding bit commitments can be constructed from distributional
collision resistant hash functions [BHKY19]888A distributional collision-
resistant hash function [DI06] is a weaker variant of a collision-resistant
hash function that requires the hardness of sampling a collision $(x,y)$ where
$x$ is uniformly random and $y$ is uniformly random conditioned on colliding
with $x$., which exist if there is an hard-on-average problem in
$\mathbf{SZK}$ [KY18]. Therefore we also have the following result.999It is
also known that constant-round statistically-hiding and computationally-
binding commitments can be constructed from multi-collision resistant hash
functions [BDRV18, KNY18], and therefore we have constant-round IV-PoQ from
multi-collision resistant hash functions as well.

###### Theorem 1.3.

Constant-round IV-PoQ exist if there exist distributional collision-resistant
hash functions, which exist if there is an hard-on-average problem in
$\mathbf{SZK}$.

The assumptions in Theorems 1.2 and 1.3 are average-case-hard assumptions. We
can further weaken the assumptions to worst-case-hard ones if we require only
worst-case soundness for IV-PoQ. Namely, we define auxiliary-input IV-PoQ (AI-
IV-PoQ) that only requires that for any malicious prover, there exist
infinitely many auxiliary inputs under which the prover cannot cheat. We can
show the following:

###### Theorem 1.4.

$(k+6)$-round AI-IV-PoQ exist if auxiliary-input statistically-hiding and
computationally-binding classical bit commitments with $k$-round commit phase
exist.

Its proof is omitted because it is similar to that of Theorem 1.1. Although
AI-IV-PoQ is weaker than IV-PoQ, we believe that it still demonstrates a
meaningful notion of quantum advantage, because it shows “worst-case quantum
advantage” in the sense that no PPT algorithm can simulate the QPT honest
prover on all auxiliary inputs.

Auxiliary-input OWFs101010Roughly speaking, auxiliary-input OWFs are keyed
functions such that for each adversary there exist infinitely many keys on
which the adversary fails to invert the function. exist if
$\mathbf{CZK}\not\subseteq\mathbf{BPP}$ [OW93].111111$\mathbf{CZK}$ is the
class of promise problems that have computational zero-knowledge proofs. By
abuse of notation, we write $\mathbf{BPP}$ to mean the class of promise
problems (instead of languages) that are decidable in PPT.  Moreover, the
construction of statistically-hiding and computationally-binding commitments
from OWFs in [HNO+09] can be modified for the auxiliary-input setting. We
therefore have the following result.

###### Theorem 1.5.

AI-IV-PoQ exist if there exist auxiliary-input OWFs, which exist if
$\mathbf{CZK}\not\subseteq\mathbf{BPP}$.

Furthermore, relying on the known constructions of constant-round (auxiliary-
input) statistically-hiding commitments [HM96, OV08], we obtain the following
result.

###### Theorem 1.6.

Constant-round AI-IV-PoQ exist if auxiliary-input collision-resistant hash
functions exist (which is equivalent to
$\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$)121212See Section B.1 for the
definitions of $\mathbf{PWPP}$ and $\mathbf{FBPP}$. or
$\mathbf{SZK}\nsubseteq\mathbf{BPP}$.

Finally, we can also define another variant of IV-PoQ that we call infinitely-
often IV-PoQ (IO-IV-PoQ) where the soundness is satisfied for infinitely many
values of the security parameter. We note that IO-IV-PoQ lie between IV-PoQ
and AI-IV-PoQ. It is known that infinitely-often OWFs exist if
$\mathbf{SRE}\not\subseteq\mathbf{BPP}$ [AR16].131313$\mathbf{SRE}$ is the
class of problems that admit statistically-private randomized encoding with
polynomial-time client and computationally-unbounded server. Therefore we also
have the following result.

###### Theorem 1.7.

IO-IV-PoQ exist if infinitely-often OWFs exist, which exist if
$\mathbf{SRE}\not\subseteq\mathbf{BPP}$.

A comparison table among existing and our results on quantum advantage can be
found in Table 1.

Table 1: Comparison among results on quantum advantage. In column
“Verification”, “No” means that the verification is not known to be possible.
(Actually, it seems to be impossible.) In column “Assumption”, PH stands for
the polynomial-time hierarchy, seOWFs stands for subexponentially secure one-
way functions, 2-1 TDCRHFs stands for 2-to-1 trapdoor collision-resistant hash
functions, QHE stands for quantum homomorphic encryption, fdTDPs stands for
full-domain trapdoor permutations, OWFs stands for one-way functions, dCRHFs
stands for distributional collision-resistant hash functions, and CRHFs stands
for collision-resistant hash functions. In column “Misc”, Mult.err. and
Add.err. stand for multiplicative and additive errors, respectively. In the
row of [Sho94], the number of rounds is two, because the verifier sends a
composite number to the prover, and the prover returns its factorization. It
can be considered as a non-interactive if the composite number is given as an
auxiliary input.
Ref. | Verification | #Rounds | Assumption | Misc
---|---|---|---|---
[TD04, AA11, BJS11, FKM+18] | No | $1$ | PH does not collapse | Mult.err. sampling
[AA11, BMS16, BFNV19, Mor17] | No | $1$ | Ad hoc | Add.err. sampling
[AA15] | No | $1$ | Random oracle | Fourier Sampling
[AC17] | No | $1$ | seOWFs+$\mathbf{P}/\mathbf{poly}$-oracle | Fourier Sampling
[AC17, AG19] | Inefficient | $1$ | Ad hoc | HOG, XHOG
[Aar10] | Inefficient | $1$ | Random oracle | Fourier Fishing
[AC17] | Inefficient | $1$ | seOWFs+$\mathbf{P}/\mathbf{poly}$-oracle | Fourier Fishing
[ACC+22] | Inefficient | $1$ | Random oracle | Collision Hashing
[Sho94] | Efficient | $2$ | Factoring/Discrete-log |
[YZ22] | Efficient | $1$ | Random oracle |
[BCM+21, KMCVY22] | Efficient | $O(1)$ | (Noisy) 2-1 TDCRHFs |
[KLVY22] | Efficient | $O(1)$ | QHE |
[MY23] | Efficient | ${\mathrm{poly}}(\lambda)$ | fdTDPs |
Theorem 1.2 | Inefficient | ${\mathrm{poly}}(\lambda)$ | OWFs |
Theorem 1.3 | Inefficient | $O(1)$ | dCRHFs |
Theorem 1.5 | Inefficient | ${\mathrm{poly}}(\lambda)$ |  | Auxiliary-input OWFs /
---
$\mathbf{CZK}\not\subseteq\mathbf{BPP}$
AI-IV-PoQ
Theorem 1.6 | Inefficient | $O(1)$ |  | Auxiliary-input CRHFs /
---
$\mathbf{SZK}\not\subseteq\mathbf{BPP}$
AI-IV-PoQ
Theorem 1.7 | Inefficient | ${\mathrm{poly}}(\lambda)$ |  | Infinitely-often OWFs /
---
$\mathbf{SRE}\not\subseteq\mathbf{BPP}$
IO-IV-PoQ

#### Remarks on completeness-soundness gap.

We remark that the above theorems consider (AI-/IO-) IV-PoQ that only have an
inverse-polynomial completeness-soundness gap, i.e., the honest QPT prover
passes verification with probability at least $c$ and any PPT cheating prover
passes verification with probability at most $s$ where $c-s\geq
1/{\mathrm{poly}}(\lambda)$ for the security parameter $\lambda$. Due to the
inefficiency of verification, it is unclear if we can generically amplify the
gap even by sequential repetition.141414If we assume soundness against _non-
uniform_ PPT adversaries, then it is easy to show that sequential repetition
generically amplifies the gap. However, we consider the uniform model of
adversaries in this paper since otherwise we would need non-uniform
assumptions like one-way functions against non-uniform adversaries which is
stronger than the mere existence of one-way functions against uniform
adversaries. Fortunately, we find a stronger definition of soundness called
strong soundness which our constructions satisfy and enables us to amplify the
gap by sequential repetition. Roughly speaking, strong soundness requires that
soundness holds for almost all fixed cheating prover’s randomness rather than
on average. See Definition 4.8 for the formal definition. This enables us to
amplify the completeness-soundness gap to be optimal for any of our
constructions. However, we remark that this increases the round complexity and
in particular, the schemes of Theorems 1.3 and 1.6 are no longer constant-
round if we amplify the completeness-soundness gap. This issue could be
resolved if we could prove that parallel repetition amplifies the gap, but we
do not know how to prove this. Remark that we cannot use existing parallel
repetition theorems for interactive arguments because verification is
inefficient. Indeed, it is observed in [CHS05] that parallel repetition may
not amplify the gap when verification is inefficient even for two-round
arguments. Thus, we believe that it is very challenging or even impossible to
prove a general parallel repetition theorem for (AI-/IO-)IV-PoQ. Nonetheless,
it may be still possible to prove a parallel repetition theorem for our
particular constructions, which we leave as an interesting open problem.

#### Implausibility of two-round AI-IV-PoQ.

It is natural to ask how many rounds of interaction are needed. As already
mentioned, it is trivial to construct two-round PoQ if we assume the existence
of classically-hard and quantumly-easy problems such as factoring. We show
evidence that it is inevitable to rely on such an assumption for constructing
two-round (AI-/IO-)IV-PoQ. In the following, we state theorems for AI-IV-PoQ,
but they immediately imply similar results for IV-PoQ and IO-IV-PoQ because
they are stronger than AI-IV-PoQ.

First, we prove that there is no classical black-box reduction from security
of two-round AI-IV-PoQ to standard cryptographic assumptions unless the
assumptions do not hold against QPT adversaries.

###### Theorem 1.8 (Informal).

For a two-round AI-IV-PoQ, if its soundness can be reduced to a game-based
assumption by a classical black-box reduction, then the assumption does not
hold against QPT adversaries.

The formal version of the theorem is given in Theorem 7.5. Here, game-based
assumptions are those formalized as a game between the adversary and
challenger that include (but not limited to) general assumptions such as
security of OWFs, public key encryption, digital signatures, oblivious
transfers, indistinguishability obfuscation, succinct arguments etc. as well
as concrete assumptions such as the hardness of factoring, discrete-logarithm,
LWE etc.151515This is similar to falsifiable assumptions [Nao03, GW11] but
there is an important difference that we do not restrict the challenger to be
efficient. See Definition 7.1 for a formal definition. In particular, since we
believe that quantumly-secure OWFs exist, the above theorem can be interpreted
as a negative result on constructing two-round AI-IV-PoQ from general OWFs.

The proof idea is quite simple: Suppose that there is a classical black-box
reduction algorithm $R$ that is given a malicious prover as an oracle and
breaks an assumption. Intuitively, the reduction should still work even if it
is given the honest quantum prover $\mathcal{P}$ as an oracle. By considering
the combination of $R$ and $\mathcal{P}$ as a single quantum adversary, the
assumption is broken. We remark this can be seen as an extension of an
informal argument in [BKVV20] where they argue that it is unlikely that a two-
round PoQ can be constructed from the hardness of the LWE problem.161616They
use one-round PoQ to mean what we call two-round PoQ by counting interaction
from the verifier to prover and from the prover to verifier as a single round.

Note that Theorem 1.8 only rules out classical reductions. One may think that
the above argument extends to rule out quantum reductions, but there is some
technical difficulty. Roughly speaking, the problem is that a coherent
execution of the honest quantum prover may generate an entanglement between
its message register and internal register unlike a coherent execution of a
classical cheating prover (see Remark 7.6 for more explanations).171717This
observation is due to Mark Zhandry. To complement this, we prove another
negative result that also captures some class of quantum reductions.

###### Theorem 1.9 (Informal).

If a cryptographic primitive $\mathtt{P}$ has a quantumly-secure construction
(possibly 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 construction of $\mathtt{P}$ exists.

The formal version of the theorem is given in Theorem 7.13. The above theorem
can be interpreted as a negative evidence on constructing two-round IV-PoQ
from a cryptographic primitive for which we believe that quantumly-secure
constructions exist (e.g., OWFs, public key encryption, indistinguishability
obfuscation etc.) In particular, the above theorem rules out any constructions
that work relative to randomized classical oracles.181818Note that reductions
that work relative to _deterministic_ classical oracles do not necessarily
work relative to _randomized_ classical oracles [Aar08, Section 5]. Theorem
1.9 is incomparable to Theorem 1.8 since Theorem 1.9 does not require the
reduction to be classical unlike Theorem 1.8, but requires that the
construction and reduction work relative to randomized classical oracles.

Again, the proof idea is simple. Suppose that a quantumly-secure construction
$f$ of a primitive $\mathtt{P}$ exists relative to an oracle $O$. Then we
introduce an additional oracle $Q^{O}$ that takes a description of a quantum
circuit $C^{O}$ with $O$-gates and its input $x$ as input and outputs a
classical string according to the distribution of $C^{O}(x)$. Relative to
oracles $(O,Q^{O})$, there do not exist AI-IV-PoQ since a classical malicious
prover can query the description of the honest quantum prover to $Q^{O}$ to
get a response that passes the verification with high probability. On the
other hand, $f$ is quantumly-secure relative to $(O,Q^{O})$ since we assume
that it is quantumly-secure relative to $O$ and the additional oracle $Q^{O}$
is useless for quantum adversaries since they can simulate it by themselves.

We remark that the above theorems do not completely rule out black-box
constructions of two-round AI-IV-PoQ from quantumly-hard assumptions. For
example, consider a quantum black-box reduction that queries a cheating prover
with a fixed randomness multiple times. Such a reduction is not captured by
Theorem 1.8 because it is quantum. Moreover, it is not captured by Theorem 1.9
because it does not work relative to randomized classical oracles since we
cannot fix the randomness of the randomized classical oracle. It is a very
interesting open problem to study if such a reduction is possible.

#### Quantum advantage based on quantum primitives weaker than OWFs.

The existence of OWFs is the most fundamental assumption in classical
cryptography. Interestingly, it has been realized recently that it is not
necessarily the case in quantum cryptography [JLS18, Kre21, MY22b, AQY22,
BCQ23, AGQY22, CX22, MY22a, KQST22]. Many quantum cryptographic tasks can be
realized with new quantum primitives, which seem to be weaker than OWFs, such
as pseudorandom states generators [JLS18], one-way states generators [MY22b],
and EFI [BCQ23]. Can we construct PoQ (or its variants) from quantum
primitives that seem to be weaker than OWFs? We show that variants of PoQ can
be constructed from (classically-secure) quantum-evaluation OWFs (QE-OWFs).
QE-OWFs is the same as the standard classically-secure classical OWFs except
that the function evaluation algorithm is not deterministic classical
polynomial-time but quantum polynomial-time. (Its definition is given in
Section 8.) QE-OWFs seem to be weaker than classically-secure classical OWFs.
(For example, consider the function $f$ that on input $(x,y)$ outputs
$\Pi_{L}(x)\|g(y)$, where $L$ is any language in
$\mathbf{BQP}\setminus\mathbf{BPP}$, $\Pi_{L}$ is a function such that
$\Pi_{L}(x)=1$ if $x\in L$ and $\Pi_{L}(x)=0$ if $x\notin L$, and $g$ is any
classically-secure classical OWF. $f$ is a QE-OWF, and $f$ cannot be evaluated
in classical polynomial-time if $\mathbf{BQP}\neq\mathbf{BPP}$. For details,
see Section 8.) We show the following result.

###### Theorem 1.10.

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

A proof of the theorem is given in Section 8. QV-PoQ is the same as PoQ except
that the verifier is a QPT algorithm. Such a new notion of PoQ will be useful,
for example, when many local quantum computers are connected over classical
internet: A quantum local machine may want to check whether it is interacting
with a quantum computer or not over a classical channel.

The proof idea of Theorem 1.10 is as follows. Let $f$ be a QE-OWF. We
construct QV-PoQ as follows: The verifier first chooses
$x\leftarrow\\{0,1\\}^{n}$ and sends it to the prover. The prover then returns
$y$. The verifier finally evaluates $f(x)$ by himself, and accepts if it is
equal to $y$. If the soundness holds, we have QV-PoQ. On the other hand, if
the soundness does not hold, then it means that $f$ can be evaluated in PPT,
which means that $f$ is a classical OWF. It is an interesting open problem
whether PoQ or its variants can be constructed from pseudorandom quantum
states generators, one-way states generators, or EFI.

Infinitely-often classically-secure OWFs imply IO-IV-PoQ (Theorem 1.7), and
therefore Theorem 1.10 shows that the existence of QE-OWFs anyway implies
quantum advantage (i.e., QV-PoQ or IO-IV-PoQ). Moreover, QV-PoQ in Theorem
1.10 implies IV-PoQ (and therefore IO-IV-PoQ). (In general, QV-PoQ does not
necessarily imply IV-PoQ, but in our case, it does because our construction of
QV-PoQ is a two-round protocol with the verifier’s first message being a
uniformly-randomly-chosen classical bit string.) Hence we have the result that
QE-OWFs implies IO-IV-PoQ in either case.

###  1.2 Technical Overview

In this subsection, we provide technical overview of our main result, Theorem
1.1, namely, the construction of IV-PoQ from statistically-hiding commitments.
(The construction of AI-IV-PoQ is similar.) Our construction is based on PoQ
of [KMCVY22]. Let us first review their protocol. Their protocol can be
divided into two phases. In the first phase, the verifier first generates a
pair of a trapdoor and a trapdoor 2-to-1 collision resistant hash function
$F$. The verifier sends $F$ to the prover. The prover generates the quantum
state $\sum_{x\in\\{0,1\\}^{\ell}}\ket{x}\ket{F(x)}$, and measures the second
register in the computational basis to obtain the measurement result $y$. The
post-measurement state is $\ket{x_{0}}+\ket{x_{1}}$, where
$F(x_{0})=F(x_{1})=y$. This is the end of the first phase.

In the second phase, the verifier chooses a challenge bit $c\in\\{0,1\\}$
uniformly at random. If $c=0$, the verifier asks the prover to measure the
state in the computational basis. The verifier accepts and halts if the
prover’s measurement result is $x_{0}$ or $x_{1}$. (The verifier can compute
$x_{0}$ and $x_{1}$ from $y$, because it has the trapdoor.) The verifier
rejects and halts if the prover’s measurement result is not correct. If $c=1$,
the verifier sends the prover a bit string $\xi\in\\{0,1\\}^{\ell}$ which is
chosen uniformly at random. The prover changes the state
$\ket{x_{0}}+\ket{x_{1}}$ into the state $\ket{\xi\cdot
x_{0}}\ket{x_{0}}+\ket{\xi\cdot x_{1}}\ket{x_{1}}$, and measures the second
register in the Hadamard basis. If the measurement result is
$d\in\\{0,1\\}^{\ell}$, the post-measurement state is $\ket{\xi\cdot
x_{0}}+(-1)^{d\cdot(x_{0}\oplus x_{1})}\ket{\xi\cdot x_{1}}$, which is one of
the BB84 states $\\{\ket{0},\ket{1},\ket{+},\ket{-}\\}$. The verifier then
asks the prover to measure this single-qubit state in a certain basis, and
accepts if the measurement result is appropriate. This is the end of the
second phase. Intuitively, the soundness comes from the collision resistance
of $F$: If a malicious PPT prover is accepted by the verifier with some high
probability for both challenges, $c=0$ and $c=1$, we can construct a PPT
adversary that can find both $x_{0}$ and $x_{1}$ with non-negligible
probability, which contradicts the collision resistance.

Therefore, once we can construct an interactive protocol where a verifier can
let a prover generate $\ket{x_{0}}+\ket{x_{1}}$ in such a way that no
malicious PPT prover can learn both $x_{0}$ and $x_{1}$, we can construct PoQ
by running the second phase of [KMCVY22] on it. Can we do that with only OWFs?
Our key idea is to coherently execute statistically-hiding classical bit
commitments, which can be constructed from OWFs [HNO+09]. (A similar idea was
also used in [MY23].) The prover plays the role of the sender of the
commitment scheme, and the verifier plays the role of the receiver of the
commitment scheme. The prover first generates the state
$\sum_{b\in\\{0,1\\}}\sum_{x\in\\{0,1\\}^{\ell}}\ket{b}\ket{x}$, which is the
superposition of the bit $b\in\\{0,1\\}$ to commit and sender’s random seed
$x\in\\{0,1\\}^{\ell}$. The prover and the verifier then run the interactive
commitment phase. When the prover computes its message, it coherently computes
the message on its state, and measures a register to obtain the measurement
result.191919For example, in the prover’s $j$th round, if the prover possesses
a state $\sum_{b\in\\{0,1\\}}\sum_{x\in X_{b}}\ket{b}\ket{x}$, where $X_{b}$
is a certain set, it changes the state into $\sum_{b\in\\{0,1\\}}\sum_{x\in
X_{b}}\ket{b}\ket{x}\ket{f_{j}(b,x,t_{j})}$, and measures the third register
to obtain the measurement result $\alpha_{j}$, where $f_{j}$ is the function
that computes sender’s $j$th message, and $t_{j}$ is the transcript obtained
before the $j$th round. The prover sends $\alpha_{j}$ to the verifier as the
sender’s $j$th message. The prover sends the measurement result as the
sender’s message to the verifier. The verifier runs classical receiver’s
algorithm, and sends classical message to the prover. At the end of the commit
phase, the honest prover possesses the state

$\ket{0}\sum_{x\in X_{0,t}}\ket{x}+\ket{1}\sum_{x\in X_{1,t}}\ket{x},$ (1)

where $X_{b,t}$ is the set of sender’s random seeds that are consistent with
the committed bit $b$ and the transcript $t$, which is the sequence of all
classical messages exchanged between the prover and the verifier.

If $|X_{0,t}|=|X_{1,t}|=1$, Equation 1 is
$\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$, where $x_{b}$ is the unique element
of $X_{b,t}$ for each $b\in\\{0,1\\}$. In that case, we can run the second
phase of [KMCVY22] on it.202020Strictly speaking,
$\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$ is not equal to
$\ket{x_{0}}+\ket{x_{1}}$, but the protocol can be easily modified. Given
$\xi$, the prover has only to change $\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$
to $\ket{\xi\cdot x_{0}}\ket{x_{0}}+\ket{1\oplus(\xi\cdot x_{1})}\ket{x_{1}}$.
However, in general, $|X_{0,t}|=|X_{1,t}|=1$ is not always satisfied, and if
it is not satisfied, we do not know how to realize PoQ from the state of
Equation 1. This is our first problem. Moreover, even if
$|X_{0,t}|=|X_{1,t}|=1$ is satisfied, we have the second problem: The
efficient verifier cannot compute $(x_{0},x_{1})$, because there is no
trapdoor. The efficient verifier therefore cannot check whether the prover
passes the tests or not.212121 In [MY23], they resolve the first problem by
using a specific commitment scheme of [NOVY93] and resolve the second problem
by simply assuming the existence of a trapdoor. However, since the commitment
scheme of [NOVY93] relies on one-way permutations, their idea does not work
based on OWFs even if we give up efficient verification.

Unfortunately, we do not know how to solve the second problem, and therefore
we have to give up the efficient verification. On the other hand, we can solve
the first problem by introducing a new hashing technique, which may have
further applications. First, we notice that $|X_{0,t}|\simeq|X_{1,t}|$ with
overwhelming probability, because otherwise the statistical-hiding of the
classical bit commitment scheme is broken. Next, let
$\mathcal{H}\coloneqq\\{h:\mathcal{X}\to\mathcal{Y}\\}$ be a pairwise-
independent hash family with $\mathcal{X}=\\{0,1\\}^{\ell}$. The verifier
chooses $h_{0},h_{1}\in\mathcal{H}$ uniformly at random, and sends
$(h_{0},h_{1})$ to the prover. The prover changes the state of Equation 1 into

$\ket{0}\sum_{x\in X_{0,t}}\ket{x}\ket{h_{0}(x)}+\ket{1}\sum_{x\in
X_{1,t}}\ket{x}\ket{h_{1}(x)},$ (2)

and measures the third register in the computational-basis to obtain the
measurement result $y$. We show that if $|\mathcal{Y}|$ is chosen so that
$|\mathcal{Y}|\simeq 2|X_{b,t}|$, the state collapses by the measurement to
$\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$ with constant probability, where
$x_{b}\in X_{b,t}\cap h_{b}^{-1}(y)$ for $b\in\\{0,1\\}$. The remaining
problem is that the efficient verifier cannot compute $|X_{b,t}|$, and
therefore it cannot find the appropriate $|\mathcal{Y}|$. This problem is
solved by noticing that even if the verifier chooses $|\mathcal{Y}|$ randomly,
it is $\simeq 2|X_{b,t}|$ with non-negligible probability. More precisely, let
$m$ be an integer such that $(1+\epsilon)^{m}\geq 2^{\ell+1}$, where
$0<\epsilon<1$ is a small constant (which we take $\epsilon=1/100$, for
example). Then, we show that there exists a $j^{*}\in\\{0,1,...,m-1\\}$ such
that $\lceil(1+\epsilon)^{j^{*}}\rceil\simeq 2|X_{b,t}|$. Therefore, if the
efficient verifier chooses $j\in\\{0,1,...,m-1\\}$ uniformly at random, and
sets $\mathcal{Y}\coloneqq[\lceil(1+\epsilon)^{j}\rceil]$, then
$|\mathcal{Y}|\simeq 2|X_{b,t}|$ is satisfied with probability
$1/m=1/{\mathrm{poly}}(\lambda)$.

In summary, the efficient verifier can let the honest prover generate
$\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$ with non-negligible probability.
Fortunately, the second phase of [KMCVY22] is a public coin one, which means
that all messages from the verifier are uniformly-chosen random bit strings,
and therefore our efficient verifier can send all its messages without doing
any inefficient computation (such as finding an element of $X_{b,t}\cap
h_{b}^{-1}(y)$, etc.). All verifications are later done by the inefficient
verifier.

The soundness of our construction is shown from the computational-binding of
the classical bit commitment scheme. In the soundness proof of [KMCVY22], they
use the fact that no PPT malicious prover can find both $x_{0}$ and $x_{1}$,
which comes from the collision resistance. In our case, we have that property
from the computational-binding of the classical bit commitment scheme. In a
similar way as the soundness proof of [KMCVY22], we can construct a PPT
adversary $\mathcal{A}$ that can find both $x_{0}$ and $x_{1}$ from a PPT
malicious prover that passes both challenges with some high probability. We
can then construct a PPT adversary $\mathcal{B}$ that breaks computational-
binding of the classical bit commitment scheme from $\mathcal{A}$.

There is, however, a large difference in our case from that of [KMCVY22]. In
the protocol of [KMCVY22], the honest prover’s state is always
$\ket{x_{0}}+\ket{x_{1}}$, but in our case $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is not always satisfied. In
order to keep the $1/{\mathrm{poly}}$ completeness-soundness gap in our
protocol, we need a trick for the algorithm of the inefficient verifier. The
inefficient verifier first checks whether $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is satisfied or not. If it is
satisfied, the inefficient verifier computes the unique element $x_{b}\in
X_{b,t}\cap h_{b}^{-1}(y)$ for each $b\in\\{0,1\\}$, and checks whether the
transcript passes the second phase of the protocol of [KMCVY22] or not. On the
other hand, if $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is
not satisfied, we need some trick. A naive attempt would be to always accept
in such a case. Intuitively, this would give a $1/{\mathrm{poly}}$
completeness-soundness gap because we have a constant completeness-soundness
gap conditioned on $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$
by [KMCVY22] and such an event occurs with probability $1/{\mathrm{poly}}$ as
explained above. However, there is a flaw in the argument because a malicious
prover may change the probability that $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ holds. For example, if it can
control the probability to be $1$, then it passes the verification with
probability $1$, which is even higher than the honest quantum prover’s success
probability! Due to a similar reason, an attempt to let the inefficient
verifier always reject when $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap
h_{1}^{-1}(y)|=1$ is not satisfied also does not work. Our idea is to take the
middle of the two attempts: If $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap
h_{1}^{-1}(y)|=1$ is not satisfied, the inefficient verifier accepts with
probability $s$ and rejects with probability $1-s$, where $s$ is the soundness
parameter of the PoQ protocol of [KMCVY22], i.e., for any malicious prover,
the verifier accepts with probability at most $s+{\mathsf{negl}}(\lambda)$.
Let $p_{\mathbf{good}}$ be the probability that $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is satisfied in the interaction
between the honest prover and the verifier. Then, the probability that the
inefficient verifier accepts the honest prover is at least
$p_{\mathbf{good}}c+(1-p_{\mathbf{good}})s$, where $c$ is the completeness
parameter of the PoQ protocol of [KMCVY22], i.e., the verifier accepts the
honest prover with probability at least $c$. On the other hand, we show that
the soundness parameter of our protocol is also $s$. (Intuitively, this is
because if $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is
satisfied, then a malicious prover can pass the verification with probability
at most $s+{\mathsf{negl}}(\lambda)$ by the soundness of the PoQ protocol of
[KMCVY22], and if $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$
is not satisfied, the verifier accepts with probability $s$ regardless of the
prover’s behavior.) Therefore, we have
$p_{\mathbf{good}}c+(1-p_{\mathbf{good}})s-s=p_{\mathbf{good}}(c-s)\geq
1/{\mathrm{poly}}$, because $p_{\mathbf{good}}\geq 1/{\mathrm{poly}}$ as we
have explained. In this way, we can achieve the $1/{\mathrm{poly}}$
completeness-soundness gap.

Finally, in our construction, the inefficient verifier is enough to be a
classical deterministic polynomial-time algorithm that queries the
$\mathbf{NP}$ oracle, because as we have explained above, inefficient
computations that the inefficient verifier has to do are verifying
$|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ and finding the
single element $x_{b}\in X_{b,t}\cap h_{b}^{-1}(y)$ for each $b\in\\{0,1\\}$.

###  1.3 Related Works

IV-PoQ from random oracles was constructed in [ACC+22], which they call
Collision Hashing. Their construction is based on the observation that if the
state $\sum_{x}\ket{x}\ket{g(x)}$ is generated, where $g$ is a random oracle,
and the second register is measured in the computational basis, the post-
measurement state $\sum_{x\in g^{-1}(y)}\ket{x}$ corresponding to the
measurement result $y$ is a superposition of two computational-basis states
with some probability on which the second phase of [KMCVY22] can be run.
(Actually, because they assume random oracles, the non-interactive protocol of
[BKVV20] can be run instead of [KMCVY22].) This idea seems to be somehow
related to our idea.

[AA15] studied a sampling problem, Fourier Sampling, where given an oracle
$f:\\{0,1\\}^{n}\to\\{+1,-1\\}$, it is required to sample from the
distribution $\\{p_{y}\\}_{y}$, where $p_{y}\coloneqq
2^{-n}\hat{f}(y)^{2}=(\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}f(x)(-1)^{x\cdot
y})^{2}$ within an additive error. It needs exponentially-many queries to
classically solve it relative to a random oracle. [Aar10] also introduced a
search problem, Fourier Fishing, where given an oracle
$f:\\{0,1\\}^{n}\to\\{+1,-1\\}$, find $z\in\\{0,1\\}^{n}$ such that
$|\hat{f}(z)|\geq 1$. It needs exponentially-many queries to classically solve
it relative to a random oracle. The verification of Fourier Fishing can be
done inefficiently. [Aar10] also introduced a decision problem, Fourier
Checking, and show that it requires exponentially-many queries to solve it
classically relative to a certain oracle. Whether
$\mathbf{BQP}\neq\mathbf{BPP}$ relative to a random oracle is an open problem,
and given the Aaronson-Ambainis conjecture [AA14], showing it seems to be
difficult.

[AC17] showed that if OWFs exist, then there are oracles
$A\in\mathbf{P}/\mathbf{poly}$ such that
$\mathbf{BPP}^{A}\neq\mathbf{BQP}^{A}$ (and even
$\mathbf{BQP}^{A}\not\subset\mathbf{SZK}^{A}$). The paper also showed that if
there exist subexponentially-secure OWFs, then Fourier Sampling and Fourier
Fishing are classically hard relative to oracles in
$\mathbf{P}/\mathbf{poly}$. Regarding the possibility of removing the oracles,
the authors say that “… in the unrelativized world, there seems to be no hope
at present of proving $\mathbf{BPP}\neq\mathbf{BQP}$ under any hypothesis
nearly as weak as the existence of one-way functions”, which suggests the
difficulty of demonstrating quantum advantage based only on one-way functions.
We bypass the difficulty by considering interactive protocols.

It was pointed out in [LLQ22] that the complexity assumption of
$\mathbf{PP}\neq\mathbf{BPP}$ is necessary for the existence of PoQ. A similar
idea can be applied to show that $\mathbf{PP}\neq\mathbf{BPP}$ is necessary
for the existence of (AI-/IO-)IV-PoQ. (For the convenience of readers, we
provide a proof in Appendix A.) We remark that the proof holds even if we
allow the honest prover to perform post-selection. Moreover, it holds even if
the verifier in the first phase is unbounded-time.

Unconditional quantum advantage over restricted classical computing was also
studied [BGK18, BGKT20, WKST19, GS20]. Unconditional separations between
quantum and classical computing are appealing, but in this paper we do not
focus on the setups of restricting classical computing. Note that showing
unconditional quantum advantage without restricting classical computing is at
least as hard as proving $\mathbf{PP}\neq\mathbf{BPP}$ ([LLQ22] and Appendix
A), which is a major open problem in complexity theory.

The idea of coherently running statistically-hiding commitments was first
introduced in [MY23]. However, they could apply the idea only to the specific
commitment scheme of [NOVY93] whereas we can apply it to _any_ statistically-
hiding commitments. This is made possible by our new hashing technique as
explained in Section 1.2.

##  2 Preliminaries

###  2.1 Basic Notations

We use the standard notations of quantum computing and cryptography. We use
$\lambda$ as the security parameter. $[n]$ means 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 a set $S$, $|S|$ means the
cardinality of $S$. We write ${\mathsf{negl}}$ to mean a negligible function
and ${\mathrm{poly}}$ to mean a polynomial. PPT stands for (classical)
probabilistic polynomial-time and QPT stands for quantum polynomial-time. For
an algorithm $A$, $y\leftarrow A(x)$ means that the algorithm $A$ outputs $y$
on input $x$. For two bit strings $x$ and $y$, $x\|y$ means the concatenation
of them. For simplicity, we sometimes omit the normalization factor of a
quantum state. (For example, we write
$\frac{1}{\sqrt{2}}(|x_{0}\rangle+|x_{1}\rangle)$ just as
$|x_{0}\rangle+|x_{1}\rangle$.) $I\coloneqq|0\rangle\langle
0|+|1\rangle\langle 1|$ is the two-dimensional identity operator. For the
notational simplicity, we sometimes write $I^{\otimes n}$ just as $I$ when the
dimension is clear from the context.

###  2.2 Pairwise-Independent Hash Family

###### Definition 2.1.

A family of hash functions
$\mathcal{H}\coloneqq\\{h:\mathcal{X}\to\mathcal{Y}\\}$ is pairwise-
independent 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}}.$ (3)

###  2.3 OWFs

###### Definition 2.2 (OWFs).

A function $f:\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ is a (classically-secure) OWF if
it is computable in classical deterministic polynomial-time, and 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).$
(4)

###### Definition 2.3 (Infinitely-often OWFs).

A function $f:\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ is a (classically-secure)
infinitely-often OWF if it is computable in classical deterministic
polynomial-time, and there exists an infinite set $\Lambda\subseteq\mathbb{N}$
such that for any PPT adversary $\mathcal{A}$,

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

for all $\lambda\in\Lambda$.

###### Definition 2.4 (Auxiliary-input function ensemble).

An auxiliary-input function ensemble is a collection of functions
$\mathcal{F}\coloneqq\\{f_{\sigma}:\\{0,1\\}^{p(|\sigma|)}\to\\{0,1\\}^{q(|\sigma|)}\\}_{\sigma\in\\{0,1\\}^{*}}$,
where $p$ and $q$ are polynomials. We call $\mathcal{F}$ polynomial-time
computable if there is a classical deterministic polynomial-time algorithm $F$
such that for every $\sigma\in\\{0,1\\}^{*}$ and
$x\in\\{0,1\\}^{p(|\sigma|)}$, we have $F(\sigma,x)=f_{\sigma}(x)$.

###### Definition 2.5 (Auxiliary-input OWFs).

A (classically-secure) auxiliary-input OWF is a polynomial-time computable
auxiliary-input function ensemble
$\mathcal{F}\coloneqq\\{f_{\sigma}:\\{0,1\\}^{p(|\sigma|)}\to\\{0,1\\}^{q(|\sigma|)}\\}_{\sigma\in\\{0,1\\}^{*}}$
such that for every uniform PPT adversary $\mathcal{A}$ and a polynomial
${\mathrm{poly}}(\lambda)$, there exists an infinite set
$\Lambda\subseteq\\{0,1\\}^{*}$ such that,

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

for all $\sigma\in\Lambda$.

######  Remark 2.6.

It is easy to see that OWFs imply infinitely-often OWFs, and infinitely-often
OWFs imply auxiliary-input OWFs.

###### Theorem 2.7 ([OW93]).

Auxiliary-input OWFs exist if $\mathbf{CZK}\not\subseteq\mathbf{BPP}$.

######  Remark 2.8.

As is pointed out in [Vad06], auxiliary-input OWFs secure against non-uniform
PPT adversaries exist if $\mathbf{CZK}\not\subseteq\mathbf{P}/\mathbf{poly}$.

###  2.4 Commitments

###### Definition 2.9 (Statistically-hiding and computationally-binding
classical bit commitments).

A statistically-hiding and computationally-binding classical bit commitment
scheme is an interactive protocol $\langle\mathcal{S},\mathcal{R}\rangle$
between two PPT algorithms $\mathcal{S}$ (the sender) and $\mathcal{R}$ (the
receiver) such that

  * •

In the commit phase, $\mathcal{S}$ takes $b\in\\{0,1\\}$ and $1^{\lambda}$ as
input and $\mathcal{R}$ takes $1^{\lambda}$ as input. $\mathcal{S}$ and
$\mathcal{R}$ exchange classical messages. The transcript $t$, i.e., the
sequence of all classical messages exchanged between $\mathcal{S}$ and
$\mathcal{R}$, is called a commitment. At the end of the commit phase,
$\mathcal{S}$ privately outputs a decommitment $\mathsf{decom}$.

  * •

In the open phase, $\mathcal{S}$ sends $(b,\mathsf{decom})$ to $\mathcal{R}$.
$\mathcal{R}$ on input $(t,b,\mathsf{decom})$ outputs $\top$ or $\bot$.

We require the following three properties.

#### Perfect Correctness:

For all $\lambda\in\mathbb{N}$ and $b\in\\{0,1\\}$, if
$\mathcal{S}(1^{\lambda},b)$ and $\mathcal{R}(1^{\lambda})$ behave honestly,
$\Pr[\top\leftarrow\mathcal{R}]=1$.

#### Statistical Hiding:

Let us consider the following security game between the honest sender
$\mathcal{S}$ and a malicious receiver $\mathcal{R}^{*}$:

  1. 1.

$\mathcal{S}(b,1^{\lambda})$ and $\mathcal{R}^{*}(1^{\lambda})$ run the commit
phase.

  2. 2.

$\mathcal{R}^{*}$ outputs $b^{\prime}\in\\{0,1\\}$.

We say that the scheme is statistically hiding if for any computationally
unbounded adversary $\mathcal{R}^{*}$,

$|\Pr[0\leftarrow\mathcal{R}^{*}|b=0]-\Pr[0\leftarrow\mathcal{R}^{*}|b=1]|\leq{\mathsf{negl}}(\lambda).$
(7)

#### Computational Binding:

Let us consider the following security game between a malicious sender
$\mathcal{S}^{*}$ and the honest receiver $\mathcal{R}$:

  1. 1.

$\mathcal{S}^{*}(1^{\lambda})$ and $\mathcal{R}(1^{\lambda})$ run the commit
phase to generate a commitment $t$.

  2. 2.

$\mathcal{S}^{*}$ sends $(0,\mathsf{decom}_{0})$ and $(1,\mathsf{decom}_{1})$
to $\mathcal{R}$.

We say that the scheme is computationally binding if for any PPT malicious
$\mathcal{S}^{*}$,

$\Pr[\top\leftarrow\mathcal{R}(0,\mathsf{decom}_{0})\wedge\top\leftarrow\mathcal{R}(1,\mathsf{decom}_{1})]\leq{\mathsf{negl}}(\lambda).$
(8)

Statistically-hiding and computationally-binding bit commitments can be
constructed from OWFs.

###### Theorem 2.10 ([HNO+09]).

If OWFs exist, then statistically-hiding and computationally-binding bit
commitments exist.

Moreover, constant-round schemes are known from collision-resistant hash
functions [HM96]. The assumption is further weakened to the existence of
distributional collision-resistant hash functions, which exist if there is an
hard-on-average problem in $\mathbf{SZK}$.

###### Theorem 2.11 ([KY18, BHKY19]).

If distributional collision-resistant hash functions exist, which exist if
there is an hard-on-average problem in $\mathbf{SZK}$, then constant-round
statistically-hiding and computationally-binding bit commitments exist.

We define an infinitely-often variant of statistically-hiding and
computationally-binding commitments as follows.

###### Definition 2.12 (Infinitely-often statistically-hiding and
computationally-binding commitments).

Infinitely-often statistically-hiding and computationally-binding commitments
are defined similarly to Definition 2.9 except that we require the existence
of an infinite set $\Lambda\subseteq\mathbb{N}$ such that statistical hiding
and computational binding hold for all $\lambda\in\Lambda$ instead of for all
$\lambda\in\mathbb{N}$.

By using infinitely-often OWFs instead of OWFs in the commitment scheme of
[HNO+09], we obtain the following theorem. Since the construction and proof
are almost identical to those of [HNO+09], we omit the details.

###### Theorem 2.13 (Infinitely-often variant of [HNO+09]).

If infinitely-often OWFs exist, then infinitely-often statistically-hiding and
computationally-binding bit commitments exist.

We also define an auxiliary-input variant of statistically-hiding and
computationally-binding commitments. Intuitively, it is a family of commitment
schemes indexed by an auxiliary input where correctness and statistical hiding
hold for all auxiliary inputs and an “auxiliary-input” version of
computational binding holds, i.e., for any PPT cheating sender
$\mathcal{S}^{*}$, there is an infinite set of auxiliary inputs under which
computational binding holds.

###### Definition 2.14 (Auxiliary-input statistically-hiding and
computationally-binding classical bit commitments).

An auxiliary-input statistically-hiding and computationally-binding classical
bit commitment scheme is an interactive protocol
$\langle\mathcal{S},\mathcal{R}\rangle$ between two PPT algorithms
$\mathcal{S}$ (the sender) and $\mathcal{R}$ (the receiver) associated with an
infinite subset $\Sigma\subseteq\\{0,1\\}^{*}$such that

  * •

In the commit phase, $\mathcal{S}$ takes $b\in\\{0,1\\}$ and the auxiliary
input $\sigma\in\Sigma$ as input and $\mathcal{R}$ takes the auxiliary input
$\sigma$ as input. $\mathcal{S}$ and $\mathcal{R}$ exchange classical
messages. The transcript $t$, i.e., the sequence of all classical messages
exchanged between $\mathcal{S}$ and $\mathcal{R}$, is called a commitment. At
the end of the commit phase, $\mathcal{S}$ privately outputs a decommitment
$\mathsf{decom}$.

  * •

In the open phase, $\mathcal{S}$ sends $(b,\mathsf{decom})$ to $\mathcal{R}$.
$\mathcal{R}$ on input $(t,b,\mathsf{decom})$ outputs $\top$ or $\bot$.

We require the following properties:

#### Perfect Correctness:

For all $\sigma\in\Sigma$ and $b\in\\{0,1\\}$, if $\mathcal{S}(b,\sigma)$ and
$\mathcal{R}(\sigma)$ behave honestly, $\Pr[\top\leftarrow\mathcal{R}]=1$.

#### Statistical Hiding:

Let us consider the following security game between the honest sender
$\mathcal{S}$ and a malicious receiver $\mathcal{R}^{*}$:

  1. 1.

$\mathcal{S}(b,\sigma)$ and $\mathcal{R}^{*}(\sigma)$ run the commit phase.

  2. 2.

$\mathcal{R}^{*}$ outputs $b^{\prime}\in\\{0,1\\}$.

We say that the scheme is statistically hiding if for all $\sigma\in\Sigma$
and any computationally unbounded adversary $\mathcal{R}^{*}$,

$|\Pr[0\leftarrow\mathcal{R}^{*}|b=0]-\Pr[0\leftarrow\mathcal{R}^{*}|b=1]|\leq{\mathsf{negl}}(|\sigma|).$
(9)

#### Computational Binding:

Let us consider the following security game between a malicious sender
$\mathcal{S}^{*}$ and the honest receiver $\mathcal{R}$:

  1. 1.

$\mathcal{S}^{*}(\sigma)$ and $\mathcal{R}(\sigma)$ run the commit phase to
generate a commitment $t$.

  2. 2.

$\mathcal{S}^{*}$ sends $(0,\mathsf{decom}_{0})$ and $(1,\mathsf{decom}_{1})$
to $\mathcal{R}$.

We say that the scheme is computationally binding if for any PPT malicious
sender $\mathcal{S}^{*}$ and a polynomial ${\mathrm{poly}}$, there exists an
infinite subset $\Lambda\subseteq\Sigma$ such that for any $\sigma\in\Lambda$,

$\Pr[\top\leftarrow\mathcal{R}(t,0,\mathsf{decom}_{0})\wedge\top\leftarrow\mathcal{R}(t,1,\mathsf{decom}_{1})]\leq\frac{1}{{\mathrm{poly}}(|\sigma|)}.$
(10)

By using auxiliary-input OWFs instead of OWFs in the commitment scheme of
[HNO+09], we obtain the following theorem. Since the construction and proof
are almost identical to those of [HNO+09], we omit the details.

###### Theorem 2.15 (Auxiliary-input variant of [HNO+09]).

If auxiliary-input OWFs exist, then auxiliary-input statistically-hiding and
computationally-binding bit commitments exist.

Similarly, by using auxiliary-input collision-resistant hash functions instead
of collision-resistant hash functions in the commitment scheme of [HM96], we
obtain 2-round auxiliary-input statistically-hiding and computationally-
binding bit commitments. As shown in Section B.1, auxiliary-input collision-
resistant hash functions exist if and only if
$\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$. Thus, we obtain the following theorem.

###### Theorem 2.16 (Auxiliary-input variant of [HM96]).

If auxiliary-input collision-resistant hash functions exist, which exist if
and only if $\mathbf{PWPP}\nsubseteq\mathbf{FBPP}$, then 2-round auxiliary-
input statistically-hiding and computationally-binding bit commitments exist.

In addition, we observe in Section B.2 that the instance-dependent commitments
for $\mathbf{SZK}$ of [OV08] directly gives constant-round auxiliary-input
statistically-hiding and computationally-binding bit commitments under the
assumption that $\mathbf{SZK}\nsubseteq\mathbf{BPP}$.

###### Theorem 2.17 (Auxiliary-input variant of [OV08]).

If $\mathbf{SZK}\nsubseteq\mathbf{BPP}$, then constant-round auxiliary-input
statistically-hiding and computationally-binding bit commitments exist.

######  Remark 2.18.

In the constructions for Theorems 2.15 and 2.16, we can set
$\Sigma\coloneqq\\{0,1\\}^{*}$. However, we do not know if this is possible
for the construction for Theorem 2.17 given in Section B.2. This is why we
introduce the subset $\Sigma$ in Definition 2.14.

##  3 Hashing Lemmas

In this section, we show two useful lemmas, Lemma 3.1 and Lemma 3.2. Lemma 3.1
is used to show Lemma 3.2, and Lemma 3.2 is used in the proof of our main
result.

###### Lemma 3.1.

Let $\mathcal{H}\coloneqq\\{h:\mathcal{X}\to\mathcal{Y}\\}$ be a pairwise-
independent hash family such that $|\mathcal{X}|\geq 2$. Let
$S\subseteq\mathcal{X}$ be a subset of $\mathcal{X}$. For any
$y\in\mathcal{Y}$,

$\Pr_{h\leftarrow\mathcal{H}}[|S\cap h^{-1}(y)|\geq
1]\geq\frac{|S|}{|\mathcal{Y}|}-\frac{|S|^{2}}{2|\mathcal{Y}|^{2}}.$ (11)

###### Proof of Lemma 3.1.

First, if $|S|=0$, Equation 11 trivially holds. Second, let us consider the
case when $|S|=1$. In that case,

$\displaystyle\Pr_{h\leftarrow\mathcal{H}}[|S\cap h^{-1}(y)|\geq 1]$
$\displaystyle=\frac{1}{|\mathcal{Y}|}$ (12)
$\displaystyle\geq\frac{1}{|\mathcal{Y}|}-\frac{1}{2|\mathcal{Y}|^{2}}$ (13)
$\displaystyle=\frac{|S|}{|\mathcal{Y}|}-\frac{|S|^{2}}{2|\mathcal{Y}|^{2}},$
(14)

and therefore Equation 11 is satisfied. Here, the first equality comes from
the fact that the probability that the unique element of $S$ is mapped to $y$
is $1/|\mathcal{Y}|$.

Finally, let us consider the case when $|S|\geq 2$. The following argument is
based on [Sta22]. First, for each $y\in\mathcal{Y}$,

$\displaystyle\sum_{j=1}^{|S|}j\Pr_{h\leftarrow\mathcal{H}}[|S\cap
h^{-1}(y)|=j]$
$\displaystyle=\underset{h\leftarrow\mathcal{H}}{\mathbb{E}}[|S\cap
h^{-1}(y)|]$ (15)
$\displaystyle=\underset{h\leftarrow\mathcal{H}}{\mathbb{E}}[|\\{x\in
S:h(x)=y\\}|]$ (16) $\displaystyle=\sum_{x\in
S}\Pr_{h\leftarrow\mathcal{H}}[h(x)=y]$ (17)
$\displaystyle=\frac{|S|}{|\mathcal{Y}|}.$ (18)

Second, for each $y\in\mathcal{Y}$,

$\displaystyle\sum_{j=1}^{|S|}(j-1)\Pr_{h\leftarrow\mathcal{H}}[|S\cap
h^{-1}(y)|=j]$ $\displaystyle\leq\sum_{j=1}^{|S|}{j\choose
2}\Pr_{h\leftarrow\mathcal{H}}[|S\cap h^{-1}(y)|=j]$ (19)
$\displaystyle=\underset{h\leftarrow\mathcal{H}}{\mathbb{E}}\left[{|S\cap
h^{-1}(y)|\choose 2}\right]$ (20)
$\displaystyle=\underset{h\leftarrow\mathcal{H}}{\mathbb{E}}[|\\{\\{x,x^{\prime}\\}\subseteq
S:x\neq x^{\prime},h(x)=h(x^{\prime})=y\\}|]$ (21)
$\displaystyle=\sum_{\\{x,x^{\prime}\\}\subseteq S,x\neq
x^{\prime}}\Pr_{h\leftarrow\mathcal{H}}[h(x)=h(x^{\prime})=y]$ (22)
$\displaystyle=\frac{1}{|\mathcal{Y}|^{2}}{|S|\choose 2}$ (23)
$\displaystyle=\frac{|S|(|S|-1)}{2|\mathcal{Y}|^{2}}$ (24)
$\displaystyle\leq\frac{|S|^{2}}{2|\mathcal{Y}|^{2}}.$ (25)

(Note that ${n\choose m}=0$ for any $n<m$.) By extracting both sides of
Equation 18 and Equation 25, we have

$\displaystyle\sum_{j=1}^{|S|}\Pr_{h\leftarrow\mathcal{H}}[|S\cap
h^{-1}(y)|=j]$ $\displaystyle\geq$
$\displaystyle\frac{|S|}{|\mathcal{Y}|}-\frac{|S|^{2}}{2|\mathcal{Y}|^{2}},$
(26)

which shows Lemma 3.1. ∎

###### Lemma 3.2.

Let $\mathcal{H}\coloneqq\\{h:\mathcal{X}\to\mathcal{Y}\\}$ be a pairwise-
independent hash family such that $|\mathcal{X}|\geq 2$. Let
$S\subseteq\mathcal{X}$ be a subset of $\mathcal{X}$. For any
$y\in\mathcal{Y}$,

$\Pr_{h\leftarrow\mathcal{H}}[|S\cap
h^{-1}(y)|=1]\geq\frac{|S|}{|\mathcal{Y}|}-\frac{|S|^{2}}{|\mathcal{Y}|^{2}}.$
(27)

###### Proof of Lemma 3.2.

For any $y\in\mathcal{Y}$,

$\displaystyle\frac{|S|}{|\mathcal{Y}|}$
$\displaystyle=\sum_{j=1}^{|S|}j\Pr_{h\leftarrow\mathcal{H}}[|S\cap
h^{-1}(y)|=j]$ (28) $\displaystyle\geq\Pr_{h\leftarrow\mathcal{H}}[|S\cap
h^{-1}(y)|=1]+2\Pr_{h\leftarrow\mathcal{H}}[|S\cap h^{-1}(y)|\geq 2]$ (29)
$\displaystyle=2\Pr_{h\leftarrow\mathcal{H}}[|S\cap h^{-1}(y)|\geq
1]-\Pr_{h\leftarrow\mathcal{H}}[|S\cap h^{-1}(y)|=1]$ (30)
$\displaystyle\geq\frac{2|S|}{|\mathcal{Y}|}-\frac{|S|^{2}}{|\mathcal{Y}|^{2}}-\Pr_{h\leftarrow\mathcal{H}}[|S\cap
h^{-1}(y)|=1].$ (31)

Here, the first equality is from Equation 18, and in the last inequality we
have used Lemma 3.1. Therefore,

$\displaystyle\Pr_{h\leftarrow\mathcal{H}}[|S\cap h^{-1}(y)|=1]$
$\displaystyle\geq\frac{2|S|}{|\mathcal{Y}|}-\frac{|S|^{2}}{|\mathcal{Y}|^{2}}-\frac{|S|}{|\mathcal{Y}|}$
(32)
$\displaystyle=\frac{|S|}{|\mathcal{Y}|}-\frac{|S|^{2}}{|\mathcal{Y}|^{2}},$
(33)

which shows Lemma 3.2. ∎

##  4 Inefficient-Verifier Proofs of Quantumness

In this section, we define inefficient-verifier proofs of quantumness (IV-PoQ)
and its variants. Then we show that sequential repetition amplifies the
completeness-soundness gap assuming a special property of soundness, which we
call a strong soundness, for the base scheme.

###  4.1 Definitions

We define IV-PoQ. It is identical to the definition of PoQ, which are
implicitly defined in [BCM+21], except that we allow the verifier to be
unbounded-time after completing interaction with the prover.

###### Definition 4.1 (Inefficient-verifier proofs of quantumness (IV-PoQ)).

An inefficient-verifier proof of quantumness (IV-PoQ) is an interactive
protocol $(\mathcal{P},\mathcal{V})$ between a QPT algorithm $\mathcal{P}$
(the prover) and an algorithm $\mathcal{V}=(\mathcal{V}_{1},\mathcal{V}_{2})$
(the verifier) where $\mathcal{V}_{1}$ is PPT and $\mathcal{V}_{2}$ is
unbounded-time. The protocol is divided into two phases. In the first phase,
$\mathcal{P}$ and $\mathcal{V}_{1}$ take the security parameter $1^{\lambda}$
as input and interact with each other over a classical channel. Let $I$ be the
transcript, i.e., the sequence of all classical messages exchanged between
$\mathcal{P}$ and $\mathcal{V}_{1}$. In the second phase, $\mathcal{V}_{2}$
takes $I$ as input and outputs $\top$ or $\bot$. We require the following two
properties for some functions $c$ and $s$ such that $c(\lambda)-s(\lambda)\geq
1/{\mathrm{poly}}(\lambda)$.

####  $c$-completeness:

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\geq
c(\lambda)-{\mathsf{negl}}(\lambda).$ (34)

####  $s$-soundness:

For any PPT malicious prover $\mathcal{P}^{*}$,

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\leq
s(\lambda)+{\mathsf{negl}}(\lambda).$ (35)

######  Remark 4.2.

$\mathcal{V}_{2}$ could take $\mathcal{V}_{1}$’s secret information as input
in addition to $I$, but without loss of generality, we can assume that
$\mathcal{V}_{2}$ takes only $I$, because we can always modify the protocol of
the first phase in such a way that $\mathcal{V}_{1}$ sends its secret
information to $\mathcal{P}$ at the end of the first phase.

######  Remark 4.3.

In our constructions, $\mathcal{V}_{2}$ is actually enough to be a classical
deterministic polynomial-time algorithm that queries the $\mathbf{NP}$ oracle.
(See Section 6.3.)

We define an infinitely-often version of IV-PoQ as follows.

###### Definition 4.4 (Infinitely-often inefficient-verifier proofs of
quantumness (IO-IV-PoQ)).

An infinitely-often inefficient-verifier proofs of quantumness (IO-IV-PoQ) is
defined similarly to IV-PoQ (Definition 4.1) except that we require the
existence of an infinite set $\Lambda\subseteq\mathbb{N}$ such that
$c$-completeness and $s$-soundness hold for all $\lambda\in\Lambda$ instead of
for all $\lambda\in\mathbb{N}$.

We also define an auxiliary-input variant of IV-PoQ as follows. It is defined
similarly to IV-PoQ except that the prover and verifier take an auxiliary
input instead of the security parameter and completeness should hold for all
auxiliary inputs wheres soundness is replaced to auxiliary-input soundness,
i.e., for any PPT cheating prover $\mathcal{P}^{*}$, there exists an infinite
set of auxiliary inputs under which soundness holds.

###### Definition 4.5 (Auxiliary-input inefficient-verifier proofs of
quantumness (AI-IV-PoQ)).

An auxiliary-input inefficient-verifier proof of quantumness (AI-IV-PoQ) is an
interactive protocol $(\mathcal{P},\mathcal{V})$ between a QPT algorithm
$\mathcal{P}$ (the prover) and an algorithm
$\mathcal{V}=(\mathcal{V}_{1},\mathcal{V}_{2})$ (the verifier) where
$\mathcal{V}_{1}$ is PPT and $\mathcal{V}_{2}$ is unbounded-time, associated
with an infinite set $\Sigma\subseteq\\{0,1\\}^{*}$. The protocol is divided
into two phases. In the first phase, $\mathcal{P}$ and $\mathcal{V}_{1}$ take
an auxiliary input $\sigma\in\Sigma$ as input and interact with each other
over a classical channel. Let $I$ be the transcript, i.e., the sequence of all
classical messages exchanged between $\mathcal{P}$ and $\mathcal{V}_{1}$. In
the second phase, $\mathcal{V}_{2}$ takes $I$ as input and outputs $\top$ or
$\bot$. We require the following two properties for some functions $c$ and $s$
such that $c(|\sigma|)-s(|\sigma|)\geq 1/{\mathrm{poly}}(|\sigma|)$.

####  $c$-completeness:

For any $\sigma\in\Sigma$,

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}(\sigma),\mathcal{V}_{1}(\sigma)\rangle]\geq
c(|\sigma|)-{\mathsf{negl}}(|\sigma|).$ (36)

####  $s$-soundness:

For any PPT malicious prover $\mathcal{P}^{*}$ and polynomial $p$, there
exists an infinite set $\Lambda\subseteq\Sigma$ such that

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}(\sigma),\mathcal{V}_{1}(\sigma)\rangle]\leq
s(|\sigma|)+\frac{1}{p(|\sigma|)}$ (37)

for all $\sigma\in\Lambda$.

######  Remark 4.6.

We can set $\Sigma\coloneqq\\{0,1\\}^{*}$ for all our constructions of AI-IV-
PoQ except for the one based on $\mathbf{SZK}\neq\mathbf{BPP}$. See also
Remark 2.18.

######  Remark 4.7.

It is easy to see that IV-PoQ imply IO-IV-PoQ, and IO-IV-PoQ imply AI-IV-PoQ.

Even though AI-IV-PoQ is weaker than IV-PoQ, we believe that it still
demonstrates a meaningful notion of quantum advantage, because it shows
“worst-case quantum advantage” in the sense that no PPT algorithm can simulate
the QPT honest prover on all auxiliary inputs $\sigma\in\Sigma$.

###  4.2 Strong Soundness

Unfortunately, we do not know if parallel or even sequential repetition
amplifies the completeness-soundness gap for general (AI-/IO-)IV-PoQ. Here, we
define a stronger notion of soundness which we call strong soundness. In
Section 4.3, we show that sequential repetition amplifies the completeness-
soundness gap if the base scheme satisfies strong soundness. In Section 6, we
show that our (AI-/IO-)IV-PoQ satisfies strong soundness. Thus, gap
amplification by sequential repetition works for our particular constructions
of (AI-/IO-)IV-PoQ.

Roughly, the $s$-strong-soundness requires that a PPT cheating prover can pass
verification with probability at most $\approx s$ for almost all fixed
randomness. The formal definition is given below.

###### Definition 4.8 (Strong soundness for IV-PoQ).

We say that an IV-PoQ
$(\mathcal{P},\mathcal{V}=(\mathcal{V}_{1},\mathcal{V}_{2}))$ satisfies
$s$-strong-soundness if the following holds:

####  $s$-strong-soundness:

For any PPT malicious prover $\mathcal{P}^{*}$ and any polynomial $p$,

$\displaystyle\Pr_{r\leftarrow\mathcal{R}}\left[\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}_{r}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\geq
s(\lambda)+\frac{1}{p(\lambda)}\right]\leq\frac{1}{p(\lambda)}$ (38)

for all sufficiently large $\lambda$ where $\mathcal{R}$ is the randomness
space for $\mathcal{P}^{*}$ and $\mathcal{P}^{*}_{r}$ is $\mathcal{P}^{*}$
with the fixed randomness $r$.  It is defined similarly for (AI-/IO-)IV-PoQ.

It is easy to see that $s$-strong-soundness implies $s$-soundness.

###### Lemma 4.9.

For any $s$, $s$-strong-soundness implies $s$-soundness for (AI-/IO-)IV-PoQ.

###### Proof.

We focus on the case of IV-PoQ since the cases of (AI-/IO-)IV-PoQ are similar.
If there is a PPT malicious prover $\mathcal{P}^{*}$ that breaks $s$-soundness
of IV-PoQ, then there exists a polynomial $p$ such that

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\geq
s(\lambda)+\frac{3}{p(\lambda)}$ (39)

for infinitely many $\lambda$. By a standard averaging argument, this implies

$\displaystyle\Pr_{r\leftarrow\mathcal{R}}\left[\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}_{r}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\geq
s(\lambda)+\frac{1}{p(\lambda)}\right]\geq\frac{2}{p(\lambda)}$ (40)

for infinitely many $\lambda$. This contradicts $s$-strong-soundness. Thus,
Lemma 4.9 holds. ∎

We remark that the other direction does not seem to hold. For example, suppose
that a PPT malicious prover $\mathcal{P}^{*}$ passes the verification with
probability $1$ for $0.99$-fraction of randomness and with probability $0$ for
the rest of randomness. In this case, $\mathcal{P}^{*}$ breaks
$0.99$-soundness. On the other hand, it does not break $s$-strong-soundness
for any constant $s>0$.

###  4.3 Gap Amplification

Algorithm 1 $N$-sequential-repetition version $\Pi^{N\text{-}\mathsf{seq}}$ of
$\Pi$

  1. The first phase:

The QPT prover $\mathcal{P}^{N\text{-}\mathsf{seq}}$ and PPT verifier
$\mathcal{V}_{1}^{N\text{-}\mathsf{seq}}$ run the first phase of $\Pi$
sequentially $N$ times (i.e., after they finish $i$-th execution, they start
$(i+1)$-st execution) where $\mathcal{P}^{N\text{-}\mathsf{seq}}$ plays the
role of $\mathcal{P}$ and $\mathcal{V}_{1}^{N\text{-}\mathsf{seq}}$ plays the
role of $\mathcal{V}_{1}$. Let $I_{i}$ be the transcript of $i$-th execution
of $\Pi$ for $i\in[N]$.

  2. The second phase:

The unbounded-time $\mathcal{V}_{2}^{N\text{-}\mathsf{seq}}$ takes the
transcript $\\{I_{i}\\}_{i\in[N]}$ of the first phase as input. For $i\in[N]$,
it runs $\mathcal{V}_{2}$ on $I_{i}$ and sets $X_{i}\coloneqq 1$ if it accepts
and otherwise sets $X_{i}\coloneqq 0$. If
$\frac{\sum_{i\in[N]}X_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}$, it outputs
$\top$ and otherwise outputs $\bot$.

We prove that sequential repetition amplifies the completeness-soundness gap
if the base scheme satisfies strong soundness.

###### Theorem 4.10 (Gap amplification theorem).

Let $\Pi=(\mathcal{P},\mathcal{V}=(\mathcal{V}_{1},\mathcal{V}_{2}))$ be an
(AI-/IO-)IV-PoQ that satisfies $c$-completeness and $s$-strong-soundness where
$c(\lambda)-s(\lambda)\geq 1/{\mathrm{poly}}(\lambda)$ and $c$ and $s$ are
computable in polynomial-time. Let
$\Pi^{N\text{-}\mathsf{seq}}=(\mathcal{P}^{N\text{-}\mathsf{seq}},\mathcal{V}^{N\text{-}\mathsf{seq}}=(\mathcal{V}_{1}^{N\text{-}\mathsf{seq}},\mathcal{V}_{2}^{N\text{-}\mathsf{seq}}))$
be its $N$-sequential-repetition version as described in Algorithm 1. If
$N\geq\frac{\lambda}{(c(\lambda)-s(\lambda))^{2}}$, then
$\Pi^{N\text{-}\mathsf{seq}}$ satisfies $1$-completeness and $0$-soundness.

######  Remark 4.11.

Note that the meaning of “sequential repetition” is slightly different from
that for usual interactive arguments: we defer the second phases of each
execution to the end of the protocol so that inefficient computations are only
needed after completing the interaction.

######  Remark 4.12.

If we assume $s$-soundness against _non-uniform_ PPT adversaries, we can
easily prove a similar amplification theorem without introducing strong
soundness. However, for proving soundness against non-uniform PPT adversaries,
we would need non-uniform hardness assumptions such as non-uniformly secure
OWFs. Since our motivation is to demonstrate quantum advantage from the
standard notion of _uniformly_ secure OWFs, we do not take the above approach.

###### Proof of Theorem 4.10.

We focus on the case of IV-PoQ since it is almost identical for (AI-/IO-)IV-
PoQ. First, $1$-completeness of $\Pi^{N\text{-}\mathsf{seq}}$ immediately
follows from Hoeffding’s inequality. (Recall that $1$-completeness means that
the honest prover’s acceptance probability is at least
$1-{\mathsf{negl}}(\lambda)$.) In the following, we prove that
${\Pi}^{N\text{-}\mathsf{seq}}$ satisfies $0$-soundness. Suppose that it does
not satisfy $0$-soundness. Then, there is a PPT malicious prover
${\mathcal{P}}^{N\text{-}\mathsf{seq}^{*}}$ against
$\Pi^{N\text{-}\mathsf{seq}}$ and a polynomial $p$ such that

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}(I_{1},\ldots,I_{N}):(I_{1},\ldots,I_{N})\leftarrow\langle{\mathcal{P}^{N\text{-}\mathsf{seq}}}^{*}(1^{\lambda}),\mathcal{V}_{1}^{N\text{-}\mathsf{seq}}(1^{\lambda})\rangle]\geq\frac{1}{p(\lambda)}$
(41)

for infinitely many $\lambda$. We define random variables $X_{1},\ldots,X_{N}$
as in Algorithm 1, i.e., $X_{i}=1$ if $\mathcal{V}_{2}$ accepts the $i$-th
transcript $I_{i}$ and otherwise $X_{i}=0$. Using this notation, the above
inequality can be rewritten as

$\displaystyle\Pr\left[\frac{\sum_{i\in[N]}X_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}\right]\geq\frac{1}{p(\lambda)}$
(42)

for infinitely many $\lambda$. For $i\in[N]$, let $X^{\prime}_{i}$ be an
independent random variable over $\\{0,1\\}$ such that
$\Pr[X^{\prime}_{i}=1]=s(\lambda)+\frac{1}{2Np(\lambda)}$. Noting that
$\frac{c(\lambda)+s(\lambda)}{2}-(s(\lambda)+\frac{1}{2Np(\lambda)})\geq\frac{c(\lambda)-s(\lambda)}{4}$
for sufficiently large $\lambda$,222222 This can be seen as follows:
$\frac{c(\lambda)+s(\lambda)}{2}-(s(\lambda)+\frac{1}{2Np(\lambda)})=\frac{c(\lambda)-s(\lambda)}{2}-\frac{1}{2Np(\lambda)}\geq\frac{c(\lambda)-s(\lambda)}{2}-\frac{1}{2N}\geq\frac{c(\lambda)-s(\lambda)}{2}-\frac{(c(\lambda)-s(\lambda))^{2}}{2\lambda}\geq\frac{c(\lambda)-s(\lambda)}{2}-\frac{c(\lambda)-s(\lambda)}{4}=\frac{c(\lambda)-s(\lambda)}{4}$
for sufficiently large $\lambda$ where the first inequality follows from the
assumption $p(\lambda)\geq 1$, the second inequality follows from
$N\geq\frac{\lambda}{(c(\lambda)-s(\lambda))^{2}}$, the third inequality
follows from $2\lambda\geq 4$ and $0\leq c(\lambda)-s(\lambda)\leq 1$ for
sufficiently large $\lambda$.  by Hoeffding’s inequality, we have

$\displaystyle\Pr\left[\frac{\sum_{i\in[N]}X^{\prime}_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}\right]\leq{\mathsf{negl}}(\lambda).$
(43)

Moreover, we prove below that for any $k\in[N]$, we have

$\displaystyle\Pr\left[\frac{\sum_{i=1}^{k}X_{i}+\sum_{i=k+1}^{N}X^{\prime}_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}\right]-\Pr\left[\frac{\sum_{i=1}^{k-1}X_{i}+\sum_{i=k}^{N}X^{\prime}_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}\right]\leq\frac{1}{2Np(\lambda)}$
(44)

for sufficiciently large $\lambda$. By a standard hybrid argument, Equations
42 and 44 imply

$\displaystyle\Pr\left[\frac{\sum_{i\in[N]}X^{\prime}_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}\right]\geq\frac{1}{2p(\lambda)}.$
(45)

for infinitely many $\lambda$. This contradicts Equation 43. Thus, we only
have to prove Equation 44 holds for all $k\in[N]$ and sufficiently large
$\lambda$.

#### Proof of Equation 44.

Let $\mathcal{P}^{*}_{k}$ be a malicious prover against $\Pi$ that works as
follows: $\mathcal{P}^{*}_{k}$ first simulates the interaction between
${\mathcal{P}}^{N\text{-}\mathsf{seq}^{*}}$ and
$\mathcal{V}_{1}^{N\text{-}\mathsf{seq}}$ for the first $k-1$ executions of
$\Pi$ where it also simulates $\mathcal{V}_{1}^{N\text{-}\mathsf{seq}}$ by
itself in this phase. Then $\mathcal{P}^{*}_{k}$ starts interaction with the
external verifier $\mathcal{V}_{1}$ of $\Pi$ where it works similarly to
${\mathcal{P}}^{N\text{-}\mathsf{seq}^{*}}$ in the $k$th execution of $\Pi$.
Note that the randomness of $\mathcal{P}^{*}_{k}$ consists of the randomness
$r_{P}$ for ${\mathcal{P}}^{N\text{-}\mathsf{seq}^{*}}$ and randomness
$r_{V}^{k-1}$ for $\mathcal{V}_{1}^{N\text{-}\mathsf{seq}}$ for the first
$k-1$ executions of $\Pi$. Therefore, by applying $s$-strong-soundness of
$\Pi$ for the above malicious prover $\mathcal{P}^{*}_{k}$, there is a set of
$\left(1-\frac{1}{2Np(\lambda)}\right)$-fraction of $(r_{P},r_{V}^{k-1})$,
which we denote by $\mathcal{G}_{k-1}$, such that for all
$(r_{P},r_{V}^{k-1})\in\mathcal{G}_{k-1}$,

$\displaystyle\Pr[X_{k}=1|r_{P},r_{V}^{k-1}]\leq
s(\lambda)+\frac{1}{2Np(\lambda)}$ (46)

for sufficiently large $\lambda$, where $\Pr[X_{k}=1|r_{P},r_{V}^{k-1}]$ means
the conditional probability that $X_{k}=1$ occurs conditioned on the fixed
values of $(r_{P},r_{V}^{k-1})$. On the other hand, because $X^{\prime}_{k}$
is independent of $(r_{P},r_{V}^{k-1})$,

$\displaystyle\Pr[X^{\prime}_{k}=1|r_{P},r_{V}^{k-1}]=\Pr[X^{\prime}_{k}=1]=s(\lambda)+\frac{1}{2Np(\lambda)}$
(47)

for any fixed $(r_{P},r_{V}^{k-1})$.

For notational simplicity, we denote the events that
$\frac{\sum_{i=1}^{k}X_{i}+\sum_{i=k+1}^{N}X^{\prime}_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}$
and
$\frac{\sum_{i=1}^{k-1}X_{i}+\sum_{i=k}^{N}X^{\prime}_{i}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}$
by $E_{k}$ and $E_{k-1}$, respectively. Then for any
$(r_{P},r_{V}^{k-1})\in\mathcal{G}_{k-1}$,

$\displaystyle\Pr\left[E_{k}\middle|(r_{P},r_{V}^{k-1})\right]$ (48)
$\displaystyle=$
$\displaystyle\Pr\left[\frac{X_{k}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}-\frac{\sum_{i=1}^{k-1}X_{i}+\sum_{i=k+1}^{N}X^{\prime}_{i}}{N}\middle|(r_{P},r_{V}^{k-1})\right]$
(49) $\displaystyle\leq$
$\displaystyle\Pr\left[\frac{X^{\prime}_{k}}{N}\geq\frac{c(\lambda)+s(\lambda)}{2}-\frac{\sum_{i=1}^{k-1}X_{i}+\sum_{i=k+1}^{N}X^{\prime}_{i}}{N}\middle|(r_{P},r_{V}^{k-1})\right]$
(50) $\displaystyle=$
$\displaystyle\Pr\left[E_{k-1}\middle|(r_{P},r_{V}^{k-1})\right]$ (51)

for sufficiently large $\lambda$ where Equation 50 follows from Equations 46
and 47 and the observations that $X_{1},\ldots,X_{k-1}$ are determined by
$(r_{P},r_{V}^{k-1})$ and $X^{\prime}_{k+1},\ldots,X^{\prime}_{N}$ are
independent of $X_{k}$ or $X^{\prime}_{k}$.

Then, for sufficiently large $\lambda$, we have

$\displaystyle\Pr\left[E_{k}\right]-\Pr\left[E_{k-1}\right]$ (52)
$\displaystyle=$
$\displaystyle\left(\Pr\left[E_{k}~{}\land~{}(r_{P},r_{V}^{k-1})\in\mathcal{G}_{k-1}\right]-\Pr\left[E_{k-1}~{}\land~{}(r_{P},r_{V}^{k-1})\in\mathcal{G}_{k-1}\right]\right)$
(53)
$\displaystyle+\left(\Pr\left[E_{k}~{}\land~{}(r_{P},r_{V}^{k-1})\notin\mathcal{G}_{k-1}\right]-\Pr\left[E_{k-1}~{}\land~{}(r_{P},r_{V}^{k-1})\notin\mathcal{G}_{k-1}\right]\right)$
(54) $\displaystyle\leq$
$\displaystyle\Pr\left[(r_{P},r_{V}^{k-1})\in\mathcal{G}_{k-1}\right]\cdot\left(\Pr\left[E_{k}\middle|(r_{P},r_{V}^{k-1})\in\mathcal{G}_{k-1}\right]-\Pr\left[E_{k-1}\middle|(r_{P},r_{V}^{k-1})\in\mathcal{G}_{k-1}\right]\right)$
(55)
$\displaystyle+\Pr\left[(r_{P},r_{V}^{k-1})\notin\mathcal{G}_{k-1}\right]$
(56) $\displaystyle\leq$ $\displaystyle\frac{1}{2Np(\lambda)},$ (57)

where Equation 57 follows from Equations (48)-(51) and the fact that
$\mathcal{G}_{k-1}$ consists of
$\left(1-\frac{1}{2Np(\lambda)}\right)$-fraction of $(r_{P},r_{V}^{k-1})$.
This implies Equation 44 and completes the proof of Theorem 4.10. ∎

##  5 Coherent Execution of Classical Bit Commitments

In this section, we explain our key concept, namely, executing classical bit
commitments coherently.

Let $(\mathcal{S},\mathcal{R})$ be a classical bit commitment scheme. If we
explicitly consider the randomness, the commit phase can be described as in
Algorithm 2.

Algorithm 2 The commit phase of a classical bit commitment scheme

  1. 1.

The sender $\mathcal{S}$ takes the comitted bit $b\in\\{0,1\\}$ and the
security parameter $1^{\lambda}$ as input. The receiver $\mathcal{R}$ takes
$1^{\lambda}$ as input.

  2. 2.

$\mathcal{R}$ samples a random seed $r\leftarrow\\{0,1\\}^{\ell}$, where
$\ell\coloneqq{\mathrm{poly}}(\lambda)$.

  3. 3.

$\mathcal{S}$ samples a random seed $x\leftarrow\\{0,1\\}^{\ell}$. (Without
loss of generality, we assume that $\mathcal{R}$’s random seed and
$\mathcal{S}$’s random seed are of equal length.)

  4. 4.

Let $L$ be the number of rounds. For $j=1$ to $L$, $\mathcal{S}$ and
$\mathcal{R}$ repeat the following.

    1. (a)

$\mathcal{S}$ computes $\alpha_{j}\coloneqq
f_{j}(b,x,\alpha_{1},\beta_{1},\alpha_{2},\beta_{2},...,\alpha_{j-1},\beta_{j-1})$,
and sends $\alpha_{j}$ to $\mathcal{R}$. Here, $f_{j}$ is the function that
computes $\mathcal{S}$’s $j$th message.

    2. (b)

$\mathcal{R}$ computes $\beta_{j}\coloneqq
g_{j}(r,\alpha_{1},\beta_{1},\alpha_{2},\beta_{2},...,\alpha_{j})$, and sends
$\beta_{j}$ to $\mathcal{S}$. Here, $g_{j}$ is the function that computes
$\mathcal{R}$’s $j$th message.

Algorithm 3 Coherent execution of the commit phase of a classical bit
commitment scheme

  1. 1.

The sender $\mathcal{S}$ takes $1^{\lambda}$ as input. The receiver
$\mathcal{R}$ takes $1^{\lambda}$ as input.

  2. 2.

$\mathcal{R}$ samples a random seed $r\leftarrow\\{0,1\\}^{\ell}$.

  3. 3.

$\mathcal{S}$ generates the state
$\sum_{b\in\\{0,1\\}}\sum_{x\in\\{0,1\\}^{\ell}}\ket{b}\ket{x}$.

  4. 4.

Let $L$ be the number of rounds. For $j=1$ to $L$, $\mathcal{S}$ and
$\mathcal{R}$ repeat the following.

    1. (a)

$\mathcal{S}$ possesses the state

$\sum_{b\in\\{0,1\\}}\sum_{x\in\cap_{i=0}^{j-1}X_{b}^{i}}\ket{b}\ket{x},$ (58)

where

$\displaystyle X_{b}^{0}$ $\displaystyle\coloneqq\\{0,1\\}^{\ell},$ (59)

and

$X_{b}^{i}\coloneqq\\{x\in\\{0,1\\}^{\ell}:f_{i}(b,x,\alpha_{1},\alpha_{2},...,\alpha_{i-1},\beta_{i-1})=\alpha_{i}\\}$
(60)

for $i\geq 1$.

    2. (b)

$\mathcal{S}$ generates the state

$\sum_{b\in\\{0,1\\}}\sum_{x\in\cap_{i=0}^{j-1}X_{b}^{i}}\ket{b}\ket{x}\ket{f_{j}(b,x,\alpha_{1},\beta_{1},...,\alpha_{j-1},\beta_{j-1})},$
(61)

and measures the third register in the computational basis to obtain the
measurement result $\alpha_{j}$. The post-measurement state is

$\sum_{b\in\\{0,1\\}}\sum_{x\in\cap_{i=0}^{j}X_{b}^{i}}\ket{b}\ket{x}.$ (62)

$\mathcal{S}$ sends $\alpha_{j}$ to $\mathcal{R}$.

    3. (c)

$\mathcal{R}$ computes $\beta_{j}\coloneqq
g_{j}(r,\alpha_{1},\beta_{1},...,\alpha_{j})$, and sends $\beta_{j}$ to
$\mathcal{S}$.

Now let us consider the coherent execution of Algorithm 2, which is shown in
Algorithm 3. Let
$t\coloneqq(\alpha_{1},\beta_{1},\alpha_{2},\beta_{2},...,\alpha_{L},\beta_{L})$
be the transcript obtained in the execution of Algorithm 3. At the end of the
execution of Algorithm 3, $\mathcal{S}$ possesses the state

$\frac{1}{\sqrt{|X_{0,t}|+|X_{1,t}|}}\sum_{b\in\\{0,1\\}}\sum_{x\in
X_{b,t}}\ket{b}\ket{x},$ (63)

where

$\displaystyle
X_{b,t}\coloneqq\bigcap_{j=0}^{L}X_{b}^{j}=\Big{\\{}x\in\\{0,1\\}^{\ell}:\bigwedge_{j=1}^{L}f_{j}(b,x,\alpha_{1},\beta_{1},...,\alpha_{j-1},\beta_{j-1})=\alpha_{j}\Big{\\}}.$
(64)

The probability $\Pr[t]$ that the transcript $t$ is obtained in the execution
of Algorithm 3 is

$\Pr[t]=\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|+|X_{1,t}|}{2^{\ell+1}},$ (65)

where

$R_{t}\coloneqq\Big{\\{}r\in\\{0,1\\}^{\ell}:\bigwedge_{j=1}^{L}g_{j}(r,\alpha_{1},\beta_{1},...,\alpha_{j})=\beta_{j}\Big{\\}}.$
(66)

In the remaining of this section, we show two lemmas, Lemma 5.1 and Lemma 5.2,
that will be used in the proofs of our main results.

The following Lemma 5.1 roughly claims that $|X_{0,t}|$ and $|X_{1,t}|$ are
almost equal with overwhelming probability.

###### Lemma 5.1.

Let $0<\epsilon<1$ be a constant. Define the set

$T\coloneqq\\{t:(1-\epsilon)|X_{1,t}|<|X_{0,t}|<(1+\epsilon)|X_{1,t}|\\}.$
(67)

Then,

$\sum_{t\in T}\Pr[t]\geq 1-{\mathsf{negl}}(\lambda).$ (68)

Here, $\Pr[t]$ is the probability that the transcript $t$ is obtained in the
execution of Algorithm 3 as is given in Equation 65.

###### Proof of Lemma 5.1.

Intuitively, this follows from the statistical hiding property since whenever
$t\notin T$, an unbounded adversary can guess the committed bit from the
transcript $t$ with probability $1/2+\Omega(\epsilon)$. Below, we provide a
formal proof.

Define

$\displaystyle T^{+}$
$\displaystyle\coloneqq\\{t:(1+\epsilon)|X_{1,t}|\leq|X_{0,t}|\\},$ (69)
$\displaystyle T^{-}$
$\displaystyle\coloneqq\\{t:|X_{0,t}|\leq(1-\epsilon)|X_{1,t}|\\}.$ (70)

In order to show the lemma, we want to show that

$\sum_{t\in T^{+}\cup T^{-}}\Pr[t]\leq{\mathsf{negl}}(\lambda).$ (71)

To show this, assume that

$\sum_{t\in T^{+}\cup T^{-}}\Pr[t]\geq\frac{1}{{\mathrm{poly}}(\lambda)}$ (72)

for infinitely many $\lambda$. Then the following computationally-unbounded
malicious receiver $\mathcal{R}^{*}$ can break the statistical hiding of the
classical bit commitment scheme in Algorithm 2.

  1. 1.

$\mathcal{R}^{*}$ honestly executes the commit phase with $\mathcal{S}$. Let
$t$ be the transcript obtained in the execution.

  2. 2.

If $t\in T^{+}$, $\mathcal{R}^{*}$ outputs 0. If $t\in T^{-}$,
$\mathcal{R}^{*}$ outputs 1. If $t\in T$, $\mathcal{R}^{*}$ outputs $0$ with
probability $1/2$ and outputs 1 with probability $1/2$.

The probability that $\mathcal{R}^{*}$ outputs 0 when $\mathcal{S}$ commits
$b\in\\{0,1\\}$ is

$\displaystyle\Pr[0\leftarrow\mathcal{R}^{*}|b]$ $\displaystyle=\sum_{t\in
T^{+}}\Pr[t|b]+\frac{1}{2}\sum_{t\in T}\Pr[t|b]$ (73)
$\displaystyle=\sum_{t\in
T^{+}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{b,t}|}{2^{\ell}}+\frac{1}{2}\sum_{t\in
T}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{b,t}|}{2^{\ell}}.$ (74)

Therefore

$\displaystyle\Pr[0\leftarrow\mathcal{R}^{*}|b=0]-\Pr[0\leftarrow\mathcal{R}^{*}|b=1]$
(75) $\displaystyle=\sum_{t\in T^{+}}\Pr[t|b=0]+\frac{1}{2}\sum_{t\in
T}\Pr[t|b=0]-\sum_{t\in T^{+}}\Pr[t|b=1]-\frac{1}{2}\sum_{t\in T}\Pr[t|b=1]$
(76) $\displaystyle=\sum_{t\in T^{+}}\Pr[t|b=0]+\frac{1}{2}\Big{(}1-\sum_{t\in
T^{+}}\Pr[t|b=0]-\sum_{t\in T^{-}}\Pr[t|b=0]\Big{)}$ (77)
$\displaystyle~{}~{}-\sum_{t\in
T^{+}}\Pr[t|b=1]-\frac{1}{2}\Big{(}1-\sum_{t\in T^{+}}\Pr[t|b=1]-\sum_{t\in
T^{-}}\Pr[t|b=1]\Big{)}$ (78) $\displaystyle=\frac{1}{2}\sum_{t\in
T^{+}}(\Pr[t|b=0]-\Pr[t|b=1])+\frac{1}{2}\sum_{t\in
T^{-}}(\Pr[t|b=1]-\Pr[t|b=0])$ (79) $\displaystyle=\frac{1}{2}\sum_{t\in
T^{+}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|-|X_{1,t}|}{2^{\ell}}+\frac{1}{2}\sum_{t\in
T^{-}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{1,t}|-|X_{0,t}|}{2^{\ell}}$ (80)
$\displaystyle\geq\frac{1}{2}\sum_{t\in
T^{+}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|-\frac{|X_{0,t}|}{1+\epsilon}}{2^{\ell}}+\frac{1}{2}\sum_{t\in
T^{-}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{1,t}|-(1-\epsilon)|X_{1,t}|}{2^{\ell}}$
(81) $\displaystyle=\frac{1}{2}\Big{(}1-\frac{1}{1+\epsilon}\Big{)}\sum_{t\in
T^{+}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|}{2^{\ell}}+\frac{\epsilon}{2}\sum_{t\in
T^{-}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{1,t}|}{2^{\ell}}$ (82)
$\displaystyle=\frac{1}{2}\frac{\epsilon}{1+\epsilon}\sum_{t\in
T^{+}}\frac{|R_{t}|}{2^{\ell}}\frac{2|X_{0,t}|}{2^{\ell+1}}+\frac{\epsilon}{2}\sum_{t\in
T^{-}}\frac{|R_{t}|}{2^{\ell}}\frac{2|X_{1,t}|}{2^{\ell+1}}$ (83)
$\displaystyle\geq\frac{1}{2}\frac{\epsilon}{1+\epsilon}\sum_{t\in
T^{+}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|+|X_{1,t}|}{2^{\ell+1}}+\frac{\epsilon}{2}\sum_{t\in
T^{-}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|+|X_{1,t}|}{2^{\ell+1}}$ (84)
$\displaystyle\geq\frac{1}{2}\frac{\epsilon}{1+\epsilon}\sum_{t\in
T^{+}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|+|X_{1,t}|}{2^{\ell+1}}+\frac{\epsilon}{2(1+\epsilon)}\sum_{t\in
T^{-}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|+|X_{1,t}|}{2^{\ell+1}}$ (85)
$\displaystyle=\frac{1}{2}\frac{\epsilon}{1+\epsilon}\sum_{t\in T^{+}\cup
T^{-}}\frac{|R_{t}|}{2^{\ell}}\frac{|X_{0,t}|+|X_{1,t}|}{2^{\ell+1}}$ (86)
$\displaystyle=\frac{1}{2}\frac{\epsilon}{1+\epsilon}\sum_{t\in T^{+}\cup
T^{-}}\Pr[t]$ (87)
$\displaystyle\geq\frac{1}{2}\frac{\epsilon}{1+\epsilon}\frac{1}{{\mathrm{poly}}(\lambda)}$
(88) $\displaystyle=\frac{1}{{\mathrm{poly}}(\lambda)}$ (89)

for infinitely many $\lambda$, which breaks the statistical hiding. ∎

The following Lemma 5.2 roughly claims that whenever $t\in T$ a good
approximation $k$ of $2|X_{0,t}|$ and $2|X_{1,t}|$ up to a small constant
multiplicative error can be chosen with probability
$1/m=1/{\mathrm{poly}}(\lambda)$.

###### Lemma 5.2.

Let $0<\epsilon<1$ be a constant. Let

$T\coloneqq\\{t:(1-\epsilon)|X_{1,t}|<|X_{0,t}|<(1+\epsilon)|X_{1,t}|\\}.$
(90)

Let $m$ be an integer such that $(1+\epsilon)^{m}\geq 2^{\ell+1}$. For any
$t\in T$, there exists an integer $j\in\\{0,1,2,...,m-1\\}$ such that

$k\leq 2|X_{0,t}|\leq(1+\epsilon)k$ (91)

and

$\frac{k}{1+\epsilon}\leq 2|X_{1,t}|\leq\frac{1+\epsilon}{1-\epsilon}k.$ (92)

Here, $k\coloneqq\lceil(1+\epsilon)^{j}\rceil$.

###### Proof of Lemma 5.2.

Let $t\in T$. Because $0\leq(1-\epsilon)|X_{1,t}|<|X_{0,t}|$, we have
$|X_{0,t}|\geq 1$. Because $2|X_{0,t}|\leq 2^{\ell+1}$, there exists an
integer $j\in\\{0,1,2,...,m-1\\}$ such that
$(1+\epsilon)^{j}<2|X_{0,t}|\leq(1+\epsilon)^{j+1}$. Let us take
$k=\lceil(1+\epsilon)^{j}\rceil$. Because $2|X_{0,t}|$ is an integer, $k\leq
2|X_{0,t}|$. Moreover, we have

$\displaystyle 2|X_{0,t}|$ $\displaystyle\leq(1+\epsilon)^{j+1}$ (93)
$\displaystyle=(1+\epsilon)\times(1+\epsilon)^{j}$ (94)
$\displaystyle\leq(1+\epsilon)\times\lceil(1+\epsilon)^{j}\rceil$ (95)
$\displaystyle=(1+\epsilon)\times k.$ (96)

In summary, we have $k\leq 2|X_{0,t}|\leq(1+\epsilon)k$. We also have
$2|X_{1,t}|<\frac{2|X_{0,t}|}{1-\epsilon}\leq\frac{1+\epsilon}{1-\epsilon}k$,
and $2|X_{1,t}|>\frac{2|X_{0,t}|}{1+\epsilon}\geq\frac{k}{1+\epsilon}$. ∎

##  6 Construction of IV-PoQ

In this section, we prove Theorem 1.1. That is, we construct IV-PoQ from
statistically-hiding and computationally-binding classical bit commitments.

Let $(\mathcal{S},\mathcal{R}$) be a statistically-hiding and computationally-
binding classical bit commitment scheme. The first phase where the PPT
verifier $\mathcal{V}_{1}$ and the QPT prover $\mathcal{P}$ interact is given
in Algorithm 4. The second phase where the inefficient verifier
$\mathcal{V}_{2}$ runs is given in Algorithm 5.

Algorithm 4 The first phase by $\mathcal{V}_{1}$ and $\mathcal{P}$

  1. 1.

The PPT verifier $\mathcal{V}_{1}$ and the QPT prover $\mathcal{P}$ coherently
execute the commit phase of the classical bit commitment scheme
$(\mathcal{S},\mathcal{R})$. (See Algorithm 3.) $\mathcal{V}_{1}$ plays the
role of the receiver $\mathcal{R}$. $\mathcal{P}$ plays the role of the sender
$\mathcal{S}$. Let $t$ be the transcript obtained in the execution.

  2. 2.

$\mathcal{P}$ has the state $\sum_{b\in\\{0,1\\}}\sum_{x\in
X_{b,t}}\ket{b}\ket{x}$.

  3. 3.

Let $0<\epsilon<1$ be a small constant. (We set
$\epsilon\coloneqq\frac{1}{100}$ for clarity.) Let $m$ be an integer such that
$(1+\epsilon)^{m}\geq 2^{\ell+1}$. (Such an $m$ can be computed in
${\mathrm{poly}}(\lambda)$ time. In fact, we have only to take the minimum
integer $m$ such that $m\geq\frac{\ell+1}{\log_{2}(1+\epsilon)}$.)
$\mathcal{V}_{1}$ chooses $j\leftarrow\\{0,1,2,...,m-1\\}$. Define
$k\coloneqq\lceil(1+\epsilon)^{j}\rceil$. Let
$\mathcal{H}\coloneqq\\{h:\mathcal{X}\to\mathcal{Y}\\}$ be a pairwise-
independent hash family with $\mathcal{X}\coloneqq\\{0,1\\}^{\ell}$ and
$\mathcal{Y}\coloneqq[k]$. $\mathcal{V}_{1}$ chooses
$h_{0},h_{1}\leftarrow\mathcal{H}$, and sends $(h_{0},h_{1})$ to
$\mathcal{P}$.

  4. 4.

$\mathcal{P}$ changes its state into $\sum_{b\in\\{0,1\\}}\sum_{x\in
X_{b,t}}\ket{b}\ket{x}\ket{h_{b}(x)}$, and measures the third register in the
computational basis to obtain the result $y\in[k]$. $\mathcal{P}$ sends $y$ to
$\mathcal{V}_{1}$. The post-measurement state is

$\sum_{b\in\\{0,1\\}}\sum_{x\in X_{b,t}\cap h_{b}^{-1}(y)}\ket{b}\ket{x}.$
(97)

(If there is only a single $x_{b}$ such that $x_{b}\in X_{b,t}\cap
h_{b}^{-1}(y)$ for each $b\in\\{0,1\\}$, Equation 97 is
$\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$. We will show later that it occurs
with a non-negligible probability.)

  5. 5.

From now on, $\mathcal{V}_{1}$ and $\mathcal{P}$ run the protocol of
[KMCVY22]. $\mathcal{V}_{1}$ chooses $v_{1}\leftarrow\\{0,1\\}$.
$\mathcal{V}_{1}$ chooses $\xi\leftarrow\\{0,1\\}^{\ell}$. $\mathcal{V}_{1}$
sends $v_{1}$ and $\xi$ to $\mathcal{P}$.

  6. 6.

     * •

If $v_{1}=0$: $\mathcal{P}$ measures all qubits of the state of Equation 97 in
the computational basis, and sends the measurement result
$(b^{\prime},x^{\prime})\in\\{0,1\\}\times\\{0,1\\}^{\ell}$ to
$\mathcal{V}_{1}$. $\mathcal{V}_{1}$ halts.

     * •

If $v_{1}=1$: $\mathcal{P}$ changes the state of Equation 97 into

$\sum_{b\in\\{0,1\\}}\sum_{x\in X_{b,t}\cap
h_{b}^{-1}(y)}\ket{b\oplus(\xi\cdot x)}\ket{x},$ (98)

measures its second register in the Hadamard basis to obtain the measurement
result $d\in\\{0,1\\}^{\ell}$, and sends $d$ to $\mathcal{V}_{1}$. The post-
measurement state is

$\sum_{b\in\\{0,1\\}}\sum_{x\in X_{b,t}\cap h_{b}^{-1}(y)}(-1)^{d\cdot
x}\ket{b\oplus(\xi\cdot x)}.$ (99)

(If there is only a single $x_{b}$ such that $x_{b}\in X_{b,t}\cap
h_{b}^{-1}(y)$ for each $b\in\\{0,1\\}$, Equation 98 is $\ket{\xi\cdot
x_{0}}\ket{x_{0}}+\ket{1\oplus(\xi\cdot x_{1})}\ket{x_{1}}$, and Equation 99
is $|\xi\cdot x_{0}\rangle+(-1)^{d\cdot(x_{0}\oplus x_{1})}|1\oplus(\xi\cdot
x_{1})\rangle$.)

  7. 7.

$\mathcal{V}_{1}$ chooses $v_{2}\leftarrow\\{0,1\\}$. $\mathcal{V}_{1}$ sends
$v_{2}$ to $\mathcal{P}$.

  8. 8.

If $v_{2}=0$, $\mathcal{P}$ measures Equation 99 in the basis
$\left\\{\cos\frac{\pi}{8}|0\rangle+\sin\frac{\pi}{8}|1\rangle,\sin\frac{\pi}{8}|0\rangle-\cos\frac{\pi}{8}|1\rangle\right\\}$.
If $v_{2}=1$, $\mathcal{P}$ measures Equation 99 in the basis
$\left\\{\cos\frac{\pi}{8}|0\rangle-\sin\frac{\pi}{8}|1\rangle,\sin\frac{\pi}{8}|0\rangle+\cos\frac{\pi}{8}|1\rangle\right\\}$.
Let $\eta\in\\{0,1\\}$ be the measurement result. (For the measurement in the
basis $\\{|\phi\rangle,|\phi^{\perp}\rangle\\}$, the result 0 corresponds to
$|\phi\rangle$ and the result 1 corresponds to $|\phi^{\perp}\rangle$.)
$\mathcal{P}$ sends $\eta$ to $\mathcal{V}_{1}$.

Algorithm 5 The second phase by $\mathcal{V}_{2}$

  1. 1.

$\mathcal{V}_{2}$ takes $(t,h_{0},h_{1},y,v_{1}=0,\xi,b^{\prime},x^{\prime})$
or $(t,h_{0},h_{1},y,v_{1}=1,\xi,d,v_{2},\eta)$ as input.

  2. 2.

If $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is not
satisfied, $\mathcal{V}_{2}$ outputs $\top$ with probability $7/8$ and outputs
$\bot$ with probability $1/8$. Then $\mathcal{V}_{2}$ halts. If $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is satisfied, $\mathcal{V}_{2}$
computes $(x_{0},x_{1})$ and goes to the next step. Here, $x_{b}$ is the
single element of $X_{b,t}\cap h_{b}^{-1}(y)$ for each $b\in\\{0,1\\}$.

  3. 3.

If $v_{1}=0$ and $x^{\prime}=x_{b^{\prime}}$, $\mathcal{V}_{2}$ outputs $\top$
and halts. Otherwise, $\mathcal{V}_{2}$ outputs $\bot$ and halts.

  4. 4.

If $v_{1}=1$, $\mathcal{V}_{2}$ outputs $\top$ if

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

or

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

Otherwise, $\mathcal{V}_{2}$ outputs $\bot$.

We can show the completeness and soundness of our IV-PoQ as follows.

###### Theorem 6.1 (Completeness).

Our IV-PoQ satisfies
$(\frac{7}{8}+\frac{1}{{\mathrm{poly}}(\lambda)})$-completeness.

###### Theorem 6.2 (Soundness).

Our IV-PoQ satisfies $\frac{7}{8}$-strong-soundness, which in particular
implies $\frac{7}{8}$-soundness.

The above only gives an inverse-polynomial completeness-soundness gap, but we
can amplify the gap to $1$ by sequential repetition by Theorem 4.10. Theorem
6.1 is shown in Section 6.1. Theorem 6.2 is shown in Section 6.2. By combining
Theorem 6.1 and Theorem 6.2, we obtain Theorem 1.1.

###  6.1 Completeness

In this subsection, we show
$(\frac{7}{8}+\frac{1}{{\mathrm{poly}}(\lambda)})$-completeness.

###### Proof of Theorem 6.1.

Let $p_{\mathsf{good}}$ be the probability that Equation 97 in the Item 4 of
Algorithm 4 is in the form of $\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$. Then

$p_{\mathsf{good}}\geq(1-{\mathsf{negl}}(\lambda))\frac{0.1}{m}$ (102)

because of the following reasons.

  * •

In Step 1 of Algorithm 4, the probability that the transcript $t$ such that
$t\in T$ is obtained is at least $1-{\mathsf{negl}}(\lambda)$ from Lemma 5.1
where $T$ is defined in Lemma 5.1.

  * •

Given $t\in T$, in Step 3 of Algorithm 4, the probability that
$\mathcal{V}_{1}$ chooses $j$ such that $k$ satisfies Equation 91 and Equation
92 of Lemma 5.2 is $\frac{1}{m}$.

  * •

Given that $k$ satisfies Equation 91 and Equation 92 of Lemma 5.2, in Step 4
of Algorithm 4, the probability that $y$ such that $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is obtained is at least 0.1 from
Lemma 6.3 shown below.

Moreover, if Equation 97 in Step 4 of Algorithm 4 is in the form of
$\ket{0}\ket{x_{0}}+\ket{1}\ket{x_{1}}$, the probability that
$\mathcal{V}_{2}$ outputs $\top$ in Algorithm 5 is
$\frac{1}{2}+\frac{1}{2}\cos^{2}\frac{\pi}{8}\geq 0.9$ as is shown in Appendix
C.

Therefore, the probability that $\mathcal{V}_{2}$ outputs $\top$ is

$\displaystyle\Big{(}\frac{1}{2}+\frac{1}{2}\cos^{2}\frac{\pi}{8}\Big{)}p_{\mathsf{good}}+\frac{7}{8}(1-p_{\mathsf{good}})$
(103)
$\displaystyle=\frac{7}{8}+\Big{(}\frac{1}{2}+\frac{1}{2}\cos^{2}\frac{\pi}{8}-\frac{7}{8}\Big{)}p_{\mathsf{good}}$
(104) $\displaystyle\geq\frac{7}{8}+\frac{1}{{\mathrm{poly}}(\lambda)},$ (105)

which shows the completeness. ∎

###### Lemma 6.3.

Assume that $k$ satisfies Equation 91 and Equation 92 of Lemma 5.2. In Step 4
of Algorithm 4, the probability that $y$ such that $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is obtained is at least 0.1.

###### Proof of Lemma 6.3.

By using Lemma 3.2 with $S=X_{b,t}$, $h=h_{b}$, and $\mathcal{Y}=[k]$, we
have, for any $b\in\\{0,1\\}$, $t$, and $y\in\mathcal{Y}$,

$\displaystyle\Pr_{h_{b}\leftarrow\mathcal{H}}[|X_{b,t}\cap h_{b}^{-1}(y)|=1]$
$\displaystyle\geq\frac{|X_{b,t}|}{k}-\frac{|X_{b,t}|^{2}}{k^{2}}$ (106)
$\displaystyle\geq\frac{1}{2(1+\epsilon)}-\frac{(1+\epsilon)^{2}}{4(1-\epsilon)^{2}}.$
(107)

Here, in the last inequality, we have used Lemma 5.2.

In Step 4 of Algorithm 4, the probability that $y$ is obtained is

$\frac{|X_{0,t}\cap h_{0}^{-1}(y)|+|X_{1,t}\cap
h_{1}^{-1}(y)|}{|X_{0,t}|+|X_{1,t}|}.$ (108)

Let us define

$G_{b,t,h_{b}}\coloneqq\\{y\in[k]:|X_{b,t}\cap h_{b}^{-1}(y)|=1\\}.$ (109)

Then, the probability that we obtain $y$ such that $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is

$\displaystyle\underset{h_{0},h_{1}\leftarrow\mathcal{H}}{\mathbb{E}}\left[\sum_{y\in
G_{0,t,h_{0}}\cap G_{1,t,h_{1}}}\frac{2}{|X_{0,t}|+|X_{1,t}|}\right]$ (110)
$\displaystyle=\underset{h_{0},h_{1}\leftarrow\mathcal{H}}{\mathbb{E}}\left[\frac{2|G_{0,t,h_{0}}\cap
G_{1,t,h_{1}}|}{|X_{0,t}|+|X_{1,t}|}\right]$ (111)
$\displaystyle\geq\underset{h_{0},h_{1}\leftarrow\mathcal{H}}{\mathbb{E}}\left[\frac{2|G_{0,t,h_{0}}\cap
G_{1,t,h_{1}}|}{\frac{(1+\epsilon)k}{1-\epsilon}}\right]$ (112)
$\displaystyle=\frac{2(1-\epsilon)}{1+\epsilon}\underset{h_{0},h_{1}\leftarrow\mathcal{H}}{\mathbb{E}}\left[\frac{|G_{0,t,h_{0}}\cap
G_{1,t,h_{1}}|}{k}\right]$ (113)
$\displaystyle=\frac{2(1-\epsilon)}{1+\epsilon}\frac{1}{|\mathcal{H}|^{2}}\sum_{h_{0},h_{1}\in\mathcal{H}}\frac{1}{k}\sum_{y\in[k]}\delta_{y\in
G_{0,t,h_{0}}}\delta_{y\in G_{1,t,h_{1}}}$ (114)
$\displaystyle=\frac{2(1-\epsilon)}{1+\epsilon}\frac{1}{k}\sum_{y\in[k]}\Big{(}\frac{1}{|\mathcal{H}|}\sum_{h_{0}\in\mathcal{H}}\delta_{y\in
G_{0,t,h_{0}}}\Big{)}\Big{(}\frac{1}{|\mathcal{H}|}\sum_{h_{1}\in\mathcal{H}}\delta_{y\in
G_{1,t,h_{1}}}\Big{)}$ (115)
$\displaystyle=\frac{2(1-\epsilon)}{1+\epsilon}\frac{1}{k}\sum_{y\in[k]}\Big{(}\Pr_{h_{0}\leftarrow\mathcal{H}}[y\in
G_{0,t,h_{0}}]\Big{)}\Big{(}\Pr_{h_{1}\leftarrow\mathcal{H}}[y\in
G_{1,t,h_{1}}]\Big{)}$ (116)
$\displaystyle\geq\frac{2(1-\epsilon)}{1+\epsilon}\frac{1}{k}\sum_{y\in[k]}\Big{[}\frac{1}{2(1+\epsilon)}-\frac{(1+\epsilon)^{2}}{4(1-\epsilon)^{2}}\Big{]}^{2}$
(117)
$\displaystyle=\frac{2(1-\epsilon)}{1+\epsilon}\Big{[}\frac{1}{2(1+\epsilon)}-\frac{(1+\epsilon)^{2}}{4(1-\epsilon)^{2}}\Big{]}^{2}$
(118) $\displaystyle>0.1.$ (119)

Here, $\delta_{\alpha}$ is 1 if the statement $\alpha$ is true, and is 0 if
not. In Equation 112, we have used Lemma 5.2, and in Equation 117, we have
used Equation 107. In the last inequality, we have taken
$\epsilon=\frac{1}{100}$.

∎

###  6.2 Soundness

In this subsection, we show $\frac{7}{8}$-strong-soundness.

###### Proof of Theorem 6.2.

Our goal is to prove that for any PPT malicious prover $\mathcal{P}^{*}$ and
any polynomial $p$,

$\Pr_{r\leftarrow\mathcal{R}}\left[\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}_{r}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\geq\frac{7}{8}+\frac{1}{p(\lambda)}\right]\leq\frac{1}{p(\lambda)}$
(120)

for sufficiently large $\lambda$ where $\mathcal{R}$ is the randomness space
for $\mathcal{P}^{*}$ and $\mathcal{P}^{*}_{r}$ is $\mathcal{P}^{*}$ with the
fixed randomness $r$.

Toward contradiction, suppose that there are a PPT prover $\mathcal{P}^{*}$
and a polynomial $p$ such that

$\displaystyle\Pr_{r\leftarrow\mathcal{R}}\left[\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}_{r}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\geq\frac{7}{8}+\frac{1}{p(\lambda)}\right]>\frac{1}{p(\lambda)}$
(121)

for infinitely many $\lambda$. Then we prove the following lemma.

###### Lemma 6.4.

There is an oracle-aided PPT algorithm $\mathcal{B}$ that breaks the
computational binding property of the commitment scheme if it is given black-
box access to $\mathcal{P}^{*}_{r}$ such that

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}_{r}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]\geq\frac{7}{8}+\frac{1}{p(\lambda)}$
(122)

for infinitely many $\lambda$.

By combining Equations 121 and 6.4, $\mathcal{B}^{\mathcal{P}^{*}_{r}}$ for
random $r\leftarrow\mathcal{R}$ breaks the computational binding property,
which is a contradiction. Thus, we only have to prove Lemma 6.4 for completing
the proof of Theorem 6.2.

###### Proof of Lemma 6.4..

The proof is very similar to that of [MY23], which in turn is based on
[KMCVY22]. Nonetheless, there is a difference that we have to deal with the
case where $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is not
satisfied. Thus, we provide the full proof even though we sometimes repeat the
same arguments as those in [MY23] where some sentences are taken verbatim from
there with notational adaptation.

We fix $r$ and an infinite set $\Gamma\subseteq\mathbb{N}$ such that Equation
122 holds for all $\lambda\in\Gamma$. In the following, we simply write
$\mathcal{P}^{*}$ to mean $\mathcal{P}^{*}_{r}$ and
$\Pr[\top\leftarrow\mathcal{V}_{2}]$ to mean
$\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}_{r}(1^{\lambda}),\mathcal{V}_{1}(1^{\lambda})\rangle]$.
We also often omit to say “for all $\lambda\in\Gamma$”, but whenever we refer
to some inequality where $\lambda$ appears, we always mean it holds for all
$\lambda\in\Gamma$.

Define

$\displaystyle\mathsf{Good}\coloneqq\left\\{(t,h_{0},h_{1},y):\Pr[\top\leftarrow\mathcal{V}_{2}~{}|~{}(t,h_{0},h_{1},y)]\geq\frac{7}{8}+\frac{1}{2p(\lambda)}\right\\},$
(123)

where $\Pr[\top\leftarrow\mathcal{V}_{2}~{}|~{}(t,h_{0},h_{1},y)]$ denotes
$\mathcal{V}_{2}$’s acceptance probability conditioned on a fixed
$(t,h_{0},h_{1},y)$, and define

$\displaystyle p_{\mathsf{Good}}:=\Pr[(t,h_{0},h_{1},y)\in\mathsf{Good}].$
(124)

Note that we have $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$
for all $(t,h_{0},h_{1},y)\in\mathsf{Good}$ since otherwise
$\Pr[\top\leftarrow\mathcal{V}_{2}~{}|~{}(t,h_{0},h_{1},y)]=\frac{7}{8}$. Then
we have

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}]$
$\displaystyle=\Pr[\top\leftarrow\mathcal{V}_{2}\land(t,h_{0},h_{1},y)\in\mathsf{Good}]+\Pr[\top\leftarrow\mathcal{V}_{2}\land(t,h_{0},h_{1},y)\notin\mathsf{Good}]$
(125) $\displaystyle\leq
p_{\mathsf{Good}}+(1-p_{\mathsf{Good}})\cdot\left(\frac{7}{8}+\frac{1}{2p(\lambda)}\right).$
(126)

By Equations 122 and 126, we have

$\displaystyle p_{\mathsf{Good}}\geq\frac{1}{2p(\lambda)}.$ (127)

We fix $(t,h_{0},h_{1},y)\in\mathsf{Good}$ until Equation 137.

For $b\in\\{0,1\\}$, let $x_{b}\in\\{0,1\\}^{\ell}$ be the unique element in
$X_{b,t}\cap h_{b}^{-1}(y)$. Note that it is well-defined since we assume
$(t,h_{0},h_{1},y)\in\mathsf{Good}$, which implies $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$.

We define the following probabilities all of which are conditioned on the
fixed value of $(t,h_{0},h_{1},y)$:

$p_{0}$:

The probability that $\mathcal{V}_{2}$ returns $\top$ conditioned on
$v_{1}=0$.

$p_{1}$:

The probability that $\mathcal{V}_{2}$ returns $\top$ conditioned on
$v_{1}=1$.

$p_{1,0}$:

The probability that $\mathcal{V}_{2}$ returns $\top$ conditioned on $v_{1}=1$
and $v_{2}=0$.

$p_{1,1}$:

The probability that $\mathcal{V}_{2}$ returns $\top$ conditioned on $v_{1}=1$
and $v_{2}=1$.

Clearly, we have

$\displaystyle\Pr[\top\leftarrow\mathcal{V}_{2}|(t,h_{0},h_{1},y)]=\frac{p_{0}+p_{1}}{2}$
(128)

and

$\displaystyle p_{1}=\frac{p_{1,0}+p_{1,1}}{2}.$ (129)

By $(t,h_{0},h_{1},y)\in\mathsf{Good}$, Equations 123 and 128, and a trivial
inequality $p_{0},p_{1}\leq 1$, we have

$\displaystyle p_{0}\geq\frac{3}{4}+\frac{1}{p(\lambda)}$ (130)

and

$\displaystyle p_{1}\geq\frac{3}{4}+\frac{1}{p(\lambda)}.$ (131)

Let $\mathcal{A}$ be a classical deterministic polynomial-time algorithm that
works as follows:

  1. 1.

$\mathcal{A}$ takes $(t,h_{0},h_{1},y)$ and $\xi\in\\{0,1\\}^{\ell}$ as input.

  2. 2.

$\mathcal{A}$ runs Step 6 of $\mathcal{P}^{*}$ where the transcript of Step
1-4 is set to be $(t,h_{0},h_{1},y)$ and the transcript of Step 5 is set to be
$(v_{1}=1,\xi)$. Let $d\in\\{0,1\\}^{\ell}$ be the message sent from
$\mathcal{P}^{*}$ to $\mathcal{V}_{1}$. Note that $\mathcal{P}^{*}$’s message
is determined by the previous transcript since $\mathcal{P}^{*}$ is
deterministic. (Recall that $\mathcal{P}^{*}$ is a shorthand of
$\mathcal{P}^{*}_{r}$ for a fixed randomness $r$.)

  3. 3.

$\mathcal{A}$ runs Step 8 of $\mathcal{P}^{*}$ where the transcript of Step
1-4 is set to be $(t,h_{0},h_{1},y)$, the transcript of Step 5 is set to be
$(v_{1}=1,\xi)$, the transcript of Step 6 is set to be $d$, and the transcript
of Step 7 is set to be $v_{2}=0$. Let $\eta_{1,0}$ be the message sent from
$\mathcal{P}^{*}$ to $\mathcal{V}_{1}$.

  4. 4.

$\mathcal{A}$ runs Step 8 of $\mathcal{P}^{*}$ where the transcript of Step
1-4 is set to be $(t,h_{0},h_{1},y)$, the transcript of Step 5 is set to be
$(v_{1}=1,\xi)$, the transcript of Step 6 is set to be $d$, and the transcript
of Step 7 is set to be $v_{2}=1$. Let $\eta_{1,1}$ be the message sent from
$\mathcal{P}^{*}$ to $\mathcal{V}_{1}$.

  5. 5.

$\mathcal{A}$ outputs $\eta_{1,0}\oplus\eta_{1,1}\oplus 1$.

By the union bound, the probability that both $(d,\eta_{1,0})$ and
$(d,\eta_{1,1})$ pass the verification is at least

$\displaystyle
1-(1-p_{1,0})-(1-p_{1,1})=-1+2p_{1}\geq\frac{1}{2}+\frac{1}{p(\lambda)},$
(132)

where the equation follows from Equation 129 and the inequality follows from
Equation 131. When this occurs, for each $v_{2}\in\\{0,1\\}$, we have

$\displaystyle(\xi\cdot x_{0}\neq\xi\cdot x_{1})\wedge(\eta_{1,v_{2}}=\xi\cdot
x_{0}),$ (133)

or

$\displaystyle(\xi\cdot x_{0}=\xi\cdot x_{1})\wedge(\eta_{1,v_{2}}=v_{2}\oplus
d\cdot(x_{0}\oplus x_{1})).$ (134)

(Remark that the same $d$ is used for both cases of $v_{2}=0$ and $v_{2}=1$.)
In particular, if $\xi\cdot x_{0}\neq\xi\cdot x_{1}$ then
$\eta_{1,0}=\eta_{1,1}$, and if $\xi\cdot x_{0}=\xi\cdot x_{1}$ then
$\eta_{1,0}=\eta_{1,1}\oplus 1$. This implies that

$\displaystyle\eta_{1,0}\oplus\eta_{1,1}\oplus 1=\xi\cdot(x_{0}\oplus x_{1}).$
(135)

Therefore, we have

$\displaystyle\Pr_{\xi\leftarrow\\{0,1\\}^{\ell}}[\mathcal{A}((t,h_{0},h_{1},y),\xi)=\xi\cdot(x_{0}\oplus
x_{1})]\geq\frac{1}{2}+\frac{1}{p(\lambda)}.$ (136)

Thus, by the Goldreich-Levin theorem [GL89], there is a PPT algorithm
$\mathcal{E}$ such that

$\displaystyle\Pr[\mathcal{E}(t,h_{0},h_{1},y)=x_{0}\oplus
x_{1}]\geq\frac{1}{p^{\prime}(\lambda)}$ (137)

for some polynomial $p^{\prime}$. (Remark that what we have shown so far is
that the above holds for any fixed $(t,h_{0},h_{1},y)\in\mathsf{Good}$.)

Then, we construct a PPT algorithm $\mathcal{B}$ that breaks the computational
binding property of the classical bit commitment scheme as follows:

  1. 1.

$\mathcal{B}$ interacts with the receiver $\mathcal{R}$ in the same way as
$\mathcal{P}^{*}$ does in Step 1 of Algorithm 4, and let $t$ be the transcript
obtained from the execution.

  2. 2.

$\mathcal{B}$ chooses hash functions $h_{0}$ and $h_{1}$ as in Step 3 of
Algorithm 4, and send them to $\mathcal{P}^{*}$.

  3. 3.

$\mathcal{P}^{*}$ returns $y$ as a message of Step 4 in Algorithm 4. At this
point, $(x_{0},x_{1})$ is implicitly determined if
$(t,h_{0},h_{1},y)\in\mathsf{Good}$.

  4. 4.

$\mathcal{B}$ sends $v_{1}=0$ and $\xi\leftarrow\\{0,1\\}^{\ell}$ to
$\mathcal{P}^{*}$ as a message of Step 5 in Algorithm 4.

  5. 5.

$\mathcal{P}^{*}$ returns $(b^{\prime},x^{\prime})$ as a message of the first
case of Step • ‣ 6 in Algorithm 4.

  6. 6.

$\mathcal{B}$ runs $\mathcal{E}(t,h_{0},h_{1},y)$ and let $z$ be the output.

  7. 7.

$\mathcal{B}$ sets $x^{\prime}_{0}\coloneqq x^{\prime}$ and
$x^{\prime}_{1}\coloneqq x^{\prime}\oplus z$ if $b^{\prime}=0$, and
$x^{\prime}_{0}\coloneqq x^{\prime}\oplus z$ and $x^{\prime}_{1}\coloneqq
x^{\prime}$ otherwise. For each $b\in\\{0,1\\}$, $\mathcal{B}$ generate a
decommitment $\mathsf{dcom}_{b}$ corresponding to the sender’s randomness
$x^{\prime}_{b}$ and transcript $t$. $\mathcal{B}$ outputs
$(0,\mathsf{decom}_{0})$ and $(1,\mathsf{decom}_{1})$.

Recall that we have shown that for any $(t,h_{0},h_{1},y)\in\mathsf{Good}$,
Equations 130 and 137 hold. Thus, for any $(t,h_{0},h_{1},y)\in\mathsf{Good}$,
we have

$\displaystyle\Pr[x^{\prime}=x_{b^{\prime}}|(t,h_{0},h_{1},y)]\geq\frac{3}{4}+\frac{1}{p(\lambda)}$
(138)

and

$\displaystyle\Pr[z=x_{0}\oplus
x_{1}|(t,h_{0},h_{1},y)]\geq\frac{1}{p^{\prime}(\lambda)}.$ (139)

Moreover, the two events $x^{\prime}=x_{b^{\prime}}$ and $z=x_{0}\oplus x_{1}$
are independent once we fix $(t,h_{0},h_{1},y)$. Therefore, for any
$(t,h_{0},h_{1},y)\in\mathsf{Good}$, we have

$\displaystyle\Pr[x^{\prime}=x_{b^{\prime}}\wedge z=x_{0}\oplus
x_{1}|(t,h_{0},h_{1},y)]\geq\frac{3}{4p^{\prime}(\lambda)}.$ (140)

Combined with Equation 127, we have

$\displaystyle\Pr[(t,h_{0},h_{1},y)\in\mathsf{Good}\land
x^{\prime}_{0}=x_{0}\land
x^{\prime}_{1}=x_{1}]\geq\frac{3}{8p(\lambda)p^{\prime}(\lambda)}.$ (141)

By the definition of $x_{b}$, we have $x_{b}\in X_{b,t}$ for $b\in\\{0,1\\}$.
Thus, by the perfect correctness of the commitment scheme,
$\mathsf{decom}_{b}$ derived from $(x_{b},t)$ is a valid decommitment. Thus,
Equation 141 implies that $\mathcal{B}$ outputs valid decommitments for both
messages $0$ and $1$ with probability at least
$\frac{3}{8p(\lambda)p^{\prime}(\lambda)}$ (for all $\lambda\in\Gamma$). This
completes the proof of Lemma 6.4. ∎

This completes the proof of Theorem 6.2. ∎

###  6.3 Computational Power of the Inefficient Verifier

In this subsection, we show that $\mathcal{V}_{2}$ can be a classical
deterministic polynomial-time algorithm querying an $\mathbf{NP}$ oracle. (The
inefficient verifier in our construction actually uses randomness when
$|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is not satisfied,
but the inefficient verifier can be deterministic if we let the first phase
verifier append the randomness to the transcript.)

The inefficient parts of $\mathcal{V}_{2}$ are verifying $|X_{0,t}\cap
h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ and finding $(x_{0},x_{1})$,
where $x_{b}$ is the single element of $X_{b,t}\cap h_{b}^{-1}(y)$. We show
that these two tasks can be done in classical deterministic polynomial-time
querying an $\mathbf{NP}$ oracle. Note that the membership of $x\in
X_{b,t}\cap h_{b}^{-1}(y)$ can be decided in a classical deterministic
polynomial time. Therefore, the decision problem

  * Yes:

There exists $x\in\\{0,1\\}^{\ell}$ such that $x\in X_{b,t}\cap
h_{b}^{-1}(y)$.

  * No:

For any $x\in\\{0,1\\}^{\ell}$, $x\notin X_{b,t}\cap h_{b}^{-1}(y)$.

is in $\mathbf{NP}$.

First, $\mathcal{V}_{2}$ queries the above decision problem to the
$\mathbf{NP}$ oracle for each $b\in\\{0,1\\}$. If the answer is no for a
$b\in\\{0,1\\}$, it means that $|X_{b,t}\cap h_{b}^{-1}(y)|=0$. In that case,
$\mathcal{V}_{2}$ concludes that $|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap
h_{1}^{-1}(y)|=1$ is not satisfied. If the answer is yes for both
$b\in\\{0,1\\}$, $|X_{0,t}\cap h_{0}^{-1}(y)|\geq 1$ and $|X_{1,t}\cap
h_{1}^{-1}(y)|\geq 1$ are guaranteed.

Then, $\mathcal{V}_{2}$ finds an element $x_{b}\in X_{b,t}\cap h_{b}^{-1}(y)$
for each $b\in\\{0,1\\}$. Finding such an element is just an $\mathbf{NP}$
search problem, which can be solved in classical deterministic polynomial-time
by querying the $\mathbf{NP}$ oracle polynomially many times.

$\mathcal{V}_{2}$ finally queries the following decision problem to the
$\mathbf{NP}$ oracle for each $b\in\\{0,1\\}$.

  * Yes:

There exists $x\in\\{0,1\\}^{\ell}$ such that $x\in(X_{b,t}\cap
h_{b}^{-1}(y))\setminus\\{x_{b}\\}$.

  * No:

For any $x\in\\{0,1\\}^{\ell}$, $x\notin(X_{b,t}\cap
h_{b}^{-1}(y))\setminus\\{x_{b}\\}$.

If the answer is yes for a $b\in\\{0,1\\}$, it means that $|X_{b,t}\cap
h_{b}^{-1}(y)|\geq 2$. In that case, $\mathcal{V}_{2}$ concludes that
$|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is not satisfied.
If the answer is no for both $b\in\\{0,1\\}$, $\mathcal{V}_{2}$ concludes that
$|X_{0,t}\cap h_{0}^{-1}(y)|=|X_{1,t}\cap h_{1}^{-1}(y)|=1$ is satisfied.

##  7 Implausibility of Two-Round AI-IV-PoQ

In this section, we prove Theorems 1.8 and 1.9.

###  7.1 Impossibility of Classical Reduction

In this subsection, we formally state Theorem 1.8 and prove it.

First, we define game-based assumptions. The definition is identical to
_falsifiable assumptions_ in [GW11] except for the important difference that
the challenger can be unbounded-time.

###### Definition 7.1 (Game-based assumptions).

A game-based assumption consists of a possibly unbounded-time interactive
machine $\mathcal{C}$ (the challenger) and a constant $t\in[0,1)$. On the
security parameter $1^{\lambda}$, the challenger $\mathcal{C}(1^{\lambda})$
interacts with a classical or quantum machine $\mathcal{A}$ (the adversary)
over a classical channel and finally outputs a bit $b$. We denote this
execution by
$b\leftarrow\langle\mathcal{A}(1^{\lambda}),\mathcal{C}(1^{\lambda})\rangle$.

We say that a game-based assumption $(\mathcal{C},t)$ holds against classical
(resp. quantum) adversaries if for any PPT (resp. QPT) adversary
$\mathcal{A}$,
$|\Pr[1\leftarrow\langle\mathcal{A}(1^{\lambda}),\mathcal{C}(1^{\lambda})\rangle]-t|\leq{\mathsf{negl}}(\lambda).$

######  Remark 7.2 (Examples).

As explained in [GW11], the above definition captures a very wide class of
assumptions used in cryptography even if we restrict the challenger to be PPT.
They include (but not limited to) general assumptions such as security of
OWFs, public key encryption, digital signatures, oblivious transfers etc. as
well as concrete assumptions such as the hardness of factoring, discrete-
logarithm, LWE etc. In addition, since we allow the challenger to be
unbounded-time, it also captures some non-falsifiable assumptions such as
hardness of indistinguishability obfuscation [BGI+12, GGH+16] or succinct
arguments [Mic00] etc. Examples of assumptions that are not captured by the
above definition include so called knowledge assumptions [Dam92, CD08, CD09,
BCCT12] and zero-knowledge proofs with non-black-box zero-knowledge [HT98,
Bar01].

We clarify meanings of several terms used in the statement of our theorem.

###### Definition 7.3 (Classical oracle-access to a cheating prover).

Let $\Pi=(\mathcal{P},\mathcal{V}=(\mathcal{V}_{1},\mathcal{V}_{2}))$ be a
two-round AI-IV-PoQ. We say that a (possibly unbounded-time stateless)
randomized classical machine $\mathcal{P}^{*}$ breaks $s$-soundness of $\Pi$
if there is a polynomial ${\mathrm{poly}}$ such that
$\Pr[\top\leftarrow\mathcal{V}_{2}(I):I\leftarrow\langle\mathcal{P}^{*}(\sigma),\mathcal{V}_{1}(\sigma)\rangle]\geq
s(|\sigma|)+1/{\mathrm{poly}}(|\sigma|)$ for all but finitely many
$\sigma\in\Sigma$. We say that an oracle-aided classical machine $\mathcal{R}$
is given oracle access to $\mathcal{P}^{*}$ if it can query an auxiliary input
$\sigma$ and the first-round message $m_{1}$ of $\Pi$ and the oracle returns
the second-round message $m_{2}$ generated by $\mathcal{P}^{*}$ with a fresh
randomness $r$ in each invocation.

######  Remark 7.4.

Since we consider two-round protocols, we can assume that $\mathcal{P}^{*}$ is
stateless without loss of generality.

Then we state the formal version of Theorem 1.8.

###### Theorem 7.5.

Let $\Pi$ be a two-round AI-IV-PoQ that satisfies $c$-completeness and
$s$-soundness where $c(\lambda)-s(\lambda)\geq 1/{\mathrm{poly}}(\lambda)$ and
let $(\mathcal{C},t)$ be a game-based assumption. Suppose that there is an
oracle-aided PPT machine $\mathcal{R}$ (the reduction algorithm) such that for
any (possibly unbounded-time stateless) randomized classical machine
$\mathcal{P}^{*}$ that breaks $s$-soundness of $\Pi$,
$|\Pr[1\leftarrow\langle\mathcal{R}^{\mathcal{P}^{*}}(1^{\lambda}),\mathcal{C}(1^{\lambda})\rangle]-t|$
is non-negligible. Then the game-based assumption $(\mathcal{C},t)$ does not
hold against quantum adversaries.

###### Proof.

Let $\widetilde{\mathcal{P}}^{*}$ be an unbounded-time randomized classical
machine that simulates the honest QPT prover $\mathcal{P}$. Then
$\widetilde{\mathcal{P}}^{*}$ breaks $s$-soundness of $\Pi$ because of
$c$-soundness and $c(\lambda)-s(\lambda)\geq 1/{\mathrm{poly}}(\lambda)$.
Thus,
$|\Pr[1\leftarrow\langle\mathcal{R}^{\widetilde{\mathcal{P}}^{*}}(1^{\lambda}),\mathcal{C}(1^{\lambda})\rangle]-t|$
is non-negligible. Since $\widetilde{\mathcal{P}}^{*}$ is simulatable by a QPT
machine, $\mathcal{R}^{\widetilde{\mathcal{P}}^{*}}$ is simulatable by a QPT
machine. Thus, $(\mathcal{C},t)$ does not hold against quantum adversaries. ∎

######  Remark 7.6.

One might think that a similar proof extends to the case of quantum
reductions. However, we believe that this is non-trivial. For example, suppose
that a quantum reduction algorithm $\mathcal{R}$ queries a uniform
superposition $\sum_{m_{1}}\ket{m_{1}}$ to the oracle where we omit an
auxiliary input for simplicity. If the oracle is a classical randomized
cheating prover $\mathcal{P}^{*}$, then it should return a state of the form
$\sum_{m_{1}}\ket{m_{1}}\ket{\mathcal{P}^{*}(m_{1};r)}$ for a randomly chosen
$r$ where $\mathcal{P}^{*}(m_{1};r)$ is the second message $m_{2}$ sent by
$\mathcal{P}^{*}$ given the first-round message $m_{1}$ and randomness $r$. On
the other hand, if we try to simulate the oracle by using the honest QPT
prover $\mathcal{P}$, then the resulting state is of the form
$\sum_{m_{1},m_{2}}\ket{m_{1}}\ket{m_{2}}\ket{garbage_{m_{1},m_{2}}}$. Due to
potential entanglement between the first two registers and the third register,
this does not correctly simulate the situation with a classical prover.

###  7.2 Oracle Separation

In this subsection, we formally state Theorem 1.9 and prove it.

First, we define cryptographic primitives. The following definition is taken
verbatim from [RTV04] except for the difference that we consider quantum
security. We remark that we restrict primitives themselves to be classical and
only allow the adversary (the machine $M$) to be quantum.

###### Definition 7.7 (Cryptographic primitives; quantumly-secure version of
[RTV04, Definition 2.1]).

A primitive $\mathtt{P}$ is a pair $(F_{\mathtt{P}},R_{\mathtt{P}})$, where
$F_{\mathtt{P}}$ is a set of functions
$f:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{*}$, and $R_{\mathtt{P}}$ is a relation
over pairs $(f,M)$ of a function $f\in F_{\mathtt{P}}$ and an interactive
quantum machine $M$. The set $F_{\mathtt{P}}$ is required to contain at least
one function which is computable by a PPT machine.

A function $f:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{*}$ implements $\mathtt{P}$
or is an implementation of $\mathtt{P}$ if $f\in F_{\mathtt{P}}$. An efficient
implementation of $\mathtt{P}$ is an implementation of $\mathtt{P}$ which is
computable by a PPT machine. A machine $M$ $\mathtt{P}$-breaks $f\in
F_{\mathtt{P}}$ if $(f,M)\in R_{\mathtt{P}}$. A quantumly-secure
implementation of $\mathtt{P}$ is an implementation of $\mathtt{P}$ such that
no QPT machine $\mathtt{P}$-breaks $f$.

It was pointed out in [BBF13] that the above definition was too general and
there are subtle logical gaps and counter examples in their claims. In
particular, [RTV04] implicitly assumes that if two machines $M$ and
$M^{\prime}$ behave identically, then $(f,M)\in R_{\mathtt{P}}$ and
$(f,M^{\prime})\in R_{\mathtt{P}}$ are equivalent. We formalize this property
following [BBF13] where the definitions are taken verbatim from there except
for adaptation to the quantumly-secure setting.

###### Definition 7.8 (Output distribution [BBF13, Definition B.1 in the
ePrint version]).

An interactive (oracle-aided) quantum Turing machine $M$ together with its
oracle defines an output distribution, namely, each fixed finite sequence of
inputs fed to $M$ induces a distribution on the output sequences by
considering all random choices of $M$ and its oracle. The output distribution
of $M$ is defined to be the set of these distributions, indexed by the finite
sequences of input values.

###### Definition 7.9 (Semantical cryptographic primitive [BBF13, Definition
B.2 in the ePrint version]).

A cryptographic primitive $\mathtt{P}=(F_{\mathtt{P}},R_{\mathtt{P}})$ is
called semantical, if for all $f\in F_{\mathtt{P}}$ and all interactive
(oracle-aided) quantum Turing machines $M$ and $M^{\prime}$ (including their
oracles), it holds: If $M$ induces the same output distribution as
$M^{\prime}$, then $(f,M)\in R_{\mathtt{P}}$ if and only if $(f,M^{\prime})\in
R_{\mathtt{P}}$.

######  Remark 7.10 (Examples).

As explained in [RTV04, BBF13], most cryptographic primitives considered in
the literature are captured by semantical cryptographic primitives. They