In this section we prove a round compression result for quantum interactive arguments. It was proved by Kitaev and Watrous in <cit.> that every $m$-round quantum interactive proof (i.e. were the prover has unbounded computational power) for a (promise) language $L$ can be compressed into another interactive proof for $L$ that only has $3$ messages and the soundness is worsened by a factor $\poly(m)$. By parallel repetition, the soundness can be improved back to a constant <cit.>. This stands in contrast to the classical case, where an analogous round compression technique for interactive proofs is unknown and considered unlikely.

We prove an analogue of the Kitaev–Watrous compression procedure for interactive arguments:

Let $L$ be a promise language with an $m(n)$-message quantum interactive argument with completeness $c$ and soundness $s$ for $m \ge 3$.
Then there exists a $3$-message quantum interactive argument for $L$ with completeness $1 - \frac{2(1 - c)}{m - 1}$ and soundness $1 - \frac{1 - s}{(m - 1)^4}$.
Furthermore, if the original prover has complexity $t_P$ and verifier has complexity $t_V$, then the compressed protocol has prover complexity $m^{O(1)}(t_P + t_V)$ and verifier complexity $m^{O(1)}t_V$.

We follow the proof approach of Kempe et al. <cit.> (see also <cit.>) who gave an iterative procedure to round-compress quantum proof systems (whereas the original Kitaev-Watrous proposal achieved the compression in one step). The idea as follows: given a $(2r+1)$-message “original” protocol, one can obtain an $(r+1)$-message “compressed” protocol where the prover first sends the intermediate state of the verifier at round $r+1$ of the original protocol (i.e., the midpoint). The verifier in the compressed protocol randomly decides whether to play the original protocol forwards or backwards to check respectively whether the original verifier would have accepted, or was initialized properly.
Our protocol is similar in spirit to this reduction, except that we must slightly tweak the reduction and analysis to ensure that the reduction is efficient.

In the quantum interactive proof setting, the assumption of perfect completeness on the original protocol is not necessary, because every quantum interactive proof can be transformed to have perfect completeness (see <cit.> and <cit.>). However we do not know whether quantum arguments can be generically transformed to have perfect completeness.

To maintain consistency with existing work regarding interactive proofs and arguments, in this section we adopt the terminology “verifier”, “honest prover”, and “adversary” (or malicious prover).  The verifier corresponds to the challenger in an interactive argument.  When talking about completeness, the honest prover corresponds to the adversary, and when talking about soundness we still use the term adversary.

When we refer to the total run-time of an efficient adversary in an interactive argument, as the total time it takes to execute the entire interaction between the adversary and the challenger.  If every action the adversary takes is polynomial time, then the total run-time will be a polynomial in $n$ as well.

We first describe a “round-halving” compression procedure that transforms a verifier for a $(2r+1)$-message protocol to a verifier for an equivalent $(r+1)$-message protocol (in the completeness and soundness sense).  Our reduction adds at most a constant overhead to the gate complexity of the verifier. At the end, we will iterate this procedure logarithmically many times to obtain a $3$-message protocol.

Let $\{C_i\}_{i \leq r}$ be a verifier in a $(2r+1)$-message quantum interactive protocol.
We describe a $(r + 1)$-message protocol and analyse its completeness and soundness.  We briefly recall the notation used to describe quantum interactive arguments.  $\reg{A_i}$ denotes the adversaries private workspace in round $i$, $\reg{M}_i$ denotes the message register sent from the adversary to the challenger, and $\reg{R_i}$ denotes the response register sent from the challenger to the adversary.  The adversary applies the unitary $A_i$ on $\reg{A_iR_{i-1}}$ to get a state on $\reg{A_{i+1}M_i}$, and the verifier applies a unitary $C_i$ on $\reg{W_iM_i}$ to get a state on $\reg{W_{i+1}R_i}$.  In the final round, the challenger applies a POVM $\{D, \id - D\}$ on $\reg{W_{r}M_{r}}$ to decide whether to accept or reject.

[breakable=false, padding=1em, margin-top=1em, margin-bottom=1em]
Verifier for $(r+1)$-message compressed protocol

* Receive registers $\reg{M}_{r/2}\reg{W}_{r/2}$ from the adversary.  Flip a unbiased coin.

* If the outcome of the coin flip is heads:

* Run the original $2r+1$-message protocol starting from interaction $r/2$, i.e. apply unitary $C_{r/2}$ to registers $\reg{M}_{r/2}\reg{W}_{r/2}$, send the result of the coin flip and $\reg{R}_{r/2}$ to the adversary, and continue for interactions $r/2+1$ through $r$.step]step:forward_compression

* After $r/2$ many interactions, receive register $\reg{M_{r}}$, measure $\Pi$ on registers $M_{r}\reg{W}_{r}$.  Accept if the measurement accepts.

* If outcome of the coin flip is tails:

* Run the original $2r+1$-message protocol in reverse, i.e. send the result of the coin flip and $\reg{M}_{r/2}$ back to the adversary, receive register $\reg{R}_{r/2-1}$ from the adversary, apply $(C_{r/2-1})^{\dagger}$ to $\reg{R}_{r/2-1}\reg{W}_{r/2}$, and continue for interactions $r/2-1$ through $1$.  step]step:backward_compression

* After $r/2$ many interactions, receive register $\reg{R}_{1}$.  Apply $(C_{1})^{\dagger}$ on registers $\reg{R}_1\reg{W}_2$ to get registers $\reg{M}_0\reg{W}_0$, and measure $\proj{0}_{\reg{W}_0}$.  Accept if the measurement accepts.

If there is an non-uniform (resp. uniform) honest prover (denoted the original honest prover) that succeeds in the original $(2r+1)$-message protocol with probability $1 - \epsilon$, then there is a non-uniform (resp. uniform) honest prover that succeeds in the $(r+1)$-message compressed protocol with probability $1 - \epsilon/2$.
Furthermore, if the original protocol has running time $t_P, t_V$ for the prover and the verifier, then the new protocol has running time $O(t_P + t_V)$ for the prover and $O(t_V)$ for the verifier.

Let $A_{i}$ be unitary operations that the honest prover implements in the $i$'th interaction.  Specifically, the honest prover applies $A_{i}$ to registers $\reg{R}_{i-1}\reg{A_i}$ to get a message register $\reg{M_i}$ and new private register $\reg{A_{i+1}}$, and then sends $\reg{M}_i$ to the verifier.  Initially, $\reg{R}_{0}$ is an empty register, and $\reg{A_0}$ is initialized to some state $\proj{\aux}_{\reg{A}_0}$ (in the non-uniform case this might be an advice state, otherwise $\proj{0}$).

The honest prover for the compressed protocol will essentially implement the honest strategy, applying the unitaries of the un-compressed honest prover forward or backwards depending on the outcome of the verifier's coin flip.  The honest prover begins by performing preparing a register $\reg{W_0}$ in the state $\ket{0}_{\reg{W_0}}$, and then performs $A_{0}, C_0, A_{1}, C_1, \ldots, A_{r/2}$ to the appropriate registers to get a state over registers $\reg{A_{r/2+1}}\reg{M_{r/2}}\reg{W_{r/2}}$.  The honest prover then sends $\reg{M_{r/2}}\reg{W_{r/2}}$ to the challenger as their initial message.

If the outcome of the verifier's coin flip is heads, the honest prover applies $A_{r/2+1}$ to the verifier's response, and continues as the un-compressed honest prover would starting from round $(r/2)+1$.  After all $r/2$ interactions, the verifier and honest prover hold the state after implementing the unitaries $A_0, C_0, \ldots, A_{r}$ on the initial state $\proj{\aux}_{\reg{A_0}}\otimes \proj{0}_{\reg{W_0}}$ and then measuring $D$ on registers $\reg{M_{r}}\reg{W_{r}}$.  Since the original protocol accepted with probability $1-\epsilon$, we have that

\begin{equation*}
\Tr(D (A_{r} C_{r-1} \ldots C_0 A_0) (\proj{\aux}_{\reg{A}_0} \otimes  \proj{0}_{\reg{W_0}}) (A_0^\dagger C_0^{\dagger} \ldots C_{r-1}^{\dagger} A_{r}^{\dagger})) = 1 - \epsilon\,.
\end{equation*}

Thus, the probability that the honest prover is accepted is also $1 - \epsilon$.

If the outcome of the verifier's coin flip is tails, when the honest prover receives register $\reg{M_i}$, the honest prover applies $(A_{i})^{\dagger}$ to $\reg{M_i}\reg{A_{i+1}}$ and sends registers $\reg{R}_{i-1}$ to the verifier, and continues by applying the inverse of the un-compressed honest prover unitary, going backwards in round number.  When the protocol reaches the final message, the honest prover and verifier will have performs the inverse of $C_0, A_1, C_1, \ldots, A_{r/2}$ to yield some state $\ket{\psi}_{\reg{M_0}\reg{A_1}} \otimes \ket{0}_{\reg{W_0}}$.  When the verifier measures $\proj{0}$, the measurement will accept with probability $1$.

So with probability $1/2$, the honest prover is accepted with probability $1 - \epsilon$, and with probability $1/2$ the honest prover is accepted with probability $1$.  Thus, the overall probability that the honest prover is accepted is $1 - \epsilon/2$.

To analyze the runtime of the honest prover, note that the honest prover for the compressed protocol applies every unitary $A_i$ at most twice, and runs the first verifier's unitaries $C_i$ at most once.  The verifier runs every $C_i$ at most once, so together they run every $A_i$ and $C_i$ at most twice, so its total running time of the protocol is at most twice the total running time of the original honest prover.  We note that the compressed honest prover can be implemented by controlling the $A_i$ and $C_i$ on the message register (so that they act correct controlled on the outcome of the verifier's coin flip).  If the honest prover can only use $2$-qubit gates, this might result in a constant multiplicative overhead to the gate complexity of the honest prover.

If there is a adversary that has total run-time $t$ that succeeds in the $(r+1)$-message compressed protocol with probability $1 - \epsilon$, then there is an adversary that has total run-time $O(t + t_V)$ and succeeds in the original $(2r+1)$-message protocol with probability $1 - 16\epsilon$.

We can assume that $\epsilon \leq 1/16$, otherwise the claim is trivially true.  Assume that the adversary for the $(r+1)$-message compressed protocol implements an initial unitary $A_{0}$ on register $\reg{A_0}$, which is initialized in state $\ket{\aux}_{\reg{A_0}}$.  Call the output registers of this unitary $\reg{A_{r/2 + 1}}\reg{M_{r/2}}\reg{W_{r/2}}$, of which $\reg{M_{r/2}W_{r/2}}$ are sent to the challenger as the adversary's first message.  After seeing the result of the coin flip, $b \in \{H, T\}$, from the challenger, we denote by $A^{b}_{i}$ the unitaries that the adversary implements in interactions $i = 1$ through $r/2$.  We say that the unitary $A^{H}_{i}$ acts on registers $\reg{R_{r/2 + i - 1}}\reg{A_{r/2 + i}}$ (so that the first one acts on registers $\reg{R_{r/2}}\reg{A_{r/2 + 1}}$ and counts up from there) and the unitary $A^{T}_{i}$ acts on registers $\reg{M_{r/2 - i + 1}}\reg{A_{r/2 - i + 2}}$ (so that the first one acts on registers $\reg{M_{r/2}}\reg{A_{r/2 + 1}}$).  The challengers actions in the game are specified in <Ref>.  Define the following projectors.

\begin{align*}
\Pi_{H} &= (A_0^{\dagger}  C_{r/2}^{\dagger} {A^{H}_{1}}^{\dagger} C_{r/2+1}^{\dagger} \ldots A^{H \dagger}_{r/2}) D_{\reg{M_{r}W_{r}}} (A^{H}_{r/2} \ldots C_{r/2 + 1} A^{H}_{1} C_{r/2}  A_0)\,,\\
\Pi_{T} &= (A_0^{\dagger} {A^{T}_{1}}^{\dagger} C_{r/2-1} \ldots A^{T \dagger}_{r/2} C^{\dagger}_{0}) (\id \otimes \proj{0}_{\reg{W_0}}) (C_{0}^{\dagger} A^{T}_{r/2}\ldots C_{r/2-1}^{\dagger} A^{T}_{1} A_0)\,.
\end{align*}

It is clear that $\Tr(\Pi_{H}\proj{\aux})$ and $\Tr(\Pi_{T}\proj{\aux})$ are the probabilities that the adversary is accepted when the result of the challenger's coin flip is $H$ and $T$ respectively.  By assumption, the adversary is accepted in the $r+1$-message compressed protocol with probability $1 - \epsilon$, so the adversary must be accepted in the protocol if the coin flip is fixed to being either heads or tails with probability at least $1-2\epsilon$.  Therefore we have the inequalities

\begin{align*}
\Tr(\Pi_{H}\proj{\aux}) \geq 1 - 2\epsilon\,,\\
\Tr(\Pi_{T}\proj{\aux}) \geq 1 - 2\epsilon\,.
\end{align*}

Now we construct an adversary for the original $(2r+1)$-message protocol as follows:

[breakable=false, padding=1em, margin-top=1em, margin-bottom=1em]
Adversary for the $(2r+1)$-message protocol

Input:  Initial state $\ket{\aux}$.

* Run $A_0$ to receive a state on registers $\reg{A_{r/2+1}M_{r/2}W_{r/2}}$.  Implement unitaries $A^{T}_{1}, C^{\dagger}_{r/2 - 1} \ldots, A^{T}_{r/2}, C_0^{\dagger}$ to receive a state on registers $\reg{M_0}\reg{W_0}$.  Measure $\id \otimes \proj{0}_{\reg{W}_0}$, if the measurement fails, abort.  If it accepts, send register $\reg{M_0}$ to the verifier.

* For steps $i = 1$ through $r/2$:

* Run $(A^{T}_{r/2 - i})^{\dagger}$ to get the next message register and send it to the verifier.

* For steps $i = r/2+1$ through $r$:

* Run $A^{H}_{i - r/2}$ to get the next message register and send it to the verifier.

Let $\rho_T$ be the state of the adversary after measuring $\Pi_T$ on $\proj{\aux}$ and accepting.  Let $\rho_H$ be the state after measuring $\Pi_H$ on $\proj{\aux}$ and accepting.  By the gentle measurement lemma (<Ref>) and the definition of the squared Bures distance, we have that the the following inequalities

\begin{align*}
\buresdist(\rho_T, \proj{\aux}) &\leq 2(1 - \sqrt{1 - 2\epsilon}) \leq 3\epsilon\,,\\
\buresdist(\rho_H, \proj{\aux}) &\leq 3\epsilon\,.
\end{align*}

Here the first inequality holds for any $0 \le \epsilon \le \frac49$.
Using the weak triangle inequality for the squared Bures distance (<Ref>), we have that

\begin{equation*}
\buresdist(\rho_H, \rho_T) \leq 12 \epsilon\,.
\end{equation*}

By the definition of the squared Bures distance, we have that

\begin{equation}\label{eqn:heads_tails_fidelity}
\fidelity(\rho_H, \rho_T) \geq (1 - 6\epsilon)^2 \geq 1 - 12\epsilon\,,
\end{equation}

where we applied the Bernoulli inequality here.  Now we examine the state of the adversary in the un-compressed game.  If the un-compressed adversary does not abort in step $1$, after step $2$, the adversary is left with exactly $\rho_T$, because they condition on $\proj{0}_{\reg{W_0}}$ accepting.  At the end of the protocol, the challenger will have implemented the measurement $\Pi_{H}$ on the adversary's state after step $2$, $\rho_{T}$.  Since $\Pi_{H}$ is a projector and $\rho_{H}$ is the post-measurement state of some initial state after measuring $\Pi_{H}$, we have that $\Tr(\Pi_{H} \rho_{H}) = 1$.  Applying <Ref> and <Ref>, we have that $\Tr(\Pi_{H}\rho_{T}) \geq \fidelity(\rho_{H}, \rho_{T}) \geq 1 - 16\epsilon$.  Thus, the adversary is accepted with probability at least $1 - 16\epsilon$.  By assumption, the first measurement in the step succeeds with probability $(1 - 2\epsilon)$, thus the total probability of failure is given by

\begin{equation*}
2\epsilon + (1 - 2\epsilon) \cdot 12 \epsilon \leq 16\epsilon\,.
\end{equation*}

The un-compressed adversary applies every the unitaries $A_i^{T}$ (and $(A_i^{T})^{\dagger}$) two times, the unitaries $C_{i}^{\dagger}$ once, and the unitaries $A_i^{H}$ once.
Thus the total run time of the adversary is $O(t + t_V)$ accounting for constant multiplicative overheads in implementing controlled unitaries.

To prove the theorem, we iterate the round-halving procedure. Let $L = (L_{yes},L_{no})$ be a (promise) decision language with a quantum interactive proof $\proto$ where for inputs of length $n$, the protocol has $m(n)$ messages. We assume without loss of generality that $m(n)$ is of the form $2^{k(n)}+1$; the adversary and challenger can send empty messages at the beginning of the protocol.
In other words, $k = \lceil\log(m - 1)\rceil$ and $2^{k - 1} < m - 1 \le 2^k$.

Let $\proto'$ denote protocol that applies the round-halving procedure described above $k - 1$ times. In other words, when the challenger receives input $x$, it first computes the description of the challenger for the $(2^{k-1}+1)$-message protocol (where $n = |x|$), and then based on this computes the description of the challenger for the $(2^{k-2}+1)$-message protocol, and so forth, until it obtains a challenger for a $3$-message protocol. Since $m(n)$ is polynomial in $n$, $k = O(\log n)$.
The final honest prover runs in time $m^{O(1)} (t_P + kt_V)$ and the verifier runs in time $m^{O(1)} t_V$, where the $O(1)$ factors here are exactly the constant multiplicative overhead above.

We now analyze the completeness and soundness of the $3$-message protocol. Given a “yes” instance $x \in L_{yes}$, by definition there is an adversary that is accepted with probability $c = 1 - \delta$.  By <Ref>, there is an adversary for the $2^{k(n) - 1}$+1-message protocol that is accepted with probability $1 - \delta/2$.  Repeating the compression $k - 1$ times, there exists an adversary that is accepted by the $3$-message protocol with probability

\begin{equation*}
1 - \frac{\delta}{ 2^{k - 1}} \geq 1 - \frac{2\delta}{m(n) - 1}.
\end{equation*}

Given a “no” instance $x \in L_{no}$, the original protocol accepts with probability at most $s = 1 - \eps$ for all efficient adversaries. Then by <Ref>, the soundness of the $2^{k(n)-1}+1$-message protocol is at most $1 - \eps/16$.
Similarly the  soundness of the $2^{k(n)-1}+1$-message protocol is at most $1 - \eps/16^2$. Iterating this we see that the $3$-message protocol has soundness at most

\[
1 - \frac{\eps}{16^{k - 1}} \leq 1 - \frac{\eps}{(m - 1)^4}.
\]

We note that all of the reductions are efficient, even after $k - 1$ iterations of round collapse.  Specifically, for “no” instances, if there is an adversary for the compressed protocol that has total run-time $t(n)$, then there is an adversary for the original protocol that has total run-time $m^{O(1)} (t + kt_V)$, which is efficient.

We can slightly extend our round compression to compile any $3$-message quantum interactive argument into a public coin argument using the same strategy as <cit.>.  A public coin quantum interactive argument is a quantum interactive argument where all of the challenger messages are uniformly random coin flips.  At a high level, if we were to apply round compression starting with a $3$-message protocol, the challenger only ever needs to receive one register (either $\reg{R}_0$ to go backwards, or $\reg{M}_1$ to go forwards) from the adversary, so they do not need to send back a quantum register as in round compression for $m > 3$.  Formally, we have the following.

Let $L$ be a promise language with a $3$-message quantum interactive argument with completeness $c$ and soundness $s$.  Then there exists a $3$-message public coin quantum interactive argument for $L$ with completeness $1 - \frac{1 - c}{2}$ and soundness $1 - \frac{1 - s}{16}$.

Let $(C_0, \Pi)$ be a challenger for a $3$-message quantum interactive protocol.  Consider the following challenger for a $3$-message protocol.

[breakable=false, padding=1em, margin-top=1em, margin-bottom=1em]
Challenger for $3$-message public coin protocol

* Receive registers $\reg{W}_{1}$ from the adversary.  Flip a unbiased coin and send it to the adversary.

* If the outcome of the coin flip is heads:

* The adversary sends register $\reg{M}_1$.

* Measure $\Pi$ on $\reg{M}_1\reg{W}_1$, accept if the measurement accepts.

* If outcome of the coin flip is tails:

* The adversary sends register $\reg{R}_0$.

* Perform $C_{0}^{\dagger}$, and measure $\proj{0}$ on registers $\reg{W}_0$, accept if the measurement accepts.

This protocol is clearly public coin, as the challenger only sends the outcome of a single coin flip to the adversary.  An honest adversary runs the original $3$-message protocol up to the first two messages and sends the challenger's private workspace to the challenger.  Upon seeing heads they perform the honest adversary unitary and send $\reg{M}_1$, and upon seeing tails they send back $\reg{R}_0$ to the challenger.  A similar argument as <Ref> shows that the completeness behaves the same way as applying a single round of round compression.

Similarly, given an adversary for the public coin protocol, a malicious adversary for the original protocol can simulate the interaction between the public coin adversary and the challenger, and measure the challenger's private workspace to get $\proj{0}_{\reg{W}_0}$, and then get a suitable state on $\reg{M}_0$ to send to the challenger.  From there they run the public coin adversary, conditioned on seeing tails, in reverse for one step, and then the public coin adversary, conditioned on seeing heads, forward for one step.  The same argument as in <Ref> shows that the soundness of the public coin protocol is equivalent to having applied round compression one additional step.

The run-time of the adversary in both directions is multiplied by a constant factor in the reduction, so the reduction is efficient.

Finally, we combine <Ref> with our hardness amplification result to show that all polynomial-message quantum interactive arguments can be compressed into $3$-message quantum interactive arguments with negligible soundness.

Let $L$ be a (promise) language that has a polynomial-message quantum interactive argument with completeness $c \geq 1 - \negl(n)$ (or 1, respectively) and soundness $s \leq 1 - \frac{1}{\poly(n)}$.  Then there is a $3$-message public coin quantum interactive argument for $L$ with completeness $1 - \negl(n)$ (or 1, respectively) and soundness $\negl(n)$.

We remark that this parallel repetition is not as efficient as what is possible classically.
Classically, to amplify any interactive argument (say of soundness $\frac12$ to soundness $\frac14$) while preserving round complexity $r$, the state of the art incurs a multiplicative cost of order either $r$ <cit.> or $\lambda$ <cit.>, where $\lambda$ is a security parameter.
Turning back to quantum interactive arguments, we note that we can first round collapse the argument into three rounds (if it has more than three rounds), which only incurs a constant multiplicative overhead, and then apply the three-round soundness amplification.
In the end, the cost of the overall compiled protocol is $\Omega(r^4)$, since we need to make up for the loss in soundness in the round collapse theorem.
A more careful analysis of <Ref> could improve the exponent from $\log 16 = 4$ down to $\log 10 \approx 3.32$ but we leave as future work to further improve the amplification efficiency.

§ APPLICATIONS

The parallel repetition theorem has many immediate applications in cryptography, from boosting the security of commitments, to round reduction for zero-knowledge proofs.

§.§ Strong amplification of quantum bit commitment schemes

Here we show that the security of canonical quantum bit commitment schemes can be amplified through parallel repetition.  While we have already defined bit commitments and notions of post-quantum security, here we review canonical quantum bit commitment schemes, and the standard notions of security they are described by, honest hiding and binding

Canonical quantum bit commitments. A canonical quantum bit commitment is a kind of non-interactive bit commitment scheme. The scheme consists of two quantum circuits $C_0,C_1$, to commit to be a bit $b$, the sender generates the bipartite pure state $\ket{\psi_b}_{\reg{CR}} = C_b \ket{0 \ldots 0}$ and sends the $\reg{C}$ register of $\ket{\psi_b}$. To reveal, the sender sends $\reg{R}$ to the receiver, along with the bit $b$. The receiver can then verify the original bit $b$ by applying the circuit $C_b^{\dagger}$ and measuring $\ket{0\ldots 0}$. Importantly, Yan <cit.> showed that all quantum commitment schemes can be compiled to this canonical form while preserving (honest) hiding and binding security. Throughout this section we focus on canonical quantum commitment schemes.  The honest hiding property of a commitment scheme guarantees that an adversarial receiver can not reveal the bit committed to before the reveal phase. Formally,

Let $\eps(\lambda)$ denote a function. We say that a commitment scheme  $(\pi_{\lambda})_{\lambda}$ satisfies $\eps$-computational (resp. $\eps$-statistical) honest hiding if for all non-uniform polynomial-time algorithms  (resp. for non-uniform algorithms) $A = (A_\lambda)_\lambda$ that take as input the receiver's register immediately after an honest execution of the commit stage of $\proto_{\lambda}$, the following holds for sufficiently large $\lambda$:

\begin{equation*}\label{eqn:commitment_hiding_property}
\Big|\Pr \mbracket{A_\lambda(\rho_{\lambda,0}) = 1} - \Pr\mbracket{A_\lambda(\rho_{\lambda,1}) = 1} \Big | \leq \eps(\lambda) \,.
\end{equation*}

Here, $\rho_{\lambda,b}$ denotes the reduced density matrix of the receiver's register after a honest execution of the commit stage of $\proto_{\lambda}$ when the sender is committing to $b$.
If $\eps$ is a negligible function of $\lambda$ then we simply say that the scheme satisfies strong computational (resp. statistical) hiding. If $\epsilon(\lambda)\leq 1-\frac{1}{p(\lambda)}$ for some polynomial $p(\lambda)$ we say it satisfies weak computational (resp. statistical) hiding.

The honest binding property, at a high level, says that after the commit phase of a commitment scheme, an adversarial sender can only reveal to the bit that they committed to. Formally,

Let $\eps(\lambda)$ denote a function. We say that a commitment scheme $(\proto_{\lambda})_{\lambda}$ satisfies $\eps$-computational (resp. $\eps$-statistical) honest binding if for all
non-uniform polynomial-time algorithms  (resp. for all non-uniform algorithms) $A = (A_\lambda)_\lambda$ that take as input the sender's register immediately after an honest execution of the commit stage of $\proto_{\lambda}$, the following holds for sufficiently large $\lambda$:

\begin{equation*}
\fidelity\mparen{\Big( A_{\lambda} \otimes \id_{\reg{C}} \Big)(\psi_{\lambda,0}) , \psi_{\lambda,1}} \leq \eps(\lambda)\,,
\end{equation*}

where $\psi_{\lambda,b}$ denotes the state of the joint sender-receiver system after an honest execution of the commit stage of $\proto_{\lambda}$ when the committed bit is $b$.

If $\eps$ is a negligible function of $\lambda$ then we simply say that the scheme satisfies strong computational (resp. statistical) honest binding. Otherwise if $\epsilon(\lambda)\leq 1-\frac{1}{p(\lambda)}$ for some polynomial $p(\cdot)$ we say that it satisfies weak computational (resp. statistical) honest binding.

Parallel repetition of quantum bit commitments. We show that parallel repetition can be used to amplify weak computationally binding (and strong statistically hiding) commitments into commitments where both hiding and binding are strong.

Let $\{C_{\lambda, b}\}_{\lambda, b}$ be a canonical commitment scheme satisfying the $\paren{1 - \frac{1}{p(\lambda)}}$-computational honest binding property for some polynomial $p(\cdot)$, and strong statistical hiding.  Then there exists a polynomial $q(\cdot)$ such that the commitment scheme $\{C_{\lambda, b}^{\otimes q(\lambda)}\}_{\lambda, b}$ satisfies the strong computational honest binding property and strong statistical hiding property.

The computational honest binding property of (canonical) quantum commitments can be equivalently viewed as the maximum winning probability of the following $2$-message game (over efficient adversaries):

* The challenger commits to $0$, and sends the reveal register to the adversary.

* The adversary sends back a reveal register.

* The challenger accepts if applying $C_{\lambda, 1}$ and measuring in the computational basis yields $\ket{0^{\lambda}}$.

The maximum winning probability of this game is exactly the fidelity present in <Ref>.  By <Ref>, no non-uniform adversary can win the parallel repeated game with probability non-negligibly greater than $(1 - \frac{1}{p(\lambda)})^{q(\lambda)} = \negl(\lambda)$.  Thus, the repeated commitment satisfies strong computational honest binding.  Since $q$ is polynomial, the game still satisfies strong statistical hiding.

We can also amplify commitments that satisfy weak computational hiding (instead of binding) using flavor switching <cit.>, which we state below.

Let $\eps(n),\delta(n)$ be functions. If $\{C_{\lambda,b}\}_{\lambda,b}$ is an $\eps$-computationally (resp. statistical) hiding and $\delta$-statistical (resp. computational) binding commitment scheme, then there exists a $\sqrt{\delta}$-statistical (resp. computational) hiding and $\eps$-computationally (resp. statistical) binding commitment scheme.

The existence of either strong statistical hiding, weak computational honest binding, or strong statistical honest binding and weak computational hiding commitments imply standard commitments.

The first part of the corollary is the previous corollary, the second part is a direct implication of flavor switching for commitments.

This resolves an open problem from Yan <cit.> about the strong amplification of the Uhlmann transformation problem (equivalently quantum bit commitments).
We can push this result slightly to allow for amplification of some commitment schemes that have both weak security against both parties.

Let $\{C_{\lambda, b}\}_{\lambda, b}$ be a canonical commitment scheme satisfying the $\paren{1 - \frac{1}{p(\lambda)}}$-computational honest binding property for some polynomial $p(\cdot)$, and $\frac{1}{q(\lambda)}$ weak computational hiding, where  $q(\lambda) \geq 2\lambda p(\lambda)$.  Then standard commitments exist.

From <Ref>, the $\lambda p(\lambda)$-fold parallel repetition of the commitment has binding error $(1 - \frac{1}{p(\lambda)})^{\lambda p(\lambda)} + \negl(\lambda) \leq e^{-\lambda} + \negl(\lambda)$, and thus satisfies strong honest binding property, and the $\frac{\lambda p(\lambda)}{q(\lambda)} \leq \frac{1}{2}$-weak hiding property by hybrid argument.
We can then apply flavor switching to get a commitment that is satisfies the strong computational hiding property and the $\frac{1}{2}$-weak computational binding property.  The $\lambda$-fold parallel repetition of this commitment then satisfies the strong computational binding property too.

For example, a scheme which is $\frac{1}{2}$-binding and $\lambda^{-1}$-hiding can be amplified to a fully-secure commitment in this way. We leave as an open question whether an $\alpha$-binding, $\beta$-hiding quantum commitment can be amplified for some constant $\alpha,\beta$; classically, this is known for $\alpha + \beta \leq 1 - 1/\poly(\lambda)$, which is tight for black-box constructions <cit.>.

§.§ Quantum XOR lemma

XOR lemma for commitments.
By examining the flavor switching technique for quantum commitments closely, we can get an XOR lemma for quantum commitments, which states that one can amplify the computational hardness of breaking the hiding property of a quantum commitment via the XOR repetition of a computationally hiding commitment scheme. In the context of classical commitments, the $k$-fold XOR repetition of a commitment $C$ is a new commitment $C^{\oplus k}$ where to commit to bit $b \in \bits$, the sender will send commitments (using the “base commitment” $C$) to $x_1,\ldots,x_k$ for a randomly chosen string $x \in \bits^k$ with parity $b$. It was shown by Yao <cit.> that if $C$ was originally $\eps$-computationally hiding against classical adversaries, then $C^{\oplus k}$ is $O(\eps^k)$-computationally hiding. We now show that a quantum version of the XOR repetition applied to canonical quantum commitments does indeed amplify the hiding security of the commitment.

Let $C = \{C_{\lambda,b}\}_{\lambda,b}$ be a canonical quantum commitment scheme  that is $\eps$-computational hiding and $\delta$-statistically binding. Define the XOR repetition $C^{\oplus k} = \{ C^{\oplus k}_{\lambda,b} \}_{\lambda,b}$ to be the following quantum commitment scheme. Letting $\ket{\psi_{\lambda,b}} = C_{\lambda,b} \ket{0\cdots 0}$ for all $\lambda,b$, we define the circuits $C_{\lambda,b}^{\oplus k}$ so that the corresponding states $\ket{\psi^{\oplus k}_{\lambda,b}}$ are

\[
\ket{\psi^{\oplus k}_{\lambda,b}}_{\reg{R C}} := \frac{1}{\sqrt{2^{k-1}}} \sum_{x \in \bits^k : |x| = b \, \mathrm{mod}\, 2} \ket{x} \otimes \ket{\psi_{\lambda,x_1}}_{\reg{R_1 C_1}} \otimes \cdots \otimes \ket{\psi_{\lambda,x_k}}_{\reg{R_k C_k}}.
\]

In other words, the XOR-repeated commitment to $b$ is the uniform superposition, over all $k$-bit strings $x$ with parity $b$, of commitments to $x_1, x_2, \ldots, x_k$.
This state can be efficiently prepared by first preparing uniform superposition on $x_1, ..., x_{k - 1}$ and then coherently compute $x_k = x_1 \oplus \cdots \oplus x_{k - 1} \oplus b$.
The commitment register (resp. reveal register) of the XOR-repetition is the concatenation of the commitment register (resp. reveal register plus an extra register storing $x$) of all the individual commitments.

If the commitment $C$ is $\eps$-computational hiding and $\delta$-statistically binding, then the XOR repetition $C^{\oplus k}$ is $(\eps^{k/2} + \negl)$-computational hiding and $(k\sqrt\delta)$-statistically binding.

By applying flavor switching for quantum commitments (<Ref>) to $C$ to obtain a commitment $\hat{C}$ that is $\sqrt{\delta}$-statistical hiding and $\eps$-computational binding. The corresponding commitment states have the following form:

\[
\ket{\hat{\psi}_{\lambda,b}} = \frac{1}{\sqrt{2}} \Big( \ket{0} \ot \ket{\psi_{\lambda,0}} + (-1)^b \ket{1} \ot \ket{\psi_{\lambda,1}} \Big)
\]

where the commitment register of $\ket{\hat{\psi}_{\lambda,b}}$ is the reveal register of $\ket{\psi_{\lambda,b}}$ and the reveal register is everything else (including the extra ancilla qubit).

Now we take the parallel repetition of $\hat{C}$ to get $\hat{C}^{\otimes k}$; the corresponding commitment states have the following form:

\[
\ket{\hat{\psi}_{\lambda,b}^{\ot k}} = \frac{1}{\sqrt{2^k}} \sum_{x \in \bits^k} (-1)^{|x|} \ket{x} \ot \ket{\psi_{\lambda,x_1}} \ot \cdots \ot \ket{\psi_{\lambda,x_k}}~.
\]

By <Ref> we get that $\hat{C}^{\ot k}$ is $(k \sqrt{\delta})$-statistical hiding (by hybrid argument) and $(\eps^k + \negl)$-computational binding.

Now we flavor switch back to get our final commitment, which with the construction of <Ref> happens to be the XOR repeated commitment $C^{\oplus k}$. We get that $C^{\oplus k}$ is thus a $(\eps^{k/2} + \negl)$-computational hiding and $(k\sqrt{\delta})$-statistical binding commitment. Furthermore, it is easy to check that the corresponding commitment states $\ket{\psi^{\oplus k}_{\lambda,b}}$ have the desired form. This completes the proof.

We remark that due to the commitment duality <cit.>, parallel repetition theorem and XOR lemma for commitments are reducible to each other with very little cost, while classically the reduction to parallel repetition from XOR lemma requires majority <cit.>.
The reason we are able to do this more efficiently quantumly can be understood as we are replacing the Goldreich–Levin part <cit.> in the reduction (or the duality construction) with quantum Goldreich–Levin <cit.>, which is much more efficient.

Another consequence is polarization for EFI pairs <cit.>: pairs of efficient mixed states that are $\beta$-weakly statistically distinguishable but $\alpha$-weakly computationally indistinguishable where $\beta^2 \gg \sqrt\alpha$, for example, when $\alpha = \frac14$ and $\beta = \frac34$.

If there exist weak EFI pairs that are $\beta$-weakly statistically distinguishable but $\alpha$-weakly computationally indistinguishable such that $\beta^2 - \sqrt\alpha$ is at least constant, then standard EFI pairs exist.

In fact a stronger statement is true: assuming we have computational XOR lemma that amplifies to $\eps^{ck} + \negl$ for constant $\frac12 \le c \le 1$ and $\beta^2 - \alpha^c$ is at least constant, then EFI pairs exist.
Therefore, a tighter commitment duality (without the square root loss) would give better polarization parameters as well.
To prove this,  Watrous' construction and proof of $\mathsf{QSZK}$ polarization <cit.> immediately adapts to this setting, except that for we use $\alpha^c$ instead of $\alpha$ when picking the number of repetition.

For completeness, we reproduce the proof here.

We write $\cd(\rho_0, \rho_1) \le \alpha$ to mean that states $\rho_0$ and $\rho_1$ are $\alpha$-computationally indistinguishable.
Let $r = \lceil\log(8\lambda)/\log(\beta^2/\alpha^c)\rceil = O(\log \lambda)$ and $s = \lfloor\alpha^{-cr}/2\rfloor = \lambda^{O(1)}$.
We first apply $r$-fold XOR to these states giving $\rho_0', \rho_1'$, then we have that $\cd(\rho_0', \rho_1') \le \alpha^{cr} + \negl$ and $\td(\rho_0', \rho_1') \ge \beta^r$ <cit.>.
Next we apply $s$-fold parallel repetition to them giving $\rho_0'', \rho_1''$, and obtain that $\cd(\rho_0'', \rho_1'') \le \frac12 + \negl$ by hybrid argument, and $\td(\rho_0'', \rho_1'') \ge 1 - e^{1 - 2\lambda}$ following the same computation as Watrous.
Applying $\lambda$-fold XOR again completes the construction.

XOR lemma for quantum predicates.
Yao's classical XOR lemma states that taking the XOR of many copies of a Boolean predicate amplifies average-case hardness of prediction.
We can similarly use our XOR lemma to amplify unpredictability of quantum predicates.

An (average-case) quantum predicate is defined to be a Hermitian matrix $\rho$ with trace $0$ and Schatten $1$-norm at most $2$.
By Jordan–Hahn decomposition, this gives a bijection to the YES instances $\rho_+$ and the NO instances $\rho_-$ such that $\rho = \rho_+ - \rho_-$, with trace $\Tr(\rho_{+}) = \Tr(\rho_{-}) \leq 1$ and orthogonal support $\rho_{+}\rho_{-} = 0$ (so that the unpredictability is not caused by the input being a superposition over YES and NO).
(A worst-case extension of this is given by the promise Boolean observable $\sgn\rho$.)
We say the predicate $\rho$ is $\epsilon$-unpredictable if for all efficient observables $0 \preccurlyeq P \preccurlyeq \id$ with advice $\sigma$, its advantage $\Tr(P(\rho \otimes \sigma)) = \Tr(P(\rho_+ \otimes \sigma)) - \Tr(P(\rho_- \otimes \sigma)) \le \epsilon$.

The advantage of this notation (other than capturing everything with a single matrix) is that the $k$-fold XOR of $\rho$ is simply $\rho^{\otimes k}$, since for any two matrices $\rho_0, \rho_1$, $(\rho_0 - \rho_1)^{\otimes k} = \sum_{x \in \{0, 1\}^k} (-1)^{|x|} \rho_{x_1} \otimes \cdots \otimes \rho_{x_k}$.
The following corollary gives an XOR lemma for quantum predicate indistinguishability.

Let $\rho$ be an $\epsilon$-unpredictable predicate.
Then $\rho^{\otimes k}$ is $(\epsilon^{k/2} + \negl)$-unpredictable.

There is a bijection between every quantum state distinguishing problem $(\rho_0, \rho_1)$ and an average-case problem of implementing a quantum predicate $\rho = \rho_0 - \rho_1$, where in the backwards mapping, $\rho_0, \rho_1$ can be taken to be $\rho_+ + (1 - \Tr(\rho_+)) \cdot \id, \rho_- + (1 - \Tr(\rho_+)) \cdot \id$ respectively.
Furthermore, the distinguishing advantage of $P$ against $\rho_0$ vs $\rho_1$ is exactly $\Tr(P(\rho_0 \otimes \sigma)) - \Tr(P(\rho_1 \otimes \sigma)) = \Tr(P(\rho \otimes \sigma))$ for any $P, \sigma$.
We complete the proof by invoking <Ref>.

§.§ Security amplification for public-key quantum money

Another direct corollary of our main result (<Ref>) is security amplification for public-key quantum money schemes. We first define public-key quantum money.

Public-key quantum money.
Public-key quantum money, informally, is a scheme in which a trusted bank can efficiently generate an unlimited number of quantum banknotes, everyone can verify a valid banknote, and no efficient adversary can produce counterfeit bank notes with non-negligible success probability.  Formally,

A public-key quantum money scheme is a triple of efficient quantum algorithms $\cal{S} = (\mathsf{KeyGen},\mathsf{Mint},\mathsf{Ver})$ where

* $\mathsf{KeyGen}$ takes as input the security parameter $1^\lambda$ and outputs a private/public key pair $(k_{\mathrm{private}},k_{\mathrm{public}})$,

* $\mathsf{Mint}(k_{\mathrm{private}})$ outputs a pair $(s,\rho_{\$})$ where $s$ is a string representing a serial number and $\rho_{\$}$ is a quantum state representing a bank note, and

* $\mathsf{Ver}$ takes as input the public key $k_{\mathrm{public}}$, a serial number $s$, and an alleged banknote $\sigma$, and either accepts or rejects.

A public-key quantum money scheme $\cal{S}$ satisfies correctness if for all $\lambda$,

\[
\Pr \left [ \mathsf{Ver}(k_{\mathrm{public}}, s, \rho_{\$}) \text{ accepts} : \begin{array}{c}
(k_{\mathrm{private}},k_{\mathrm{public}}) \leftarrow  \mathsf{KeyGen}(1^\lambda) \\
(s,\rho_{\$}) \leftarrow \mathsf{Mint}(k_{\mathrm{private}})
\end{array}
\right ] \geq 1 - \negl(\lambda)\,.
\]

The scheme $\cal{S}$ is $\eps$-secure if for all efficient adversaries $A$, the success probability of $A$ in the counterfeit security game (<Ref>) is at most $\eps(\lambda)$.

[breakable=false, padding=1em, margin-top=1em, margin-bottom=1em]
Counterfeit security game challenger

* Generate $(k_{\mathrm{private}},k_{\mathrm{public}}) \leftarrow \KeyGen(1^{\lambda})$, $(s, \rho_{\$})\leftarrow \Mint(k_{\mathrm{private}})$ and send $(k_{\mathrm{public}}, s, \rho_{\$})$.

[Adversary returns two registers $\reg{AB}$ in some entangled state $\sigma_{\reg{AB}}$.]

* Run $\Ver(k_{\mathrm{public}}, s, \sigma_{\reg{A}})$ and $\Ver(k_{\mathrm{public}}, s, \sigma_{\reg{B}})$.  If either reject, reject, otherwise accept.

More money, fewer problems. Aaronson and Christiano <cit.> raised the question of whether there exists a general security amplification procedure for public-key quantum money schemes. They exhibited a procedure based on amplitude amplification that (for a class of schemes where the verification is a rank-1 projection) reduces the soundness error of $\Ver$ from a constant to negligible.
However, we note that this is different than reducing the soundness error of the counterfeit security game.  Their construction is only amplifies the success probability of the counterfeiter per serial number, in the sense that if the original $\Ver$ would have rejected an alleged banknote with constant probability, the new $\Ver$ will accept the same alleged banknote with negligible probability.
As a consequence, it would not amplify a weakly secure scheme where the proposed quantum money is unclonable for half of the serial numbers but trivially clonable for the other half.

We show that the parallel repetition of a quantum money scheme indeed achieves security amplification for all weak quantum money schemes.
More precisely, let $\cal{S}^{n}$ denote the $n$-fold parallel repetition of the quantum money scheme $\cal{S}$, with algorithms $(\mathsf{KeyGen}^n,\mathsf{Mint}^n,\mathsf{Ver}^n)$. The algorithm $\mathsf{KeyGen}^n$ algorithm runs $n$ independent instances of $\mathsf{KeyGen}$ to get pairs $(k_{\mathrm{private}}^{(1)},k_{\mathrm{public}}^{(1)}),\ldots,(k_{\mathrm{private}}^{(n)},k_{\mathrm{public}}^{(n)})$, and treats the tuple of individual private keys (resp. public keys) as a large private key (resp. public key) for $\cal{S}^n$. The algorithm $\mathsf{Mint}^n$ takes as input the tuple of private key and runs $\mathsf{Mint}(k_{\mathrm{private}}^{(i)})$ for $i = 1,\ldots,n$ to obtain  $n$ pairs $(s^{(1)},\rho_{\$}^{(1)}),\ldots,(s^{(n)},\rho_{\$}^{(n)})$; the output serial number is the tuple $(s^{(1)},\ldots,s^{(n)})$ and the output bank note is the concatenation $(\rho_{\$}^{(1)},\ldots,\rho_{\$}^{(n)})$. Finally the algorithm $\mathsf{Ver}^n$ will simply run $\mathsf{Ver}(k_{\mathrm{public}}^{(i)},s^{(i)},\rho_{\$}^{(i)})$ for $i=1,\ldots,n$ and accept if they all accept.

It is clear that if the base money scheme $\cal{S}$ satisfies correctness, so does the repeated scheme $\cal{S}^n$ (provided that the number of repetitions $n$ is polynomial in the security parameter $\lambda$). Next, the security game for the repeated scheme $\cal{S}^n$ is the $n$-fold parallel repetition of the security game for the base scheme $\cal{S}$. Since the security game is a $3$-message quantum interactive protocol, <Ref> directly implies the following:

Let $\cal{S}$ be an $\eps$-secure public-key quantum money scheme. Then $\cal{S}^n$ is an $(\eps^n + \negl)$-secure public-key quantum money scheme.

We note that the same argument essentially generalizes to any quantum cryptographic primitive with a security game consisting of at most three messages.
So far we have already considered two examples (commitments and money) where the security game has two messages.
Another notable example is quantum lightning <cit.>, a potentially stronger primitive than quantum money where the bank may not be able to produce two copies of the same banknote, also admits exponential security amplification via parallel repetition.
This is because the security game for quantum lightning is also a two-message quantum interactive protocol.

§.§ 3-round quantum zero knowledge

Weakly sound protocols also naturally occur in the context of zero knowledge protocols.
An important template for constructing zero knowledge protocols is the $\Sigma$-protocol.
At a high level, a $\Sigma$-protocol is a three-round protocol with inverse polynomial soundness (bounded away from 1), zero knowledge, and where the verifier's message is uniformly random.
$\Sigma$-protocols where the prover and verifier are quantum are sometimes called $\Xi$-protocols <cit.>).

A quantum $\Sigma$-protocol for a language $L$ is a public coin with $O(\log|x|)$ random bits of challenge, quantum interactive proof system the following additional property called computational zero knowledge defined as follows.
There exists a polynomial time quantum simulator $\Sim$ that takes as input a string $x$ and randomness $r$, and outputs a pair of quantum states $(\rho, \sigma)$ such that

\begin{equation*}
\{(\rho, \sigma) : (\rho, \sigma) \leftarrow \Sim(x, r)\}_{r} \approx_{c} \{(\rho, \sigma) : (\rho, \sigma) \leftarrow V(x) \interact_{r} P(x, \ket{\psi_{x}})\}_{r}
\end{equation*}

where $(\rho, \sigma) \leftarrow V(x) \interact_{r} P(x, \ket{\psi_{x}})$ denotes the mixed state of the message registers that the honest prover $P$ sends, conditioned on the challenger's randomness being $r$.

Note that in the context of classical and post-quantum zero knowledge proofs, $\Sigma$-protocol in addition requires special soundness, which we intentionally omit here.
Furthermore, below we also slightly abuse this notation to also include discussions of statistical zero knowledge arguments that follow this template.

While a $\Sigma$-protocol for all languages in $\class{QMA}$ is already known <cit.> and can be constructed from minimal assumptions <cit.>, the round collapse theorem also allows us to construct these differently by unconditionally compiling any honest-verifier zero knowledge protocol into a $\Sigma$-protocol.
As before, using our round collapse theorem can be advantageous (over building one from scratch by e.g. invoking <cit.>) for preserving certain properties of the original protocol like succinctness.

For any language $L$ that admits an $m$-message honest-verifier quantum statistical (resp. computational) zero knowledge protocol and computational (resp. statistical) soundness, $L$ also admits a malicious-verifier quantum statistical (resp. computational) zero knowledge protocol with 3 messages and computational (resp. statistical) soundness $1 - 1/\poly$.
Furthermore, the verifier's message is a coin flip, and the verifier and communication complexity only blows up by $m^{O(1)}$.

The statement for computational zero knowledge proofs is already proven by <cit.>, and generalizing this to arguments is straightforward with <Ref>.
For completeness, we sketch the proof strategy here.

The first step of the construction is to apply the round collapse theorem (<Ref>) to the original protocol.
We first show honest-verifier zero knowledge is preserved at each step in the iteration of <Ref>, and thus the final protocol is honest-verifier zero knowledge.
This can be seen as the honest verifier's view at round $i$ (out of $r + 1$ rounds) is simply a random bit $b$ (except for the first round where $b$ is uninitialized) along with the precompiled verifier's view at round $r + 1 + (-1)^b \cdot (i - 1)$.

In order to have malicious-verifier zero knowledge, we need to compile this protocol into a $\Sigma$-protocol where the verifier's second message is a single coin flip.  To do this, we apply <Ref>.
Honest verifier zero knowledge is still preserved since the view after round 1 is identical to the original view at round 2, and the view after round 3 is a random bit $b$ along with the original view at round $2 + (-1)^b$.

Finally, to show malicious-verifier zero knowledge, we can use the honest-verifier zero knowledge simulator to simulate the honest transcript and then apply Watrous rewinding <cit.> to the malicious verifier.

Thus we have round-collapsed the protocol while preserving relevant properties except soundness error.
To get back the same level of soundness, the natural approach is to apply $m^{O(1)}$-fold parallel repetition.
While the protocol after parallel repetition is unlikely to be zero knowledge <cit.>, witness indistinguishability (as well as honest-verifier zero knowledge) is preserved via a standard hybrid argument.
We thus arrive at the following.

For any language $L$ that admits an $m$-message honest-verifier quantum statistical (resp. computational) zero knowledge protocol and computational (resp. statistical) soundness, $L$ also admits a malicious-verifier statistical (resp. computational) witness indistinguishable protocol with 3 messages and negligible computational (resp. statistical) soundness.
Furthermore, the verifier is public coin, and the verifier and communication complexity only increases by a multiplicative $m^{O(1)}$ factor.

We leave as future work to improve this to a stronger security, which is beyond the scope of this work.
For starters, we conjecture that this class of 3-message protocols is already witness hiding even for instances with unique witness <cit.>.
Another direction is to consider recovering zero knowledge by further augmenting the protocol like classically.
For example, we expect one could combine <Ref> with <cit.> using (instance-dependent) commitments to compile a computational zero knowledge proof down to 4 rounds (with coherent expected-QPT simulation <cit.>
It is known that constant-round post-quantum zero knowledge cannot be achieved with “standard” expected-QPT simulators <cit.>.
We leave as an open problem to investigate whether this impossibility generalizes to quantum protocols.
It is plausible that further ideas could even yield a constant-round transform for statistical zero knowledge arguments.

§.§ Simpler construction of commitments from undecodable black holes

Finally, we give a more intuitive one-page proof of a theorem from <cit.>.
The work by Brakerski <cit.> showed that the existence of EFI/commitments is equivalent to the existential hardness of black-hole radiation decoding, as formulated by Hayden and Harlow <cit.>.

Black hole radiation decoding. First, we recall the setting.
A radiation state is an efficiently preparable quantum state $\ket\psi_{\reg{HBR}}$.
We are promised that is that it is statistically possible to extract a qubit from $\reg R$ that is maximally entangled with $\reg B$, but computationally hard to do so with success probability non-negligibly greater than some threshold $\delta \ll 1$.
Note that $\delta \ge \frac14$ always since that is the trivial success probability that can always be achieved by outputting a constant 0 qubit.

Commitments from undecodable states, simplified.
<cit.> constructs an undecodable radiation state from a commitment in a straightforward way: consider the overall pure state where we simply use a statistically-binding quantum state commitment (like the folk-lore construction <cit.>) to commit to a half of an EPR pair; we assign the other half of EPR being the qubit $\reg B$, the commitment register being the prior radiation $\reg R$, and the reveal register being the rest of the black hole $\reg H$.
However, the construction of EFI from undecodable states is much more involved.
Their construction on a high level is constructing a canonical-form commitment that is weakly statistically binding but strongly computationally hiding.
In order to argue computational hiding, they have to develop additional tools like superdense decoding.

We give, from undecodable radiation states, an alternative construction of commitments that is instead weakly computationally binding but strongly statistically hiding with a tighter analysis (since our parallel repetition theorem is tight); furthermore, it can be viewed as the dual construction for the converse direction.  The construction of the bit commitment is as follows:

* Prepare the radiation state along with the EPR pair $\ket\psi_{\reg{HBR}} \otimes \ket{\Psi^+}_{\reg{CD}}$.

* To commit to 0, send registers $\reg{HB}$.

* To commit to 1, send registers $\reg{HD}$.

This is statistically hiding, since by statistical decodability and monogamy of entanglement, after tracing out $\reg R$, the state on $\reg{HB}$ is close to a product state where $\reg B$ is maximally mixed.
On the other hand, the task of breaking honest computational binding (from 0 to 1) is exactly on input register $\reg R$ and an (unrelated) EPR pair $\reg{CD}$, output a state such that the overall state looks like $\reg{HD} \otimes \reg{RCB}$.
In particular, the output $\reg C$ register would be correctly entangled with the test qubit, and thus we conclude that this is computationally $\delta$-binding.
Combining this with the computational amplification (given that $\delta$ is inverse-polynomially bounded away from 1), we obtain a construction of EFI via parallel repetition and commitment flavor switching.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractWe investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction is quantitatively more efficient than the known classical version. If the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n/$\epsilon$2) in the classical case but only by a factor of O(1/$\epsilon$) in the quantum case, where 1/2 +$\epsilon$ is the probability of predicting the hard-predicate. We also show that, using the Goldreich- Levin Theorem, a quantum bit (or qubit) commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation.
booktitleSTACS 2002
titleA Quantum Goldreich-Levin Theorem with Cryptographic Applications

Theory of Computing

journaltitleTheory of Computing
titleQuantum Money from Hidden Subspaces

Seattle, WA, USA

Association for Computing Machinery

abstractWe give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
booktitleProceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing
seriesSTOC '06
titleA New Quantum Lower Bound Method,: With Applications to Direct Product Theorems and Time-Space Tradeoffs
lower bounds,direct product theorems,quantum computing,time-space tradeoffs

Springer Nature Switzerland

abstractIs it possible to convert classical reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions do carry over. However, when considering quantum auxiliary input, this conversion results in a non-constructive post-quantum reduction that requires duplicating the quantum auxiliary input, which is in general inefficient or even impossible. This violates the win-win premise of provable cryptography: an attack against a cryptographic primitive should lead to an algorithmic advantage.
booktitleAdvances in Cryptology – CRYPTO 2022
titleConstructive Post-Quantum Reductions

Dagstuhl, Germany

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

annotationKeywords: quantum cryptography, efi, commitment scheme, oblivious transfer, zero knowledge, secure multiparty computation
booktitle14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleOn the Computational Hardness Needed for Quantum Cryptography

titleUnitary Complexity and the Uhlmann Transformation Problem

journaltitleSIAM Journal on Computing
titleQMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge

Springer International Publishing

abstractHardness amplification is a central problem in the study of interactive protocols. While “natural” parallel repetition transformation is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols (Bellare, Impagliazzo, and Naor [FOCS '97]) and public-coin protocols (Håstad, Pass, Wikström, and Pietrzak [TCC '10], Chung and Liu [TCC '10] and Chung and Pass [TCC '15]), it fails to do so in the general case (the above Bellare et al.; also Pietrzak and Wikström [TCC '07]).
booktitleAdvances in Cryptology – CRYPTO 2020
titleA Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence

booktitleProceedings 38th Annual Symposium on Foundations of Computer Science
titleDoes parallel repetition lower the error in computationally sound protocols?

Springer International Publishing

abstractWe introduce a new notion of one-message zero-knowledge (1ZK) arguments that satisfy a weak soundness guarantee—the number of false statements that a polynomial-time non-uniform adversary can convince the verifier to accept is not much larger than the size of its non-uniform advice. The zero-knowledge guarantee is given by a simulator that runs in (mildly) super-polynomial time. We construct such 1ZK arguments based on the notion of multi-collision-resistant keyless hash functions, recently introduced by Bitansky, Kalai, and Paneth (STOC 2018). Relying on the constructed 1ZK arguments, subexponentially-secure time-lock puzzles, and other standard assumptions, we construct one-message fully-concurrent non-malleable commitments. This is the first construction that is based on assumptions that do not already incorporate non-malleability, as well as the first based on (subexponentially) falsifiable assumptions.
booktitleTheory of Cryptography
titleOne-Message Zero Knowledge and Non-malleable Commitments

Springer Nature Switzerland

abstractWe propose to study equivalence relations between phenomena in high-energy physics and the existence of standard cryptographic primitives, and show the first example where such an equivalence holds. A small number of prior works showed that high-energy phenomena can be explained by cryptographic hardness. Examples include using the existence of one-way functions to explain the hardness of decoding black-hole Hawking radiation (Harlow and Hayden 2013, Aaronson 2016), and using pseudorandom quantum states to explain the hardness of computing AdS/CFT dictionary (Bouland, Fefferman and Vazirani, 2020).
booktitleAdvances in Cryptology – CRYPTO 2023
titleBlack-Hole Radiation Decoding Is Quantum Cryptography

booktitle2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
titleOn the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round

Springer International Publishing

abstractIn a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for $$\mathbf {NP}$$NPsecure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation.
booktitleAdvances in Cryptology – CRYPTO 2021
titleA Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds

Cambridge, MA

abstractIs it harder to solve many puzzles than it is to solve just one? This question has different answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by Yao that solving many independent instances simultaneously is indeed harder than solving a single instance (cf. the transformation from weak to strong one-way functions). The known proofs of that result, however, use in an essential way the fact that for one-way functions, verifying candidate solutions to a given puzzle is easy. We extend this result to the case where solutions are efficiently verifiable only by the party that generated the puzzle. We call such puzzles weakly verifiable. That is, for weakly verifiable puzzles we show that if no efficient algorithm can solve a single puzzle with probability more than ε, then no efficient algorithm can solve n independent puzzles simultaneously with probability more than εn. We also demonstrate that when the puzzles are not even weakly verifiable, solving many puzzles may be no harder than solving a single one.Hardness amplification of weakly verifiable puzzles turns out to be closely related to the reduction of soundness error under parallel repetition in computationally sound arguments. Indeed, the proof of Bellare, Impagliazzo and Naor that parallel repetition reduces soundness error in three-round argument systems implies a result similar to our first result, albeit with considerably worse parameters. Also, our second result is an adaptation of their proof that parallel repetition of four-round systems may not reduce the soundness error.
booktitleProceedings of the Second International Conference on Theory of Cryptography
titleHardness Amplification of Weakly Verifiable Puzzles

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractWe study efficient parallel repetition theorems for several classes of interactive arguments and obtain the following results:
booktitleTheory of Cryptography
titleParallel Repetition Theorems for Interactive Arguments

Los Alamitos, CA, USA

IEEE Computer Society

booktitle2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
titlePost-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

noteAccessed: 2023-09-15
titleEquivalents of Yao's Xor lemma to rounds, or other hardness amplification methods?

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractWe present a new and conceptually simpler proof of a tight parallel-repetition theorem for public-coin arguments [Pass-Venkitasubramaniam, STOC'07], [Håstad et al, TCC'10], [Chung-Liu, TCC'10]. We follow the same proof framework as the previous non-tight parallel-repetition theorem of Håstad et al—which relied on statistical distance to measure the distance between experiments—and show that it can be made tight (and further simplified) if instead relying on KL-divergence as the distance between the experiments.
booktitleTheory of Cryptography
titleTight Parallel Repetition Theorems for Public-Coin Arguments Using KL-Divergence

titleParallel Repetition of Free Entangled Games: Simplification and Improvements

New Orleans, Louisiana, USA

Association for Computing Machinery

booktitleProceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing
seriesSTOC '91
titleNon-Malleable Cryptography

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractIf we have a problem that is mildly hard, can we create a problem that is significantly harder? A natural approach to hardness amplification is the “direct product”; instead of asking an attacker to solve a single instance of a problem, we ask the attacker to solve several independently generated ones. Interestingly, proving that the direct product amplifies hardness is often highly non-trivial, and in some cases may be false. For example, it is known that the direct product (i.e. “parallel repetition”) of general interactive games may not amplify hardness at all. On the other hand, positive results show that the direct product does amplify hardness for many basic primitives such as one-way functions, weakly-verifiable puzzles, and signatures.
booktitleTheory of Cryptography
titleCounterexamples to Hardness Amplification beyond Negligible

Springer International Publishing

abstractWe revisit the problem of whether the known classic constant-round public-coin argument/proof systems are witness hiding for languages/distributions with unique witnesses. Though strong black-box impossibility results are known, we provide some less unexpected positive results on the witness hiding security of these classic protocols:We give sufficient conditions on a hard distribution over unique witness NP relation for which all witness indistinguishable protocols (including all public-coin ones, such as ZAPs, Blum protocol and GMW protocol) are indeed witness hiding. We also show a wide range of cryptographic problems with unique witnesses satisfy these conditions, and thus admit constant-round public-coin witness hiding proof system.For the classic Schnorr protocol (for which the distribution of statements being proven seems not to satisfy the above sufficient conditions), we develop an embedding technique and extend the result of Bellare and Palacio to base the witness hiding property of the Schnorr protocol in the standalone setting on a relaxed version of one-more like discrete logarithm (DL) assumption, which essentially assumes there does not exist instance compression scheme for the DL problem, and show that breaking this assumption would lead to some surprising consequences, such as zero knowledge protocols for the AND-DL language with extremely efficient communication and highly non-trivial hash combiner for hash functions based on the DL problem. Similar results hold for the Guillou-Quisquater protocol.
booktitlePublic-Key Cryptography – PKC 2018
titleOn the Security of Classic Protocols for Unique Witness Relations

Orlando, FL, USA

Association for Computing Machinery

abstractWhat does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions. Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.
booktitleProceedings of the 55th Annual ACM Symposium on Theory of Computing
seriesSTOC 2023
titleCommitments to Quantum States
quantum state commitments,quantum succinct arguments,quantum zero knowledge,quantum cryptography,quantum rewinding

Springer International Publishing

abstractThere has been recent exciting progress on building non-interactive non-malleable commitments from judicious assumptions. All proposed approaches proceed in two steps. First, obtain simple “base” commitment schemes for very small tag/identity spaces based on a various sub-exponential hardness assumptions. Next, assuming sub-exponential non-interactive witness indistinguishable proofs (NIWIs), and variants of keyless collision resistant hash functions, construct non-interactive compilers that convert tag-based non-malleable commitments for a small tag space into tag-based non-malleable commitments for a larger tag space.
booktitleAdvances in Cryptology – EUROCRYPT 2021
titleBlack-Box Non-interactive Non-malleable Commitments

Seattle, Washington, USA

Association for Computing Machinery

abstractA central tool in constructing pseudorandom generators, secure encryption functions, and in other areas are “hard-core” predicates b of functions (permutations) undefined, discovered in [Blum Micali 82]. Such b(x) cannot be efficiently guessed (substantially better than 50-50) given only undefined(x). Both b, undefined are computable in polynomial time.[Yao 82] transforms any one-way function undefined into a more complicated one, undefined*, which has a hard-core predicate. The construction applies the original undefined to many small pieces of the input to undefined* just to get one “hard-core” bit. The security of this bit may be smaller than any constant positive power of the security of undefined. In fact, for inputs (to undefined*) of practical size, the pieces effected by undefined are so small that undefined can be inverted (and the “hard-core” bit computed) by exhaustive search.In this paper we show that every one-way function, padded to the form undefined(p, x) = (p, g(x)), ‖‖p‖‖ = ‖x‖, has by itself a hard-core predicate of the same (within a polynomial) security. Namely, we prove a conjecture of [Levin 87, sec. 5.6.2] that the scalar product of Boolean vectors p, x is a hard-core of every one-way function undefined(p, x) = (p, g(x)). The result extends to multiple (up to the logarithm of security) such bits and to any distribution on the x's for which undefined is hard to invert.
booktitleProceedings of the Twenty-First Annual ACM Symposium on Theory of Computing
seriesSTOC '89
titleA Hard-Core Predicate for All One-Way Functions

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractA fundamental lemma of Yao states that computational weak-unpredictability of Boolean predicates is amplified when the results of several independent instances are XOR together. We survey two known proofs of Yao's Lemma and present a third alternative proof. The third proof proceeds by first proving that a function constructed by concatenating the values of the original function on several independent instances is much more unpredictable, with respect to specified complexity bounds, than the original function. This statement turns out to be easier to prove than the XOR-Lemma. Using a result of Goldreich and Levin (1989) and some elementary observation, we derive the XOR-Lemma.
booktitleStudies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
titleOn Yao's XOR-Lemma

Phoenix, AZ, USA

Association for Computing Machinery

abstractAn n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.
booktitleProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
seriesSTOC 2019
titleQuantum Singular Value Transformation and beyond: Exponential Improvements for Quantum Matrix Arithmetics
quantum signal processing,block-encdoing,qubitization

booktitle2009 50th Annual IEEE Symposium on Foundations of Computer Science
titleA Parallel Repetition Theorem for Any Interactive Argument

abstractIn this paper we discuss quantum computational restrictions on the types of thought experiments recently used by Almheiri, Marolf, Polchinski, and Sully to argue against the smoothness of black hole horizons. We argue that the quantum computations required to do these experiments would take a time which is exponential in the entropy of the black hole under study, and we show that for a wide variety of black holes this prevents the experiments from being done. We interpret our results as motivating a broader type of nonlocality than is usually considered in the context of black hole thought experiments, and claim that once this type of nonlocality is allowed there may be no need for firewalls. Our results do not threaten the unitarity of black hole evaporation or the ability of advanced civilizations to test it.
journaltitleJournal of High Energy Physics
titleQuantum computation vs. firewalls

Virtual, Italy

Association for Computing Machinery

abstractIn a seminal work, Goldreich, Micali and Wigderson (CRYPTO ’86) demonstrated the wide applicability of zero-knowledge proofs by constructing such a proof system for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question in the negative, assuming a standard cryptographic assumption (i.e., the hardness of learning with errors (LWE)). Leveraging a connection observed by Dwork, Naor, Reingold, and Stockmeyer   nbsp;(FOCS ’99), our negative result is obtained by making positive progress on a related fundamental problem in cryptography: securely instantiating the Fiat-Shamir heuristic for eliminating interaction in public-coin interactive protocols. A recent line of work has shown how to instantiate the heuristic securely, albeit only for a limited class of protocols. Our main result shows how to instantiate Fiat-Shamir for parallel repetitions of much more general interactive proofs. In particular, we construct hash functions that, assuming LWE, securely realize the Fiat-Shamir transform for the following rich classes of protocols: 1) The parallel repetition of any “commit-and-open” protocol (such as the GMW protocol mentioned above), when a specific (natural) commitment scheme is used. Commit-and-open protocols are a ubiquitous paradigm for constructing general purpose public-coin zero knowledge proofs. 2) The parallel repetition of any base protocol that (1) satisfies a stronger notion of soundness called round-by-round soundness, and (2) has an efficient procedure, using a suitable trapdoor, for recognizing “bad verifier randomness” that would allow the prover to cheat. Our results are obtained by establishing a new connection between the Fiat-Shamir transform and list-recoverable codes. In contrast to the usual focus in coding theory, we focus on a parameter regime in which the input lists are extremely large, but the rate can be small. We give a (probabilistic) construction based on Parvaresh-Vardy codes (FOCS ’05) that suffices for our applications.
booktitleProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
seriesSTOC 2021
titleFiat–Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is Not Zero-Knowledge)
list-recoverable codes,zero-knowledge protocols,Fiat-Shamir heuristic,cryptographic protocols

Springer Nature Switzerland

abstractRecently, Aaronson et al. (arXiv:2009.07450) showed that detecting interference between two orthogonal states is as hard as swapping these states. While their original motivation was from quantum gravity, we show its applications in quantum cryptography.
booktitleAdvances in Cryptology – EUROCRYPT 2023
titleFrom the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractWe present a general parallel-repetition theorem with an efficient reduction. As a corollary of this theorem we establish that parallel repetition reduces the soundness error at an exponential rate in any public-coin argument, and more generally, any argument where the verifier's messages, but not necessarily its decision to accept or reject, can be efficiently simulated with noticeable probability.
booktitleTheory of Cryptography
titleAn Efficient Parallel Repetition Theorem

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractWe give new proofs for the hardness amplification of efficiently samplable predicates and of weakly verifiable puzzles which generalize to new settings. More concretely, in the first part of the paper, we give a new proof of Yao's XOR-Lemma that additionally applies to related theorems in the cryptographic setting. Our proof seems simpler than previous ones, yet immediately generalizes to statements similar in spirit such as the extraction lemma used to obtain pseudo-random generators from one-way functions [Håstad, Impagliazzo, Levin, Luby, SIAM J. on Comp. 1999].
booktitleTheory of Cryptography
titleGeneral Hardness Amplification of Predicates and Puzzles

Société mathématique de France

journaltitleBulletin de la Société Mathématique de France
titleEssai sur la géométrie à $n$ dimensions
-dimensional geometry; lines; planes and hyperplanes

journaltitlecomputational complexity
titleUsing Entanglement in Quantum Multi-Prover Interactive Proofs

Berlin, Heidelberg

Springer Berlin Heidelberg

abstractThis paper studies general properties of quantum zero- knowledge proof systems. Among others, the following properties are proved on quantum computational zero-knowledge proofs:
booktitleTheory of Cryptography
titleGeneral Properties of Quantum Zero-Knowledge Proofs

booktitle2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
titleHow to Achieve Non-Malleability in One or Two Rounds

Portland, Oregon, USA

Association for Computing Machinery

booktitleProceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing
seriesSTOC '00
titleParallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems

abstractPseudorandom generators transform in polynomial time a short random “seed” into a long “pseudorandom” string. This string cannot be random in the classical sense of [6], but testing that requires an unrealistic amount of time (say, exhaustive search for the seed). Such pseudorandom generators were first discovered in [2] assuming that the function (axmodb) is one-way, i.e., easy to compute, but hard to invert on a noticeable fraction of instances. In [12] this assumption was generalized to the existence of any one-way permutation. The permutation requirement is sufficient but still very strong. It is unlikely to be proven necessary, unless something crucial, like P=NP, is discovered. Below, among other observations, a weaker assumption about one-way functions is proposed, which is not only sufficient, but also necessary for the existence of pseudorandom generators.
titleOne way functions and pseudorandom generators

booktitle2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
titlePost-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably

journaltitleSIAM Journal on Computing
titleTwo-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles

titleA New Approach to Post-Quantum Non-Malleability

abstractWe show that quantum query complexity satisfies a strong direct product theorem. This means that computing k copies of a function with fewer than k times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in k. For a boolean function f, we also show an XOR lemma—computing the parity of k copies of f with fewer than k times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.
journaltitlecomputational complexity
titleA strong direct product theorem for quantum query complexity

abstractThis paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that$${\text{QMA}} \subseteq {\text{PP}}.$$Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.
journaltitlecomputational complexity
titleQuantum Arthur–Merlin games

titleOne-Wayness in Quantum Cryptography

New York, NY, USA

Association for Computing Machinery

abstractWe show a parallel-repetition theorem for constant-round Arthur-Merlin Proofs, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coin proofs of knowledge. The first of these results resolves an open question posed by Bellare, Impagliazzo, and Naor (FOCS’97).
journaltitleACM Transactions on Computation Theory (TOCT)
titleA Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs
public-coin protocols,parallel-repetition,Interactive proofs,soundness error

abstractWe prove a negative result concerning error reduction by parallel repetition for computationally sound protocols, e.g., interactive arguments. Our main result is a complete and computationally sound eight round interactive argument for which k-fold parallel repetition does not reduce the error below a constant for any polynomial k.
journaltitleJournal of Cryptology
titleParallel Repetition of Computationally Sound Protocols Revisited

Zurich, Switzerland

Association for Computing Machinery

abstractPrivate quantum money allows a bank to mint quantum money states that it can later verify, but that no one else can forge. In classically verifiable quantum money – introduced by Gavinsky (CCC 2012) – the verification is done via an interactive protocol between the bank and the user, where the communication is classical, and the computational resources required of the bank are classical. In this work, we consider memoryless interactive protocols in which the minting is likewise classical, and construct a private money scheme that achieves these two notions simultaneously (i.e., classical verification and classical minting). We call such a construction a private semi-quantum money scheme, since all the requirements from the bank in terms of computation and communication are classical.In terms of techniques, our main contribution is a strong parallel repetition theorem for Noisy Trapdoor Claw Free Functions (NTCF), a notion introduced by Brakerski et al. (FOCS 2018).
booktitleProceedings of the 1st ACM Conference on Advances in Financial Technologies
seriesAFT '19
titleSemi-Quantum Money
Trapdoor Claw Free Functions,Quantum Money,Quantum cryptography,Semi-Quantum Money

San Jose, California, USA

Association for Computing Machinery

abstractA strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability 2-Ω(n). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.
booktitleProceedings of the Forty-Third Annual ACM Symposium on Theory of Computing
seriesSTOC '11
titleStrong Direct Product Theorems for Quantum Communication and Query Complexity
quantum query complexity,strong direct product theorems,XOR lemmas,quantum communication complexity

Victoria, British Columbia, Canada

Association for Computing Machinery

abstractHardness amplification is the fundamental task of converting a δ-hard function f : (0, 1)n -   gt; (0, 1) into a (1/2-ε)-hard function Amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. Typically, ε,δ are small (and δ=2-k captures the case where f is worst-case hard). Achieving ε = 1/nΩ(1) is a prerequisite for cryptography and most pseudorandom-generator constructions.In this paper we study the complexity of black-box proofs of hardness amplification. A class of circuits cal D proves a hardness amplification result if for any function h that agrees with Amp(f) on a 1/2+e fraction of the inputs there exists an oracle circuit D ∈ D such that Dh agrees with f on a 1-δ fraction of the inputs. We focus on the case where every D ∈ D makes non-adaptive queries to h. This setting captures most hardness amplification techniques. We prove two main results: The circuits in D "can be used" to compute the majority function on 1e bits. In particular, these circuits have large depth when ε ≤ 1/ poly log n. The circuits in D must make Ω log(1/δ)/e2 oracle queries.Both our bounds on the depth and on the number of queries are tight up to constant factors. Our results explain why hardness amplification techniques have failed to transform known lower bounds against constant-depth circuit classes into strong average-case lower bounds. When coupled with the celebrated "Natural Proofs" result by Razborov and Rudich (J. CSS '97) and the pseudorandom functions by Naor and Reingold (J. ACM '04), our results show that standard techniques for hardness amplification can only be applied to those circuit classes for which standard techniques cannot prove circuit lower bounds. Our results reveal a contrast between Yao's XOR Lemma (Amp(f) := f(x1) ⊕ ... ⊕ f(xt) ∈ zo) and the Direct-Product Lemma (Amp(f) := f(x1) O ... O f(xt) ∈ zot; here Amp(f) is non-Boolean). Our results (1) and (2) apply to Yao's XOR lemma, whereas known proofs of the direct-product lemma violate both (1) and (2). One of our contributions is a new technique to handle "non-uniform" reductions, i.e. the case when D contains many circuits.
booktitleProceedings of the Fortieth Annual ACM Symposium on Theory of Computing
seriesSTOC '08
titleHardness Amplification Proofs Require Majority
natural proofs,average-case complexity,amplification,constant-depth circuits,black-box,majority,hardness

Now Publishers, Inc.

journaltitleFoundations and Trends® in Theoretical Computer Science
titleQuantum proofs

booktitleThe 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
titleLimits on the power of quantum statistical zero-knowledge

Seattle, WA, USA

Association for Computing Machinery

abstractThis paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich-Micali-Wigderson classical zero-knowledge protocols for Graph Isomorphism and Graph 3-Coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive protocol for a complete problem for the complexity class of problems having "honest verifier" quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: QSZK = QSZKHV. Previously no non-trivial proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest-verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.
booktitleProceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing
seriesSTOC '06
titleZero-Knowledge against Quantum Attacks
zero-knowledge proof systems,quantum cryptography

Cambridge University Press

titleQuantum Information Theory

journaltitleIEEE Transactions on Information Theory
titleCoding theorem and strong converse for quantum channels

Springer Nature Switzerland

booktitleAdvances in Cryptology – ASIACRYPT 2022
titleGeneral Properties of Quantum Bit Commitments (Extended Abstract)

titleGeneral Non-interactive Quantum Commitments Are Compatible with Quantum Rewinding

abstractThe purpose of this paper is to introduce a new information theory and explore its appplications. Using modern computational complexity, we study the notion of information that can be accessed through a feasible computation. In Part 1 of this paper, we lay the foundation of the theory and set up a framework for cryptography and pseudorandom number generation. In Part 2, we study the concept of trapdoor functions and examine applications of such functions in cryptography, pseudorandom number generation, and abstract complexity theory.
booktitle23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
titleTheory and application of trapdoor functions

Springer International Publishing

abstractWe explore the problem of traitor tracing where the pirate decoder can contain a quantum state. Our main results include:We show how to overcome numerous definitional challenges to give a meaningful notion of tracing for quantum decodersWe give negative results, demonstrating barriers to adapting classical tracing algorithms to the quantum decoder setting.On the other hand, we show how to trace quantum decoders in the setting of (public key) private linear broadcast encryption, capturing a common approach to traitor tracing.
booktitleTheory of Cryptography
titleSchrödinger's Pirate: How to Trace a Quantum Decoder

abstractPublic key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, we investigate quantum lightning, a formalization of “collision-free quantum money” defined by Lutomirski et al. [ICS'10], where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results:We demonstrate the usefulness of quantum lightning beyond quantum money by showing several potential applications, such as generating random strings with a proof of entropy, to completely decentralized cryptocurrency without a blockchain where transactions are instantaneous and local.We give win–win results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quantum money or lightning. Given the difficulty in constructing public key quantum money, this suggests that natural schemes do attain strong security guarantees.We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC'12] with indistinguishability obfuscation that is secure against quantum computers yields a secure quantum money scheme. This construction can be seen as an instance of our win–win result for signatures, giving the first separation between two security notions for signatures from the literature.Finally, we give a plausible construction for quantum lightning, which we prove secure under an assumption related to the multicollision resistance of degree-2 hash functions. Our construction is inspired by our win–win result for hash functions and yields the first plausible standard model instantiation of a non-collapsing collision-resistant hash function. This improves a result of Unruh [Eurocrypt'16] which is relative to a quantum oracle.Thus, we provide the first constructions of public key quantum money from several cryptographic assumptions. Along the way, we develop several new techniques including a new precise variant of the no-cloning theorem.
journaltitleJournal of Cryptology
titleQuantum Lightning Never Strikes the Same State Twice. Or: Quantum Money from Cryptographic Assumptions