First, since $\Pi$ $\CSQSA{S}$-realizes $\Fpm{M,f_0}$, by defining $\Sim(\omega) \eqdef \tilde{\P}(\omega) \interactsF{\Fpm{M,f_0}} \tilde{\V}$, we have in particular $(\P \interacts \V) \approxRVC \Sim$ and $\Sim$ runs in poly-time since $M$ is efficiently implementable. Let $\omega$ such that $\lang_\omega \neq \emptyset$. Because $\lang_\omega \neq \emptyset$, $\tilde{\P}(\omega)$ produces, by definition, a state $\rho_0^{\V_0,\P}$ in $E_\omega$, and since $\tilde{\V}$ sends $f = \top$, $\tilde{\P}$ outputs $\omega_s = f_0(m)$, where $m$ is the measurement outcome of the ideal functionality. Also, by definition of $\Fpm{M,f_0}$, the post-measured state is $\rho^{\P,\V} = \xi_m(\rho_0^{\V_0,\P})$. Therefore, by definition of $\lang_{\omega, \omega_s}$, the output state $\rho^{\P,\V}$ belongs to $\lang_{\omega, \omega_s}$ with probability $1$, and $\tilde{\V}$ always outputs $a=1$. Therefore, <ref> is true, completing the proof of completeness.

We proceed now with the soundness:

Let $\hat{\P} = \{\hat{\P}_\lambda\}_{\lambda \in \N}$ be a malicious prover (unbounded if $\P \in S$, in which case all symbols $\approxRVC$ should be replaced with $\approxRVS$ in the rest of this proof). Because $\Pi$ $\CSQSA{S}$-realizes $\Fpm{M,f_0}$, there exists $\Sim'_{\hat{\P}}$ such that $(\hat{\P} \interacts \V) \approxRVC \Sim'_{\hat{\P}} \interactsF{\Fpm{M,f_0}} \tilde{\V}$. So let us define $\Sim_{\hat{\P}}(\sigma^\P_\lambda) = (\Sim'_{\hat{\P}}(\sigma^\P_\lambda) \interactsF{\Fpm{M,f_0}} \tilde{\V})$: we then have $(\hat{\P} \interacts \V) \approxRVC \Sim_{\hat{\P}}$. Moreover, since $\lang_\cQ$ corresponds to all the bipartite states that can be obtained when applying $\xi_m$ for some $m$ on the first register, and an arbitrary deviation depending on $f_0(m)$ on the other register (remember that $\Fpm{M,f_0}$ gives back $f_0(m)$ to the adversary, so $\hat{\xi}_{f_0(m)}$ would be defined as the second part of $\Sim{\hat{\P}}$, after waiting for the answer of the functionality), <ref> is true (even with probability $1$), completing the proof.

We finish now with the quantum ZK property:

Let $\hat{\V} = \{\hat{\V}_\lambda\}_{\lambda \in \N}$ be a malicious verifier (unbounded if $\V \in S$, in which case all symbols $\approxRVC$ should be replaced with $\approxRVS$ in the rest of this proof). Because $\Pi$ $\CSQSA{S}$-realizes $\Fpm{M,f_0}$, there exists $\Sim'_{\hat{\V}}$ such that $(\P \interacts \hat{\V}) \approxRVC (\tilde{\P} \interactsF{\Fpm{M,f_0}} \Sim'_{\hat{\V}})$. Then, we define $\Sim_{\hat{\V}}(b)$ as follows. First, if $b = \bot$, it forwards the input of the environment to $\Sim'_{\hat{\V}}$ together with $\bot$ (pretending to be the functionality $\Fpm{M,f_0}$). Since $\tilde{\P}(\omega)$ aborts iff $\lang_\omega = \emptyset$, we actually have for any $\omega$ such that $\lang_\omega = \emptyset$, $\tilde{\P}(\omega) \interactsF{\Fpm{M,f_0}} \Sim'_{\hat{\V}} = (\xi_\omega \otimes I)(\Sim_{\hat{\V}}(\lang_\omega \neq \emptyset)$ where $\xi_\omega$ is given $b$ as input and outputs $\bot$ if $b = \bot$: by transitivity, <ref> is true in that case. Otherwise, if $b = \top$, since $M$ are postponable measurement operators with respect to $G$, there exists by definition $\rho^{\V,F}$ and a quantum map $M'$ such that $M G \approxRVS (I^\V \otimes M')(\rho^{\V,F} \otimes G)$. Therefore, $\tilde{\P} \interactsF{\Fpm{M,f_0}} \Sim'_{\hat{\V}}$ is equivalent to:

* Generate $\rho^{\V,F}$ and send $\rho^\V$ to $\Sim'_{\hat{\V}}$ (pretending to be $\Fpm{M,f_0}$) to get a function $f$ and an output state $\rho'$.

* Run $M'(\rho^F \otimes G(\omega))$ to get outcome $m'$, send back $f_\omega(m')$ to $\tilde{\P}(\omega)$ and outputs the final state of $\tilde{\P}(\omega)$.

However, if we define $\Sim_{\hat{\V}}$ to do the first step, and $\xi_\omega$ to be the second and third step (when $b = 1$), we have $(\tilde{\P} \interactsF{\Fpm{M,f_0}} \Sim'_{\hat{\V}}) = (\xi_\omega \otimes I)\Sim_{\hat{\V}}$, therefore <ref> is respected, concluding the proof.

While the above results show that we can obtain a ZKoQS protocol from any protocol realizing the functionality $\Fpm{M,f_0}$ (where $M$ must be postponable), we show in the next section how we can realize such a functionality to prove that a state was partially collapsed (measured in the computational basis) without revealing the position of the collapsed qubit. We will then see that, as a corollary, there exists a ZKoQS protocol for the quantum language of “semi-collapsed” states.

§.§ Protocol to prove that a state has been semi-collapsed

We prove now that we can realize the functionality below, that informally measures a set $T$ of qubits (the measured qubits, chosen by the prover, being constraint to respect $\Pred(T) = \top$, for an arbitrary predicate $\Pred$), randomly rotates the other one, and provides the resulting state to the verifier.

Let $n \in \N$, and $\Pred \colon \cP([n]) \rightarrow \{\top,\bot\}$ be an efficiently computable predicate on the subsets of $[n]$. We define the semi-collapsing functionality $\Fsemicol{\Pred}$ as $\Fpm{M,f_0}$ (<ref>), where:

* $M$ is the measurement operator that receives a quantum state on two registers, measures the first register[Informally this register contains the subset of qubits in the second register to measure. Since the first operation of $M$ is to measure them, we can (and will) also consider them as classical inputs.] in the computational basis to get (an encoding of) $T \subseteq [n]$, checks if $\Pred(T) = \top$: if not it outputs $m = \bot$ and a dummy quantum state $\ket{\bot}$. Otherwise, it measures (non-destructively) in the computational basis all qubits in the second register whose index belongs to the set of “target” qubits $T$, getting outcomes $\{m^{(j)}\}_{j \in T}$, and for any $i \in [n] \setminus T$, it samples a random bit $r^{(i)} \sample \{0,1\}$, and applies $Z^{r^{(i)}}$ on the $i$-th qubit. Finally it outputs $m = (T, (m^{(j)})_{j \in T}, (r^{(i)})_{i \in [n] \setminus T})$ and the post-measured state.

* If $m = \bot$, $f_0(m) = \bot$, otherwise if $m = (T, (m^{(j)})_{j \in T}, (r^{(i)})_{i \in [n] \setminus T})$, $f_0(m) = (r^{(i)})_{i \in [n] \setminus T})$.

We also consider the following dummy ideal parties:

* $\tilde{P}(T, \rho)$ sends $a = \Pred(T)$ and $\rho$ to the ideal functionality $\Fsemicol{\Pred}$, and it forwards the received message from the functionality.

* $\tilde{V}$ checks if it receives $a = \bot$ from the functionality, or if the received quantum state is $\ket{\bot}$. If so it sends back $f = \bot$ to the functionality and aborts, and otherwise it sets $f = \top$ for the functionality and outputs the quantum state to the environment.

We prove now that we can realize the functionality $\Fsemicol{\Pred}$:
[Realization of $\Fsemicol{\Pred}$][text link=,end]
Let $\{h_k\}_{k \in \cK}$ be a family of collision resistant functions sampled by $\Gen$, having the hardcore second-bit property (<ref>). Let $\Pi_h = (\P_h, \V_h)$ be a protocol[As a reminder, this protocol is sampling and distributing a function $h$ according to $\Gen$, and can either be done without communication in the CRS model (or heuristically if we replace $h$ with a well known collision-resistant hash function), or with one message in the plain model.] $\CSQSA{S_h}$ realizing $\cFcrs{\Gen}$ and $\Pizk = (\Azk,\Bzk)$ be a protocol that S realizes the ZK functionality $\Fzk{\cR}$, where $(h^{(c)}_d)_{c \in [n], d \in \{0,1\}} \cR (T, (w^{(c)}_d)_{c \in [n], d \in \{0,1\}}) \Leftrightarrow \Pred(T) = \top \land \forall c,d, h(d \| w_d^{(c)}) = h_d^{(c)}$ and $\forall c \in T, \exists c$ such that $w_d^{(c)}[1] = 1$.

Then, the protocol $\Pisemicol$ (<ref>, see also the equivalent picture in <ref><ref>) $\CSQSA{S'}$-realizes $\Fsemicol{\Pred}$ for any $S'$ such that:

* $S' \subseteq S \cap S_h$,

* $\{ \P \} \in S'$ only if $h$ has the statistical hardcore second-bit property,

* $\{ \V \} \in S'$ only if for any $k \in \cK$, $h_k$ is injective (i.e. statistically collision resistant).

Part of the proofs of this theorem are generalizations of <ref>. Some care must be taken to show that the distributions in the honest case (ideal world versus real world) are really indistinguishable, we do so by computing the appropriate density matrices. There is also a slight difference as here we measure the state instead of applying a rotation, but it turns out that measuring is indistinguishable from rotating a state and discarding the rotation angle. We refer to the [proof:prAtEnd]full security proof in  for more details.

Case 1: correctness (no corrupted party).

We prove first correctness when the parties are all honest:

First, if $\Pred(T) = \bot$, the parties abort in both the ideal and real worlds. Otherwise, like in <ref>, the ZK proof in the real world succeeds by the completeness of the ZK protocol, and the first measurement of Bob will not disturb the state, so we can remove indistinguishably the ZK proof and the first measurement of Bob (we should technically define new worlds as we did before, but we omit them for conciseness as we already applied similar arguments earlier). Similarly, since for any $j \in T$, the first register of the state $\rho^{(j)}$ is already measured, the Hadamard basis measurement on its second register does not alter the state, so we can remove indistinguishably all operations involving $\rho^{(j)}$'s except for the measurements in the computational basis by $\P$. Therefore, we can concentrate now on $\rho^{(i)}$ for $i \in [n] \setminus T$, and show that the random rotation $Z^{r^{(i)}}$ followed by the map $x \rightarrow x,w_x^{(i)}$, the Hadamard measurement on the second register, and the update of $r^{(i)}$ is statistically indistinguishable from a single random $Z^{r^{(i)}}$.

Let $i \in [n] \setminus T$. We can show this property in two ways: either by doing the computation directly on density matrices (which is a bit long, but we do it below for completeness), or remark that the map and Hadamard measurement commute with the $Z^{r^{(i)}}$, and that the map and Hadamard measurement performs a $Z^{\langle s^{(b)}, w_0^{(b)} \rangle}$ rotation: therefore we can sample $r^{(i)}$ after knowing the outcome of the measurement, and since the distribution $r^{(i)}$ is indistinguishable from the distribution $c \xor r^{(i)}$ for any constant $c$, we can take $c = \langle s^{(b)}, w_0^{(b)} \rangle$ to cancel the rotation applied earlier by the Hadamard, making it virtually equal to a single rotation $Z^{r^{(i)}}$.

We provide now an alternative proof, more verbose but certainly more formal, by directly computing the appropriate density matrices. If we consider a purification[Technically $\rho^{(i)}$ could be entangled with other $\rho^{(i')}$, so this purification might contain elements in $\rho^{(i')}$. This is not an issue as soon as we apply this transformation sequentially, on a single $i$ at a time.] of $\rho^{(i)}$, there exists two vectors $\ket{\psi_0}$ and $\ket{\psi_1}$ such that $\rho^{(i)} = \alpha_0\ket{0}\ket{\psi_0}+\alpha_1 \ket{1}\ket{\psi_1}$. Moreover, if we consider the density operator of this whole process, we have after the sampling of $a$ (put on the first register) and $Z^a$ rotation:

\begin{align}
\begin{split}
&\frac{1}{2} (\ket{0}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 \ket{1}\ket{\psi_1}))((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* \bra{\psi_1}\bra{1})\bra{0})\\
+ &\frac{1}{2} (\ket{1}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1 \ket{1}\ket{\psi_1}))((\alpha_0^*\bra{\psi_0}\bra{0}-\alpha_1^* \bra{\psi_1}\bra{1})\bra{1})
\end{split}
\end{align}

Then, after the $x \mapsto x, w_x^{(c)}$ operation, and the Hadamard (omitting the normalisation factor), we get:

\begin{align}
\begin{split}
&\sum_{s^{b}}\sum_{s^{\prime (i)}}(\frac{1}{2} (\ket{0}(\alpha_0(-1)^{\langle s^{(i)}, w_0^{(i)} \rangle}\ket{0}\ket{\psi_0}\ket{s^{(i)}}+\alpha_1 (-1)^{\langle s^{(i)}, w_1^{(i)} \rangle}\ket{1}\ket{\psi_1}\ket{s^{(i)}}))\\
&((\alpha_0^*(-1)^{\langle s^{\prime (i)}, w_0^{(i)} \rangle}\bra{s^{\prime (i)}}\bra{\psi_0}\bra{0}+\alpha_1^* (-1)^{\langle s^{\prime (i)}, w_1^{(i)} \rangle}\bra{s^{\prime (i)}}\bra{\psi_1}\bra{1})\bra{0})\\
&+ \frac{1}{2} (\ket{1}(\alpha_0(-1)^{\langle s^{(i)}, w_0^{(i)} \rangle}\ket{0}\ket{\psi_0}\ket{s^{(i)}}-\alpha_1(-1)^{\langle s^{(i)}, w_1^{(i)} \rangle} \ket{1}\ket{\psi_1}\ket{s^{(i)}}))\\
&((\alpha_0^*(-1)^{\langle s^{\prime (i)}, w_0^{(i)} \rangle}\bra{s^{\prime (i)}}\bra{\psi_0}\bra{0}-\alpha_1^*(-1)^{\langle s^{\prime (i)}, w_1^{(i)} \rangle} \bra{s^{\prime (i)}}\bra{\psi_1}\bra{1})\bra{1}))
\end{split}
\end{align}

However, since the output of $\P$ XOR to $b$ the value $\langle s^{(i)}, w_0^{(i)} \xor w_1^{(i)} \rangle$, the final density matrix representing this process is as follows (to obtain this, we factored out the $(-1)^{\langle s^{(i)}, w_0^{(i)} \rangle}$ that gets canceled as a global phase, we rename $\alpha_{s^{(i)}} \eqdef \langle s^{(i)}, w_0^{(i)} \xor w_1^{(i)} \rangle$, and we XOR the first register with $\alpha_{s^{(i)}}$):

\begin{align}
\begin{split}
&\frac{1}{2} \sum_{s^{b}}\sum_{s^{\prime (i)}}((\ket{\alpha_{s^{(i)}}}(\alpha_0\ket{0}\ket{\psi_0}\ket{s^{(i)}}+\alpha_1 (-1)^{\alpha_{s^{(i)}}}\ket{1}\ket{\psi_1}\ket{s^{(i)}}))\\
&((\alpha_0^*\bra{s^{\prime (i)}}\bra{\psi_0}\bra{0}+\alpha_1^* (-1)^{\alpha_{s^{\prime (i)}}}\bra{s^{\prime (i)}}\bra{\psi_1}\bra{1})\bra{\alpha_{s^{(i)}}})\\
&+ (\ket{1 \xor \alpha_{s^{(i)}}}(\alpha_0\ket{0}\ket{\psi_0}\ket{s^{(i)}}-\alpha_1(-1)^{\alpha_{s^{(i)}}} \ket{1}\ket{\psi_1}\ket{s^{(i)}}))\\
&((\alpha_0^*\bra{s^{\prime (i)}}\bra{\psi_0}\bra{0}-\alpha_1^*(-1)^{\alpha_{s^{\prime (i)}}} \bra{s^{\prime (i)}}\bra{\psi_1}\bra{1})\bra{1 \xor \alpha_{s^{(i)}}}))
\end{split}
\end{align}

Moreover, the last register $s^{(i)}$ is discarded, so we can trace is out:

\begin{align}
\begin{split}
&\frac{1}{2} \sum_{s^{b}}((\ket{\alpha_{s^{(i)}}}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 (-1)^{\alpha_{s^{(i)}}}\ket{1}\ket{\psi_1}))\\
&((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* (-1)^{\alpha_{s^{(i)}}}\bra{\psi_1}\bra{1})\bra{\alpha_{s^{(i)}}})\\
&+ (\ket{1 \xor \alpha_{s^{(i)}}}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1(-1)^{\alpha_{s^{(i)}}} \ket{1}\ket{\psi_1}))\\
&((\alpha_0^*\bra{\psi_0}\bra{0}-\alpha_1^*(-1)^{\alpha_{s^{(i)}}} \bra{\psi_1}\bra{1})\bra{1 \xor \alpha_{s^{(i)}}}))
\end{split}
\end{align}

We have now two cases: if $w_0^{(i)} \xor w_1^{(i)} = 0 \dots 0$, then $\alpha_{s^{(i)}} = 0$ and we actually see that the second register is not even entangled with the first one, so the Hadamard measurement does not change the first qubit, therefore we only apply a random $Z^{a}$ on it and output $a$, like in the ideal world. Now, if $w_0^{(i)} \xor w_1^{(i)} \neq 0$, then the the number of $s^{(i)}$ such that $\alpha_{s^{(i)}} = 0$ is exactly equal to the number of cases where $\alpha_{s^{(i)}} = 1$:

To see that, since $w_0^{(i)} \xor w_1^{(i)} \neq 1$, there exists one position where they differ: then, just flipping the bit of $s^{(i)}$ at that position will also flip the value of $\alpha_{s^{(i)}}$, providing a simple way to partition $s^{(i)}$'s in two sets of equal size, each set having the same value of $\alpha_{s^{(i)}}$.

Therefore, we can sum over $\alpha_{s^{(i)}}$ instead of $s^{b}$ (this adds a fixed constant (thanks to the argument we just mentioned) factor that we ignore for simplicity):

\begin{align}
\begin{split}
&\frac{1}{2} \sum_{\alpha_{s^{(i)}} \in \{0,1\}}((\ket{\alpha_{s^{(i)}}}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 (-1)^{\alpha_{s^{(i)}}}\ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* (-1)^{\alpha_{s^{(i)}}}\bra{\psi_1}\bra{1})\bra{\alpha_{s^{(i)}}})\\
&\qquad+ (\ket{1 \xor \alpha_{s^{(i)}}}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1(-1)^{\alpha_{s^{(i)}}} \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}-\alpha_1^*(-1)^{\alpha_{s^{(i)}}} \bra{\psi_1}\bra{1})\bra{1 \xor \alpha_{s^{(i)}}}))
\end{split}
\\
\begin{split}
\frac{1}{2} ((\ket{0}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* \bra{\psi_1}\bra{1})\bra{0})\\
&\qquad+ (\ket{1}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}-\alpha_1^* \bra{\psi_1}\bra{1})\bra{1})\\
&\qquad+ (\ket{1}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad+ (\ket{0}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* \bra{\psi_1}\bra{1})\bra{0})
\end{split}
\\
\begin{split}
\frac{1}{2} ((\ket{0}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* \bra{\psi_1}\bra{1})\bra{0})\\
&\qquad+ (\ket{1}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}-\alpha_1^* \bra{\psi_1}\bra{1})\bra{1})\\
&\qquad+ (\ket{1}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad+ (\ket{0}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* \bra{\psi_1}\bra{1})\bra{0})
\end{split}
\\
\begin{split}
(\ket{0}(\alpha_0\ket{0}\ket{\psi_0}+\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}+\alpha_1^* \bra{\psi_1}\bra{1})\bra{0})\\
&\qquad+ (\ket{1}(\alpha_0\ket{0}\ket{\psi_0}-\alpha_1 \ket{1}\ket{\psi_1}))\\
&\qquad((\alpha_0^*\bra{\psi_0}\bra{0}-\alpha_1^* \bra{\psi_1}\bra{1})\bra{1})
\end{split}
\end{align}

We see (once we renormalize this state) that this is exactly the density matrix of the ideal world that applies a random $Z^a$ operation on the qubit and outputs $a$ in the first register.

Case 2: malicious verifier.
We prove now the equivalence of the ideal and real worlds if the adversary corrupts the verifier.

We consider now the case where the adversary $\cA = \hat{\V}$ corrupts the verifier. The proof of this section is quite close to the second case of the proof of <ref>, so we will be quicker here. First, as before we cut $\hat{\V}$ into multiple parts ($\hat{\V}_0$ running against $\A_h$ to generate $h$, $\hat{\V}_1$ will be the circuit run when receiving $\bot$ (since the interaction will stop there in that case, $\hat{\V}_1$ only outputs a state for the environment), otherwise $\hat{\V}_2$ will be the circuit playing the ZK proof, and $\hat{\V}_3$ receiving the quantum state and outputting a final state and the measurements back to $\A$). Then, similarly to what we did before we define the simulator $\Sim_{\hat{\V}}$ as follows: first, the simulator will simulate the protocol $\Pi_h$ by running $\Sim_{h,\hat{B}_0}$ to get $h$. Then, if the output of the functionality $\Fsemicol{\Pred}$ is $\bot$, it will run $\hat{\V}_1$ and forward the output of $\hat{\V}_1$ to the environment. Otherwise, it samples all $w_c^{(d)}$ starting with a $0$, computes the hashes $\{h^{(c)}_d\}_{c \in [n], d \in \{0,1\}}$, and runs the ZK simulator $\Sim_{zk,\hat{B}_2}((h^{(c)}_d)_{c,d})$. Then, for all $c \in [n]$, it will sample $r^{(c)} \sample \{0,1\}$ and send the states $\rho^{(c)} = \ket{0}\ket{w_0^{(c)}} + (-1)^{r^{(c)}} \ket{1}\ket{w_1^{(c)}}$. After receiving the $\{s^{(c)}\}_{c \in \{0,1\}}$, it defines $f(T,(m^{(j)})_{j \in T},(r^{(i)})_{i \in [n] \setminus T}) \eqdef (r^{(i)} \xor \bigoplus_k s^{(i)}[k] (w^{(i)}_0 \xor w^{(i)}_1)[k])_{i \in [n] \setminus T}$ and sends $f$ to the functionality.

To prove that we have $\P \interacts \hat{\V} \approxRVC \tilde{\P} \interactsF{\Fsemicol{\Pred}} \Sim_{\hat{\V}}$ ($\approxRVC$ are replaced with $\approxRVS$ if $\{\V\} \in S$), we can first study the case where the classical message $T$ sent to the prover is such that $\Pred(T) = \bot$. In that case, by definition of $\P$, $\P$ will abort, and send $\bot$ to $\hat{\V}$, which is also exactly what $\Sim_{\hat{\V}}$ is doing once $\tilde{\P}$ sent the abort bit forwarded by the functionality to the simulator. Now, we focus on $T$ such that $\Pred(T) = \top$, and therefore $\hat{\V}_1$ is never called. We can design as before a series of games, where we also cut $\P$ is a part that runs $\Pi_h$, a part $\P_0$ that checks $\Pred$, a part $\P_1$ that measures the state and samples $w$'s, a part $\P_2$ that runs the ZK proof, and the last part $\P_3$ that runs the rest of the protocol (we refer to <ref> for more details on the steps that are almost identical).

* We start from $\P \interacts \hat{\V}$. Then, we replace $\P_0$ interacting with $\hat{B}_0$ with $\Sim_{h,\hat{B}_0}$ to get $h$. Both worlds are indistinguishable since $\Pi_h$ $\CSQSA{S_h}$ realizes $\cFcrs{\Gen}$.

* Then, since the statement proven is true, we can replace $\P_2$ interacting with $\V_2$ with $\Sim_{zk,\V_2}$ that only takes as input the hashes. This is indistinguishable since $\Pizk$ $\CSQSA{S}$ realizes $\Fzk{}$.

* Then, we can new sample all $w$'s such that they start with a $0$, which is indistinguishable thanks to the hardcore second-bit property (<ref>) of $h$.

* Then, we sample $r^{(i)}$ for all $i \in [n]$, and instead of measuring the qubits for $i \in T$, we rotate them according to $Z^{r^{(i)}}$. This is statistically indistinguishable since neither $l$ nor $r^{(i)}$ are reused anywhere else, and are therefore discarded. But one can easily see that measuring and discarding the outcome is statistically equivalent to applying $Z^{r^{(i)}}$ and discarding $r^{(i)}$. This can easily be seen diagrammatically (using the doubling formalism), or via simple computations:

If we purify a state as $\alpha_0 \ket{0}\ket{\psi_0} + \alpha_1 \ket{1}\ket{\psi_1}$, then applying a random $Z$ phase on the first qubit gives the density matrix:

\begin{align}
\begin{split}
&\frac{1}{2} ((\alpha_0 \ket{0}\ket{\psi_0} + \alpha_1 \ket{1}\ket{\psi_1})(\alpha_0^* \bra{\psi_0}\bra{0} + \alpha_1^* \bra{\psi_1}\bra{1})\\
&+ (\alpha_0 \ket{0}\ket{\psi_0} - \alpha_1 \ket{1}\ket{\psi_1})(\alpha_0^* \bra{\psi_0}\bra{0} - \alpha_1^* \bra{\psi_1}\bra{1}))\\
\end{split}
\\
&= |\alpha_0|^2 \ket{0}\ket{\psi_0}\bra{\psi_0}\bra{0} + |\alpha_1|^2 \ket{1}\ket{\psi_1}\bra{\psi_1}\bra{1}\label{eg:measuringIsRotating}
\end{align}

and this second line corresponds to the density matrix of a (non-destructive) measurement in the computational basis.

* Finally, by reorganizing the elements and using the functionality with the appropriately chosen function $f$ defined above to pick the appropriate $r^{(i)} \xor \langle s^{(i)}, w_0^{(i)} \xor w_1^{(i)} \rangle$ only for $i \in [n] \setminus T$, we obtain the ideal world concluding the proof.

Case 3: malicious prover.
We prove now the equivalence of the ideal and real worlds if the adversary corrupts the prover.

We consider now the case where the adversary $\cA = \hat{\P}$ corrupts the prover. The proof of this section is quite close to the last case of the proof of <ref>, so we will be quicker here. First, we can divide $\hat{\P}$ and $\V$ into multiple parts: $\hat{\P}_0$ will interact with $\V_0$ that will play the protocol $\V_h$ to obtain $h$, then $\hat{\P}_1$ will interact with $\V_1$ to run the ZK protocol, and finally $\hat{\P}_2$ will interact with $\V_2$ for the remaining part of the protocol.

Now, we can, as before, define a series of indistinguishable worlds.

* First, we start from the ideal world, and we replace $\hat{\P}_0$ and $\V_0$ with the simulator $\Sim_{h,\hat{\P}_0}$ interacting with $\Fh{\Gen}$. This is indistinguishable since $\Pi_h$ realises $\Fh{\Gen}$.

* Similarly, we replace $\hat{\P}_1$ and $\V_1$ with the simulator $\Sim_{zk,\hat{\P}_1}$ interacting

* Then, since the simulator has now access to the set $T$, it can measure all the states in $T$ once the quantum test passes. To show that it is indistinguishable, we use the exact same argument as the one made in case 3 of <ref> to show that $\World_2 \approxRV \World_3$. The only differences is that now we measure more states (but we can apply sequentially the same argument for one state at a time, and since the number of states is polynomial the distinguishing probability is still negligible: note that in the current proof the ZK contains more statements, but in particular the statements needed in <ref> are fulfilled). The second difference is that we show that the trace distance between $\rho$ and $Z_1\rho Z_1^\dagger$ is smaller than $2t\sqrt{\beta}$ (<ref>), while here we want to show that the trace distance between $\rho$ and the measured $\rho$ (non-destructively and in the computational basis) denoted $\rho'$ is negligible. However, we showed in <ref> that rotating by a random $Z^a$ (and discarding the $a$) is strictly equivalent to measuring (non-destructively) and discarding the outcome. Therefore:

\begin{align}
\TD(\rho, M\rho)
&= \TD(\rho, \frac{1}{2} \rho + \frac{1}{2} Z_1\rho Z_1^\dagger)\\
&\leq \frac{1}{2}(\TD(\rho, \rho) + \TD( \rho, Z_1\rho Z_1^\dagger)\\
&\leq \frac{1}{2} 2t\sqrt{\beta} \leq 2t\sqrt{\beta}
\end{align}

which allows us to conclude.

* Then, because the state is collapsed before applying the Hadamard basis measurement on its second register, it is still collapsed after applying this measurement: so we can indistinguishably apply a second measurement in the computational basis after.

* We can also, at the very end of the protocol, sample random $(r^{(i)})_{i \in [n] \setminus T}$, and apply $Z^{r^{(i)}}$ twice on the $i$-th qubit: this is strictly equivalent since $ZZ=I$.

* Then, we can just attribute the operations to the appropriate parties and $\Fsemicol{\Pred}$ to obtain the ideal world: the simulator will run all the tasks, except that it sends $\bot$ to $\Fsemicol{\Pred}$ if the ZK protocol aborted, the second measurement in the computational basis on qubits in $T$, together with the sampling of $(r^{(i)})_{i \in  [n] \setminus T}$ and the first rotation $Z^{r^{(i)}}$ is done by $\Fsemicol{\Pred}$ (as expected by definition). Note that the second rotation $Z^{r^{(i)}}$ (cancelling the first one) can be applied later by the simulator since $\tilde{V}$ sends $f = \bot$, and therefore the $r^{(i)}$'s are sent back to the simulator. Since all these attribution does not change the global map performed by all parties, this is statistically indistinguishable, concluding the proof of security.

ZKoQS protocol to realize $\Fsemicol{\Pred}$
Inputs: The prover $\P$ gets $T \subseteq [n]$, a subset of qubits to measure, and the quantum state $\rho^{(1),\dots,(n)}$ to partially measure, the verifier $\V$ gets no input.

Assumption: $\Pred$ is an efficiently computable predicate on subsets of $[n]$, $(\P_{zk},\V_{zk})$ is a $n$-message ZK protocol (<ref>), $h$ is a collision-resistant (<ref>) and second-bit hardcore (<ref>) function distributed using $\Fh{}$ (<ref>), either non-interactively via a CRS, heuristically using a fixed hash function, or sent by the verifier, adding an additional message (<ref>).

* The prover checks if $\Pred(T) = \top$, and abort and send $\bot$ to $\V$ otherwise. The, she samples $\forall d \in \{0,1\}, i \in [n] \setminus T, w^{(i)}_d \sample \{0\} \times \{0,1\}^n$ and for each $j \in T$, she measures (non destructively) $\rho^{(j)}$ to get outcome $l$, and samples $w^{(j)}_l \sample \{0\} \times \{0,1\}^n$ $l \in \bin$ and $w^{(j)}_{1-l} \sample \{1\} \times \{0,1\}^n$. Then, for each $(c,d) \in T \times \{0,1\}$ she defines $h_d^{(c)} \assign h(d \| w_d^{(c)})$. Then, she sends $(h^{(c)}_d)_{c \in [n], d \in \bin}$ to the verifier (if the ZK protocol is non-interactive she can send it later in a single message with the NIZK proof and the quantum states) and runs the ZK protocol $\P_{zk}$ with the verifier (running $\P_{zk}$) to prove that:

\begin{align}
&\exists T \subseteq [n], (w_d^{(c)})_{c \in T, d \in \{0,1\}}, \forall c, d, h_d^{(c)} = h(d\| w_d^{(c)}) \\
\text{and }& \forall j \in T, \exists d \text{ s.t. } w_d^{(j)}[1] = 1, \text{ and } \Pred(T) = \top
\end{align}

Then, she samples for each $i \in [n] \setminus T$, $r^{(i)} \sample \{0,1\}$, and applies $Z^{r^{(i)}}\rho^{(i)}$. Finally, for each $c \in [n]$, she applies on $\rho^{(c)}$ the unitary mapping $\ket{x} \mapsto \ket{x}\ket{w_x^{(c)}}$ (we call $\rho_1^{(1),\dots,(n)}$ the resulting state) and she sends $\rho_1^{(1),\dots,(n)}$ to the verifier.

* The verifier aborts if the prover aborted or if it received a wrong ZK proof. Then, it applies on each qubit $c$ the unitary $\ket{x}\ket{w} \mapsto \ket{x}\ket{w}\ket{w[1] \neq 1 \land \exists d, h(x\|w) = h_d^{(c)}}$, and measures the last auxiliary register, checking if they are all equal to $1$. If not, he aborts (and sends an abort message to the prover), otherwise he measures for each $c \in [n]$ the second registers of $\rho^{(c)}$ (getting outcomes $s^{(c)}$) in the Hadamard basis. Finally, it outputs the remaining (first) qubit of each $\rho_1^{(c)}$, and sends $(s^{(c)})_{c \in [n]}$ to the prover.

* The prover computes $\omega_s \assign (r^{(i)} \xor \bigoplus_k s^{(i)}[k] (w^{(i)}_0 \xor w^{(i)}_1)[k])_{i \in [n] \setminus T}$ and outputs $\omega_s$.

ZKoQS protocol to realize $\Fsemicol{\Pred}$

(𝐓 ⊆[𝐧], ρ^(1),…,(𝐧))

$T$ is a subset of qubits to measure.

Run $\P_h$ to obtain $h$.  <->length=1.6cm  Run $\V_h$ to obtain $h$.[overlay,remember picture]
[name=start,anchor=north,align=left,text width=8cm,blue,rounded corners,draw,yshift=-5mm,xshift=-7mm]$h$ is a collision-resistant (<ref>) and second-bit hardcore (<ref>) function distributed using $\Fh{}$ (<ref>), either non-interactively via a CRS, heuristically using a fixed hash function, or sent by the verifier, adding an additional message (<ref>);
[blue,->] (start) – (-2mm,-1mm);

If $\Pred(T) = \bot$ abort and send $\bot$ to $\V$.

∀d ∈{0,1}, i ∈[n] ∖T, w^(i)_d {0} ×{0,1}^n

∀j ∈T, l Measure non destructively $\rho^{(j)}$

w^(j)_l {0} ×{0,1}^n

w^(j)_1-l {1} ×{0,1}^n

Compute the characterization

of the languages:

∀(c,d) ∈T ×{0,1}, h_d^(c) h(d  w_d^(c))

π(NI)ZK proof that:[overlay,remember picture]
[name=startPi,align=left,text width=5cm,anchor=west,yshift=1mm,xshift=5cm,blue,rounded corners,draw]If the ZK proof is interactive, then we actually run the ZK protocol (before sending the quantum state) instead of sending the proof (of course this adds additional rounds of communication).;
[blue,->](startPi) – (2mm,1mm);

∃T ⊆[n], (w_d^(c))_c ∈T, d ∈{0,1},

∀c, d, h_d^(c) = h(d w_d^(c))

and  ∀j ∈T, ∃d  s.t.  w_d^(j)[1] = 1,

and  (T) = ⊤.

∀i ∈[n] ∖T, r^(i) {0,1}

$\forall i \in [n] \setminus T$, applies $Z^{r^{(i)}}\rho^{(i)}$

∀c ∈[n], Apply on $\rho^{(c)}$:  |x⟩ ↦|x⟩|w_x^(c)⟩

(call $\rho_1^{(1),\dots,(n)}$ the resulting state)

->style=transform canvas=yshift=-3mm,length=1.6cm,topstyle=overlay,top=$\forall (c \in [n],d \in \{0,1\}): h^{(c)}_d, \pi, \rho_1^{(1),\dots,(n)}$

If Alice sent an abort message $\bot$,

Check (or run if interactive proof) $\pi$.

$\forall c$, apply on $\rho_1^{(c)} \otimes \ketbra{0}{0}$ the unitary

x,w ↦w[1] ≠1 ∃d, h(xw) = h_d^(c),

measure the last (output) register

and check that the outcome is $1$.

∀c, measure the second register of $\rho_1^{(c)}$

in the Hadamard basis (outcome $s^{(c)}$).
[dotted]End of the send procedure
Remaining (first) qubit of each $\rho_1^{(i)}$.

<-length=1.6cm,topstyle=overlay,top=$\forall c, s^{(c)}$

ω_s (r^(i) ⟨s^(i), w^(i)_0 w^(i)_1⟩)_i ∈[n] ∖T

We will see that the $\Fsemicol{\Pred}$ functionality can be used to trivially get more advanced OT protocols, notably string OT and $k$-out-of-$n$ OT for any $k$ and $n$. But first, we prove that it is a ZKoQS functionality for the quantum language of “semi-collapsed” states with respect to a predicate $\Pred$. Informally, we define the quantum language of semi-collapsed states as the set states such that there exists a subset $T$ of qubits such that $\Pred(T) = \top $, and such that all qubits in $T$ are collapsed, i.e. measured in the computational basis and equal to $\ket{0}$ or $\ket{1}$ (therefore not entangled with any other system). Moreover, the identity of the set $T$ of collapsed qubits stays hidden to a malicious verifier, and in an honest protocol the non-collapsed qubits are either a $\ket{+}$ or a $\ket{-}$, this description being known to the prover.

Note that the predicate $\Pred$ might (implicitly[In which case, the witness must be used to generate the ZK proof.]) depend on an additional secret classical witness (like a password, a signature provided by some trusted parties, or any NP statement) only known by the prover. This can allow the prover to prove even more advanced statements, like “Either all states are collapsed, or I am the owner of this bitcoin wallet and a single state is collapsed”, which can for instance be useful to obtain “anonymous authorized OT” (i.e. an OT protocol where only parties knowing the witness can participate, while the sender never knows if the receiver knows the witness or not).

The quantum language $\langSemCol{\Pred}$ of semi-collapsed states relative to a predicate $\Pred \colon \cP([n]) \rightarrow \{\top,\bot\}$ on the subsets of qubits is composed of the classes $\cC = \cP([n])$ (denoting the set of collapsed qubits), the sub-classes $\cC_s = \{ s \in \{0,1\}^* \mid |s| \leq n\}$ (denoting the description of the non-collapsed qubits), and the quantum (sub-)classes defined as follows, for any $T \in \cC$ and $\omega_s \in \cC_s$:

* $\lang_{T,\omega_s}$ is the empty set if $\Pred(T) = \false$ or if $|\omega_s| \neq |T|$, and otherwise is the set of all $n$-qubits states where qubits in $T$ are either $\ket{0}$ or $\ket{1}$, and other qubits $i$ ($i \in \{1,\dots,|T|\}$ is the index of the qubits in $[n] \setminus T$) are equal to $\ket{+}$ if $\omega_s[i] = 0$ and $\ket{-}$ otherwise.

* $\langSemCol{\Pred}$ is the set of bipartite states on registers $\P$ and $\V$ such that $\V$ contains $n$ qubits, and such that there exists $T \subseteq [n]$ such that $\Pred(T) = \bot$ and for any $i \in T$, $i$-th qubit of register $\V$ is not entangled with any other qubit and either $\ket{0}$ or $\ket{1}$.

[ZKoQS for semi-collapsed states][end]
Let $G(T)$ be the procedure that samples $(r^{(i)})_{i \in [n]} \sample \{0,1\}$ and outputs the quantum state $\bigotimes_i H^{\delta_{i \notin T}}\ket{a^{(i)}}$ (i.e. all qubits in $T$ are in the computational basis, others are in the Hadamard basis).

The functionality $\Fsemicol{\Pred}$ (where the ideal party $\tilde{\P}$ is slightly updated[$\Fsemicol{\Pred}$ can be used for any input quantum state, but for the ZKoQS we need to consider a particular case where the initial state is picked by the party instead of by the environment. The reason is that in ZKoQS protocols, an honest prover is only given as input a class.]: instead of receiving $T$ and $\rho$, it receives $T \subseteq [n]$, and samples $\rho \gets G(T)$, before continuing as usual) is a ZKoQS ideal functionality (<ref>) for the quantum language $\langSemCol{\Pred}$ (<ref>).

In particular, if we consider the protocol where the honest prover gets as input $T$, picks $\rho \gets G(T)$, and runs <ref>, this protocol is a ZKoQS protocol for the quantum language $\langSemCol{\Pred}$.

This is mostly a corollary of <ref>. The only non-trivial statement is to prove that the measurement is postponable: this can be done by teleporting the state without applying any correction.

The first statement is a quite direct application of <ref>, where we define:

* $M$ like in <ref>,

* and for any $T \in [n] = \cC$, if $\Pred(T) = \top$ then $E_{T} \eqdef \ket{T} \otimes (\ket{0}^{(T)}\ket{+}^{([n] \setminus T)})$, otherwise $E_T = \emptyset$.

The only non-trivial check is to show that $M$ are postponable measurement operators (<ref>) with respect to $\{G_T\}_{T, \lang_T \neq \emptyset} = \{G_T\}_{T, \Pred(T) = \top}$. The idea is to do teleportation without corrections, exploiting the fact that the uncorrected corrections just flip the encoded bit without changing its basis (note that to avoid dirty matrix computations, we give a more intuitive proof in the ZX calculus (but it's of course possible to derive the same proof with the usual matrix algebra). We refer curious readers unfamiliar with the ZX calculus to <cit.>.). More precisely, we define $\rho^{\V,F}$ as the system containing $n$ Bell pairs $\ket{00}+\ket{11}$ shared between registers $\V$ and $F$ (the Bell pairs being between the $\V^{(i)}$ and $F^{(i)}$ for all $i$). Then, we define $M'$ as follows:

* $M'$ takes as input the register $F$ containing Bell pairs, and a state $\rho_0$ (sampled by $G_T$).

* Then, it runs $M\rho_0$, to get a post-measured state $\rho_1$ and a measurement outcome

\begin{align}
(T, (m^{(j)})_{j \in T}, (r^{(i)})_{i \in [n] \setminus T})
\end{align}

* Then, for all $i\in [n]$, it performs a Bell measurement (i.e. it does a projection on $\{\ket{0x}+(-1)^{z}\ket{1\bar{x}}\}_{x \in \bin, z \in \bin}$) between the $i$-th qubit of $F$ and the $i$-th qubit of $\V$ to get outcomes $(x^{(i)},z^{(i)})$.

* Finally, it outputs the outcome measurement $(T, (x^{(j)} \xor m^{(j)})_{j \in T}, (z^{(i)} \xor r^{(i)})_{i \in [n] \setminus T})$

We prove now that $M G_\omega \approxRVS (I^\V \otimes M')(\rho^{\V,F} \otimes G_\omega)$. Note that both $M$ and $M'$ work separately on each system composed of the $i$-th qubit of each register, we can therefore just consider each system $i \in [n]$ separately. Let $T \in \cP([n])$ such that $\Pred(T) = \top$, and $i \in [n]$. Then $G_T$ outputs on qubit $i$ the state $H^{\delta_{i \notin T}}\ket{0}$ with probability $1/2$ and $H^{\delta_{i \notin T}}\ket{1}$ otherwise. We do two cases: if $i \notin T$, then $G_T$ generated a state $H\ket{a}$ (we omit the index, $H\ket{a}$ being represented as $\zx{\zxZ{a\pi} \zxNR{}}$ in the ZX calculus), and $M$ (and therefore $M'$) will perform a random $Z^{r}$ flip on it (represented as $\zx{\zxNL \zxZ{r\pi} \zxNR{}}$), we can easily see (manually or with the ZX calculus) that the final state at the end of the procedure $(I^\V \otimes M')(\rho^{\V,F} \otimes G_\omega)$ is $Z^{r \xor z}H\ket{a}$:

\begin{align}
\begin{ZX}[
execute at end picture={
\zxNamedBox[fit margins={right=2.2mm}]{(measX)(measZ)}{below:\footnotesize Bell measurement}
\zxNamedBox[fit margins={bottom=2pt,top=2pt,left=1.5mm}][green!80!black]{(bellA)(bellB)}{left:\footnotesize $\rho^{\V,F} =$ Bell pair: }
\zxN[a=bellA]{} \dar[C] \ar[rrrr] & & & & \zxN{} \\[\zxwCol]
\zxN[a=bellB]{} \ar[rrr] &&&\zxX[a=measX]{x\pi} \dar[C-]&\\
& \zxZ{a\pi} \rar& \zxZ{r\pi} \rar & \zxZ[a=measZ]{z\pi}
\end{ZX}
\eqAboveWidth{(S)}
\begin{ZX}
\zxN[a=bellA]{} \dar[C] \ar[rr] & & \zxN{} \\[\zxwCol]
\zxN[a=bellB]{} \ar[r] &\zxX[a=measX]{x\pi} \dar[C-]&\\
& \zxZ{(a\xor r \xor z)\pi}
\end{ZX}
\eqAboveWidth{(C)}
\begin{ZX}
\zxZ{(a\xor r \xor z)\pi} \zxNR{}
\end{ZX}
\eqAboveWidth{(S)}
\begin{ZX}
\zxZ{a\pi} \rar & \zxZ{(r \xor z)\pi} \zxNR{}
\end{ZX}
\end{align}

(the first equality comes from the spider fusion rule that allows to merge spiders of the same color, adding the angles modulo $2\pi$, the second rule being a particular case of the copy rule and the “only topology matters” principle that states that one can deform a graph without changing its interpretation). Note that since $r$ is sampled uniformly at random, and since the outcome of the measurement $z$ is independent of the value of $r\pi$ and uniformly distributed (this is easy to see as the norm of this state (computable by computing the trace using the discarding ground operation that trivially absorbs[Note that here we removed all scalars and global phases as they are just constant re-normalisation factors.] all terms: $\zx{\zxZ{(a\xor r \xor z)\pi} \rar & \zxGround{}} = \zx{\zxEmptyDiagram} $) is independent of the value of all the variables). Therefore, by defining $r' \eqdef r \xor z$, $r'$ is sampled uniformly at random, and the final state corresponds to a random rotation $Z^{r'}$ of the original qubit, exactly like in the original $M$ operation, concluding the proof[If wants to be even more formal, we can actually compute the exact density matrix of the whole process, including the outcome of the measurement, using either standard linear algebra, or diagrammatically using the discard construction <cit.> or using the doubling formalism <cit.> to represent density matrices, but this lead to the same result.].

Now, if $i \in T$, then $M'$ will measure the state $\ket{a}$ provided by $G_T$, but since it is anyway already in the computational basis this measurement has no effect (except revealing the value of $a$). Then, the Bell measurement similarly gives:

\begin{align}
\begin{ZX}
\zxN[a=bellA]{} \dar[C] \ar[rrr] & & & \zxN{} \\[\zxwCol]
\zxN[a=bellB]{} \ar[rr] &&\zxX[a=measX]{x\pi} \dar[C-]&\\
& \zxX{a\pi} \rar & \zxZ[a=measZ]{z\pi}
\end{ZX}
\eqAboveWidth{(C)}
\begin{ZX}
\zxN[a=bellA]{} \dar[C] \ar[rrr] & & & \zxN{} \\[\zxwCol]
\zxN[a=bellB]{} \ar[rr] &&\zxX[a=measX]{x\pi} \dar[C-]&\\
& \zxX{a\pi} \rar & \zxN{}
\end{ZX}
\eqAboveWidth{(S)}
\begin{ZX}
\zxX{(a \xor x)\pi} \zxNR{}
\end{ZX}
\end{align}

where $\zx{\zxX{(a \xor x)\pi} \zxNR{}} = \ket{a \xor x}$. We can similarly see that the outcome $x$ is independent of $a$. Therefore, since $a$ and $x$ are uniformly at random, the final state is a state sampled uniformly at random in the computational basis, exactly like in $M G_\omega$, concluding this part of the proof.

Finally, the second statement is trivial to check: since we just shown that the functionality $\Fsemicol{\Pred}$ is a ZKoQS, all protocols realizing it are ZKoQS protocols. However, we already know from <ref> that <ref> realizes $\Fsemicol{\Pred}$, with a slightly different dummy ideal party, say $\tilde{\P}_0$. However, since we obtain the new ideal dummy party and new protocol by doing exactly the same pre-processing ($\tilde{\P} = \tilde{\P}_0(G_T)$ and  $\P = \P_0(G_T)$, where $\P_0$ is the original party in <ref>), the distinguishing probability between the new real world and ideal world is lower, otherwise a distinguisher could apply $G_T$ to attack the original protocol known to be secure.

§.§ ZKstatesQIP and ZKstatesQMA: ZKoQS from a complexity theory point of view

While we defined ZKoQS using a “cryptographic” definition, we can also consider them from the point of view of complexity theory. While classically, complexity classes involve a verifier taking an input $x$ potentially belonging to a given classical language $\lang$, and outputting a single accept bit (this is not an issue as the input $x$ can anyway be copied by the verifier if it needs to be used later), for quantum languages this definition turns out to be hard (or even impossible) to use as the verification procedure will alter the input state. (<cit.> does something along that line, but needs to send many copies of the input state, which is of little interest in cryptography as it leads to polynomial security.) To overcome this issue, it is therefore natural to say that the quantum state belonging to the quantum language must be an output of the verifier. This is the successful point of view that we took above, and a similar approach has also been used before in <cit.> to quantify the complexity to produce a given state by defining a complexity class . However, the class  only captures how hard it is to generate a given state, but it does not capture any notion of privacy against a malicious verifier. The following definition addresses this issue:

Let $\lang$ be a quantum language (<ref>), $k \in \N$ be a number of exchanged messages, $S \in \{\emptyset, \P, \V\}$ be a subset of parties allowed to be unbounded, and $\setup$ be a given setup assumption (e.g. CRS, Random Oracle, or plain-model). We say that $\lang$ belongs to the complexity class $\ZKstatesQIP*{S}[\setup]{k}$ if there exists a $\text{ZKoQS}_S$ protocol for $\lang$, secure assuming the setup assumption $\setup$, whose  phase consists of $k$ exchanged messages (note that we might omit $S$, $\setup$, or $k$ if we do not want to constraint this parameter).

Similarly, we define $\ZKstatesQMA*{S}[\setup] = \ZKstatesQIP*{S}[\setup]{1}$ to capture non-interactive protocols.

Note that <cit.> defines multiple complexity classes like  (update: similarly, <cit.>, that was uploaded online a day after our own work, defines ): it is therefore natural to want to compare  and $\ZKstatesQIP{}{}$, similarly to the result $\textsf{stateQIP} = \textsf{statePSPACE}$ presented in <cit.>. However, note that since <cit.> and <cit.> mostly care about the complexity required to create quantum states, there is no notion of hiding or witnesses[Actually, in <cit.>, they do define witnesses but in a different way, as they send the witness directly to the verifier: thus, their notion of witness corresponds rather to the transcript of the proof in our case, and should not be understood as an information that must be hidden to the verifier like our own notion of witness (a.k.a. class).]: expressed with our terminology, their quantum languages have a single element (for a fixed, public, $n$) $\ket{\psi_n}$. Said differently, the verifier knows in advance the state $\ket{\psi_n}$ that will be generated with the help of the prover. On the other side, we have no reasons to introduce in $\ZKstatesQIP{}{}$ an asymptotic parameter $n$ denoting the size of the quantum state obtained by the verifier, as ZKoQS already makes sense for a fixed $n = 2$ (but of course, nothing prevents $\lang_{\cQ}$ from containing states of various sizes). However, it might be possible to generalize the definition of <cit.> by replacing $(\ket{\psi_n})_{n \in \N}$ with $\lang_{\cQ}$, where the parameter $n$ could represent the size of the state obtained by the verifier, or to consider a sequence of quantum languages $(\lang_{\cQ,n})_{n \in \N}$, in order to define $\mathsf{state\underline{\mathsf{s}}QIP}$ (the additional $\mathsf{s}$ being used to denote the fact that the verifier might produce a state among multiple, valid, candidates). However, properly generalizing <cit.> and defining $\mathsf{state\mathbf{s}QIP}$/$\mathsf{statesQMA}$ is out of the scope of this paper.

We prove now that $\langSemCol{\Pred}$ belongs to these classes:

[$\langSemCol{\Pred}$ is in ][end]
For any predicate $\Pred$, the quantum language $\langSemCol{\Pred}$ belong to $\ZKstatesQMA{}[\mathsf{RO}]$ (where $\mathsf{RO}$ stands for Random Oracle model). Moreover, assuming the hardness of  (see <cit.> for the exact assumptions), $\langSemCol{\Pred}$ belongs to $\ZKstatesQIP{}[\mathsf{pm}]{}$ (where $\mathsf{pm}$ stands for plain-model).

More generally, assuming the existence of a $k$-message ZK protocol $\CSQSA{S}$ realizing $\Fzk{}$ for any  statement assuming a setup $\setup$, $\langSemCol{\Pred}$ belong to $\ZKstatesQIP{S}[\setup]{k}$.

These statements can be proven using <ref>, together with the constructions of <cit.> and <cit.>.

The last statement is a direct consequence of <ref> and of the definition of $\ZKstatesQMA{S}[\setup]{k}$. The first statement is obtained by instantiating the ZK protocol using the NIZK construction of <cit.> secure in the Random Oracle model (we prove in <ref> that their definition can be translated in a the quantum standalone framework). The second statement is obtained by instantiating the ZK protocol using the construction of <cit.>, proven secure in the plain-model assuming the hardness of  (this construction is already proven secure on the quantum standalone model, so no additional work is required).

§.§ Applications to build string and $k$-out-of-$n$ OT protocols

We prove in this section that the above functionality $\Fsemicol{\Pred}$ actually allows us to have string OT or $k$-out-of-$n$ OT. But first, we show that we can realize this functionality:

Let $\Pred$ be a predicate on subsets of $[n]$. Assuming the existence of a protocol $\Pisemicol* = (\Asemicol, \Bsemicol)$ that $\CSQSA{S}$-realises $\Fsemicol{\Pred}$, there <ref> $\CSQSA{S}$-realises $\FotPred$.

This is a generalisation of the last part of the proof of <ref>.

This is a straightforward generalisation of the last part of the proof of <ref>. We start with correctness.

Case 1: correctness (no corrupted party).
Since $\Pisemicol*$ $\CSQSA{S}$-realises $\Fsemicol{\Pred}$, we can indistinguishably replace $\Asemicol*$ and $\Bsemicol*$ with dummy ideal adversaries interacting with $\Fsemicol{\Pred}$. Then, we show that this world is indistinguishable from the real world: if the input $B$ is such that $\Pred(T) = \bot$, all parties would abort like in the real world. Otherwise, if $\Pred(T) = \top$, then the functionality measures states not in $B$… but since these states are already measured, it left them unchanged. It also rotates the qubits in $B$ (in the Hadamard basis) them by $Z^{z^{(i)}}$. Therefore, for all $i \in B$, the $i$-th qubit becomes $\rho^{(i)} = Z^{r^{(i)} \xor s^{(i)}}\ket{+}$. After the rotation performed by $\Bob$, we get $Z^{r^{(i)} \xor s^{(i)} \xor m_i}\ket{+}$, and therefore the measurement in the Hadamard basis gives $z^{(i)} = r^{(i)} \xor s^{(i)} \xor m_i$. Since $\Alice$ outputs for each $i \in B$, $r^{(i)} \xor s^{(i)} \xor z^{(i)} = m_i$, the output of $\Alice$ is exactly the same as in the ideal world, making both worlds indistinguishable, concluding the correctness proof.

Case 2: malicious receiver Alice.
If $\hat{\Alice}$ is malicious, we can cut $\hat{\Alice}$ in two parts, $\hat{\Alice}_0$ interacting with $\Bsemicol*$ and $\hat{\Alice}_1$ doing the rest of the computation. Since $\Pisemicol*$ $\CSQSA*{S}$-realises $\Fsemicol{\Pred}$, there exists a simulator $\Sim_{\hat{A}_0}$ such that $\hat{\Alice}_0 \interacts \Bsemicol* \approxRVC \Sim_{\hat{A}_0} \interactsF{\Fsemicol{\Pred}} \tilde{\Bsemicol*}$ (or $\approxRVS$ if $\P \in S$). We can therefore indistinguishably replace the first one with the last one. Since $\tilde{\Bsemicol*}$ measures qubits not in $B$, the rotation on these qubits performed by Bob has no effect: as a result, we can remove them indistinguishably. Now, neither $\Alice$ nor $\Bob$ depends on $m_i$ for $i \notin B$, we can therefore move them into the final simulator, using the $(m_i)_{i \in B}$ provided by $\FotPred$ otherwise (note that if $\Pred(B) = \bot$, $\FotPred$ would not provide these values and abort, but this is not an issue since anyway $\Fsemicol{\Pred}$ also aborts in that case). This new world is therefore equal to the ideal world, and indistinguishable from the previous world, concluding the proof of security.

Case 3: malicious sender Bob.
If $\hat{\Bob}$ is malicious, we can cut $\hat{\Bob}$ in two parts, $\hat{\Bob}_0$ interacting with $\Asemicol*$ and $\hat{\Bob}_1$ doing the rest of the protocol. Since $\Pisemicol*$ $\CSQSA*{S}$-realises $\Fsemicol{\Pred}$, there exists a simulator $\Sim_{\hat{B}_0}$ such that $\Asemicol* \interacts \hat{\Bob}_0 \approxRVC \tilde{\Bsemicol*} \interactsF{\Fsemicol{\Pred}} \Sim_{\hat{B}_0}$ (or $\approxRVS$ if $\P \in S$). We can therefore indistinguishably replace the first one with the last one. Then, since the qubits in $B$ are already in the computational basis, the functionality can skip the measurements of these qubits without being detected. Similarly, as we already saw it earlier, since sampling a qubit in $\ket{0}$ or $\ket{1}$ is indistinguishable from sampling a qubit in $\ket{+}$ or $\ket{-}$ (the encoded value being discarded), we can indistinguishably apply an $H$ gate on these qubits to turn them back into qubits in the Hadamard basis, and also compute $r^{(i)} \xor s^{(i)} \xor z^{(i)}$ for these qubits (it will be discarded anyway). Then, except for the return procedure of $\P$ that discards some terms, all the steps are independent of $m_i$'s: we can therefore move everything into our final simulator, let it send the $r^{(i)} \xor s^{(i)} \xor z^{(i)}$ to the ideal functionality $\FotPred$ that will be in charge of discarded elements not it $T$. This last step is indistinguishable as we only moved some operations, ending this proof of security.

Protocol to compile a ZKoQS protocol $(\Asemicol*,\Bsemicol*)$ for the quantum language $\langSemCol{\Pred}$ into a predicate OT protocol.

Alice($B \subseteq \{0,1\}^n$)   Bob($(m_1,\dots,m_n) \in \{0,1\}^n$)

If $\Pred(B) = \bot$, abort.

∀i ∈[n], r^(i)

ρ⊗_i ∈[n] H^δ_i ∈B|r^(i)⟩

(s^(i))_i ∈B *(B,ρ)  <->length=,topstyle=overlay,top=  ρ*

Abort if the previous step aborted.   If the previous step aborted, abort.

∀c, apply $Z^{m_c}$ on $\rho^{(c)}$ and measure it

in the Hadamard basis (outcome $z^{(c)}$).

(r^(i) s^(i) z^(i))_i ∈B <-topstyle=overlay,length=,top=$\forall c, z^{(c)}$

By choosing appropriate values for $\Pred$ like in <ref>, the protocol <ref> realizes the string OT functionality $\FotStr$ and the $k$-out-of-$n$ OT functionality $\FotKoutN$.

This is a direct consequence of <ref> and of the definition of $\FotKoutN$ and $\FotStr$.

§ COMPOSABILITY OF <CIT.>

We are now going to prove that the online extractable NIZK protocol from <cit.> quantum stand-alone realizes the $\Fzk*{\cR}$ functionality in <ref>, when the RO assumption is made.

The polynomial-time QIM prover $\P{}$ and verifier $\V{}$ from <cit.> have access to two random oracles, $G$ and $H$, which can be queried in superposition by both parties (for simplicitly we will just refer to a single oracle $H$). We will denote the polynomial-time two-party protocol by $\Pizk^{H}=(\P{},\V{})$ to stress the interaction between two machines and the trusted random oracles $\P{}\interactsF{H}\V{}$. Note that a single message is sent from the prover $\P$ to the verifier $\V$, leading to a so-called non-interactive protocol.

The protocol $\Pizk^{H}$ is proven to be complete, zero-knowledge and (even simulation-sound) online-extractable. We recall the definitions in <ref> for clarity (note that we assume they also hold against non-uniform adversaries).

* Completeness (<cit.>): $\Pizk^H$ is complete iff for any quantum-polynomial-time oracle algorithm $A$ and advice $(\sigma_\lambda)_{\lambda \in \N}$,

\begin{align}
\begin{multlined}[t]
\Pr\Bigl[(x,w)\in\cR\land y= 0 \Big| H\gets\mathsf{ROdist}, (x,w)\gets A^H(\sigma_\lambda),\\
y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle\Bigr] \leq \negl.\label{eq:un_complete}
\end{multlined}
\end{align}

* Zero-knowledge (<cit.>): $\Pizk^H$ is zero-knowledge iff there exists a polynomial-time simulator $\Sim=(\Simin,\Sim_P)$ such that for every quantum-polynomial-time oracle algorithm $A$ and advice $(\sigma_\lambda)_{\lambda \in \N}$,

\begin{align}
\begin{multlined}[t]
\left|\pr[H\gets \mathsf{ROdist},z\gets A^{H,\P}(\sigma_\lambda)]{z=1}\right.\\
-\left.\pr[H\gets \Simin,z\gets A^{H,\Sim_P}(\sigma_\lambda)]{z=1}\right|\leq\negl.
\end{multlined}
\end{align}

Since in the quantum setting we cannot allow the simulator to learn the input for each query, because this can be done in superposition, here the simulator $S_{\text{init}}$ outputs a circuit describing a classical function representing the initial random oracle instead. We assume that both $\Simin$ and $\Sim_P$ have access to the polynomial upper bound on the runtime of $A$.

* Online-extractability (<cit.>): $\Pizk^H$ is online extractable with respect to $\Simin$ iff there exists a polynomial-time extractor $E$ such that for any quantum-polynomial-time oracle algorithm $A$ and advice $(\sigma_\lambda)_{\lambda \in \N}$,

\begin{align}
\begin{multlined}[t]
\Pr\Bigl[y=1\land (x,w)\not\in\cR \Big| H\gets \Simin(), (x,\pi)\gets A^H(\sigma_\lambda), y\gets \V^H(x,\pi),\\
w\gets E(H,x,\pi)\Bigr]\leq\negl.
\label{eq:online_extrac}
\end{multlined}
\end{align}

We assume that both $\Simin$ and $E$ have access to the polynomial upper bound on the runtime of $A$.

Note that Unruh's original definition he considers only uniform adversaries, here we assume that the above conditions hold for the protocol when the adversary receives advice.

In the following we will prove that the protocol $\Pizk^{H}$ quantum stand-alone realizes the functionality $\Fzk*{\cR}$.

Let $H$ be a random oracle. The non-interactive protocol $\Pizk^{H}=(\P{},\V{})$ quantum stand-alone realizes the classical zero-knowledge functionality $\Fzk{\cR}$, were $x\in\cL\Leftrightarrow\exists w,\: x\cR w$.

We define trivially the dummy parties $\tPizk = (\tP,\tV)$ that forward the inputs/outputs to/from $\Fzk*{\cR}$. We want to show that for any  adversary $\cA$ there exists a  simulator $\Sim$ such that, for any poly-time distinguisher $\Zenv$ and input state $\sigma_\lambda$, we have $\Real^{\sigma}_{\Pizk,\cA,\Zenv}\approxRV \Ideal^{\sigma,\Fzk{\cR}}_{\tPizk,\Sim_\cA,\Zenv}$. We will split the proof depending on the parties that the static adversary $\cA$ corrupts (nobody, the prover $\P$ or the verifier $\V$).

Note that in the non-interactive protocol $\Pizk^{H}$ the prover rejects if it receives a non-valid witness $(x,w)\not\in\cR$, which is essential.

Case 1: correctness (no corrupted party).

For any bipartite input state $\sigma_\lambda^{\P,\Zenv}\in\text{D}(\S_\lambda\otimes\R_\lambda)$, with $\R_\lambda$ an arbitrary reference system, we want to show that for any environment $\Zenv$ the probability of distinguishing $\Pizk^{H}$ from the ideal functionality $\tPizk$ is negligible

\begin{align}
\begin{split}
&\left|\pr[ H\gets\ROd, y\gets\OUT_\V\langle\P(\sigma^{\P}_\lambda)\interactsF{H}\V\rangle]{\Zenv(y,\sigma^{\Zenv}_\lambda)=1}\right.\\
&\left.-\pr[H\gets\ROd, y\gets\OUT_\V\langle\tP(\sigma^\P_\lambda)\interactsF{\cF}\tV\rangle]{\Zenv(y,\sigma^\Zenv_\lambda)=1}\right|\leq\negl.
\end{split}\label{eq:correct}
\end{align}

In order to prove the above inequality we are interested in rewriting the probability of the distinguisher outputting $1$ in terms of the input/output of the interaction. Since the prover expects a classical message, we can model $\sigma_\lambda^{\P,\Zenv}$ as a quantum instrument:

\begin{align}
\sigma_\lambda^{\P,\Zenv} = \sum_{x,w} p_{x,w}\ketbra{x,w}{x,w} \otimes \sigma_{\lambda,x,w}.
\end{align}

This allows to write the LHS of <ref> as

\begin{align}
\MoveEqLeft[3] \sum_{x,w}p_{x,w}\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{\Zenv(y,\sigma_{\lambda,x,w})=1}\\
\sum_{b\in\{0,1\}}\sum_{x,w}\Bigl(p_{x,w}\pr{\Zenv(b,\sigma_{\lambda,x,w})=1}\\
\cdot\left.\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=b}\right)
\end{multlined}\label{eq:developed}
\end{align}

For the dummy protocol $\tPizk$ the above equation has a very simple form since if $(x,w)\in\cR$ (resp. $(x,w)\not\in\cR$), then $\tPizk$ will output $1$ (resp. $0$) with probability $1$. Therefore, for any input state $\sigma_\lambda^{\P,\Zenv}$ we can simplify the RHS of <ref> to

\begin{align}
\sum_{(x,w)\in\cR}p_{x,w}\pr{\Zenv(1,\sigma_{\lambda,x,w})=1}+\sum_{(x,w)\not\in\cR}p_{x,w}\pr{\Zenv(0,\sigma_{\lambda,x,w})=1}
\end{align}

For the honest protocol $\Pizk^{H}$, note that for invalid witnesses $(x,w)\not\in\cR$ the honest prover $\P^{H}$ will also always reject, therefore for $(x,w)\not\in\cR$:

\begin{align}
\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=1}=0,
\end{align}

thus for an arbitrary mixture of invalid witnesses $\sum_{(x,w)\not\in\cR}q_{x,w}\ketbra{x,w}{x,w}$ we will have that

\begin{align}
\sum_{(x,w)\not\in\cR}q _{x,w}\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=1}=0,
\label{eq:mix_nor_0}
\end{align}

and consequently

\begin{align}
\sum_{(x,w)\not\in\cR}q _{x,w}\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=0}=1.
\label{eq:mix_nor_1}
\end{align}

The case of valid witnesses is also easy as we know from completeness <ref> that given any input state $(x,w)\in\cR$, if we pick the constant algorithm $A:\sigma_\lambda^\P\mapsto(x,w)$, then

\begin{align}
\pr[H\gets\ROd,y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=0}\leq\negl,
\end{align}

thus for an arbitrary mixture of valid witnesses $\sum_{(x,w)\in\cR}q_{x,w}\ketbra{x,w}{x,w}$ we will have that

\begin{align}
\sum_{(x,w)\in\cR}q _{x,w}\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=0}\leq\negl,
\label{eq:mix_r_0}
\end{align}

and consequently

\begin{align}
\sum_{(x,w)\in\cR}q _{x,w}\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=1}\geq1-\negl.
\label{eq:mix_r_1}
\end{align}

We can combine the above <ref> to obtain the desired inequality <ref> for any input $\sigma_\lambda^{\P,\Zenv}$ and any distinguisher $\Zenv$ by noting that for any received input $b\in\{0,1\}$ and advice $\sigma_{\lambda,x,w}$, the probability of the distinguisher outputing $1$ is bounded

\begin{align}
\pr{\Zenv(b,\sigma_{\lambda,x,w})=1}\leq 1,
\end{align}

and therefore by developing <ref> in terms of the advice as in <ref> we can bound the difference by

\begin{align}
\begin{split}
\leq&\left|\sum_{(x,w)\in\cR}p_{x,w}\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=0}\right|\\
&+\left|\sum_{(x,w)\in\cR}p_{x,w}\left(\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=1}-1\right)\right|\\
&+\left|\sum_{(x,w)\not\in\cR}p_{x,w}\left(\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=0}-1\right)\right|\\
&+\left|\sum_{(x,w)\not\in\cR}p_{x,w}\pr[H\gets\ROd, y\gets\OUT_\V\langle\P(x,w)\interactsF{H}\V\rangle]{y=1}\right|\\
\leq& \negl,
\end{split}
\end{align}

Case 2: malicious Alice.

If the adversary corrupts the prover $\cA=\hat{\P}$, we will use online-extractability to construct the desired simulator.

Simulator $\Sim_\mathcal{\cA}\eqdef(S,E,\Simin)$: Prover is corrupted.

* $S$ initializes $\hat{\P}$ with whatever input state it receives.

* $S$ obtains $(x,\pi)$ from $\hat{\P}$.

* $S$ initializes $E$ with $(x,\pi)$ and the description of the oracle $H$ given by the simulator $\Simin$.

* $E(H,x,\pi)$ extracts a witness $w$ or an abort message $\bot$ and sends it to $S$.

* $S$ sends $(x,w)$ or $\bot$ to $\Fzk*{\cR}$.

We will now prove that no distinguisher can differentiate between the real protocol with corrupted Alice and the ideal functionality with the above simulator. This proof relies on the closeness of the following hybrid worlds (see <ref> for a graphical depiction):

* $\World_0 \eqdef \Ideal^{\sigma,\Fzk{\cR}}_{\tPizk,\Sim_\cA,\Zenv}$ is the ideal world. Consists of one output by the functionality (forwarded by the dummy verifier) which is accepting if the witness obtained by the extractor in <ref> is valid, i.e., $(x,w)\in\cR$.

* $\World_1$ is like $\World_0$ except that we substitute the dummy verifier by a merge of Unruh's verifier $\V$ and the simulator. In particular, we replace $\tV$ by a verifier $\V_1$ that forwards the proof from the simulator to the extractor $E$. If the extractor provides a witness $w$, then $\V_1$ accepts $y=x$ and else aborts $y=\bot$.

* $\World_2$ is like $\World_1$ except that we drop the extractor (as it is only being used to check the proof) and the dummy verifier $V_1$ which is only forwarding information, and we use Unruh's verifier $\V$ to perform the check of the proof received by the simulator $S$ instead.

* $\World_3$ is like $\World_2$ except that we drop the simulator $S$ as it is only forwarding the information to the verifier.

* $\World_4$ differs from $\World_3$ in that we replace the simulator $\Simin$ by the oracle $H$ that is simulating. Note that now $\World_4 \eqdef \Real^{\sigma}_{\Pizk,\cA,\Zenv}$.

The similarity of the first two worlds, $\World_0\approxRV\World_1$, is a consequence of online-extractability. More precisely, if we could distinguish these two worlds, there would exit an input $\sigma_\lambda^\P$ such that

\begin{align}
\begin{split}
&\left|\pr[H\gets\Simin(),  y\gets\OUT_{\tV}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} \tV\rangle]{\Zenv(y,\sigma^{\Zenv}_\lambda)=1}\right.\\
&\left.- \pr[H\gets\Simin(), y\gets\OUT_{V_1}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts V_1\rangle]{\Zenv(y,\sigma^\Zenv_\lambda)=1}\right|>\negl.
\end{split}
\end{align}

In order to work with them jointly we expand them in terms of the verifier accepting/rejecting $y\in\{x,\bot\}$:

\begin{align}
\left|\pr[H\gets\Simin(),  y\gets\OUT_{\tV}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} \tV\rangle]{\Zenv(y,\sigma^{\Zenv}_\lambda)=1}\right.\\
\left.- \pr[H\gets\Simin(), y\gets\OUT_{V_1}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts V_1\rangle]{\Zenv(y,\sigma^\Zenv_\lambda)=1}\right|
\end{multlined}\\
\begin{split}
={}&\left|\sum_{b\in\{x,\bot\}}\pr{\Zenv(b,\sigma^{\Zenv}_\lambda)=1}\pr[H\gets\Simin(),  y\gets\OUT_{\tV}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} \tV\rangle]{y=b}\right.\\
&-\left.\sum_{b\in\{x,\bot\}}\pr{\Zenv(b,\sigma^\Zenv_\lambda)=1}\pr[H\gets\Simin(), y\gets\OUT_{V_1}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts V_1\rangle]{y=b}\right|
\end{split}\\
\Big|\pr{\Zenv(x,\sigma^{\Zenv}_\lambda)=1}\nonumber\\
\cdot\sum_{M\in\{\tV,V_1\}}(-1)^{\delta_V}\pr[H\gets\Simin(),  y\gets\OUT_{M}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} M\rangle]{y=x}
\end{multlined}\nonumber\\
&\begin{multlined}[t] +\pr{\Zenv(\bot,\sigma^\Zenv_\lambda)=1}\\
\cdot\sum_{M\in\{\tV,V_1\}}(-1)^{\delta_V}\pr[H\gets\Simin(), y\gets\OUT_{M}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts M\rangle]{y=\bot}\Big|
\end{multlined}\\
\begin{split}
\leq&\left|\sum_{M\in\{\tV,V_1\}}(-1)^{\delta(V)}\pr[H\gets\Simin(),  y\gets\OUT_{M}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} M\rangle]{y=x}\right|\\
&+\left|\sum_{M\in\{\tV,V_1\}}(-1)^{\delta(V)}\pr[H\gets\Simin(),  y\gets\OUT_{M}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} M\rangle]{y=\bot}\right|.
\end{split}
\end{align}

We write down the probabilities of each protocol accepting, $y=x$, to better visualize:

\begin{align}
\MoveEqLeft[3] \pr[H\gets\Simin(),  y\gets\OUT_{\tV}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} \tV\rangle]{y=x}\\
={}&\begin{multlined}[t]\Pr\Bigl[y=x\Big| H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),w'\gets E(x,\pi,H),\\
\end{multlined}\\
={}&\begin{multlined}[t] \Pr\Bigl[ w'\not=\bot\land (x,w')\in\cR \Big| H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),\\
w'\gets E(x,\pi,H)\Bigr] \label{eq:world_1_exp1},
\end{multlined}\\
\MoveEqLeft[3] \pr[H\gets\Simin(), y\gets\OUT_{V_1}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts V_1\rangle]{y=x}\\
\Pr\Bigl[y=x\land w'\not=\bot\Big|H\gets\Simin(), (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),w'\gets E(x,\pi,H),\\
y\gets V(x,\pi)\Bigr]
\end{multlined}\\
={}&\begin{multlined}[t] \Pr\Bigl[y=x\land w'\not=\bot\land (x,w')\in\cR\Big|H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),\\
w'\gets E(x,\pi,H),y\gets V(x,\pi)\Bigr]\label{eq:world_1_exp2}
\end{multlined}\\
&\begin{multlined}[t] +\Pr\Bigl[y=x\land w'\not=\bot\land (x,w')\not\in\cR\Big| H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),\\
w'\gets E(x,\pi,H),y\gets V(x,\pi)\Bigr], \label{eq:world_1_exp3}
\end{multlined}
\end{align}

where in the last equality we just used the marginal probability expansion. Moreover, by online-extractability <ref>, we know that for all $\sigma_\lambda^\P$:

\begin{align}
\Pr\Bigl[y=x \land w'\not=\bot\land (x,w')\not\in\cR \Big| H\gets\Simin(), (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^\P),&\nonumber\\
y\gets\V(x,\pi), w'\gets E(x,\pi,H)\Bigr]& <\negl, \label{eq:online_ext_2}\\
\Pr\Bigl[y=x \land w'\not=\bot\land (x,w')\in\cR\Big| H\gets\Simin(), (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^\P), &\nonumber\\
y\gets\V(x,\pi), w'\gets E(x,\pi,H)\Bigr]& >1-\negl,
\end{align}

thus bounding <ref>. Note that we can bound <ref> by <ref>, as the former adds one more restriction to the output. Therefore, the probabilities of each protocol accepting is nearly the same as

\begin{align}
\MoveEqLeft[3] \left|\pr[H\gets\Simin(),  y\gets\OUT_{\tV}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} \tV\rangle]{y=x}\right.\nonumber\\
&\quad -\left.\pr[H\gets\Simin(), y\gets\OUT_{V_1}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts V_1\rangle]{y=x}\right|\\
\leq &\begin{multlined}[t] \left|\Pr\Bigl[ w'\not=\bot\land (x,w')\in\cR\Big|  H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),\right.\\
w'\gets E(x,\pi,H)\Bigr]
\end{multlined}\\
&\begin{multlined}[t] -\Pr\Bigl[ y=x\land w'\not=\bot\land (x,w')\in\cR \Big| H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),\\
\left.w'\gets E(x,\pi,H),y\gets V(x,\pi)\Bigr]\right| +\negl
\end{multlined}\\
\leq&\negl.
\end{align}

This bound in enough to show the similarity of the worlds as

\begin{align}
\begin{multlined}[t] \pr[H\gets\Simin(),  y\gets\OUT_{M}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} M\rangle]{y=\bot}\\
=1-\pr[H\gets\Simin(),  y\gets\OUT_{M}\langle\Sim_\cA(\sigma_\lambda^\P)\interactsF{\cF} M\rangle]{y=x},
\end{multlined}
\end{align}

for both $M=\tV$ and $M=V_1$.

We can also prove $\World_1\approxRV\World_2$ using online extractability, as the verifier $V_1$ is only using the extractor to see if it does not abort. More precisely, following the same argument as before, and expanding the probability of accepting for the protocol from $\World_2$:

\begin{align}
\MoveEqLeft[3] \pr[H\gets\Simin(), y\gets\OUT_{\V}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts \V\rangle]{y=x}\\
={}&\pr[H\gets\Simin(), (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),y\gets\V(x,\pi)]{y=x}\\
={}&\pr[H\gets\Simin(), (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),y\gets\V(x,\pi)]{y=x\land (x,w')\in}\nonumber\\
&+\pr[H\gets\Simin(), (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),y\gets\V(x,\pi)]{y=x}.
\end{align}

In order to proof the equivalence it is enough to note that

\begin{align}
\MoveEqLeft[3] \left|\pr[H\gets\Simin(), y\gets\OUT_{V_1}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts V_1\rangle]{y=x}\right.\nonumber\\
&-\left.\pr[H\gets\Simin(), y\gets\OUT_{\V}\langle\Sim_\cA(\sigma_\lambda^\P)\interacts \V\rangle]{y=x}\right|\\
={}&\begin{multlined}[t] \left|\Pr\Bigl[ y=x\land w'\not=\bot \Big| H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),w'\gets E(x,\pi,H),\right.\\
y\gets V(x,\pi)\Bigr]
\end{multlined}\nonumber\\
&-\left.\pr[H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),y\gets V(x,\pi)]{y=x}\right|.\\
={}&\begin{multlined}[t]\Pr\Bigl[ y=x\land w'=\bot \Big| H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),w'\gets E(x,\pi,H),\\
y\gets V(x,\pi)\Big]
\end{multlined}\\
={}&\begin{multlined}[t] \Pr\Bigl[ y=x\land w'=\bot\land (x,w')\not\in\cR \Big| H\gets\Simin(),  (x,\pi)\gets\hat{\P}^{H}(\sigma_\lambda^{\P}),\\
w'\gets E(x,\pi,H),y\gets V(x,\pi)]\label{eq:world_2_bound}
\end{multlined}\\
\end{align}

where in <ref> we used that $\{w'=\bot\}\subseteq\{(x,w')\not\in\cR\}$.

The rest of the relations are obvious since $\World_3$ is just $\World_2$ with a different routing of the messages – the simulator $S$ is only redirecting the information. $\World_3\approxRV\World_4$ is changing the $\Simin$ by the oracle that it is simulating $H$.

Case 3: malicious Bob. If the adversary corrupts the verifier $\cA=\V{}$, the simulator from <cit.> from the zero-knowledge property will be enough.

Recall that in his description of the adversary it also encompasses the distinguisher, but by allowing adversaries that receive advice, it is equivalent to assuming an adversary that outputs a proof for the verifier. This is, Unruh's simulator $\Sim=(\Simin,\Sim_P')$ fulfills

\begin{align}
\begin{multlined}[t] \left|\pr[H\gets\ROd,(x,\pi)\gets\P^H(\sigma_\lambda^\P),y\gets\hat{\V}(x,\pi,\sigma_\lambda^\V)]{\Zenv(y,\sigma_\lambda^\Zenv)=1}\right.\\
\left.-\pr[H\gets\Simin(),(x,\pi)\gets\Sim_P'(\sigma_\lambda^\P),y\gets\hat{\V}(x,\pi,\sigma_\lambda^\V)]{\Zenv(y,\sigma_\lambda^\Zenv)=1}\right|\\
\end{multlined}
\end{align}

Note that the simulator $\Sim_P'$ is replacing both the ideal functionality $\Fzk*{\cR}$ and the dummy verifier $\tP$ in the ideal world, i.e. aborts whenever $(x,w)\not\in\cR$ and runs $\Sim_P(x,\sigma_\lambda^\V)$ otherwise. However, we can easily modify this simulator to obtain the desired one in terms of the subsimulator $\Sim_P$.

Simulator $\Sim_\mathcal{\cA}\eqdef(S,\Simin)$: Verifier is corrupted.

* If $S$ does not receive an abort $\bot$ message from the ideal functionality $\Fzk*{\cR}$, redirects the input $x$ to the simulator $\Sim_P$. Else, it aborts.

* $S$ receives $(x,\pi)$ from the simulator $\Sim_P(x)$.

* $S$ sends $(x,\pi,\sigma_\lambda)$ to the verifier $\V$.

* $S$ redirects the output of the verifier $\V$ to the distinguisher $\Zenv$.

It is clear that $\Zenv$ cannot distinguish between the proofs provided by the verifier and the simulator, as our simulator is just a rewiering of Unruh's simulator, see <ref>.

Protocol for $\Sim_P'$.

Ideal functionality with $\Sim_\mathcal{\cA}$.

Construction of the simulator for adversarial verifier.

§ ACKNOWLEDGMENT

The authors deeply thank Christian Schaffner for many insightful exchanges, together with Stacey Jeffery, Geoffroy Couteau and James Bartusek for precious discussions.

This work is co-funded by the European Union (ERC, ASC-Q, 101040624). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

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

abstractWe present a new template for building oblivious transfer from quantum information that we call the “fixed basis” framework. Our framework departs from prior work (eg., Crepeau and Kilian, FOCS '88) by fixing the correct choice of measurement basis used by each player, except for some hidden trap qubits that are intentionally measured in a conjugate basis. We instantiate this template in the quantum random oracle model (QROM) to obtain simple protocols that implement, with security against malicious adversaries: - Non-interactive random-input bit OT in a model where parties share EPR pairs a priori. - Two-round random-input bit OT without setup, obtained by showing that the protocol above remains secure even if the (potentially malicious) OT receiver sets up the EPR pairs. - Three-round chosen-input string OT from BB84 states without entanglement or setup. This improves upon natural variations of the CK88 template that require at least five rounds. Along the way, we develop technical tools that may be of independent interest. We prove that natural functions like XOR enable seedless randomness extraction from certain quantum sources of entropy. We also use idealized (i.e. extractable and equivocal) bit commitments, which we obtain by proving security of simple and efficient constructions in the QROM.
titleA New Framework for Quantum Oblivious Transfer
quantum oblivious transfer,quantum random oracles

Springer International Publishing

abstractKnowledge extraction, typically studied in the classical setting, is at the heart of several cryptographic protocols. The prospect of quantum computers forces us to revisit the concept of knowledge extraction in the presence of quantum adversaries.
booktitleTheory of Cryptography
seriesLecture Notes in Computer Science
titleSecure Quantum Extraction Protocols
leo/Zotero/storage/FISHTQWA/Ananth et La Placa - 2020 - Secure Quantum Extraction Protocols.pdf

Berlin, Heidelberg

abstractWe describe a protocol for quantum oblivious transfer, utilizing faint pulses of polarized light, by which one of two mutually distrustful parties (“Alice”) transmits two one-bit messages in such a way that the other party (“Bob”) can choose which message he gets but cannot obtain information about both messages (he will learn his chosen bit’s value with exponentially small error probability and may gain at most exponentially little information about the value of the other bit), and Alice will be entirely ignorant of which bit he received. Neither party can cheat (ie deviate from the protocol while appearing to follow it) in such a way as to obtain more information than what is given by the description of the protocol. Our protocol is easy to modify in order to implement the All-or-Nothing Disclosure of one out of two string messages, and it can be used to implement bit commitment and oblivious circuit evaluation without complexity-theoretic assumptions, in a way that remains secure even against cheaters that have unlimited computing power. Moreover, this protocol is practical in that it can be realized with available optoelectronic apparatus while being immune to any technologically feasible attack for the foreseeable future.
booktitleAdvances in Cryptology — CRYPTO ’91
seriesLecture Notes in Computer Science
titlePractical Quantum Oblivious Transfer
leo/Zotero/storage/FMYWQPCC/Bennett et al. - 1992 - Practical Quantum Oblivious Transfer.pdf
Commitment Scheme,Dark Count,Oblivious Transfer,Parity Check Matrix,Quantum Cryptography

Springer International Publishing

abstractWe prove that quantum-hard one-way functions imply simulation-secure quantum oblivious transfer (QOT), which is known to suffice for secure computation of arbitrary quantum functionalities. Furthermore, our construction only makes black-box use of the quantum-hard one-way function.Our primary technical contribution is a construction of extractable and equivocal quantum bit commitments based on the black-box use of quantum-hard one-way functions in the standard model. Instantiating the Crépeau-Kilian (FOCS 1988) framework with these commitments yields simulation-secure QOT.
booktitleAdvances in Cryptology – CRYPTO 2021
seriesLecture Notes in Computer Science
titleOne-Way Functions Imply Secure Computation in a Quantum World
leo/Zotero/storage/UCELXNNV/Bartusek et al. - 2021 - One-Way Functions Imply Secure Computation in a Qu.pdf
Multiparty Computing,QMPC,Quantum

Springer International Publishing

abstractWe construct a two-message oblivious transfer (OT) protocol without setup that guarantees statistical privacy for the sender even against malicious receivers. Receiver privacy is game based and relies on the hardness of learning with errors (LWE). This flavor of OT has been a central building block for minimizing the round complexity of witness indistinguishable and zero knowledge proof systems, non-malleable commitment schemes and multi-party computation protocols, as well as for achieving circuit privacy for homomorphic encryption in the malicious setting. Prior to this work, all candidates in the literature from standard assumptions relied on number theoretic assumptions and were thus insecure in the post-quantum setting. This work provides the first (presumed) post-quantum secure candidate and thus allows to instantiate the aforementioned applications in a post-quantum secure manner.
booktitleTheory of Cryptography
isbn978-3-030-03809-0 978-3-030-03810-6
seriesLecture Notes in Computer Science
titleTwo-Message Statistically Sender-Private OT from LWE
leo/Zotero/storage/JUDYPIJ8/Brakerski et Döttling - 2018 - Two-Message Statistically Sender-Private OT from L.pdf

Berlin, Heidelberg

abstractWe propose a framework for analyzing classical sampling strategies for estimating the Hamming weight of a large string from a few sample positions, when applied to a multi-qubit quantum system instead. The framework shows how to interpret the result of such a strategy and how to define its accuracy when applied to a quantum system. Furthermore, we show how the accuracy of any strategy relates to its accuracy in its classical usage, which is well understood for the important examples. We show the usefulness of our framework by using it to obtain new and simple security proofs for the following quantum-cryptographic schemes: BB84 quantum-key-distribution, and quantum oblivious-transfer from bit-commitment.
booktitleAdvances in Cryptology – CRYPTO 2010
seriesLecture Notes in Computer Science
titleSampling in a Quantum Population, and Applications
leo/Zotero/storage/3DF8Z5A8/Bouman et Fehr - 2010 - Sampling in a Quantum Population, and Applications.pdf
Error Probability,Quantum Setting,Sampling Strategy,Security Proof,Trace Distance

New York, NY, USA

Association for Computing Machinery

abstractWe construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.
booktitleProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
seriesSTOC 2020
titlePost-Quantum Zero Knowledge in Constant Rounds
leo/Zotero/storage/SW3SC49L/Bitansky et Shmueli - 2020 - Post-quantum zero knowledge in constant rounds.pdf

abstractDue to the special no-cloning principle, quantum states appear to be very useful in cryptography. But this very same property also has drawbacks: when receiving a quantum state, it is nearly impossible for the receiver to efficiently check non-trivial properties on that state without destroying it. In this work, we initiate the study of Non-Destructive Zero-Knowledge Proofs on Quantum States. Our method binds a quantum state to a classical encryption of that quantum state. That way, the receiver can obtain guarantees on the quantum state by asking to the sender to prove properties directly on the classical encryption. This method is therefore non-destructive, and it is possible to verify a very large class of properties. For instance, we can force the sender to send different categories of states depending on whether they know a classical password or not. Moreover, we can also provide guarantees to the sender: for example, we can ensure that the receiver will never learn whether the sender knows the password or not. We also extend this method to the multi-party setting. We show how it can prove useful to distribute a GHZ state between different parties, in such a way that only parties knowing a secret can be part of this GHZ. Moreover, the identity of the parties that are part of the GHZ remains hidden to any malicious party. A direct application would be to allow a server to create a secret sharing of a qubit between unknown parties, authorized for example by a third party Certification Authority. Finally, we provide simpler "blind" versions of the protocols that could prove useful in Anonymous Transmission or Quantum Onion Routing, and we explicit a cryptographic function required in our protocols based on the Learning With Errors hardness problem.
titleNon-Destructive Zero-Knowledge Proofs on Quantum States, and Multi-Party Generation of Authorized Hidden GHZ States
leo/Zotero/storage/RCJH6QV8/Colisson et al. - 2021 - Non-Destructive Zero-Knowledge Proofs on Quantum S.pdf;/home/leo/Zotero/storage/5QNRTH4F/2104.html
y and Security,Cryptography,Me,Not published,Quantum Cryptography,Quantum Physics,Zero-Knowledge

New York, NY, USA

Association for Computing Machinery

abstractSecure multi-party computing, also called secure function evaluation, has been extensively studied in classical cryptography. We consider the extension of this task to computation with quantum inputs and circuits. Our protocols are information-theoretically secure, i.e. no assumptions are made on the computational power of the adversary. For the weaker task of verifiable quantum secret sharing, we give a protocol which tolerates any t ξ n/4 cheating parties (out of n). This is shown to be optimal. We use this new tool to show how to perform any multi-party quantum computation as long as the number of dishonest players is less than n/6.
booktitleProceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing
seriesSTOC '02
titleSecure Multi-Party Quantum Computation
leo/Zotero/storage/T4SWH4QD/Crépeau et al. - 2002 - Secure multi-party quantum computation.pdf;/home/leo/Zotero/storage/WPC7G76U/Crépeau et al. - 2002 - Secure multi-party quantum computation.pdf
y,secure function evaluation

abstractThere exist several graphical languages for quantum information processing, like quantum circuits, ZX-calculus, ZW-calculus, and so on. Each of these languages forms a †-symmetric monoidal category (†-SMC) and comes with an interpretation functor to the †-SMC of finite-dimensional Hilbert spaces. In recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of how to extend these languages beyond pure quantum mechanics to reason about mixed states and general quantum operations, i.e., completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map that allows one to get rid of a quantum system, an operation that is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction, which transforms any †-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction, we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However, this construction fails for some fringe cases like Clifford+T quantum mechanics, as the category does not have enough isometries.
journaltitleACM Transactions on Quantum Computing
shortjournalACM Transactions on Quantum Computing
titleCompleteness of Graphical Languages for Mixed State Quantum Mechanics
leo/Zotero/storage/JZHWYLTV/Carette et al. - 2021 - Completeness of Graphical Languages for Mixed   #xa0.pdf
anics,category theory,completely positive maps,mixed states,Quantum computing

Cambridge University Press

abstractThe unique features of the quantum world are explained in this book through the language of diagrams, setting out an innovative visual method for presenting complex theories. Requiring only basic mathematical literacy, this book employs a unique formalism that builds an intuitive understanding of quantum features while eliminating the need for complex calculations. This entirely diagrammatic presentation of quantum theory represents the culmination of ten years of research, uniting classical techniques in linear algebra and Hilbert spaces with cutting-edge developments in quantum computation and foundations. Written in an entertaining and user-friendly style and including more than one hundred exercises, this book is an ideal first course in quantum theory, foundations, and computation for students from undergraduate to PhD level, as well as an opportunity for researchers from a broad range of fields, from physics to biology, linguistics, and cognitive science, to discover a new set of tools for studying processes and interaction.
shorttitlePicturing Quantum Processes
titlePicturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning
leo/Zotero/storage/ACRTPLF2/Bob Coecke, Aleks Kissinger - Picturing Quantum Processes_ A First Course in Quantum Theory and Diagrammatic Reasoning (2017, Cambridge Uni.djvu;/home/leo/Zotero/storage/MX3QRG3Z/1119568B3101F3A685BE832FEEC53E52.html

abstractThe authors present some general techniques for establishing the cryptographic strength of a wide variety of games. As case studies, they analyze some weakened versions of the standard forms of oblivious transfer. They also consider variants of oblivious transfer that are motivated by coding theory and physics. Among their results, they show that a noisy telephone line is in fact a very sophisticated cryptographic device. They also present an application to quantum cryptography.$<>$
booktitle[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
eventtitle[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
titleAchieving Oblivious Transfer Using Weakened Security Assumptions
Circuits,Codes,Computer science,Computer security,Cryptographic protocols,Cryptography,Marine vehicles,Mathematics,Physics,Telephony

Berlin, Heidelberg

abstractWe consider two-party quantum protocols starting with a transmission of some random BB84 qubits followed by classical messages. We show a general “compiler” improving the security of such protocols: if the original protocol is secure against an “almost honest” adversary, then the compiled protocol is secure against an arbitrary computationally bounded (quantum) adversary. The compilation preserves the number of qubits sent and the number of rounds up to a constant factor. The compiler also preserves security in the bounded-quantum-storage model (BQSM), so if the original protocol was BQSM-secure, the compiled protocol can only be broken by an adversary who has large quantum memory and large computing power. This is in contrast to known BQSM-secure protocols, where security breaks down completely if the adversary has larger quantum memory than expected. We show how our technique can be applied to quantum identification and oblivious transfer protocols.
booktitleAdvances in Cryptology - CRYPTO 2009
seriesLecture Notes in Computer Science
titleImproving the Security of Quantum Protocols via Commit-and-Open
leo/Zotero/storage/22PRDHSB/Damgård et al. - 2009 - Improving the Security of Quantum Protocols via Co.pdf
Commitment Scheme,Computational Security,Oblivious Transfer,Quantum Protocol,Unconditional Security

Berlin, Heidelberg

abstractDelegating difficult computations to remote large computation facilities, with appropriate security guarantees, is a possible solution for the ever/growing needs of personal computing power. For delegated computation protocols to be usable in a larger context – or simply to securely run two protocols in parallel – the security definitions need to be composable. Here, we define composable security for delegated quantum computation. We distinguish between protocols which provide only blindness – the computation is hidden from the server – and those that are also verifiable – the client can check that it has received the correct result. We show that the composable security definition capturing both these notions can be reduced to a combination of several distinct “trace/distance/type” criteria – which are, individually, non/composable security definitions.Additionally, we study the security of some known delegated quantum computation protocols, including Broadbent, Fitzsimons and Kashefi’s Universal Blind Quantum Computation protocol. Even though these protocols were originally proposed with insufficient security criteria, they turn out to still be secure given the stronger composable definitions.
booktitleAdvances in Cryptology – ASIACRYPT 2014
seriesLecture Notes in Computer Science
titleComposable Security of Delegated Quantum Computation
leo/Zotero/storage/SRTZ9QGL/Dunjko et al. - 2014 - Composable Security of Delegated Quantum Computati.pdf
Full Version,Local Criterion,Physical Review Letter,Quantum Computation,Security Notion

Springer International Publishing

abstractThe cryptographic task of secure multi-party (classical) computation has received a lot of attention in the last decades. Even in the extreme case where a computation is performed between k mutually distrustful players, and security is required even for the single honest player if all other players are colluding adversaries, secure protocols are known. For quantum computation, on the other hand, protocols allowing arbitrary dishonest majority have only been proven for k=2k=2k=2. In this work, we generalize the approach taken by Dupuis, Nielsen and Salvail (CRYPTO 2012) in the two-party setting to devise a secure, efficient protocol for multi-party quantum computation for any number of players k, and prove security against up to k−1k−1k-1 colluding adversaries. The quantum round complexity of the protocol for computing a quantum circuit of {CNOT,T}{CNOT,T}\{\mathsf {CNOT}, \mathsf {T} \} depth d is O(k⋅(d+logn))O(k⋅(d+logn))O(k \cdot (d + \log n)), where n is the security parameter. To achieve efficiency, we develop a novel public verification protocol for the Clifford authentication code, and a testing protocol for magic-state inputs, both using classical multi-party computation.
booktitleAdvances in Cryptology – EUROCRYPT 2020
seriesLecture Notes in Computer Science
titleSecure Multi-party Quantum Computation with a Dishonest Majority
leo/Zotero/storage/7YFVF6BR/Dulek et al. - 2020 - Secure Multi-party Quantum Computation with a Dish.pdf

abstractComplexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class NP, referred to as stateQMA, which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an allpowerful but untrusted prover. This is a subclass of the class stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022), which permits polynomially many interactions between the prover and the verifier. Our main result consists of the basic properties of this class (as well as a variant with an exponentially small gap), such as error reduction, and its relationship to other fundamental state synthesizing classes, viz., states generated by uniform polynomial-time quantum circuits (stateBQP) and space-uniform polynomial-space quantum circuits (statePSPACE). Additionally, we demonstrate that stateQCMA is closed under perfect completeness. Our proof techniques are based on the quantum singular value transformation introduced by Gilyén, Su, Low, and Wiebe (STOC 2019), and its adaption to achieve exponential precision with a bounded space.
titleQuantum Merlin-Arthur Proof Systems for Synthesizing Quantum States
leo/Zotero/storage/NK5C6PHU/Delavenne et al. - 2023 - Quantum Merlin-Arthur proof systems for synthesizi.pdf

Berlin, Heidelberg

abstractWe provide the first two-party protocol allowing Alice and Bob to evaluate privately even against active adversaries any completely positive, trace-preserving map F∈L(Ain⊗Bin)→F∈L(Ain⊗Bin)→\mathscr {F} \in \mathrm {L}(\mathcal {A}_{{{\mathrm{in}}}} \otimes \mathcal {B}_{{{\mathrm{in}}}}) \rightarrow L(Aout⊗Bout)L(Aout⊗Bout)\mathrm {L}(\mathcal {A}_{{{\mathrm{out}}}} \otimes \mathcal {B}_{{{\mathrm{out}}}}), given as a quantum circuit, upon their joint quantum input state ρin∈D(Ain⊗Bin)ρin∈D(Ain⊗Bin)\rho _{\mathrm {in}}\in \mathrm{D}({\mathcal {A}_{{{\mathrm{in}}}} \otimes \mathcal {B}_{{{\mathrm{in}}}}}). Our protocol leaks no more to any active adversary than an ideal functionality for FF\mathscr {F} provided Alice and Bob have the cryptographic resources for active secure two-party classical computation. Our protocol is constructed from the protocol for the same task secure against specious adversaries presented in [4].
booktitleAdvances in Cryptology – CRYPTO 2012
seriesLecture Notes in Computer Science
titleActively Secure Two-Party Evaluation of Any Quantum Operation
leo/Zotero/storage/7WTY4KY7/Dupuis et al. - 2012 - Actively Secure Two-Party Evaluation of Any Quantu.pdf
Active Security,Authentication Code,Ideal Functionality,QMPC,Quantum Circuit,Quantum Operation

abstractRandomized protocols for signing contracts, certified mail, and flipping a coin are presented. The protocols use a 1-out-of-2 oblivious transfer subprotocol which is axiomatically defined. The 1-out-of-2 oblivious transfer allows one party to transfer exactly one secret, out of two recognizable secrets, to his counterpart. The first (second) secret is received with probability one half, while the sender is ignorant of which secret has been received. An implementation of the 1-out-of-2 oblivious transfer, using any public key cryptosystem, is presented.
journaltitleCommunications of the ACM
shortjournalCommun. ACM
titleA Randomized Protocol for Signing Contracts
leo/Zotero/storage/7ZHW7YK2/Even et al. - 1985 - A randomized protocol for signing contracts.pdf
family=ELECTRIC COIN COMPANY,

abstractZcash is a digital currency with strong privacy features. Transact efficiently and safely, with low fees, while ensuring digital transactions remain private. Selectively disclose address and transaction details for information sharing, auditing or regulatory compliance.
titleZcash: Privacy-protecting Digital Currency

New York, NY, USA

Association for Computing Machinery

booktitleProceedings of the Twenty-First Annual ACM Symposium on Theory of Computing
seriesSTOC '89
titleA Hard-Core Predicate for All One-Way Functions
leo/Zotero/storage/JPV5GFMM/Goldreich et Levin - 1989 - A hard-core predicate for all one-way functions.pdf

Springer International Publishing

abstractMiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achieves simulation-security in the plain model against malicious quantum polynomial-time adversaries, building on the foundational work of Crépeau and Killian (FOCS 1988) and Bennett, Brassard, Crépeau and Skubiszewska (CRYPTO 1991). Combining the OT protocol with prior works, we obtain secure two-party and multi-party computation protocols also in MiniQCrypt. This is in contrast to the classical world, where it is widely believed that one-way functions alone do not give us OT.In the common random string model, we achieve a constant-round universally composable (UC) OT protocol.
booktitleAdvances in Cryptology – EUROCRYPT 2021
seriesLecture Notes in Computer Science
titleOblivious Transfer Is in MiniQCrypt
leo/Zotero/storage/9JEE5DC9/Grilo et al. - 2021 - Oblivious Transfer Is in MiniQCrypt.pdf

New York, NY, USA

Association for Computing Machinery

booktitleProceedings of the Seventeenth Annual ACM Symposium on Theory of Computing
seriesSTOC '85
titleThe Knowledge Complexity of Interactive Proof-Systems
leo/Zotero/storage/CTAHEHL4/Goldwasser et al. - 1985 - The knowledge complexity of interactive proof-syst.pdf;/home/leo/Zotero/storage/REMCANVG/goldwasser1985.pdf.pdf

New York, NY, USA

Association for Computing Machinery

abstractWe present a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest. Our algorithm automatically solves all the multi-party protocol problems addressed in complexity-based cryptography during the last 10 years. It actually is a completeness theorem for the class of distributed protocols with honest majority. Such completeness theorem is optimal in the sense that, if the majority of the players is not honest, some protocol problems have no efficient solution [C].
booktitleProceedings of the Nineteenth Annual ACM Symposium on Theory of Computing
seriesSTOC '87
titleHow to Play ANY Mental Game

Berlin, Heidelberg

abstractCryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these protocols, however, deals almost exclusively with classical attackers. If we accept that quantum information processing is the most realistic model of physically feasible computation, then we must ask: what classical protocols remain secure against quantum attackers?Our main contribution is showing the existence of classical two-party protocols for the secure evaluation of any polynomial-time function under reasonable computational assumptions (for example, it suffices that the learning with errors problem be hard for quantum polynomial time). Our result shows that the basic two-party feasibility picture from classical cryptography remains unchanged in a quantum world.
booktitleAdvances in Cryptology – CRYPTO 2011
seriesLecture Notes in Computer Science
titleClassical Cryptographic Protocols in a Quantum World
leo/Zotero/storage/3TFKFIVG/Hallgren et al. - 2011 - Classical Cryptographic Protocols in a Quantum Wor.pdf;/home/leo/Zotero/storage/57FXZMRH/Hallgren et al. - 2015 - Classical Cryptographic Protocols in a Quantum Wor.pdf
Classical Protocol,Common Reference String,Oblivious Transfer,Quantum Protocol,Quantum World

abstractThe structural theory of average-case complexity, introduced by Levin (1986), gives a formal setting for discussing the types of inputs for which a problem is difficult. This is vital to understanding both when a seemingly difficult (e.g. NP-complete) problem is actually easy on almost all instances, and to determining which problems might be suitable for applications requiring hard problems, such as cryptography. The paper attempts to summarize the state of knowledge in this area, including some "folklore" results that have not explicitly appeared in print. We also try to standardize and unify definitions. Finally, we indicate what we feel are interesting research directions. We hope that the paper motivates more research in this area and provide an introduction to the area for people new to it.
booktitleProceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference
eventtitleProceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference
titleA Personal View of Average-Case Complexity
Bibliographies,Complexity theory,Computer science,Cryptography,Distributed computing,Drives

Springer International Publishing

abstractWe propose the concept of pseudorandom quantum states, which appear random to any quantum polynomial-time adversary. It offers a computational approximation to perfectly random quantum states analogous in spirit to cryptographic pseudorandom generators, as opposed to statistical notions of quantum pseudorandomness that have been studied previously, such as quantum t-designs analogous to t-wise independent distributions.
booktitleAdvances in Cryptology – CRYPTO 2018
seriesLecture Notes in Computer Science
titlePseudorandom Quantum States
leo/Zotero/storage/3X5NSBPW/Ji et al. - 2018 - Pseudorandom Quantum States.pdf

abstractThe standard inputs given to a quantum machine are classical binary strings. In this view, any quantum complexity class is a collection of subsets of {0, 1}∗. However, a quantum machine can also accept quantum states as its input. T. Yamakami has introduced a general framework for quantum operators and inputs [18]. In this paper we present several quantum languages within this model and by generalizing the complexity classes QMA and QCMA we analyze the complexity of the introduced languages. We also discuss how to derive a classical language from a given quantum language and as a result we introduce new QCMA and QMA languages.
titleOn the Complexity of Quantum Languages
leo/Zotero/storage/4SZLKR28/Kashefi et Alves - 2004 - On the Complexity of Quantum Languages.pdf
Quantum Physics

New York, NY, USA

Association for Computing Machinery

abstractSuppose your netmail is being erratically censored by Captain Yossarian. Whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. Well versed in such concepts as redundancy, this is no real problem to you. The question is, can it actually be turned around and used to your advantage? We answer this question strongly in the affirmative. We show that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol, known as oblivious circuit evaluation([Y]). We also show that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in NP. These results do not use any complexity-theoretic assumptions. We can show that they have applications to a variety of models in which oblivious transfer can be done.
booktitleProceedings of the Twentieth Annual ACM Symposium on Theory of Computing
seriesSTOC '88
titleFounding Crytpography on Oblivious Transfer
leo/Zotero/storage/H3XN3PGA/Kilian - 1988 - Founding crytpography on oblivious transfer.pdf

abstractMulti-Party Quantum Computation (MPQC) has attracted a lot of attention as a potential killer-app for quantum networks through it's ability to preserve privacy and integrity of the highly valuable computations they would enable. Contributing to the latest challenges in this field, we present a composable protocol achieving blindness and verifiability even in the case of a single honest client. The security of our protocol is reduced, in an information-theoretically secure way, to that of a classical composable Secure Multi-Party Computation (SMPC) used to coordinate the various parties. Our scheme thus provides a statistically secure upgrade of such classical scheme to a quantum one with the same level of security. In addition, (i) the clients can delegate their computation to a powerful fully fault-tolerant server and only need to perform single qubit operations to unlock the full potential of multi-party quantum computation; (ii) the amount of quantum communication with the server is reduced to sending quantum states at the beginning of the computation and receiving the output states at the end, which is optimal and removes the need for interactive quantum communication; and (iii) it has a low constant multiplicative qubit overhead compared to the single-client delegated protocol it is built upon. The main technical ingredient of our paper is the bootstraping of the MPQC construction by Double Blind Quantum Computation, a new composable resource for blind multiparty quantum computation, that demonstrates the surprising fact that the full protocol does not require verifiability of all components to achieve security.
titleDelegating Multi-Party Quantum Computations vs. Dishonest Majority in Two Quantum Rounds
leo/Zotero/storage/2L4MXWV5/Kapourniotis et al. - 2021 - Delegating Multi-Party Quantum Computations vs. Di.pdf;/home/leo/Zotero/storage/844WNPNZ/Kapourniotis et al. - 2021 - Delegating Multi-Party Quantum Computations vs. Di.pdf;/home/leo/Zotero/storage/ET5EP5WS/Kapourniotis et al. - 2021 - Delegating Multi-Party Quantum Computations vs. Di.pdf;/home/leo/Zotero/storage/BWB3ELK8/2102.html;/home/leo/Zotero/storage/F8AHZDAG/2102.html;/home/leo/Zotero/storage/ZV4SKTEC/2102.html

Multidisciplinary Digital Publishing Institute

abstractQuantum computing has seen tremendous progress in the past few years. However, due to limitations in the scalability of quantum technologies, it seems that we are far from constructing universal quantum computers for everyday users. A more feasible solution is the delegation of computation to powerful quantum servers on the network. This solution was proposed in previous studies of blind quantum computation, with guarantees for both the secrecy of the input and of the computation being performed. In this work, we further develop this idea of computing over encrypted data, to propose a multiparty delegated quantum computing protocol in the measurement-based quantum computing framework. We prove the security of the protocol against a dishonest server and against dishonest clients, under the assumption of common classical cryptographic constructions.
titleMultiparty Delegated Quantum Computing
leo/Zotero/storage/EV7NG8CZ/Kashefi et Pappa - 2017 - Multiparty Delegated Quantum Computing.pdf;/home/leo/Zotero/storage/WUCCK699/12.html
y,secure multiparty quantum computation

Berlin, Heidelberg

abstractZero-knowledge proofs with witness elimination are protocols that enable a prover to demonstrate knowledge of a witness to the verifier that accepts the interaction provided that the witness is valid for a given statement and additionally the witness does not belong to a set of eliminated witnesses. This set is determined by a public relation Q (that parameterizes the primitive) and the private input of the verifier. Zero-knowledge proofs with witness elimination thus call for a relaxation of the zero-knowledge property and are relevant in settings where a statement has a multitude of witnesses that may attest to its validity. A number of interesting issues arise in the design of such protocols that include whether a protocol transcript enables the verifier to test for witness after termination (something akin to an “offline dictionary attack”) and whether the prover should be capable of understanding whether her witness is eliminated. The primitive is motivated by the setting of identification schemes where a user wishes to authenticate herself to an access point while preserving her anonymity and the access point needs to certify that the user is eligible while at the same time making sure she does not match the identity of a suspect user that is tracked by the authorities. We call such primitives anonymous identification schemes with suspect tracking.
booktitlePublic Key Cryptography – PKC 2009
seriesLecture Notes in Computer Science
titleZero-Knowledge Proofs with Witness Elimination
leo/Zotero/storage/V2EXN4K6/Kiayias et Zhou - 2009 - Zero-Knowledge Proofs with Witness Elimination.pdf
Dictionary Attack,Elimination Relation,Encryption Scheme,Honest Party,Oblivious Transfer

abstractIn this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all $\mathcal {NP}$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO, 1989). However, the existence of constant-round zero-knowledge proofs of knowledge for all $\mathcal {NP}$is folklore, to the best of our knowledge, since no proof of this fact has been published.
journaltitleJournal of Cryptology
shortjournalJ Cryptol
titleA Note on Constant-Round Zero-Knowledge Proofs of Knowledge
leo/Zotero/storage/6AYRXUNM/Lindell - 2013 - A Note on Constant-Round Zero-Knowledge Proofs of .pdf
eme,Hamiltonian Cycle,Hamiltonian Cycle Problem,Honest Prover,Proof System

abstractA major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it. This is especially problematic in the context of zero-knowledge simulation, where preserving the adversary's state is essential. In this work, we develop new techniques for quantum rewinding in the context of extraction and zero-knowledge simulation: (1) We show how to extract information from a quantum adversary by rewinding it without disturbing its internal state. We use this technique to prove that important interactive protocols, such as the Goldreich-Micali-Wigderson protocol for graph non-isomorphism and the Feige-Shamir protocol for NP, are zero-knowledge against quantum adversaries. (2) We prove that the Goldreich-Kahan protocol for NP is post-quantum zero knowledge using a simulator that can be seen as a natural quantum extension of the classical simulator. Our results achieve (constant-round) black-box zero-knowledge with negligible simulation error, appearing to contradict a recent impossibility result due to Chia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution: (3) We introduce coherent-runtime expected quantum polynomial time, a computational model that (a) captures all of our zero-knowledge simulators, (b) cannot break any polynomial hardness assumptions, and (c) is not subject to the CCLY impossibility. In light of our positive results and the CCLY negative results, we propose coherent-runtime simulation to be the right quantum analogue of classical expected polynomial-time simulation.
shorttitlePost-Quantum Zero Knowledge, Revisited (Or
titlePost-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)
Computer Science - Cryptography and Security,Quantum Physics

American Physical Society

abstractIt had been widely claimed that quantum mechanics can protect private information during public decision in, for example, the so-called two-party secure computation. If this were the case, quantum smart-cards, storing confidential information accessible only to a proper reader, could prevent fake teller machines from learning the PIN (personal identification number) from the customers’ input. Although such optimism has been challenged by the recent surprising discovery of the insecurity of the so-called quantum bit commitment, the security of quantum two-party computation itself remains unaddressed. Here I answer this question directly by showing that all one-sided two-party computations (which allow only one of the two parties to learn the result) are necessarily insecure. As corollaries to my results, quantum one-way oblivious password identification and the so-called quantum one-out-of-two oblivious transfer are impossible. I also construct a class of functions that cannot be computed securely in any two-sided two-party computation. Nevertheless, quantum cryptography remains useful in key distribution and can still provide partial security in “quantum money” proposed by Wiesner.
journaltitlePhysical Review A
shortjournalPhys. Rev. A
titleInsecurity of Quantum Secure Computations
leo/Zotero/storage/ZJN3ZTED/Lo - 1997 - Insecurity of quantum secure computations.pdf;/home/leo/Zotero/storage/7ZS7MD7G/PhysRevA.56.html

eventtitleCybernetica As
titleReview of the State of the Art in Secure Multiparty Computation

abstractShows that the BBCS-protocol (Bennett, Brassard, Cre/spl acute/peau and Skubiszewska, CRYPTO'91, 1992) implementing one of the most important cryptographic primitives-'oblivious transfer'-is secure against any individual measurement allowed by quantum mechanics. We analyze the common situation where successive measurements on the same photon could be used to cheat in the protocol. We model this situation by using a single inner-product-preserving (IPP) operator, followed by a complete composite-outcome Von Neumann measurement. A lower bound on the residual collision entropy is then obtained under the assumption that only individual measurements can be performed. This bound is used to apply privacy amplification techniques in order to conclude the security of the BBCS-protocol.$<>$
booktitleProceedings Workshop on Physics and Computation. PhysComp '94
eventtitleProceedings Workshop on Physics and Computation. PhysComp '94
titleQuantum Oblivious Transfer Is Secure against All Individual Measurements
Cryptographic protocols,Cryptography,Entropy,Information security,Information theory,Mechanical variables measurement,Polarization,Privacy,Prototypes,Quantum mechanics

abstractComplexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomial-time quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE $\subseteq$ stateQIP. Our main result is the reverse inclusion, stateQIP $\subseteq$ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving exponentially large "PSPACE-computable" semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent block-encoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory. Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann's theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.
titlestateQIP = statePSPACE
023 - stateQIP = statePSPACE.pdf

Cambridge University Press

abstractOne of the most cited books in physics of all time, Quantum Computation and Quantum Information remains the best textbook in this exciting field of science. This 10th anniversary edition includes an introduction from the authors setting the work in context. This comprehensive textbook describes such remarkable effects as fast quantum algorithms, quantum teleportation, quantum cryptography and quantum error-correction. Quantum mechanics and computer science are introduced before moving on to describe what a quantum computer is, how it can be used to solve problems faster than 'classical' computers and its real-world implementation. It concludes with an in-depth treatment of quantum information. Containing a wealth of figures and exercises, this well-known textbook is ideal for courses on the subject, and will interest beginning graduate students and researchers in physics, computer science, mathematics, and electrical engineering.
journaltitleHigher Education from Cambridge University Press
shorttitleQuantum Computation and Quantum Information
titleQuantum Computation and Quantum Information: 10th Anniversary Edition
leo/Zotero/storage/E54FNEDQ/Nielsen et Chuang - 2010 - Quantum Computation and Quantum Information 10th .pdf;/home/leo/Zotero/storage/SQ32D94V/01E10196D0A682A6AEFFEA52D53BE9AE.html

Springer International Publishing

abstractWe finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the plain Learning With Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates the framework recently developed by Canetti et al.  [EUROCRYPT’18], Holmgren and Lombardi [FOCS’18], and Canetti et al.  [STOC’19] for soundly applying the Fiat–Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on “exotic” assumptions (e.g., indistinguishability obfuscation or optimal hardness of certain LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption (FHE). However, none of these assumptions are known to be implied by plain LWE or worst-case hardness.
booktitleAdvances in Cryptology – CRYPTO 2019
seriesLecture Notes in Computer Science
titleNoninteractive Zero Knowledge for NP from (Plain) Learning with Errors
leo/Zotero/storage/JNT92J2F/Peikert et Shiehian - 2019 - Noninteractive Zero Knowledge for NP from (Plain) .pdf

Berlin, Heidelberg

abstractWe propose a simple and general framework for constructing oblivious transfer (OT) protocols that are efficient, universally composable, and generally realizable under any one of a variety of standard number-theoretic assumptions, including the decisional Diffie-Hellman assumption, the quadratic residuosity and decisional composite residuosity assumptions, and worst-case lattice assumptions.
booktitleAdvances in Cryptology – CRYPTO 2008
seriesLecture Notes in Computer Science
titleA Framework for Efficient and Composable Oblivious Transfer
leo/Zotero/storage/EAN9AZEC/Peikert et al. - 2008 - A Framework for Efficient and Composable Oblivious.pdf
Common Reference String,Decryption Mode,Oblivious Transfer,Oblivious Transfer Protocol,Security Parameter

Springer International Publishing

abstractWe build a two-round, UC-secure oblivious transfer protocol (OT) in the common reference string (CRS) model under the Learning with Errors assumption (LWE) with super-polynomial modulus-to-noise ratio. We do so by instantiating the dual-mode encryption framework of Peikert, Vaikuntanathan and Waters (CRYPTO’08). The resulting OT can be instantiated in either one of two modes: one providing statistical sender security, and the other statistical receiver security. Furthermore, our scheme allows the sender and the receiver to reuse the CRS across arbitrarily many executions of the protocol. To our knowledge, this is the first construction of an UC-secure OT from LWE that achieves either statistical receiver security or unbounded reusability of the CRS. For comparison, the construction of UC-secure OT from LWE of Peikert, Vaikuntanathan and Waters only provides computational receiver security and bounded reusability of the CRS.
booktitleSecurity and Cryptography for Networks
seriesLecture Notes in Computer Science
titleUC-Secure OT from LWE, Revisited
leo/Zotero/storage/UK85FVW2/Quach - 2020 - UC-Secure OT from LWE, Revisited.pdf

abstractThe original paper does not have an abstract. This is a scanned version of the original hand written manuscript of this paper. It appeared in print as a Harvard University Technical Report, but at some point the university ran out of copies. At that time copies of the hand written version started to circulate, and were the only ones available. As access to these copies has become difficult I have scanned my copy of the paper and I'm posting it on the web for others to read. *Note that the manuscript has a different title, but the paper is most commonly (if not only) cited with this title. Thus, I assume that it should continue to be cited in this manner with reference to the original technical report.Scanned and typeset version produced by Tal Rabin and Mohammad Sadeq Dousti.
titleHow To Exchange Secrets with Oblivious Transfer
Oblivious Transfer

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

booktitle13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA
titleInteractive Proofs for Synthesizing Quantum States and Unitaries
leo/Zotero/storage/AFM3AILM/Rosenthal et Yuen - 2022 - Interactive proofs for synthesizing quantum states.pdf

abstractQuantum cryptography is the field of cryptography that explores the quantum properties of matter. Generally, it aims to develop primitives beyond the reach of classical cryptography and to improve existing classical implementations. Although much of the work in this field covers quantum key distribution (QKD), there have been some crucial steps towards the understanding and development of quantum oblivious transfer (QOT). One can show the similarity between the application structure of both QKD and QOT primitives. Just as QKD protocols allow quantum-safe communication, QOT protocols allow quantum-safe computation. However, the conditions under which QOT is fully quantum-safe have been subject to intense scrutiny and study. In this review article, we survey the work developed around the concept of oblivious transfer within theoretical quantum cryptography. We focus on some proposed protocols and their security requirements. We review the impossibility results that daunt this primitive and discuss several quantum security models under which it is possible to prove QOT security.
shorttitleQuantum Oblivious Transfer
titleQuantum Oblivious Transfer: A Short Review
Quantum Physics

Berlin, Heidelberg

abstractThe Universal Composability model (UC) by Canetti (FOCS 2001) allows for secure composition of arbitrary protocols. We present a quantum version of the UC model which enjoys the same compositionality guarantees. We prove that in this model statistically secure oblivious transfer protocols can be constructed from commitments. Furthermore, we show that every statistically classically UC secure protocol is also statistically quantum UC secure. Such implications are not known for other quantum security definitions. As a corollary, we get that quantum UC secure protocols for general multi-party computation can be constructed from commitments.
booktitleAdvances in Cryptology – EUROCRYPT 2010
seriesLecture Notes in Computer Science
titleUniversally Composable Quantum Multi-party Computation
leo/Zotero/storage/CRWSJ64W/Unruh - 2010 - Universally Composable Quantum Multi-party Computa.pdf
Commitment Scheme,Computational Basis,Oblivious Transfer,Quantum Protocol,Quantum Setting

Berlin, Heidelberg

abstractWe motivate, define and construct quantum proofs of knowledge, proofs of knowledge secure against quantum adversaries. Our constructions are based on a new quantum rewinding technique that allows us to extract witnesses in many classical proofs of knowledge. We give criteria under which a classical proof of knowledge is a quantum proof of knowledge. Combining our results with Watrous’ results on quantum zero-knowledge, we show that there are zero-knowledge quantum proofs of knowledge for all languages in NP (assuming quantum 1-1 one-way functions).
booktitleAdvances in Cryptology – EUROCRYPT 2012
seriesLecture Notes in Computer Science
titleQuantum Proofs of Knowledge
leo/Zotero/storage/IY2GQZEN/Unruh - 2012 - Quantum Proofs of Knowledge.pdf
Auxiliary Input,Commitment Scheme,Hamiltonian Cycle,Oracle Access,Proof System

Berlin, Heidelberg

abstractWe present a construction for non-interactive zero-knowledge proofs of knowledge in the random oracle model from general sigma-protocols. Our construction is secure against quantum adversaries. Prior constructions (by Fiat-Shamir and by Fischlin) are only known to be secure against classical adversaries, and Ambainis, Rosmanis, Unruh (FOCS 2014) gave evidence that those constructions might not be secure against quantum adversaries in general.
booktitleAdvances in Cryptology - EUROCRYPT 2015
seriesLecture Notes in Computer Science
titleNon-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model
leo/Zotero/storage/WICZKTG8/Unruh - 2015 - Non-Interactive Zero-Knowledge Proofs in the Quant.pdf
Proof System,Query Input,Random Oracle,Random Oracle Model,Signature Scheme

abstractThe ZX-calculus is a graphical language for reasoning about quantum computation that has recently seen an increased usage in a variety of areas such as quantum circuit optimisation, surface codes and lattice surgery, measurement-based quantum computation, and quantum foundations. The first half of this review gives a gentle introduction to the ZX-calculus suitable for those familiar with the basics of quantum computing. The aim here is to make the reader comfortable enough with the ZX-calculus that they could use it in their daily work for small computations on quantum circuits and states. The latter sections give a condensed overview of the literature on the ZX-calculus. We discuss Clifford computation and graphically prove the Gottesman-Knill theorem, we discuss a recently introduced extension of the ZX-calculus that allows for convenient reasoning about Toffoli gates, and we discuss the recent completeness theorems for the ZX-calculus that show that, in principle, all reasoning about quantum computation can be done using ZX-diagrams. Additionally, we discuss the categorical and algebraic origins of the ZX-calculus and we discuss several extensions of the language which can represent mixed states, measurement, classical control and higher-dimensional qudits.
titleZX-calculus for the Working Quantum Computer Scientist
leo/Zotero/storage/ZY35RJC6/van de Wetering - 2020 - ZX-calculus for the working quantum computer scien.pdf;/home/leo/Zotero/storage/LFUZAV6Q/2012.html
ed,Quantum Physics,Reviews,ZX-Calculus

Society for Industrial and Applied Mathematics