---
abstract: 'The application and analysis of the Cut-and-Choose technique in protocols secure against quantum adversaries is not a straightforward transposition of the classical case, among other reasons due to the difficulty to use “rewinding” in the quantum realm. We introduce a Quantum Computation Cut-and-Choose (QC-CC) technique which is a generalisation of the classical Cut-and-Choose in order to build quantum protocols secure against *quantum covert adversaries*. Such adversaries can essentially deviate arbitrarily provided that their deviation is not detected with high probability. As an application of the QC-CC technique we give a protocol for securely performing a two-party quantum computation with classical input and output. As a basis we use the concept of secure delegated quantum computing [@bfk], and in particular the protocol for quantum garbled circuit computation of [@KW16] that has been proven secure against only a weak specious adversaries (defined in [@DNS10]). A unique property of these protocols is the separation between classical and quantum communications and the asymmetry between client and server, which enables us to sidestep the issues linked to quantum rewinding. This opens the possibility of applying the QC-CC technique to other quantum protocols that have this separation. In our proof of security we adapt and use (at different parts of the proof) two quantum rewinding techniques, namely Watrous’ oblivious quantum rewinding [@Wat09] and Unruh’s special quantum rewinding [@Unr12]. Our protocol achieves the same functionality as in the previous work on secure two-party quantum computing such as the one in [@DNS12], however using the Cut-and-Choose technique on the protocol from [@KW16] leads to the following key improvements: (i) only one-way offline quantum communication is necessary , (ii) only one party (server) needs to have involved quantum technological abilities, (iii) only minimal extra cryptographic primitives are required, namely one oblivious transfer for each input bit and quantum-safe commitments.'
author:
- 'Elham Kashefi$^{1,2}$, Luka Music$^2$ and Petros Wallden$^1$'
bibliography:
- 'biblio.bib'
title: 'The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation'
---

Introduction
============

A key task in modern cryptography is to compute a function of many inputs given by different parties that do not trust each other and wish to maintain the privacy of their input. This is called secure multi-party computation (to name some examples: millionaire’s problem, coin tossing, voting schemes, etc). The field started with the seminal paper of Yao [@Yao86], where two-parties that do not trust each other (they are “honest-but-curious”) compute a function of their joint inputs. This protocol was later made secure against malicious adversaries by employing standard (classical) techniques for boosting the security of honest-but-curious protocols to the malicious adversarial setting (e.g. using the GMW compiler as in [@GMW87]). Another such technique is the Cut-and-Choose technique first used in this context in [@LinPin07].

The quantum analogue (secure two-party quantum computation, or 2PQC) involves the computation of a function using a quantum computer and was first examined in [@DNS10] for a quantum honest-but-curious adversaries (called specious) and later made secure against more malicious adversaries in [@DNS12]. The latter protocol, did not use any of the standard boosting classical techniques, but instead used a stepwise quantum authentication protocol, where two-ways online quantum communication was required. Moreover, both protocols use extra classical cryptographic primitives, which in the case of the malicious [@DNS12] is a full actively secure *classical* two-party computation primitive.

The use of classical boosting techniques (such as Cut-and-Choose) for quantum protocols is complicated not only because specific care is needed when defining quantum analogues, for example, for garbled circuits but also for technical reasons since the rewinding method for proving security cannot be directly used in quantum protocols (as demonstrated for zero knowledge proofs [@Wat09] and zero knowledge proofs of knowledge [@Unr12]).

#### Our Contribution

1.  We introduce a Quantum Computation Cut-and-Choose technique. Application of this technique is made possible because of the unique decomposition of quantum computation into a classical control and a quantum resource in the measurement-based quantum computing models such as gate teleportation. This separation furthermore provides a platform for a client-server setting for secure delegated computing [@bfk].

2.  We give a protocol for 2PQC with classical input and output[^1] which is secure against “quantum covert” adversaries, a notion of strong adversaries similar with the classical covert adversaries [@AumLin07] (see below for formal definition and motivation). We use the aforementioned QC-CC technique and address the subtleties in the security proof due to rewinding. Our protocol, which builds on the work of [@KW16] that gave a protocol for 2PQC secure against weak specious adversaries, resembles the original protocol by Yao [@Yao86] (e.g. asymmetry between the two parties) and in particular the one in [@LinPin07], where Yao’s protocol is boosted to the malicious case using the classical Cut-and-Choose technique.

3.  A key obstruction when using classical techniques for boosting the security of quantum protocols is that in general rewinding the *quantum* adversary during the simulation is *not* possible. There are two known cases where rewinding can be used for quantum adversaries, namely Watrous’ oblivious rewinding [@Wat09] and Unruh’s special rewinding [@Unr12]. We adapt and use both methods in different places in order to construct the simulators and prove the security of our protocol. This is one of the few protocols in which quantum rewinding is explicitly used and the only one, to our knowledge, that uses two types of quantum rewinding.

4.  [@DNS12; @DNS10] describe 2PQC protocols in a setting where the two parties are symmetric. Our protocol crucially differs in a number of points (other than using the Cut-and-Choose technique): (i) There is only one-way offline quantum communication between the parties, (ii) only one party (“server”) needs involved quantum technological abilities, while the other (“client”) only needs to prepare offline single qubits, (iii) minimal classical cryptographic primitives are required, namely oblivious transfer for input bits and quantum-safe commitments.

In Section \[prelims\] we present background material and introduce the notion of *quantum covert adversaries* (similarly with [@AumLin07]). In Section \[quantum cc\] we introduce the quantum-computation Cut-and-Choose technique. In Section \[prot\] we give the protocol for 2PQC and prove its security in Appendix \[sec proofs\].

#### Related works.

The field of secure two (and multi) party (classical) computation started with Yao’s paper [@Yao86], which was proven secure against malicious adversaries in [@GMW87] using generic Zero-Knowledge proofs and in [@LinPin07] with the Cut-and-Choose technique. Covert adversaries were introduced in [@AumLin07] where again the Cut-and-Choose technique was used to achieve an even more efficient protocol. Yao’s protocol has been used for a number of other functionalities, such as constructing non-interactive verifiable computing [@GGB10]. In the early days of quantum computation, researchers believed that quantum properties could lead to a breakthrough and achieve, with unconditional security, several (clasical) multi-party cryptographic primitives. However a series of no-go theorems, first proving that bit commitment is impossible [@commit1; @commit2] , then oblivious transfer [@OT_nogo] and finally [@SSS09] showed that any non-trivial functionality leaks some information to adversaries. Since then, it is established that any such protocol is either only computationally secure or requires the existence of certain (quantum secure) simple cryptographic primitives.

Closely related is the question of what assumptions are required if one wants to perform a secure *quantum* computation involving multiple parties. The case of 2PQC was addressed in [@DNS10] for quantum honest-but-curious and in [@DNS12] for malicious adversaries. The case of multiple parties was addressed in [@Ben-Or2006; @multipartyqc] where an honest majority was required.

In this work we use as basis the universal blind quantum computation protocol [@bfk] and its verifiable version [@fk]. For the case of weak specious adversaries, the 2PQC was addressed in [@KW16] while the multiparty quantum computation was also addressed in [@KP16], again in a restricted setting. While we use measurement-based quantum computation (MBQC) [@onewaycomputer], similar blind and verification protocols exist in the teleportation model [@B2015] and 2PQC or MPQC protocols could be explored for that case as well as other blind verification protocols such as [@hm2015].

Preliminaries and Security Definitions {#prelims}
======================================

Verifiable Blind Quantum Computation
------------------------------------

The model for quantum computations used in our contribution is MBQC [@onewaycomputer]. In this section we introduce MBQC and revise protocols for blind quantum computation (server performs computation without learning input/output or computation) [@bfk] and verifiable blind quantum computation (client can also verify that the computation was performed correctly) [@fk] which are based on it.

The MBQC model of computation is equivalent to the circuit model as it is based on the gate teleportation principle. One starts with a large, generic entangled state (represented by a graph) and, by choosing suitable single qubit measurements, can perform any quantum computation (circuit). The computation is fully characterised by the graph and default measurement angles (see below) and is called a measurement pattern. See an example of a universal set of gates expressed as MBQC measurement patterns in Appendix \[example mbqc\].

For our purpose it will be simpler to consider a client-server setting. The client can prepare single qubits while the server can perform any general quantum computation. The client prepares and sends qubits in the $\ket{+}$ state and the server entangles them according to a certain computation graph by performing $\mathrm{controlled-}Z$ gates between all qubits corresponding to adjacent vertices on the graph, resulting in a *graph state* (details can be found in [@hein2004multiparty]). The computation is defined by a default measurement angle $\phi_i$ (which depends only on the desired computation). It is carried out by having the server measure single qubits in an order defined by the flow. The actual angle of each measurement depends on $\phi_i$ and on the outcomes of previous measurements. In our setting, the client is responsible for these classical calculations to adjust the angle and therefore the server returns to the client the result of each measurement, for more details see [@bfk].

Let $I$ and $O$ be respectively the sets of input and output qubits. A flow is defined by a function ($f : O^c \rightarrow I^c$) from measured qubits to non-input qubits and a partial order $(\preceq)$ over the vertices of the graph such that $\forall i, i \preceq f(i)$ and $\forall j \in N_G(i), f(i) \preceq j$, where $N_G(i)$ denotes the neighbours of $i$ in graph $G$. Each qubit $i$ is $X$-dependent on $X_i = f^{-1}(i)$ and $Z$-dependent on all qubits $j$ such that $i \in N_G(j)$ (this set is called $Z_i$). The existence of such a flow in all the graphs used for computations in MBQC patterns guarantees that the number of dependencies does not blow up. Given the sets $X_i$ and $Z_i$ the computation angle for qubit $i$ needs to be adjusted as such : let $s_i^X = \oplus_{j \in D_i^X} s_j$ and $s_i^Z = \oplus_{j \in D_i^Z} s_j$, where $s_j$ corresponds to the outcome of the measurement on qubit $j$ and $D_i^X$ and $D_i^Z$ are subsets of $X_i$ and $Z_i$ respectively (these qubits in $D_i^X$ and $D_i^Z$ have all already been measured as they belong to the past neighbours and past neighbours of past neighbours, see the flow construction in [@DK2006]). Then the corrected angle (the one that is actually measured) is $\phi'_i = (-1)^{s_i^X}\phi_i + s_i^Z\pi$.

The computation can be totally hidden from the server due to the following observation: if instead of sending $\ket{+}$ states the client chooses at random and sends $\ket{+_\theta}=1/\sqrt{2}(\ket{0}+e^{i\theta}\ket{1})$ with $\theta \in \{0, \pi/8, 2\cdot\pi/8,\ldots, 7\cdot\pi/8\}$ then measuring the qubits in a similarly rotated basis has the same result as the initial non-rotated computation. If the client keeps the angle $\theta$ hidden from the server, the server is completely blind on what computation is being performed. To ensure that no information is leaked from the measurement outcome, we add another parameter $r_i$ for each qubit, which serves as a One-Time-Pad for the measurement outcome. The resulting measurement angle with all parameters taken into account is then $\delta_i = C(\phi_i, s_i^X, s_i^Z, \theta_i, r_i) = \phi'_i(\phi_i, s_i^X, s_i^Z) + \theta_i + r_i\pi$. In short, the client sends rotated qubits (to become the resource state once entangled) and then guides the computation with a set of classical instructions. It is the combination of these two parts (quantum state preparation and classical instructions) that leads to the desired blind computation. This idea was formalised in the *universal blind quantum computation* (UBQC) protocol in [@bfk].

We denote $ran_i$ collectively all the parameters that $\delta_i$ depends on other than $\phi_i$. We use bold and suppress the subscript that refers to a particular qubit in the graph to denote a full string, e.g. $\boldsymbol{\phi}:=\{\phi_1,\cdots,\phi_N\},\mathbf{ran}=\{ran_1,\cdots,ran_N\}$. We then define the past of qubits, which allows us to calculate upper bounds on the number of dependencies for various computation graphs.

We define $P_i = Z_i \cup X_i$ to be the set of qubits $j$ that have $X$ or $Z$ dependency on $i$. We define influence-past $c_i$ of qubit $i$ to be an assignment of an outcome $b_j \in \{0, 1\}$ for all qubits $j \in P_i$.

For example the brickwork state [@bfk], which can be used for universal quantum computation, has for each qubit a single X-dependent qubit and at most two Z-dependent qubits, and so the cardinality $\abs{P_i}$ is at most $3$ for all $i$. To each influence-past $c_i$ corresponds a unique value of $\delta_i$ (the corrected measurement angle for this influence-past). Note that we will denote $\boldsymbol{\delta}$ the set of instructions that include the measurement angles of each qubit, for all alternative influence-pasts, i.e. this is not a string of $N$ measurement angles $\delta_i$ but of $\sum_{i=1}^N|P_i|$ measurement angles of the form $\delta_i(c_i)$, where we have $|P_i|$ angles per qubit.

In UBQC, the server is not forced to follow the instructions and the client cannot verify if the computation is done correctly. One can modify the protocol to allow for such verification (see Theorem \[vbqc verif\]), as was first done in [@fk]. The central idea is to include trap qubits at positions unknown to the server. The client can send states from $\{\ket{0},\ket{1}\}$ (called dummies), which have the effect of breaking the graph at this vertex, removing it along with any attached edges. This can be used to generate isolated qubits in the graph in a way that is undetectable by the server. These isolated qubits do not affect the computation while they have deterministic outcome if measured in the correct basis. They can therefore be used as traps: a client can easily detect if one of them has been measured incorrectly but the server is ignorant of their position in the graph. This idea was introduced in [@fk] and later optimised by different protocols, such as [@KW15] which we use here. The reason to use [@KW15], other than efficiency, is because the construction is “local” and the server can obtain some information about the true graph (needed for 2PQC) without compromising the security. The construction of the resource given a base-graph $G$ (graph that the UBQC computation without traps requires), that has vertices $v\in V(G)$ and edges $e\in E(G)$, is the following:

1.  For each vertex $v_i$, we define a set of three new vertices $P_{v_i}=\{p^{v_i}_1,p^{v_i}_3,p^{v_i}_3\}$. These are called *primary* vertices.

2.  Corresponding to each edge $e(v_i,v_j)\in E(G)$ of the base-graph that connects the base vertices $v_i$ and $v_j$, we introduce a set of nine edges $E_{e(v_i,v_j)}$ that connect each of the vertices in the set $P_{v_i}$ with each of the vertices in the set $P_{v_j}$.

3.  We replace every edge in the resulting graph with a new vertex connected to the two vertices originally joined by that edge. The new vertices added in this step are called *added* vertices. This is the *dotted triple-graph* $DT(G)$.

The edge or vertex of the initial graph that each vertex $v\in DT(G)$ belongs to is called its *base-location*. We can see that by inserting dummy qubits among the added qubits we can break the $DT(G)$ in three copies of the same base-graph: one will be used for the computation while the other two can be used as traps. Furthermore for each vertex base-location the choice of where to break the graph is independent from other vertex base-locations and can be made in advance by the client. The server remains totally ignorant of this choice. This choice is called *trap-colouring*.

\[trap colouring\] We define trap-colouring to be an assignment of one colour to each of the vertices of the dotted triple-graph that is consistent with the following conditions:

1.  Primary vertices are coloured in one of the three following colours: white or black (for traps), or green (for computation).

2.  Added vertices are coloured in one of the four following colours: white, black, green or red.

3.  In each primary set $P_v$ there is exactly one vertex of each colour.

4.  Colouring the primary vertices fixes the colours of the added vertices: added vertices that connect primary vertices of different colour are red, added vertices that connect primary vertices of the same colour get that colour.

![Dotted-triple-graph for one-dimensional base graph of four qubits. Circles: primary vertices (base-location : vertex of the base-graph); Squares: added vertices (base-location : edge of the base-graph). (a) Trap-colouring. Green: computation qubits; White/black: trap qubits; Red: dummy qubits. Client chooses the trap-colouring, prepares each qubit individually and sends them one by one for the server to entangle according to the generic construction. (b) After entangling, the breaking operation defined by the dummy qubits will reduce the graph in (a) to the computation graph and for each vertex a corresponding trap/tag qubits.[]{data-label="figure3"}](figure3.jpg){width="1\columnwidth"}

The flow, Past of qubit $i$ and Influence-past of qubit $i$ can all be extended to the Dotted-Triple-Graph construction, with the result that each qubit still depends on a constant number of previous measurements (see [@KW15]).

For completeness we give the verification protocol from [@KW15] that we use:

We assume that a standard labeling of the vertices of the dotted triple-graph $DT(G)$ is known to both the client and the server. The number of qubits is at most $3N(3c+1)$ where $c$ is the maximum degree of the base graph $G$.\
$\bullet$ **Client’s resources**\
– Client is given a base graph $G$. The corresponding dotted graph state $\ket{D(G)}$ is generated by graph $D(G)$ that is obtained from $G$ by replacing every edge with a new vertex connected to the two vertices originally joined by that edge.\
– Client is given an MBQC measurement pattern $\bbbm_{\textrm{Comp}}$ which when applied to the dotted graph state $\ket{D(G)}$ performs the desired computation, in a fault-tolerant way that can detect or correct errors fewer than $\delta/2$.\
– Client generates the dotted triple-graph $DT(G)$ and selects a trap-colouring according to definition \[trap colouring\], which is done by choosing independently the colours for each set $P_v$.\
– Client for all red vertices will send dummy qubits and thus perform break operation.\
– Client chooses the green graph to perform the computation.\
– Client for the white graph will send dummy qubits for all added qubits $a^{e}_w$ and thus generate white isolated qubits at each primary vertex set $P_{v}$. Similarly for the black graph the client will send dummy qubits for the primary qubits $p^v_b$ and thus generate black isolated qubits at each added vertex set $A_{e}$.\
– The set $D$ of the positions of dummy qubits is chosen as defined above (fixed by the trap-colouring).\
– A binary string $\mathbf{s}$ of length at most $3N(3c+1)$ represents the measurement outcomes. It is initially set to all zeros.\
– A sequence of measurement angles, $\phi=(\phi_i)_{1 \leq i \leq 3N(3c+1)}$ with $\phi_i \in A = \{0, \pi/4, \cdots, 7\pi/4\}$, consistent with $\bbbm_{\textrm{Comp}}$. We define $\phi_i'(\phi_i,\mathbf{s})$ to be the measurement angle in MBQC, when corrections due to previous measurement outcomes $\mathbf{s}$ are taken into account (the function depends on the specific base-graph and its flow, see e.g. [@bfk]). We also set $\phi'_i = 0$ for all the trap and dummy qubits. – The Client chooses a measurement order on the dotted base-graph $D(G)$ that is consistent with the flow of the computation (this is known to the Server). The measurements within each set $P_v$ and $A_e$ of $DT(G)$ are ordered randomly.\
– $3N (3c+1)$ random variables $\theta_i$ with values taken uniformly at random from $A$.\
– $3N (3c+1)$ random variables $r_i$ and $|D|$ random variable $d_i$ with values taken uniformly at random from $\{0,1\}$.\
– A fixed function $C(i, \phi_i, \theta_i, r_i, \mathbf{s}) = \phi_i'(\phi_i,\mathbf{s}) +\theta_i + r_i \pi$ that for each non-output qubit $i$ computes the angle of the measurement of qubit $i$ to be sent to the Server.

(Continues on next page)

$\bullet$ **Initial Step**\
– **Client’s move:** Client sets all the value in $\mathbf{s}$ to be $0$ and prepares the input qubits:

[$$\begin{array}[c]{lllllllllllllll}
\ket e = X^{x_1} Z(\theta_1) \otimes \ldots \otimes  X^{x_l} Z(\theta_l) \ket I
\end{array}$$]{} and the remaining qubits in the following form [$$\begin{array}[c]{lllllllllllllll}
\forall i\in D &\;\;\;& \ket {d_i} \\ 
\forall i \not \in D &\;\;\;& \prod_{j\in N_G(i) \cap D} Z^{d_j}\ket {+_{\theta_i}}
\end{array}$$]{} and sends the Server all the $3N (3c+1)$ qubits in the order of the labelling of the graph.

– **Server’s move:** Server receives $3N(3c+1)$ single qubits and entangles them according to $DT(G)$.

$\bullet$ **Step $i : \; 1 \leq i \leq 3N (3c+1)$**

– **Client’s move:** Client computes the angle $\delta_i = C(i, \phi_i, \theta_i, r_i, \mathbf{s})$ and sends it to the Server.\
– **Server’s move:** Server measures qubit $i$ with angle $\delta_i$ and sends the result $b_i$ to the Client.\
– **Client’s move:** Client sets the value of $s_i$ in $\mathbf{s}$ to be $b_i + r_i$.\
$\bullet$ **Final Step:**

– **Server’s move:** Server returns the last layer of qubits (output layer) to the Client.\
$\bullet$ \[step:Alice-prep\] **Verification**\
– After obtaining the output qubits from the Server, the Client measures the output trap qubits with angle $\delta_t = \theta_t + r_t \pi$ to obtain $b_t$.

– Client accepts if $b_i = r_i$ for all the white (primary) and black (added) trap qubits $i$.

– Client applies corrections according to measurement outcomes $b_i$ and secret parameters $\theta_i, r_i$ at the output layer green qubits and obtains the final output.

\[vbqc verif\] Protocol \[prot:KW15\] is $\epsilon_{2}$-verifiable for the Client, where $\epsilon_{2} = \qty(\frac{8}{9})^{d}$ for $d = \ceil*{\frac{\delta}{2(2c+1)}}$. $\epsilon_2$-verifiability means that for any strategy of the server the real state is $\epsilon_2$-close (in trace distance) to $\rho_{ideal}(\rho_{in},p_{ok})$ for some $0\leq p_{ok}\leq 1$ where $\rho_{in}$ is the initial state and $\rho_f:=U(\rho_{in})$ is the desired final state: [$$\begin{array}[c]{lllllllllllllll}\rho_{ideal}(\rho_{in},p_{ok})&:=&p_{ok}\rho_f +(1-p_{ok})([\mathsf{abort}_1])\end{array}$$]{}

Standard Definitions of Security for Quantum Two-Party Computations
-------------------------------------------------------------------

Following [@DNS10], we have two parties $A$ and $B$ with quantum registers $\mathcal{A}$ and $\mathcal{B}$ and extra register $\mathcal{R}$, where $dim\mathcal{R} = (dim\mathcal{A} + dim \mathcal{B})$. The input is denoted $\rho_{in} \in D(\mathcal{A}\otimes\mathcal{B}\otimes\mathcal{R})$, where $D(\mathcal{A})$ is the set of all possible quantum states in register $\mathcal{A}$. Let then $L(\mathcal{A})$ be the set of linear mappings from $\mathcal{A}$ to itself and let $\phi : L(\mathcal{A}) \rightarrow L(\mathcal{B})$ be a completely positive and trace preserving superoperator, also called *quantum operation*. Finally let $\bbbone_{\mathcal{A}}$ be the totally mixed state and $\mathbf{1}_\mathcal{A}$ be identity operator in register $\mathcal{A}$. We will write $U \cdot \rho$ instead of $U \rho U^{\dagger}$ and we will sometimes denote $[b] := \dyad{b}$. Let $U_f$ be the unitary which when applied to classical inputs (computational basis) $(x, y)$, returns the classical output $f(x, y) = (f_1(x, y), f_2(x, y))$. The ideal output is $\rho_{out} = (U_f \otimes \bbbone) \cdot \rho_{in}$. Given two states $\rho_{0}$ and $\rho_{1}$, the trace norm distance is $\Delta(\rho_{0}, \rho_{1}):= \frac{1}{2}\norm{\rho_{0} - \rho_{1}}$. When $\Delta(\rho_{0}, \rho_{1}) \leq \epsilon$ then any process applied to $\rho_{0}$ behaves the same as it would on $\rho_{1}$ except with probability at most $\epsilon$. A function $\mu$ is *negligible in $n$* if, for every polynomial $p$, for sufficiently large $n$’s it holds that $\mu(n) < \frac{1}{p(n)}$.

All the proofs of security in this paper will be in the *real/ideal simulation paradigm*: when considering a party as corrupted, we will construct a simulator interacting with the ideal functionality such that they are not able to detect that they are not in fact interacting directly with a real world honest party instead.

The standard definition of security means that the simulated and real states are exponentially close and so indistinguishable for the adversary.

We say that the $n$-step two party strategy is $\epsilon$-private for $B$ if there exists $\epsilon(n)$ negligible in $n$ such that for all adversaries $\tilde{\mathcal{A}}$ and for all steps $i$ we have: $$\Delta\qty(v_{i}(\tilde{\mathcal{A}}, \rho_{in}), \Tr_{\mathcal{B}_{i}}\qty(\tilde{\rho}_{i}(\tilde{A}, \rho_{in}))) \leq \epsilon(n)$$ where $v_{i}(\tilde{\mathcal{A}}, \rho_{in})$ is the view of the adversary when interacting with the simulator and $\Tr_{\mathcal{B}_{i}}\qty(\tilde{\rho}_{i}(\tilde{A}, \rho_{in}))$ is the view of the adversary in the real protocol.

For further details on these definitions, see [@DNS10]. Another property which a quantum protocol may satisfy is *verifiability*. This intuitively means that the probability of receiving a corrupted output without aborting is negligible.

\[verification\] A protocol is said to be *$\epsilon$-verifiable for party $P_{i}$* if for any (potentially malicious) behaviour of party $P_{j}$ with $j \neq i$, the probability of obtaining a wrong output and not aborting is bounded by $\epsilon$. If the output of the real protocol with malicious party $\tilde{P}_{j}$ is $\tilde{\rho}(\tilde{P}_{j}, \rho_{in})$ then we have that: where

[$$\begin{array}[c]{lllllllllllllll}\rho_{ideal}(\rho_{in})&:=&p_{ok}(\bbbone_{\H_{P_i}}\otimes \mathcal{C}_{\H_{P_j}})\cdot U_f \cdot(\rho_{in})+(1-p_{ok})([\mathsf{abort}_1])\end{array}$$]{} where $\mathcal{C}_{\mathcal{H}_{P_{j}}}$ is the deviation that acts on $P_{j}$’s systems after they receive their outcome (a CP-map, it can be purified by including ancilla), $\rho'_{in} = (\bbbone_{\mathcal{H}_{P_i}} \otimes \mathcal{D}_{\mathcal{H}_{P_{j}}})\rho_{in}$ is an initial state compatible with $P_{i}$’s input, where $\mathcal{D}_{\mathcal{H}_{P_{j}}}$ is a deviation on the input by $P_{j}$.

Note that since $\mathcal{C}_{\H_{P_j}}$ is performed at the final step of the protocol, we also have that the global state (before the final step deviation, i.e. at step $n-1$) follows:

where $\rho^{n-1}_{ideal}(\rho_{in}) := p_{ok} U_f \cdot (\rho_{in})+(1-p_{ok})([\mathsf{abort}_1])$ During our protocol we will use bit commitment and 1-out-of-2 oblivious transfer (or OT).

Bit commitment consists of two phases, Commit and Reveal, such that after the Commit the receiver has no information about the value that has been committed (hiding), while during the Reveal the sender cannot reveal a value different from the one committed previously (binding). Both these properties can be either computationally or unconditionally verified depending on the scheme (but not both unconditionally). We suppose that all the commitments used verify the following *strict binding* property.

\[strict bind\] Let $COM$ be a commitment scheme, a deterministic polynomial-time function taking two arguments: the opening information $a$ and the message $y$. We say $COM$ is strictly binding if for all $a, y, a', y'$ with $(a, y) \neq (a', y')$, we have that $COM(a, y) \neq COM(a', y')$. It means that the sender is committed to the (unique) opening information *and* the message that is being committed.

A 1-out-of-2 oblivious transfer is a two party functionality in which one party ($P_1$ in our case) has two strings $(x_0, x_1)$ and the other ($P_2$) has a bit $b \in \{0, 1\}$. At the end of the protocol $P_2$ recovers $x_b$. $P_1$ should not know which of the strings $P_2$ has chosen while $P_2$ has no information about the string they did not choose $x_{1-b}$.

The following coin-tossing protocol will be needed later:

1.  $P_1$ chooses $\alpha_{1} \overset{R}{\in} \{0, 1\}^{\log(s)}$ uniformly at random, commits to it and sends the commitment to $P_2$ (this commitment has to be perfectly hiding).

2.  $P_2$ chooses $\alpha_{2} \overset{R}{\in} \{0, 1\}^{\log(s)}$ uniformly at random and sends it to $P_1$.

3.  $P_1$ opens their commitment and reveals $\alpha_1$.

4.  They both set $\alpha = \alpha_1 \oplus \alpha_2$, where $\oplus$ corresponds to the bitwise XOR ($\alpha$ is the index of the evaluation graph).

Quantum Covert Adversaries
--------------------------

We now introduce a new adversarial model for quantum protocols, based on the covert adversaries in [@AumLin07]. The quantum covert adversaries are also able to deviate arbitrarily from the protocol. The main difference with malicious is that when they cheat they are caught with high probability but not necessarily exponentially close to $1$.

This models real world situations where getting caught might have dire consequences for the parties, eg. financial repercussions. By associating the correct cost to being caught, even if the probability of getting caught is not exponentially close to $1$ the deterrence might be still high enough to make cheating unappealing.

We say that the protocol is $\epsilon$-private for $B$ if for all adversaries $\tilde{\mathcal{A}}$ and for all steps $i$ we have: $$\Delta\qty(v_{i}(\tilde{\mathcal{A}}, \rho_{in}), \Tr_{\mathcal{B}_{i}}\qty(\tilde{\rho}_{i}(\tilde{A}, \rho_{in}))) \leq \epsilon$$

Note that we do not have any requirement on $\epsilon$ and so, while we would like it to be close to $0$ it does not necessarily need to be negligible.

Stronger and more elegant definitions of covert adversaries that might be adaptable to the quantum case can be found in [@AumLin07], but for reasons specific to our construction (namely the fact that measurement is irreversible and disturbs quantum states) they are not directly applicable here.

#### Relation with specious and malicious adversaries

In the classical case the covert adversary lies between the honest-but-curious and malicious ones for some choices of $\epsilon$, as shown in [@AumLin07]. Their analysis partially holds also for the quantum case: the quantum covert adversary is strictly less powerful than the fully malicious adversary, unless the $\epsilon$ is negligible, in which case both notions are trivially equivalent. The situation is not as clear with quantum specious adversaries. We only get that if the protocol is secure against covert adversaries with a certain $\epsilon$ then it is also secure against specious adversaries with the same $\epsilon$, which is not required to be negligible.

The Quantum Cut-and-Choose Technique {#quantum cc}
====================================

The Cut-and-Choose method is a standard technique to boost a protocol secure against honest-but-curious to being secure against malicious adversaries, by enforcing the honest-but-curious behaviour. The classical Yao protocol, which also relies on a client/server (or garbler/evaluator) setup, was first proven secure against honest-but-curious adversaries (e.g. in [@LP04proof]) and then against malicious adversaries using this technique in [@LinPin07].

The garbler creates $s$ copies of the graph and the evaluator chooses which ones (the *check graphs*) they will check for consistency. If the checks pass and additional precautions are taken, the evaluator is confident that with high probability the remaining graphs (the *evaluation graphs*) were also constructed correctly and can be used for the computation. Here we will have $s$ graphs in total, $s-1$ *check graphs* and $1$ *evaluation graph*. In the classical Yao protocol, the probability of cheating and not getting caught is made negligible by using $\frac{s}{2}$ check graphs and $\frac{s}{2}$ evaluation graphs and revealing only the majority output of the evaluation graphs (not possible in quantum case, see below). There are several caveats in this setting even classically, cf. [@LinPin07; @Kir08].

We extend this technique to quantum computations in three steps. First, we show how to verify quantum states using Quantum-State-Preparation Cut-and-Choose (QSP-CC). This ensures that the resource state for the quantum computation in VBQC is constructed correctly. Secondly, we define *Classical Instructions Cut-and-Choose* (CI-CC), using the classical Cut-and-Choose to verify that the (classical) instructions for the computation are correct. Finally, we combine the two to get *Quantum Computation Cut-and-Choose* (QC-CC).

Quantum State Preparation Cut-and-Choose (QSP-CC) {#qscc}
-------------------------------------------------

The intuition for this functionality is that it allows the receiver to essentially test that a state $\ket{\psi_\alpha}$ was prepared and sent correctly (as promised), up to a certain probability, without the sender revealing the classical description of that state. This procedure boosts the classical commitment scheme towards a quantum-state commitment. Note however, that a proper quantum-state commitment scheme would require that the receiver also obtains no information about the state, which is not true here: in the above scheme the receivers can always obtain some (partial) information by measuring the state.

See Protocol \[qsp-cc\] (below) for details and Appendix \[proof\_cc\] for proof that the state is $\frac{1}{\sqrt{s}}$-close to the correctly-prepared. Note that if we used more than $1$ evaluation graphs (as needed for boosting the success probability), the probability of successful cheating does not scale linearly with parallel repetitions of QSP-CC due to coherent (entangled) attacks.

**Set up:** Two parties Alice and Bob.\
**Input:** Alice inputs a set of $s$ pure states $\{\ket{\psi_1},\cdots,\ket{\psi_s}\}$ along with their classical descriptions $\psi_i$. Bob chooses one index $\alpha$ at random.\
**Output:** For any strategy of an adversarial Alice, there exists a $0 \leq p \leq 1$ such that Bob obtains a state $\frac{1}{\sqrt{s}}$-close to $\rho_{id}(p) := p\dyad{\psi_\alpha} + (1 - p)[\textrm{Abort}]$.\
**Protocol:**\
– Alice commits the classical values $\psi_i$ with quantum-safe classical commitment scheme.\
– Alice sends all the $s$ labelled quantum states and then the $s$ commitments to Bob.\
– Bob randomly chooses the index $\alpha$ and request to open all commitments for $i \neq \alpha$.\
– Alice reveals all the classical values $\psi_i$ for $i \neq \alpha$.\
– Bob measures all states with index $i \neq \alpha$ in the basis $\{P_i := \dyad{\psi_i}, \bar{P}_i := I - \dyad{\psi_i}\}$ and aborts if he obtains the second outcome for any measurement. If the states $\ket{\psi_i}$ are tensor products of qubits, as is the case for the states sent by the verifier in VBQC, this measurement can be performed with local single qubit measurements.\
– The state $\ket{\psi_\alpha}$ (not measured) is guaranteed to be $\frac{1}{\sqrt{s}}$-close to $\rho_{id}(p)$ for some $p$.

Classical Instructions Cut-and-Choose (CI-CC)
---------------------------------------------

To perform the VBQC protocol, even if the resource state is correct, one needs to ensure that the classical instructions, i.e. measurement angles for each qubit $\boldsymbol{\delta}(\boldsymbol{\phi},\mathbf{ran})$, are also correct. The subscripts to bold symbols denote different graphs. The angles $\boldsymbol{\phi}$ are public, the receiver wants to ensure that $(\boldsymbol{\delta}_\alpha,\mathbf{ran}_\alpha)$, for the evaluation graph $\alpha$, is correct (and committed) without learning $\mathbf{ran}_\alpha$. To achieve this, the sender commits to the classical instructions for all graphs $\boldsymbol{\delta}_i$ after sending the (correct) qubits $\ket{\psi_i(\mathbf{ran}_i)}$ to the receiver. When $\mathbf{ran}_i$ is opened, the receiver can deterministically decide if $\boldsymbol{\delta}_i$ is correct (w.r.t. $\boldsymbol{\phi}$). Intuitively we expect that such a classical Cut-and-Choose has a $\frac1s$ probability of failure but it turns out that it is in fact $\frac{1}{\sqrt{s}}$, due to the specific proof techniques used to prove security against a quantum adversary and in particular the special rewinding from Appendix \[unruh rew\]. This will become clear in the proof of the following section.

**Set up:** Two parties Alice and Bob.\
**Input:** Alice inputs a set of $s$ pure states $\{\ket{\psi_1(\mathbf{ran}_1)},\cdots,\ket{\psi_s(\mathbf{ran}_s)}\}$ and for each state a set of classical instructions $\{\boldsymbol{\delta}_1,\cdots, \boldsymbol{\delta}_s\}$ and the underlying randomness $\{\mathbf{ran}_1,\cdots,\mathbf{ran}_s\}$. Bob chooses one index $\alpha$ at random.\
**Output:** For any strategy of an adversarial Alice involving only the classical instructions, the probability that Bob receives the wrong instructions $\boldsymbol{\delta}_\alpha$ for $\ket{\psi_\alpha(\mathbf{ran}_\alpha}$ and does not abort is at most $\frac{1}{\sqrt{s}}$.\
**Protocol:**\
– Alice commits the values $\boldsymbol{\delta}_i, \mathbf{ran}_i$ with quantum-safe classical commitments.\
– Alice sends all the $s$ labelled quantum states and then the $s$ commitments to Bob.\
– Bob randomly chooses the index $\alpha$ and request to open all commitments for $i \neq \alpha$.\
– Alice reveals all the classical values $\boldsymbol{\delta}_i, \mathbf{ran}_i$ for $i \neq \alpha$.\
– Bob verifies that all the instructions are computed correctly and aborts otherwise.\
– The remaining set of instructions $\boldsymbol{\delta}_\alpha$ is correct up to probability $\frac{1}{\sqrt{s}}$.

The receiver can use the remaining committed instructions $\boldsymbol{\delta}_\alpha$ to drive the computation by asking the sender to open the instructions corresponding to the measurement outcomes (influence-past). This differs from the classical case where the circuit evaluation is non-interactive.

Quantum Computation Cut-and-Choose (QC-CC) {#qc-cc}
------------------------------------------

We can now introduce a Cut-and-Choose technique for quantum computation. The sender can deviate in any way. By combining CI-CC with QSP-CC and using the commitments during the (quantum) computation, the evaluator knows (with high probability) that they have been asked to perform the correct quantum computation.

**Set up:** Two parties Alice and Bob, a (quantum) computation $f$ hidden in the pairs $(\mathbf{ran}_i,\boldsymbol{\delta}_i)$.\
**Input:** Alice inputs a set of $s$ pure states $\{\ket{\psi_1(\mathbf{ran}_1)},\cdots,\ket{\psi_s(\mathbf{ran}_s)}\}$ and for each state a set of classical instructions $\{\boldsymbol{\delta}_1,\cdots, \boldsymbol{\delta}_s\}$, the underlying randomness $\{\mathbf{ran}_1,\cdots,\mathbf{ran}_s\}$ and the classical description of each state. Bob chooses one index $\alpha$ at random.\
**Output:** For any adversarial Alice, the probability of performing the wrong computation and not aborting is $\order{\frac{1}{\sqrt{s}}}$. **Protocol:**\
– Alice commits the classical values $\psi_i(\boldsymbol{ran}_i)$ and $\boldsymbol{\delta}_i, \mathbf{ran}_i$ as in protocols \[qsp-cc\] and \[i-cc\] respectively.\
– Alice sends all the $s$ labelled quantum states and then the $s$ commitments to Bob.\
– Bob randomly chooses the index $\alpha$ and request to open all commitments for $i \neq \alpha$.\
– Alice reveals all the classical values $\psi_i(\boldsymbol{ran}_i), \boldsymbol{\delta}_i, \mathbf{ran}_i$ for $i \neq \alpha$.\
– Bob performs the same verifications as in protocols \[qsp-cc\] and \[i-cc\] and aborts similarly.\
– Alice reveals a subset of instructions $\boldsymbol{\delta}_\alpha$, as required by the protocol they wish to perform (but keeps secret $\mathbf{ran}_\alpha$).\
– Bob uses these along with the state $\ket{\psi_\alpha}$ to perform the desired computation.

From Protocol \[qsp-cc\], the state $\ket{\psi_\alpha(\mathbf{ran}_\alpha)}$ is $\frac1{\sqrt{s}}$-close to the ideal state. From Protocol \[i-cc\], the pair $(\boldsymbol{\delta}_\alpha,\mathbf{ran}_\alpha)$ are constructed correctly up to probability $\frac{1}{\sqrt{s}}$. It follows that the computation is performed correctly up to probability $O(\frac1{\sqrt{s}})$.

We suppose that we have access to an oracle $O^f$ which, upon being given the secret parameters $\mathbf{ran}_i, \psi_i(\boldsymbol{ran}_i)$ and a subset of the instructions $\boldsymbol{\delta}_i$ which is sufficient to drive a single specific computation on the resource state $\ket{\psi_i(\mathbf{ran}_i)}$, returns the output $f_i$ produced by using these instructions on the (correct) state $\ket{\psi_i(\mathbf{ran}_i)}$.

Let us construct a simulator for an adversarial Alice:

1.  The simulator runs the protocol normally until Alice reveals her commitments: receives the qubits and commitments, chooses random index $\alpha$ and receives the openings of commitments for $i \neq \alpha$.

2.  Using the special rewinding (Appendix \[unruh rew\]), it rewinds the simulation and chooses at random a second index $\alpha'$, (for known $\mathbf{ran}_{\alpha'}, \psi_{\alpha'}(\boldsymbol{ran}_{\alpha'})$, $\boldsymbol{\delta}_{\alpha'}$).

This (classical) part of the protocol can be viewed as three steps: commitment (sending the commitments), challenge (choosing the random $\alpha$) and response (revealing the commitments).

Furthermore it has two properties: *special soundness* and *strict soundness*. Intuitively, special soundness means that given two correct communication transcripts with different challenges, an extractor is able to compute a witness (the simulator recovers the secret values). Strict soundness means that given a commitment and challenge, there is a unique acceptable response: here the only accepted response is to decommit the correct committed values (due to perfect and strict binding).

Following the analysis in [@Unr12], protocols possessing such properties are secure against malicious quantum adversaries and can use rewinding against quantum adversaries in their security proof to extract a witness, evading issues naive rewinding faces due to no-cloning. This rewinding can only be done once as per the A-style definition of $\Sigma$-protocols in [@Unr12]. Lemma \[q rew state\] shows that after this step the distance between the real execution and the simulation is bounded by $\frac{1}{\sqrt{s}}$.

Importantly, the clear separation between classical information and quantum states in protocols based on [@fk] is what makes the rewinding possible on the classical part of the protocol.

1.  The simulator performs all the checks for $i \neq \alpha'$ and aborts in the same cases as an honest party would.

2.  Alice reveals a subset of $\boldsymbol{\delta}_{\alpha'}$ needed to perform the computation.

3.  The simulator can send this subset, along with the corresponding $\mathbf{ran}_{\alpha'}, \psi_{\alpha'}(\boldsymbol{ran}_{\alpha'})$ which were acquired previously, to the oracle $O^f$ and recover the correct output $f_{\alpha'}$, which is returned to Alice at the end of the computation.

The distance between the ideal and real execution is bounded by $O(\frac1{\sqrt{s}})$.

In addition to the arguments given in QSP-CC against using $s/2$ evaluation graphs with quantum states, we give an attack against our protocol showing concretely why this is not applicable: malicious $P_1$ encodes a teleportation of $P_2$’s input in the trap qubits of one graph. Since the results of all measurements are given back, $P_1$ can recover $P_2$’s input if the corrupt graph is (one of the) evaluated. This attack succeeds with probability $\frac{\textrm{number of evaluation graphs}}{s}$ and so we cannot hope for a better security bound than an inverse polynomial with this version of the protocol. Classically, evaluating an incorrect circuit has minimal influence when using $s/2$ evaluation circuits where only the majority output is returned. Here guaranteeing that the majority of evaluation circuits is correct would not be enough (the evaluation of a circuit gives extra information for the sake of verifiability).

A final crucial observation is that this proof provides an example where proving security against a quantum adversary is hard, even for a classical functionality (CC). The part of the protocol that needs rewinding is entirely classical and the same proof (and extra cost) is necessary even for a fully classical CC protocol (single evaluation graph). The failure probability goes from $\frac{1}{s}$ to $\frac{1}{\sqrt{s}}$ for quantum adversaries. This kind of quadratic gap is unavoidable against quantum adversaries, unless (possibly) one uses totally different proof techniques: it is not sufficient to use cryptographic primitives resistant against quantum computers (eg. based on LWE), but proof techniques (and security parameters) should also be modified.

The 2PQC Protocol {#prot}
=================

#### Ideal functionality.

-   **Inputs:** Each party has a classical input, $x, y \in \{0, 1\}^{n}$ for $P_1$ and $P_2$ respectively. The adversary has auxiliary input $z \in \{0, 1\}^{*}$. Honest parties send their input to the trusted party computing $f = (f_1, f_2)$, a corrupted party $i$ either sends $\mathsf{abort}_i$ or any input of length $n$ (computed in poly-time from their input and auxiliary input).

-   **Computation by the trusted party:** If the trusted party receives an inconsistent input or $\mathsf{abort}_i$ by any party $i$, it returns $\mathsf{abort}_i$ to both parties. Otherwise the trusted party first sends $f_1(x', y')$ to $P_1$ ($x' = x$ if $P_1$ is honest, similarly for $P_2$), who can then choose to abort if corrupted (by sending $\mathsf{abort}_1$, which the trusted party forwards to $P_2$). If not, then $P_2$ receives $f_{2}(x', y')$ from the trusted party.

-   **Outputs:** Honest parties output what they received from the trusted party, corrupted parties have no output, the adversary outputs an arbitrary BQP function of their inputs and outputs.

We will use the security parameters $s$ (number of graphs for CC) and $n$ (size of the inputs) throughout the paper. $P_1$ and $P_2$ will denote the garbler/client and the evaluator/server respectively.

#### High-level overview

$P_1$ and $P_2$ have already chosen a VBQC graph computing $f = (f_1, f_2)$ fault-tolerantly. $P_1$ chooses and commits to the randomness for the $s$ versions of the graph (the angles $\theta$ of the states and the flips $r$ in the measurements) and also to all the corresponding measurements angles according to the flow, the possible input measurement angles for both parties, the decryption keys for $P_2$’s output also according to the flow and the positions of the traps among $P_2$’s output qubits. For every input bit of $P_2$, they perform a 1-out-of-2 OT at the end of which $P_2$ learns the measurement angles for their input qubits for all graphs (doing the OTs before sending the qubits is essential for the security proof, it allows the simulator to recover the adversary’s input before constructing the graphs). They then perform a QC-CC protocol: the qubits of each graph are the states $\ket{\psi_i(\mathbf{ran}_i)}$, the commitments are $\mathbf{ran}_i, \psi_i(\boldsymbol{ran}_i)$ and $\boldsymbol{\delta}_i$, they choose the evaluation graph with a coin-tossing protocol, $P_1$ reveals the commitments of check circuits and $P_2$ verifies them as well as the states. Then they perform the evaluation with the VUBQC protocol with $P_1$ decommitting to the instructions (measurement angles). At the end they perform a simple key-exchange protocol so that $P_2$ may decrypt their output.

If both parties are honest and follow the steps of the protocol then the protocol is correct.

If the parties are honest, all the graphs and commitments are correct. The protocol (restricted to the evaluation graph) is equivalent to the normal VBQC, with the evaluator ($P_2$) keeping part of the output. The last step of the protocol allows $P_2$ to decrypt this output just the same way as the $P_1$ would in a regular execution. Moreover, all the checks pass and there is no abort. The correctness directly follows from the correctness of the VBQC protocol.

\[thm:qyao\_privacy\] Assume that the oblivious transfer protocol is $\epsilon_{2}$-private against malicious adversaries and that the commitments are perfectly hiding and binding. Let $c$ be the maximum degree of the graph, $\delta$ the number of errors tolerated by the fault-tolerant encoding and $s$ the number of graphs constructed as part of the CC. If the protocol is $\epsilon_{2}$-verifiable for $P_1$, then it is $\epsilon_{2}$-private against a malicious $P_2$ and $\epsilon_{1}$-private against a covert $P_1$, where $\epsilon_{2} = \qty(\frac{8}{9})^{d}$ for $d = \ceil*{\frac{\delta}{2(2c+1)}}$ and $\epsilon_{1} = \frac{1}{\sqrt{s}}$

*Proof Sketch.* The proof follows from Lemma \[sec P1\] ($\epsilon_1$-privacy against a covert $P_1$) and Lemma \[sec P2\] ($\epsilon_2$-privacy against a malicious $P_2$) (see detailed proof in Appendix \[sec proofs\]). The simulator for adversarial $P_1$ (Lemma \[sec P1\]) is very similar to the one in the proof for Protocol \[qc-cc\]: obtains one set of values form a first run (runs as usual until $P_1$ reveals the commitments) then rewinds the adversary to get a second set and recovers the secret parameters of the adversary which then sends to the ideal functionality, thus getting the ideal output. The simulator runs the evaluation graph with a random input, encrypts the ideal output and returns it to the adversary. The simulator for adversarial $P_2$ (Lemma \[sec P2\]) relies on the construction of a graph which has deterministic output (see Lemma \[fake graph\]). The simulator recovers the adversary’s input with the OTs and sends it to the ideal functionality, from which $P_2$’s ideal output is obtained. Then constructs a graph which always produces this output and hides it among the remaining $s-1$ graphs, which are constructed correctly. The simulator biases the choice of evaluation graph with rewinding the coin-toss so that this special graph is chosen. The checks pass and $P_2$ evaluates the fake graph and gets the correct output.

**Input:** $P_1$ has input $x \in \{0, 1\}^{n}$ and $P_2$ has input $y \in \{0, 1\}^{n}$.\
**Auxiliary input:** Functions $f_1$ and $f_2$, a security parameter $s$ (which is a power of $2$) and the description of a fault-tolerant MBQC pattern $C$ such that $C(x, y) = (f_1(x, y), f_2(x, y))$ for classical inputs $(x, y)$.\
**Output:** Party $P_1$ should receive $f_1(x, y)$ and party $P_2$ should receive $f_2(x, y)$.\
**The protocol:**

1.  $P_1$ constructs $s$ copies of the dotted-triple-graph computing $C$ using independent randomness (here they just choose everything in the different graphs, no need to prepare the qubits just yet).

2.  $P_1$ constructs commitments to:

    1.  All $\theta_{i,q}^{j}$, $r_{i,q}^{j}$ (these correspond to the $\mathbf{ran}_i$, while the $\theta_{i,q}^{j}$ alone correspond to $\ket{\psi_i(\mathbf{ran}_i}$in the QC-CC protocol, all the other commitments correspond to $\boldsymbol{\delta}_i$), $\prescript{\textsc{k}}{}\delta_{i,q}^{j}$ where $i$ runs over all $s$ graphs, $q$ is the index of the base location in the graph, j correspond to the index of computation, trap and dummy qubits for this particular base location (in the order they appear in the triple-dotted-graph $i$, so if the first qubit for this base location is a trap, $\theta_{i,q}^{1}$ will be the angle associated with that trap) for this base location $q$ and $\textsc{k}$ runs over all possible correction values (previous measurements) affecting this position, according to the flow (the position of the traps and dummies in all graphs are given implicitly through these values). They also commit to the values of the dummy qubits.

    2.  For their and $P_2$’s input they commit to both possible versions of $\prescript{}{b}\delta_{i,q}^{j}$ where $b \in \{0,1\}$, in permuted order for their input and in correct order for $P_2$’s input.

    3.  They commit to all potential keys (a One-Time-Pad) for each of $P_2$’s output qubits (according to flow).

    4.  They commit to the positions of the computation qubits, dummies and traps in the last layer of computation for $P_2$’s output qubits.

3.  $P_1$ and $P_2$ participate in $n$ instances of a 1-out-of-2 OT protocol, where in each one $P_1$’s inputs are the sets of $\qty{decommit(\prescript{}{0}\delta_{i,q}^{j})}_{0 \leq i \leq s-1}$ and $\qty{decommit(\prescript{}{1}\delta_{i,q}^{j})}_{0 \leq i \leq s-1}$ and $P_2$’s input is bit $b_{q}$ corresponding to position $q$. In the end of step 3, $P_2$ receives the decommitments to the measurement angles corresponding to all their inputs (for the same binary value across all graphs).

4.  $P_1$ and $P_2$ perform the QC-CC protocol (\[qc-cc-prot\]):

    1.  $P_1$ sends the qubits in the states $\ket*{+_{\theta_{i,q}^{j}}}$

    2.  Then $P_1$ sends the commitments

    3.  They both pick the random graph index $\alpha$ using the coin-tossing Protocol \[coin-toss\]

    4.  $P_1$ opens the commitments from 2.(a), 2.(b), 2.(c), 2.(d) for any graph whose index is not $\alpha$

    5.  $P_2$ performs checks and outputs $\mathsf{abort}_2$ and halts if any of the checks fail (the checks are the following : the $\delta$s are correctly constructed and are compatible with the choice of $\phi$, $r$ and $\theta$; the traps and dummies are in the correct place (from commitments 2.(a) and 2.(d)); the decryption keys are correct; the values they received for their input via the OTs are consistent (they are in the correct place with regard to their input bit); they verify that all $\ket*{+_{\theta_{i,q}^{j}}}$ are correct by measuring them in the $\theta_{i,q}^{j}$ basis).

    6.  Then $P_1$ opens the values from commitments to the $\delta$s in 2.(b) corresponding to their actual binary input for graph $\alpha$. $P_2$ entangles the qubits according to the dotted-triple-graph and evaluates this graph by asking $P_1$ to open the values to $\prescript{\textsc{k}}{}\delta_{i,q}^{j}$ in 2.(a) for <span style="font-variant:small-caps;">k</span> corresponding to the measurements values they obtained on each qubit. If any of the traps are measured incorrectly $P_1$ privately raises a flag *corrupted*. This corresponds to the evaluation phase of Protocol \[prot:KW15\].

5.  At the end of the computation they perform the following key-release step:

    1.  $P_2$ measures all the qubits in the final layer (output qubits) according to the corresponding $\prescript{\textsc{k}}{}\delta_{i,q}^{j}$, as decommitted by $P_1$.

    2.  They send back all the measurement outcomes corresponding to $P_1$’s output qubits and commit to the ones corresponding to their output qubits.

    3.  $P_1$ checks all the traps on their qubits and outputs $\mathsf{abort}_1$ if any fail or if the flag *corrupted* was raised during computation, otherwise they decrypt their output using their decryption keys and set the decryption as their output. (Continues on next page)

    4.  $P_1$ reveals the positions of traps and dummies in the final layer of the computation by decommitting 2.(d)

    5.  For these positions $P_2$ reveals the commitments of 5.(b)

    6.  $P_1$ checks that these traps were measured correctly and outputs $\mathsf{abort}_1$ if any fail, otherwise they decommit the decryption keys in 2.(c) corresponding to $P_2$’s output.

    7.  $P_2$ decrypts their output, sets the decryption as their final output and ends the protocol.

Acknowledgments {#acknowledgments .unnumbered}
===============

Funding from EPSRC grants EP/N003829/1 and EP/M013243/1 is acknowledged.

Mapping of a universal set of gate in the MBQC framework {#example mbqc}
========================================================

We present here diagrams taken from [@bfk] showing how to translate a universal set of gates to the MBQC model using the brickwork graphs.

![Translation of H, $\pi/8$, CNOT and identity gates[]{data-label="mbqc"}](mbqc_paterns.jpg){width="0.95\columnwidth"}

Proof of QSP-CC {#proof_cc}
===============

We have two CP-maps, one corresponding to the real protocol and one to the simulation, and need to show that these maps are $\epsilon$-close.

We define $P_0 := I \otimes_{i=1}^N [\psi_i]$ and $P_j := I \underset{i\neq j}{\bigotimes} [\psi_i] \otimes I_{j}$ for all $1 \leq j \leq s$. It is clear that $P_j P_k = P_0$ if $j \neq k$ and $\comm{P_j}{P_k} = 0$. Moreover we define $P_j = P_0 + P_j^c$ and can easily see that $P_j^c P_k^c = \delta_{j, k}P_j^c$. Also we define $p_2 = \Tr(P_0\rho)$ and $p_1 = \frac{1}{s}\underset{i}{\sum}\Tr(P_i\rho) \leq p_2 + \frac{1}{s}(1 - p_2)$. We have the following two CPTP maps:

$$\Phi_1(\rho)=\frac{1}{s}\overset{s}{\underset{i = 1}{\sum}} P_i\rho P_i + (1 - p_1)[\textrm{Abort}]$$ $$\Phi_2(\rho)=P_0\rho P_0 + (1 - p_2)[\textrm{Abort}]$$

The real protocol corresponds to Bob acting on some state $\rho$ sent by Alice, by applying the CPTP map $\Phi_1(\cdot)$, i.e. measuring if the states sent are correct by choosing randomly one state to be left unmeasured. We will show that it is $\epsilon$-close to $\Phi_2(\cdot)$ map resulting to $\rho_{id}(p)$. Let a purification of $\rho$ be $\ket{\psi}$, we need to show:

$$\Delta(P_0\dyad{\psi}P_0, \frac{1}{s}\underset{i}{\sum}P_i\dyad{\psi}\bra{\psi}P_i) \leq \epsilon$$

We use the sub-normalised fidelity and its relation with the trace distance. We will use the following properties and definitions from [@DFPR13]:

$\tilde{\Delta}\qty(\rho, \sigma) \leq \sqrt{1-\tilde{F}^2(\rho, \sigma)}$

$\tilde{F}(\rho, \sigma) = F(\rho, \sigma) + \sqrt{(1 - \Tr\rho)(1 - \Tr\sigma)}$

$F^2(\ket{\phi}, \sigma) = \expval{\sigma}{\phi}$

Let $\sigma_1 = \frac{1}{s}\underset{i}{\sum}P_i\dyad{\psi}P_i$, $\sigma_2 = P_0\dyad{\psi}P_0$, $p_2 = \Tr\sigma_2$ and $p_1 = \Tr\sigma_1 \leq p_2 + \frac{1}{s}(1 - p_2)$. It is straightforward to see that $F(\sigma_1, \sigma_2) = p_2$. We obtain: $$\tilde{F}(\sigma_1, \sigma_2) \geq p_2 + \sqrt{(1 - p_2)(1 - p_2 - \frac{1}{s}(1 - p_2))} \approx p_2 + (1-p_2)(1 - \frac{1}{2s}) \geq 1 - \frac{1}{2s}$$

assuming $s \gg 1$. It follows that:

$$\tilde{\Delta}(\sigma_1, \sigma_2) \leq \sqrt{1 - (1 - \frac{1}{2s})^2} \approx \sqrt{\frac{1}{s}}$$

We have $\Phi_1(\rho) = \sigma_1 + (1 - p_1)[\textrm{Abort}]$ and $\Phi_2(\rho) = \sigma_2 + (1 - p_2)[\textrm{Abort}]$ and using the above expressions we get:

$$\Delta(\Phi_1(\rho), \Phi_2(\rho)) \leq \sqrt{\frac{1}{s}}$$

By tracing out all but the unmeasured system $\alpha$, Bob has (in the simulated case) a state $\frac{1}{\sqrt{s}}$-close to $\rho_{id}(p_2) = p_2[\psi_c] + (1 - p_2)[\textrm{Abort}]$.

Quantum Rewinding
=================

Classically the simulator runs the adversary (chooses its input $x, z, r$) internally and rewinds it by having black box access to the *next message* function $m_{i+1} = V(x,z, r, m_1, \ldots, m_i)$ where $m_1, \ldots, m_i$ are previous messages. The simulator has to save all messages so that it can send them again later, which is impossible in the quantum setting (due to no-cloning). We present two techniques given in [@Wat09] and [@Unr12] which achieve a similar result, with different constraints, show that they are applicable for the simulators of our protocol and calculate the success probability for both cases.

Watrous’ Oblivious Quantum Rewinding {#wat rew}
------------------------------------

Let $Q$ be a unitary acting on the pure state $\ket{\psi}\ket{0^{k}}$. We first apply $Q$ to $\ket{\psi}\ket{0^{k}}$ and then measure the first qubit in the computational basis. Let $p(\psi) \in (0, 1)$ be the probability that this measurement outcome is $0$. Then there are unique unit vectors $\ket{\phi_{0}(\psi)}$ and $\ket{\phi_{1}(\psi)}$ such that: $$\label{Eq:Watrous}
Q\ket{\psi}\ket{0^{k}} = \sqrt{p(\psi)}\ket{0}\ket{\phi_{0}(\psi)} + \sqrt{1 - p(\psi)}\ket{1}\ket{\phi_{1}(\psi)}$$ Lemma 8 from [@Wat09] gives a procedure constructing from $Q$ outputting a state close to $\ket{\phi_{0}(\psi)}$ for any $\ket{\psi}$.

Q represents an attempt at simulating for some cheating adversary, $\ket{\psi}$ is the internal state of this adversary. Getting $0$ means the simulation was successful and getting $1$ corresponds to failure and necessity to rewind. Lemma 8 from [@Wat09] states that this is possible if $p(\psi)$ is non-negligible and independent of $\psi$. Rewinding gives a state $\epsilon$-close to that of a successful simulation for any exponentially small $\epsilon$ with polynomially many rewinds.

In our case the rewinding takes place during the coin-tossing part of simulation for $P_2$. Let $\hat{\alpha}$ be the random evaluation graph index chosen by the simulator at the beginning of the proof. After the coin-tossing phase of the protocol, before verifying if the simulation has succeeded or not, the state of the system is in product form (i.e. the random choices of $\alpha, \hat{\alpha}$, are depicted as an equal superposition, but are totally uncorrelated):

$$\ket{\Phi_f}:=\qty(\overset{s}{\underset{\alpha = 1}{\sum}}c_{\alpha}\ket{\phi(\psi, \alpha)}\ket{\alpha})\qty(\overset{s}{\underset{\hat{\alpha} = 1}{\sum}}\frac1{\sqrt{s}}\ket{\hat{\alpha}})$$

where $\underset{\alpha}{\sum} \abs{c_\alpha}^2 = 1$ are coefficients, $\ket{\phi(\psi, \alpha)}$ is the (normalised) state at the end of the protocol given initial state $\psi$ and choice of graph $\alpha$, while the last part ($\ket{\hat{\alpha}}$) corresponds to the random choice of graph made by the simulator. The projection to the subspace that does not need rewinding (where $\alpha = \hat{\alpha}$) is given: $P_0 := \overset{s}{\underset{\alpha' = 1}{\sum}} I \otimes \dyad{\alpha'} \otimes \dyad{\alpha'}$. We have:

$$\ket{\Phi_f} = P_0\ket{\Phi_f} + (I - P_0) \ket{\Phi_f}$$

To bring it in the form of Eq.(\[Eq:Watrous\]) we rewrite it. We define the (normalised) states:

$\ket{\phi_0(\psi)}=\overset{s}{\underset{\alpha = 1}{\sum}} c_{\alpha}\ket{\phi(\psi, \alpha)}\ket{\alpha}\ket{\alpha};\quad 
\ket{\phi_1(\psi)}=\overset{s}{\underset{\alpha = 1}{\sum}} \underset{\alpha \neq \hat{\alpha}}{\sum} \frac{c_{\alpha}}{\sqrt{s - 1}}\ket{\phi(\psi, \alpha)} \ket{\alpha} \ket{\hat{\alpha}}$

Then we have:

$$\ket{\Phi_f} = \sqrt{\frac{1}{s}}\ket{\phi_0(\psi)} + \sqrt{1 - \frac{1}{s}}\ket{\phi_1(\psi)}$$

Now, following the unitary action that led to $\ket{\Phi_f}$, we perform the measurement $\{P_0, I - P_0\}$ and store the outcome in the value of an extra qubit (the first one):

$$\ket{\Phi_f} = \sqrt{\frac{1}{s}}\ket{0}\ket{\phi_0(\psi)} + \sqrt{1 - \frac{1}{s}}\ket{1}\ket{\phi_1(\psi)}$$

Finally, we note that this is exactly in the form of Eq. (\[Eq:Watrous\]) where $p(\psi) = \frac{1}{s}$ is constant (independent of $\psi$). Further details in [@Wat09], proof of Lemma 8.

Unruh’s Special Quantum Rewinding {#unruh rew}
---------------------------------

Watrous’ lemma only ensures that the simulation is successful, but *no information* is kept between two rewinds (hence *oblivious rewinding*). In the simulator for covert $P_1$ we need two transcripts in order to recover their input (which is otherwise secret), so another type of rewinding is necessary. We present the conditions under which Unruh’s rewinding method [@Unr12] applies and then show that these conditions are met in our protocol and calculate an upper bound on the distance between the actual and simulated (rewinding to extract input) runs.

Let $\Pi$ be a protocol between $P_1$, with input $(x, w)$, and $P_2$, with input $x$ and output in $\{0, 1\}$, with three messages: commitment $com$ by $P_1$, challenge $ch$ sampled (efficiently) uniformly at random by $P_2$ from the set $C_x$ (membership in $C_x$ has to be easy to decide), and response $resp$ by $P_1$. $P_2$ accepts (outputs $0$) by a deterministic poly-time computation on $(x, com, ch, resp)$ (it is called an *accepting conversation* for $x$).

Such a protocol has *special soundness* if there is a deterministic poly-time algorithm $\mathsf{K}_{0}$ (the *special extractor*) such that for any two accepting conversations $(com, ch, resp)$ and $(com, ch', resp')$ for $x$ with $ch \neq ch'$, we have that $w := \mathsf{K}_{0}(x, com, ch, resp, ch', resp')$.

Such a protocol has *strict soundness* if for any two accepting conversations $(com, ch, resp);(com, ch, resp')$ for $x$, $resp = resp'$.

*Canonical extractor ([@Unr12])* The extractor runs the first step of the adversary to recover $com$ (each step is a separate unitary operation), chooses two values $ch, ch' \in C_{x}$, runs the second step with $ch$ to get $resp$, applies the inverse of the second step (this is the rewinding) and reruns the second step with $ch'$ to get $resp'$ before applying $\mathsf{K}_{0}$. Since each response is uniquely determined by the commitment and the challenge, if the measured response of the adversary is correct then they must have sent a state close to the real response, therefore this does not disturb too much the internal state of the adversary. In our case, $com$ corresponds to step 5 (sending commitments), $ch$ is step 6 (result of coin-toss) and $resp$ is step 7 (revealing commitments). We calculate the distance between the internal state of the adversary in the real protocol where only the commitments for the check graphs are opened and the one after the rewinding in the simulation where all commitments have been opened.

We consider the opening of the commitments as a measurement performed on a state shared with the adversary. Let $P_i$ denote the projector corresponding to one run of this part of the protocol where the challenge is $i$ (analogous to the $P_{ch}^{*}$ in [@Unr12]). This corresponds to revealing all commitments but one, corresponding to the graph of index $i$. We define $\bar{P}_i = \bbbone - P_i$. There is a “correct” subspace $P$, that projects to the subspace that answer all $s$ tests, i.e. $PP_i := P$ for all $i$.

The strict soundness property means that there is a unique classical response to each challenge. This intuitively means that two projection $P_i$ and $P_j$ acting on the same subsystem, are either identity or identical which essentially means that they commute, i.e. $P_i P_j = P_j P_i$. On the other hand, the property of special soundness means that any two of these tests, when both successful, allow the simulator to recover a “witness”. This means that $P_i P_j = P$ for all $i \neq j$.

\[q rew state\] Let $\ket{\psi}$ be any state and let $\qty{P_i}_{0 \leq i \leq s}$ and $P$ be as defined above. For $\epsilon = \frac{1}{s}$ we have that:

$$\max_{\ket{\psi}}\Delta\qty(P\ket{\psi},\frac{1}{s}\underset{i}{\sum}P_i\dyad{\psi}P_i) \leq \sqrt{\epsilon}$$

The proof follows the one above for QSP-CC. We again use the sub-normalised fidelity. Let $\rho = P\dyad{\psi}P$ and $\sigma = \frac{1}{s}\underset{i}{\sum}P_i\dyad{\psi}P_i$. We further define $P_i = P + P_i^c$ and $p = \expval{P}{\psi}$. It follows directly from special soundness that $P_i^c P_j^c = \delta_{i, j} P_i^c$. Since $P_i^c, P_j^c, P$ are orthogonal and the sum of the traces (probabilities) of the $P_i^c$-terms cannot exceed $(1 - p)$, we then have that:

$$\Tr\sigma := \Tr (\frac{1}{s}\underset{i}{\sum}P_i\dyad{\psi}P_i) = \frac{1}{s}\underset{i}{\sum}\expval{(P + P_i^c)}{\psi} = p + \frac{1}{s}\underset{i}{\sum}\expval{P_i^c}{\psi} \leq p + \frac{1}{s}(1 - p)$$

$F^2\qty(P\dyad{\psi}P, \frac{1}{s}\underset{i}{\sum}P_i\dyad{\psi}P_i) = p^2$

Assuming $\epsilon = \frac{1}{s}$ where $s \gg 1$, with simple calculation we obtain:

$$\tilde{F}(\rho, \sigma) \geq 1 - \frac{\epsilon}{2}\Rightarrow\quad \tilde{\Delta}\qty(\rho, \sigma) \leq \sqrt{1 - (1 - \frac{\epsilon}{2})^2} \approx \sqrt{\epsilon}$$

This result is independent of $\ket{\psi}$ (and $p$) and thus completes the proof.

We have $\Phi_1(\cdot)\stackrel{\sqrt{\epsilon}} \approx \Phi_2(\cdot)$ where $\Phi_1(\cdot)$ is the CP-map corresponding to the projection in the $P$ subspace, while $\Phi_2(\cdot)$ is the CP-map corresponding to the real protocol operation (project in one of $P_i$ subspace, randomly chosen from the $s$ possible challenges). The simulated view is $\sqrt{\epsilon}$-close to the real protocol. Given this measurement, the simulator, (a) if it accepts (measurement result $P$) the state is close to the real protocol, (b) if it rejects, it is identical with the real protocol (since for abort, the exact state of the parties is irrelevant).

Proof of Security {#sec proofs}
=================

All the following proofs will be carried out in the OT-hybrid model. This means that parties can at the same time communicate with one another but also rely in certain steps of the protocol on an ideal call to a trusted party (also called oracle) performing an oblivious transfer. During the simulation, the simulator replaces this trusted party and receives all inputs that the adversary sends to it. We make this assumption only in order to make the proof clearer and easier, in a real protocol this ideal functionality can then be replaced with any OT protocol which is secure against malicious quantum adversaries.

We start by proving the $\epsilon$-verifiability for the client.

Protocol \[qyao cc protool\] is $\epsilon_{2}$-verifiable for $P_1$, where $\epsilon_{2} = \qty(\frac{8}{9})^{d}$ for $d = \ceil*{\frac{\delta}{2(2c+1)}}$.

In this proof we consider that $P_1$ is honest while $P_2$ is malicious. During the first steps of the protocol, $P_2$ only participates in the perfectly secure OT at the end of which they receives their input measurement angles, based on their choice of deviated input $\hat{x}$.

$P_2$ then receives the qubits of all the graphs and the commitments. These are perfectly hiding so no information can be recovered from them until $P_1$ decides to send the decommitment values. Furthermore, deviating at this point on the qubits is equivalent to deviating later.

Because the coin-tossing protocol used is proven secure (the same rewinding techniques as the ones used in the proofs for $P_1$ and $P_2$ can be used), a malicious $P_2$ cannot bias the result. After the result of the coin-toss is known, $P_2$ receives the decommitments for all graphs but the evaluation graph, about which they therefore remain blind.

The evaluation part of the protocol follows exactly the same pattern as the VUBQC protocol in [@KW15], with the difference that instead of announcing the angles of the measurements, $P_1$ sends the corresponding decommitments, which in the case of an honest $P_1$ is perfectly equivalent. This protocol has been proven to be $\epsilon_{2}$-verifiable for $P_1$ in [@KW15], see Theorem \[vbqc verif\].

After the computation $P_2$ measures the output qubits and has to commit to the result of the measurements, of which they have to reveal the traps. $P_1$ can therefore verify that all the traps were measured correctly. The only last deviation the server is allowed to perform is a further computation on their binary output, which is by definition allowed even in the ideal case.

From this analysis it follows that the exact same verification properties from the protocol in [@KW15] hold for this protocol, namely that our protocol is $\epsilon_{2}$-verifiable for $P_1$, where $\epsilon_{2} = \qty(\frac{8}{9})^{d}$ for $d = \ceil*{\frac{\delta}{2(2c+1)}}$, which completes the proof.

The honest behaviour of $P_2$ is essentially enforced by the traps (verifiability), while the Cut-and-Choose technique enforces $P_1$ to also behave honestly.

Security Against Covert $P_1$ {#secP1}
-----------------------------

#### Intuition

The proof is an adapted version of Lindell and Pinkas’ proof for malicious $P_1$ [@LinPin07] and the proof for covert adversaries of [@AumLin07]. The intuition is that if they choose to cheat by constructing incorrectly the graphs or the OTs then they will get caught with probability at least $\epsilon_{1}$ during the opening phase of the protocol, whereas if they do construct the graphs and OTs correctly then they acts the same as an honest party would. The simulator runs the protocol normally until the opening of the commitments by $P_1$. Then, since the coin toss is random even with malicious $P_1$, the simulator does quantum rewinding (see [@Unr12]) and learn the rest of the commitments. When the malicious $P_1$ reveals their input measurement angles, having obtained the related randomness the simulator can deduce $P_1$’s bit-input and send it to the ideal functionality. It then runs the evaluation graph with random input and returns the output received from the ideal functionality (note that the correct decoding key is known to the simulator from the rewinding).

\[sec P1\] Protocol \[qyao cc protool\] is $\epsilon_{1}$-private against a covert $P_1$, where $\epsilon_{1} = \frac{1}{\sqrt{s}}$

Let us construct the simulator in the following way:

1.  The simulator runs the protocol normally until step 3 : participates in the OTs, with a random input $y'$ instead of $P_2$’s actual input.

2.  Then acts as the simulator in Protocol \[qc-cc-prot\]: receives the qubits and commitments, participates in the coin-tossing protocol, receives the openings, rewinds, performs the coin-tossing again and receives the other set of openings, performs all the verifications and aborts as an honest party would.

3.  The adversary decommits the value of their input angles for the new evaluation graph, the simulator deduces $P_1$’s binary deviated input $\hat{x}$ from the knowledge of secret parameters and sends it to the ideal functionality. It gets in return the output value $f_{1}(\hat{x}, y)$ for this deviated input.

4.  Then performs the computation on graph $\alpha'$ using a random input $y'$. At the end of the computation replaces the bits of the computation positions for $P_1$’s output with the bits received from the ideal functionality (after correcting them using the decryption keys known due to the rewinding) and returns this to the adversary, while committing to what it computed as $P_2$’s output. When $P_1$ reveals the positions of the traps and dummies in the last layer, the simulator verifies that they were traps as an honest $P_2$ and opens the corresponding positions. Receives the keys from the adversary, and outputs whatever the adversary would and halts.

The fact that the simulation is the same up to a negligible factor whether we use a random index chosen by $P_2$ or a coin-tossing protocol can be formalised in terms of a series of games, involving an ideal functionality for coin-tossing (such an ideal functionality takes as input a dummy input $\lambda$ from $P_2$ and returns to both players the same random string $\alpha$):

**Game 1.** Here the simulator runs the protocol as usual, with no rewinding.

**Game 2.** We replace the protocol for coin-tossing with the ideal functionality. Because the protocol for coin-tossing is secure against malicious quantum adversaries, the distance between the first game and the second is negligible.

**Game 3.** Here the simulator sends directly to covert $P_1$ a challenge chosen at random instead of calling the ideal functionality for coin-tossing. This is equivalent to the setup $(com, ch, resp)$ for [@Unr12]. This is indistinguishable from the previous game from the point of view of the adversary.

**Game 4.** Now we use quantum rewinding so the simulator sends two challenges to $P_1$, this is equivalent to the rewinding performed in [@Unr12]. According to the analysis performed in Lemma \[q rew state\], here the distance is $\frac{1}{\sqrt{s}}$.

**Game 5.** We perform the switch the other way : we replace the simulator sending the random challenges by two calls to the ideal functionality (there is no problem with calling this ideal functionality twice as the input is a dummy input). This is once more indistinguishable for the adversary.

**Game 6.** Again we switch back : the ideal functionality calls are replaced by the real coin-tossing protocol. The distance is also negligible and this game represents exactly what happens during our simulation.

The result of this game-based analysis is that the distance between the real execution of the protocol and the simulation the way we perform it for this step is bounded by $\frac{1}{\sqrt{s}}$, up to a negligible quantity.

Following the analysis in Appendix \[unruh rew\] and Lemma \[q rew state\], we get that after the rewinding we have (with $(\hat{x}, y)$ being the input after the adversary’s deviation, equivalent to the $\rho_{in}'$ from the definition of verifiability):

$$\Delta\qty(v_{i}(\tilde{\mathcal{P}}_1, \hat{x}), \Tr_{\mathcal{P}_{2, i}}\qty(\tilde{\rho}(\tilde{A}, \hat{x}))) \leq \frac{1}{\sqrt{s}}$$

The state at the end of the simulation is $\epsilon_1=\frac{1}{\sqrt{s}}$-close to the real execution.

Security Against Malicious $P_2$ {#secP2}
--------------------------------

We first prove a lemma, showing how to construct a graph evaluating to a given fixed output for any input in a way indistinguishable from a regular computation producing that output for a given (possibly different) input.

\[fake graph\] Given the value $f_2(x, \hat{y})$, there exist a dotted-triple graph, along with commitments identical to the evaluation graph, which when evaluated for any classical input $x'$ and $y'$ returns the fixed output $f_2(x, \hat{y})$ and is indistinguishable for the evaluator (even when given the decommitments for the evaluation graph in Protocol \[qyao cc protool\]) from a DT(G) computing $(f_1(x, y), f_2(x, y))$ for any $x$ and $y$.

The graph is constructed as such:

-   $P_1$ chooses all the parameters ($\theta_{q}^{j}$, $r_{q}$, $\prescript{\textsc{k}}{}\delta_{q}^{j}$, and $\prescript{\textsc{}}{b}\delta_{i,q}^{j}$ for inputs) at random for all the base-location qubits apart from those corresponding to $P_2$’s output.

-   For those base locations $q$, for the computation qubits $j$, $P_1$ chooses at random $\theta_{q}^{j}$ and $b_{q} \in \{0, 1\}$ and sets $\prescript{\textsc{k}}{}\delta_{q}^{j} = \theta_{q}^{j} + b_{q}\pi$ for all choices of <span style="font-variant:small-caps;">k</span>. $P_1$ then sets the corresponding decryption keys to $\prescript{\textsc{k}}{}k_{q} = f_{2}(x, \hat{y})_{q} \oplus b_{q}$ for all choices of <span style="font-variant:small-caps;">k</span>.

-   Then $P_1$ prepares all qubits in the correct state for the base locations but instead of sending the correct ones for the “added” qubits for the edges linking $P_2$’s outputs qubits to the rest of the graph, $P_1$ sends dummy qubits (in states chosen from $\{\ket{0}, \ket{1}\}$). This will have the effect of breaking away these qubits from the rest of the graph.

Since the dummies isolate the output of $P_2$ from the rest of the graph, $P_2$ obtains the result $b_{q}$ when measuring the last layer whatever the previous measurement outcomes are. Thus applying the decryption keys receives $f_{2}(x, \hat{y})$. The indistinguishability follows directly from the server’s blindness in the VBQC protocol and the hiding property of the bit commitment scheme: since the random $\theta_{q}^{j}$s are not revealed at any point server cannot get any information from the decommitments if done as in the evaluation graph in Protocol \[qyao cc protool\].

#### Intuition.

The following proof combines the proofs for a malicious $P_2$ from [@LinPin07] and [@AumLin07]. The simulator first extracts $P_2$’s deviated input $\hat{y}$ (once again $(x, \hat{y})$ plays the same role as the $\rho_{in}'$ in the verifiability definition) from the OT-protocols, which it then uses to call the ideal functionality and receive $f_2(x, \hat{y})$. Then it chooses at random one graph index for which it will construct the associated graph such that it computes always this value as $P_2$’s output (as in Lemma \[fake graph\]). Then uses the rewinding technique from [@Wat09] to bias the coin-toss so this index is picked as the evaluation graph. The other graphs are constructed correctly and all checks pass. Then for the evaluation it follows the same steps as in original protocol, guaranteeing that $P_2$ will receive $f_2(x, \hat{y})$ at the end because the computation over a single graph is verifiable and secure against a malicious $P_2$. While the property of $\epsilon_2$-verifiability for $P_1$ guarantees that the protocol is close to the ideal, the previous lemma gives the construction of a simulator of this ideal execution. Here we justify the coin tossing protocol, since if $P_2$ chose the evaluation graph we would be unable to obtain the simulator for $P_2$.

\[sec P2\] If Protocol \[qyao cc protool\] is $\epsilon_{2}$-verifiable for the client, then it is $\epsilon_{2}$-private against a malicious server.

Let us construct the simulator in the following way:

1.  The simulator chooses at random the values of $\prescript{\textsc{}}{b}\delta_{i,q}^{j}$ for $P_2$’s input and organizes these values in $2n$ sets of length $s$: $\qty{\prescript{}{0}\delta_{i,q}^{j}}_{0 \leq i \leq s-1}$ and $\qty{\prescript{}{1}\delta_{i,q}^{j}}_{0 \leq i \leq s-1}$ for all qubits $q$ corresponding to $P_2$’s input.

2.  Then invokes the adversary and receives from them what it would have sent to the trusted party computing the OT: $\hat{y} = (\hat{y}_{1}, \ldots, \hat{y}_{m})$ which is the actual input that the adversary intended to use. The simulator returns the corresponding sets of inputs. Here the simulated and real state are identical.

3.  The simulator calls the ideal functionality and receives the value $f_{2}(x, \hat{y})$. Chooses the index of the evaluation graph $\alpha$ and for all the check graphs constructs them normally (only now the values of $\theta_{i,q}^{j}$ and $r_{i,q}^{j}$ are determined by $\prescript{}{b}\delta_{i,q}^{j}$ and $\phi_{b}$) and for the evaluation constructs it as in the proof of Lemma \[fake graph\]. Commits to all those values as it would in the real protocol, in the same order, as well as the decryption keys from Lemma \[fake graph\]. The simulator sends the qubits and gives all these commitments to $P_2$. The ideal and real situations are again indistinguishable as shown in Lemma \[fake graph\].

4.  The simulator needs to “bias” the coin toss to outputs the $\alpha$ chosen:

    -   It first generates a perfectly binding commitment $\hat{c}$ to a random value $\alpha_{1}$ and sends it to the adversary.

    -   Then receives $\alpha_{2}$ from the adversary.

    -   If $\alpha_{1} \oplus \alpha_{2} = \alpha$, the simulator continues by decommiting $\alpha_{1}$. Otherwise rewinds back to the beginning of this step, with fresh randomness and a new value for $\alpha_{1}$.

It should be noted that *no information is kept between rewinds* as it is only used to ensure that the adversary is forced to pick our fake graph as the evaluation graph. The probability of success of the rewinding is $\frac{1}{s}$, which is independent of the initial state of the adversary. We can therefore use the oblivious quantum rewind technique from [@Wat09] for this step of simulation. At this point $\mel{\phi_{0}(\psi)}{\rho(\psi)}{\phi_{0}(\psi)} \geq 1 - \epsilon$, where $\ket{\psi}$ is the state of the adversary before this step, $\ket{\phi_{0}(\psi)}$ corresponds to the state after a success happening in one try while $\rho(\psi)$ is the state at the end of the rewinding process. The expected number of rewinds is $\order{\frac{s^2}{s - 1} log{\frac{1}{\epsilon}}}$. Here we want an $\epsilon$ negligible in $n$, so $log{\frac{1}{\epsilon}} = \order{n}$ is sufficient and we get $\order{ns}$ rewinds. More details can be found in Appendix \[wat rew\].

1.  The simulator opens all commitments as in the protocol for the checks. These correspond to the correct graphs and thus all pass. Nothing is leaked about the evaluation graph and so the ideal and real states are indistinguishable.

2.  The simulator then runs the remaining graph and runs the computation until the end of the protocol on the modified evaluation graph as $P_1$. In the end, outputs whatever the adversary outputs and halts.

Let $k^{P_2}$ be the key committed as the decryption key for $P_2$’s output as part of the fake graph construction in Lemma \[fake graph\]. At the end of the computation, $P_2$ is in possession of the state $\Tr_{\H_{P_1}}\qty(E_{k^{P_2}}(f(x, \hat{y}))) = E_{k^{P_2}}(f_{2}(x, \hat{y}))$, where $E_{k^{P_2}}(z)$ denotes the encryption as a quantum state of the classical value $z$ under the key $k^{P_2}$ (this key is the one chosen as part of the construction of the fake graph in the previous lemma). At the end of the computation the simulator reveals the key by decommitting it and $P_2$ can decrypt their outcome. The server’s view of the real protocol after receiving the key is:

$$\Tr_{\H_{P_1}}\qty(E_{k^{P_2}}\qty(\tilde\rho^{n-1}(\tilde{P}_{2}, \hat{y})))$$

From Eq. (\[eq:verification2\]) (noting that partial trace is a distance non-increasing operation): $$\Delta\qty(\Tr_{\H_{P_1}}\qty(E_{k^{P_2}}\qty(\tilde\rho^{n-1}(\tilde{P}_{2}, \hat{y}))), \Tr_{\H_{P_1}}\qty(E_{k^{P_2}}(\rho^{n-1}_{ideal}(\hat{y})))) \leq \epsilon_{1}$$

We showed that the simulated view is $\epsilon_{2}$-close to the real view of $P_2$.

[^1]: Note, that even though we evaluate a classical function we still need quantum computation if this function cannot be efficiently computed (in the honest case) with a classical computer (e.g. functions that involve factoring) and thus classical techniques are not applicable.
