\section{Introduction}\label{intro}

In this paper, we address the problem of privately evaluating some
unitary transform $U$ upon a joint quantum input state held by two
parties.  Since unitaries model what quantum algorithms are
implementing, we can see this problem as a natural extension of secure
two-party evaluation of functions to the quantum realm.  Suppose that
a state $\ensuremath{\ket{\phi_{{\tt in}}}}\in \hreg{A}\otimes\hreg{B}$ is the initial shared
state where Alice holds register \hreg{A} and Bob holds register
\hreg{B}.  Let $U\in \unit{\hreg{A}\otimes \hreg{B}}$ be some unitary
transform acting upon \hreg{A} and \hreg{B}. What cryptographic
assumptions are needed for a private evaluation of $\ensuremath{\ket{\phi_{{\tt out}}}} = U\ensuremath{\ket{\phi_{{\tt in}}}}$
where {\em private} means that each player learns no more than in the
ideal situation depicted in Fig.~\ref{ideal}? Of course, answers to
this question  depend upon the adversary we are
willing to tolerate.

 \begin{wrapfigure}{r}{0.333\textwidth}
  \vspace{-20pt}
 \begin{center}
  \mbox{\scriptsize \Qcircuit @C=1em @R=.7em
  {\twowire{{\ensuremath{\ket{\phi_{{\tt in}}}}}} &
    \lstick{\hreg{A}} & \multigate{1}{U} & \qw & \hreg{A} &
  \twowirer{  {\ket{\phi_{\tt out}}}}\\
    &  \lstick{\hreg{B}}  & \ghost{U}        & \qw &\hreg{B} &
    }}
\end{center}
\small{\caption{Ideal Functionality for unitary $U$.}
\label{ideal}}
  \vspace{-10pt}
\end{wrapfigure}

 In \cite{SSS09}, it was shown that unitaries cannot be used to
 implement classical cryptographic primitives. Any non-trivial
 primitive implemented by unitaries will necessarily leak information
 toward one party. Moreover, this leakage is available to a weak class
 of adversaries that can be interpreted as the quantum version of
 classical semi-honest adversaries. It follows that quantum two-party
 computation of unitaries cannot be used to implement classical
 cryptographic primitives. This opens the possibility that the
 cryptographic assumptions needed for private evaluations of unitaries
 are weaker than for their classical counterpart. So, what classical
 cryptographic assumptions, if any, are required to achieve privacy in
 our setting? Are there unitaries more difficult to evaluate
 privately than others?

 In this work, we answer these questions against a class of weak
 quantum adversaries, called specious, related to classical
 semi-honest adversaries.  We say that a quantum adversary is specious
 if at any step during the execution of a protocol, it can provide a
 judge with some state that, when joined with the state held by the
 honest player, will be indistinguishable from a honest
 interaction. In other words, an adversary is specious if it can pass
 an audit with success at any step.  Most known impossibility proofs
 in quantum cryptography apply when the adversary is restricted to be
 specious. Definitions similar to ours have been proposed for the
 quantum setting and usually named semi-honest. However, translating
 our definition to the classical setting produces a strictly stronger
 class of adversaries than semi-honest\footnote{As an example, assume
 there exist public key cryptosystems where you can sample a public
 key without learning the secret key. Then this is a semi-honest
 oblivious transform: The receiver, with choice bit $c$, samples
 $pk_c$ in the normal way and learns its corresponding secret key and
 samples $pk_{1-c}$ without learning its secret key. He sends
 $(pk_0,pk_1)$.  Then the sender sends $(E_{pk_0}(m_0),E_{pk_1}(m_1))$
 and the receiver decrypts $E_{pk_c}(m_c)$.  This is not secure
 against a specious adversary who can sample $pk_{1-c}$ along with its
 secret key $sk_{1-c}$ and then delete $sk_{1-c}$ before the
 audit.}\fullv{, as demonstrated in Appendix~\ref{app:spec}}{} which
 justifies not adopting the term \emph{semi-honest}. We propose the
 name \emph{specious} as the core of the definition is that the
 adversary must appear to act honestly.

\paragraph{Contributions.}
First, we define two-party protocols for the evaluation of unitaries
having access to oracle calls. This allows us to consider protocols
with security relying on some ideal functionalities in order to be
private. We then say that a protocol is in the {\em bare model} if it
does not involve any call to an ideal functionality.  We then formally
define what we mean by specious adversaries.  Privacy is then defined
via simulation. We say that a protocol for the two-party evaluation of
unitary $U$ is private against specious adversaries if, for any joint
input state and at any step of the protocol, there exists a simulator
that can reproduce the adversary's view having only access to its own
part of the joint input state. Quantum simulation must rely on a
family of simulators for the view of the adversary rather than one
because quantum information does not accumulate but can vanish as the
protocol evolves.  For instance, consider the trivial protocol that
let Alice send her input register to Bob so that he can apply locally
$\ensuremath{\ket{\phi_{{\tt out}}}}=U\ensuremath{\ket{\phi_{{\tt in}}}}$ before returning her register. The final state of
such a protocol is certainly private, as Bob cannot clone Alice's
input and keep a copy, yet at some point Bob had access to Alice's
input thus violating privacy. No simulator can possibly reproduce
Bob's state after he received Alice's register without having access
to her input state.

Second, we show that no  protocol
can be shown
statistically private against
specious adversaries
in the bare model for a very simple unitary: the swap gate. As
the name suggests, the swap gate simply permutes Alice's and Bob's
input states.  Intuitively, the reason why this gate is impossible is
that at some point during the execution of such protocol, one party
that still has almost all its own input state receives a non-negligible
amount of information (in the quantum  sense) about the other party's input state.
At this point,
no simulator can possibly re-produce the complete
state held by the receiving party since a call to the ideal functionality
only provides access to
the other party's state while no call to the ideal functionality only
provides information about that party's own input.
Therefore, any simulator cannot re-produce a state that contains
information about the input states of both parties.
It follows that
cryptographic assumptions are needed for the private evaluation of
unitaries against specious adversaries.  On the other hand, a
classical bit commitment is sufficient to implement the swap privately
in our model.

Finally, we give a very simple protocol for the private evaluation of
any unitary based on ideas introduced by \cite{GC99a,GC99b} in the
context of fault tolerant quantum computation. Our construction is
similar to Yao's original construction in the classical
world\cite{Yao86,kilian88}. We represent any unitary $U$ by a quantum
circuit made out of gates taken from the universal set $\ensuremath{{\cal UG}}=\{X,Y,Z,
{\sf CNOT}, {\sf H}, {\sf P}, {\sf R}\}$ \cite{NC00}.  The protocol evaluates
each gate of the circuit upon shared encrypted input where the
encryption uses the Pauli operators $\{X,Y,Z\}$ together with the
identity.  In addition to the Pauli gates $X,Y$, and $Z$, gates {\sf CNOT},
{\sf H}, and {\sf P}\ can easily be performed over encrypted states
without losing the ability to decrypt.  Gates of that kind belong to
what is called the {\em Clifford group}.  The {\sf CNOT}\ gate is the only
gate in \ensuremath{{\cal UG}}\ acting upon more than one qubit while the {\sf R}-gate is
the only one that does not belong to the Clifford group. In order to
evaluate it over an encrypted state while preserving the ability to
decrypt, we need to rely upon a classical ideal functionality
computing securely an additive sharing for the AND of Alice's and
Bob's input bits.  We call this ideal functionality an AND-box.  Upon
input $x\in\{0,1\}$ for Alice and $y\in\{0,1\}$ for Bob, it produces
$a\in_R \{0,1\}$ and $b\in \{0,1\}$ to Alice and Bob respectively such
that $a\oplus b = x\wedge y$.  An AND-box can be obtained from any
flavor of oblivious transfer and is defined the same way than an
NL-box\cite{PR94,PR97} without the property that its output can be
obtained before the input of the other player has been provided to the
box (i.e., NL-boxes are non-signaling).  The \emph{equivalence}
between AND-boxes, NL-boxes, and oblivious transfer is discussed in
\cite{WW05b}. At the end of the protocol, each part of the shared key
allowing to decrypt the output must be exchanged in a fair way. For
this task, Alice and Bob rely upon an ideal swap functionality called
{\ensuremath{\sf SWAP}}.  The result is that any $U$ can be evaluated privately upon any
input provided Alice and Bob have access to one AND-box per
{\sf R}-gate and one call to the an ideal swap. If the circuit happens
to have only gates in the Clifford group then only one call to an
ideal swap is required for privacy. In other words, {\ensuremath{\sf SWAP}}\ is
universal for the private evaluation of circuits in the Clifford group
(i.e., those circuits having no {\sf R}-gate) and itself belongs to
that group ({\ensuremath{\sf SWAP}}\ is not a classical primitive). To some extent,
circuits in the Clifford group are the {\em easy} ones.  Privacy for
circuits containing {\sf R}-gates however needs a classical
cryptographic primitive to be evaluated privately by our protocol. It
means that AND-boxes are universal for the private evaluation of any
circuit against specious adversaries. We don't know whether there
exist some unitary transforms that are universal for the private
evaluation of any unitary against specious adversaries.

\paragraph{Previous works.}
All impossibility results in quantum cryptography we are aware of
apply to classical primitives. In fact, the impossibility proofs
usually rely upon the fact that an adversary with a seemingly honest
behavior can force the implementation of classical primitives to
behave quantumly. The result being that implemented that way, the
primitive must leak information to the adversary. This is the spirit
behind the impossibility of implementing oblivious transfer securely
using quantum communication\cite{Lo97}. In that same paper the
impossibility of any one-sided private evaluation of non-trivial
primitives was shown. All these results can be seen as generalizations
of the impossibility of bit commitment schemes based on quantum
communication\cite{LC97,Mayers97}.  The most general impossibility
result we are aware of applies to any {\em non-trivial} two-party
classical function\cite{SSS09}.  It states that it suffices for the
adversary to {\em purify} its actions in order for the quantum
primitive to leak information. An adversary purifying its actions is
specious as defined above. None of these impossibility proofs apply to
quantum primitives characterized by some unitary transform applied to
joint quantum inputs. Blind quantum computation is a primitive
that shows similarities to ours. In \cite{BFK09}, a protocol allowing
a client to get its input to a quantum circuit evaluated blindly has
been proposed. The security of their scheme is unconditional
while in our setting almost no unitary allows for  unconditional
privacy.

An unpublished work of Smith\cite{Smith06}
shows how one can devise a private protocol
for the evaluation of any unitary
that seems to remain private against all quantum adversaries.
However, the
techniques used require strong cryptographic assumptions like
homomorphic encryption schemes, zero-knowledge and witness
indistinguishable proof systems.
The construction is in the
spirit of protocols for multiparty quantum computation\cite{BCGHS06,CGS02}
and fault tolerant quantum circuits\cite{Shor96,AB97}.
Although our protocol only
guarantees privacy  against specious adversaries, it
is obtained using much weaker cryptographic assumptions.

\fullv{\paragraph{Organization.}
We introduce protocols for the two-party evaluation of unitaries in
Sect.~\ref{twoparty}. In Sect.~\ref{semihonest}, we define
the class of specious
quantum adversaries and  in Sect.~\ref{privacy}, we
define privacy.
  We show in Sect.~\ref{impossiblesect} that no private
protocol
 exists for swap. The description of our protocol follows in
Sect.~\ref{prot} and the proof of privacy is in
Appendix~\ref{privacyproof}.}{}

\section{Preliminaries}
\label{sect:preliminaries}

The $N$-dimensional complex Euclidean space (i.e., Hilbert space) will
be denoted by \hdim{N}. We denote quantum registers using calligraphic
typeset \hreg{A}. As usual, $\hreg{A} \otimes \hreg{B}$ denotes the
space of two such quantum registers.  We write $\hreg{A}\approx
\hreg{B}$ when $\hreg{A}$ and $\hreg{B}$ are such that
$\dim{(\hreg{A})}=\dim{(\hreg{B})}$. A register $\hreg{A}$ can undergo
transformations as a function of time; we denote by $\hreg{A}_i$ the
state of space $\hreg{A}$ at time $i$.  When a quantum computation is
viewed as a circuit accepting input in \hreg{A}, we denote all wires
in the circuit by $\wire{w}\in \hreg{A}$.  If the circuit accepts
input in $\hreg{A}\otimes\hreg{B}$ then the set of all wires is
denoted $\wire{w}\in \hreg{A}\cup \hreg{B}$.

The set of all linear mappings from \hreg{A}\ to \hreg{B}\ is denoted
by \lin{\hreg{A}}{\hreg{B}}\ while \linop{\hreg{A}}\ stands for
\lin{\hreg{A}}{\hreg{A}}. To simplify notation, for $\rho\in
\linop{\hreg{A}}$ and $M\in \lin{\hreg{A}}{\hreg{B}}$ we write $M\cdot
\rho$ for $M\rho M^{\dagger}$.
\fullv{

}{}
We denote by $\pos{\hreg{A}}$ the set of positive semi-definite
operators in \hreg{A}. The set of positive semi-definite operators
with trace $1$ acting on \hreg{A}\ is denoted $\dens{\hreg{A}}$;
$\dens{\hreg{A}}$ is the set of all possible quantum states for
register $\reg{A}$.  An operator $A\in\lin{\hreg{A}}{\hreg{B}}$ is
called a {\em linear isometry} if $A^{\dagger}A=\Idt_{\hreg{A}}$.  The
set of unitary operators (i.e., linear isometries with
$\hreg{B}=\hreg{A}$) acting in \hreg{A}\ is denoted by
$\unit{\hreg{A}}$.  The identity operator in \hreg{A}\ is denoted
$\Idt_{\hreg{A}}$ and the completely mixed state in \dens{\hreg{A}}\
is denoted by $\id_{\hreg{A}}$.  For any positive integer $N>0$,
$\Idt_{N}$ and $\id_N$ denote the identity operator respectively the
completely mixed state in \hdim{N}. When the context requires, a pure
state $\ket{\psi}\in \hreg{AB}$ will be written
$\ket{\psi}^{\hreg{AB}}$ to make explicit the registers in which it is
stored.

A linear mapping $\Phi:\linop{\hreg{A}} \mapsto \linop{\hreg{B}}$ is
called a {\em super-operator} since it belongs to
$\lin{\linop{\hreg{A}}}{\linop{\hreg{B}}}$.  $\Phi$ is said to be {\em
positive} if $\Phi(A)\in\pos{\hreg{B}}$ for all $A\in\pos{\hreg{A}}$.
The super-operator $\Phi$ is said to be {\em completely positive} if
$\Phi \otimes \Idt_{\linop{\hreg{Z}}}$ is positive for every choice of
the Hilbert space $\hreg{Z}$.  A super-operator $\Phi$ can be
physically realized or is {\em admissible} if it is completely
positive and preserves the trace: $\trace{\Phi(A)}=\trace{A}$ for all
$A\in \linop{\hreg{A}}$. We call such a super-operator a {\em quantum
operation}. \fullv{Any quantum operation $\Phi:\linop{\hreg{A}} \mapsto
\linop{\hreg{B}}$ can be written in its Kraus form
$\{E_j\}_{j=1}^{\dim{(\hreg{A})}\cdot\dim{(\hreg{B})}}$ where $E_j\in
\lin{\hreg{A}}{\hreg{B}}$ for every $j$ such that $\Phi(\rho) = \sum_j
E_j \rho E_j^{\dagger},$ for any $\rho\in\pos{\hreg{A}}$ and where
$\sum_j E^{\dagger}_j E_j = \Idt_{\hreg{B}}$.}{} Another way to represent
any quantum operation is through a linear isometry $W\in
\lin{\hreg{A}}{\hreg{B}\otimes\hreg{Z}}$ such that $\Phi(\rho) =
\trace[\hreg{Z}]{W\cdot \rho},$ for some extra space
$\hreg{Z}$. Any such isometry $W$ can be implemented by a physical
process as long as the resource to implement\fullv{ the space}{} \hreg{Z}\
is available. This is just a unitary transform in
$\unit{\hreg{A}\otimes\hreg{Z}}$ where the system in \hreg{Z}\ is
initially in known state $\ket{0_{\hreg{Z}}}$.

\fullv{\begin{wrapfigure}{r}{0.42\textwidth}
\vspace{-10pt}
\centering \mbox{\scriptsize
  \Qcircuit @C=1em @R=.7em {
    \lstick{\ket{\psi}} & \multigate{1}{Bell} & \ustick{x} \cw & \cw &
       \control\cw & \\
    \twowire{\ket{\Psi_{0,0}}}& \ghost{Bell}        & \ustick{z} \cw &
       \control\cw & \cwx & \\
       & \qw  & \qw & \gate{Z} \cwx & \gate{X} \cwx &
          \rstick{\ket{\psi}}\qw \gategroup{1}{4}{3}{5}{1em}{--}
  }}
\small{\caption{The teleportation circuit}
\label{fig:teleportation}}
\vspace{-20pt}
\end{wrapfigure}}{}

For two states $\rho_0,\rho_1 \in \dens{\hreg{A}}$, we denote by
$\Delta(\rho_0,\rho_1)$ the trace norm distance between $\rho_0$ and
$\rho_1$: $\Delta(\rho_0,\rho_1) := \frac{1}{2} \|
\rho_0-\rho_1\|$. If $\Delta(\rho_0,\rho_1)\leq \varepsilon$ then any
quantum process applied to $\rho_0$ behaves exactly as for $\rho_1$
except with probability at most $\varepsilon$~\cite{RK05}.

\fullv{We let $C_1$ be the Pauli group (the set of tensor products of the
three Pauli matrices $X,$ $Y,$ and $Z$, see Appendix~\ref{commut}, and
the $2 \times 2$ identity matrix $\Idt_2$). Furthermore, $C_{i+1}$ is
then defined recursively for $i\geq 1$ as $C_{i+1} \equiv \{ U | U C_1
U^\dag \in C_{i} \}$, where $C_2$ is called the Clifford group.

}
{ Let $X$,$Y$, and $Z$ be the three non-trivial one-qubit Pauli operators.
}
The Bell measurement is a complete orthogonal measurement on two
qubits made out of the measurement operators\fullv{ $\{\proj{\Psi_{0,0}},
\proj{\Psi_{0,1}}, \proj{\Psi_{1,0}}, \proj{\Psi_{1,1}}\}$ where
$\ket{\Psi_{0,0}}:=
\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$,
$\ket{\Psi_{0,1}}:=
\frac{1}{\sqrt{2}}(\ket{00}-\ket{11})$,
$\ket{\Psi_{1,0}}:=
\frac{1}{\sqrt{2}}(\ket{01}+\ket{10})$, and
$\ket{\Psi_{1,1}}:=
\frac{1}{\sqrt{2}}(\ket{01}-\ket{10})$.
The outcome $\ket{\Psi_{x,z}}$ of the Bell measurement is identified by the
two classical bits $(x,z) \in \{0,1\}^2$.}{
$\{\proj{\Psi_{x,y}}\}_{x,y\in\{0,1\}}$
where $\ket{\Psi_{x,y}} := \frac{1}{\sqrt{2}}(\ket{0, x} +  (-1)^y \ket{1,\overline{x}})$.
We say that the outcome  of a Bell measurement is $(x,y)\in\{0,1\}^2$ if
$\proj{\Psi_{x,y}}$ has been observed.
}
The quantum one-time-pad is a perfectly secure encryption of quantum
states\cite{AMTW00}. It encrypts a qubit $\ket{\psi}$ as $X^x
Z^z\ket{\psi}$, where the key is two classical bits, $(x,z) \in
\{0,1\}^2$ and $X^0 Z^0 = \Idt$, $X^0 Z^1 = Z$, $X^1 Z^0 = X$ and $X^1
Z^1 = Y$ are the Pauli operators.\fullv{ Quantum
teleportation\cite{BBCJPW93} can be used to implement the quantum
one-time-pad. Consider the teleportation circuit in
Fig.~\ref{fig:teleportation}. If the state to encrypt is $\ket{\psi}$
then the state of the lower wire  before entering the
out-dashed box is the encryption of $\ket{\psi}$ under a uniformly
random key produced by the Bell measurement. The two gates inside the
dashed-box is the decryption circuit.}{}

\newcommand{\ensuremath{\rho_{\mathrm{in}}}}{\ensuremath{\rho_{\mathrm{in}}}}

\subsection{Modeling two-party strategies}\label{twoparty}

Consider an interactive two-party strategy $\Pi^{\qop{O}}$ between
parties $\ensuremath{\mathscr{A}}$ and $\ensuremath{\mathscr{B}}$ and oracle calls \qop{O}.
$\Pi^{\qop{O}}$ can be modeled by a sequence of quantum operations for
each player together with some oracle calls also modeled by quantum
operations.  Each quantum operation in the sequence corresponds to the
action of one party at a certain step of the strategy.  The following
definition is a straightforward adaptation of $n$-turn interactive
quantum strategies as described in \cite{GW07}.  The main difference
is that here, we provide a joint input state to both parties and that
quantum transmissions taking place during the execution is modeled by
a quantum operation; one that is moving a state on one party's side to the
other party.

\begin{definition}
A {\em $n$--step two party strategy with oracle calls} denoted
$\Pi^{\qop{O}}=(\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ consists of:
\begin{enumerate}
\item

  input spaces ${\hreg{A}}_0$ and ${\hreg{B}}_0$ for parties \ensuremath{\mathscr{A}}\ and
  \ensuremath{\mathscr{B}}\ respectively,

\item

  memory spaces ${\hreg{A}}_1,\ldots,{\hreg{A}}_n$ and
  ${\hreg{B}}_1,\ldots,{\hreg{B}}_n$ for \ensuremath{\mathscr{A}}\ and \ensuremath{\mathscr{B}}\
  respectively,

\item

  an $n$-tuple of quantum operations $(\alice{1},\ldots,\alice{n})$
  for \ensuremath{\mathscr{A}}, $\alice{i}: \linop{{\hreg{A}}_{i-1}} \mapsto
  \linop{{\hreg{A}}_{i}}$, $(1\leq i \leq n)$,

\item

  an $n$-tuple of quantum operations $(\bob{1},\ldots,\bob{n})$ for
  \ensuremath{\mathscr{B}}, $\bob{i}: \linop{{\hreg{B}}_{i-1}} \mapsto
  \linop{{\hreg{B}}_{i}}$, $(1\leq i \leq n)$,

\item

  memory spaces $\hreg{A}_1,\ldots, \hreg{A}_n$ and
  $\hreg{B}_1,\ldots,\hreg{B}_n$ can be written as $\hreg{A}_i
  =\ao{i}\otimes \hreg{A}'_i$ and $\hreg{B}_i = \bo{i}\otimes
  \hreg{B}'_i$, $(1\leq i \leq n)$, and $\qop{O} =
  (\qop{O}_1,\qop{O}_2,\ldots, \qop{O}_n)$ is an $n$-tuple of quantum
  operations: $\qop{O}_i : \linop{\ao{i}\otimes\bo{i}} \mapsto
  \linop{\ao{i}\otimes\bo{i}}$, $(1\leq i \leq n)$.

\end{enumerate}
If $\Pi=(\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},n)$ is a $n$-turn two-party protocol then the
final state of the interaction upon input state $\ensuremath{\rho_{\mathrm{in}}}\in
\dens{{\hreg{A}}_0\otimes {\hreg{B}}_0 \otimes \hreg{R}}$, where
$\hreg{R}$ is a system of dimension $\dim \hreg{R} = \dim \hreg{A}_0
\dim \hreg{B}_0$, is:
\[
\begin{split}
[\ensuremath{\mathscr{A}}\circledast\ensuremath{\mathscr{B}}](\ensuremath{\rho_{\mathrm{in}}}) := & (\Idt_{\linop{\hreg{A}'_n \otimes \hreg{B}'_n\otimes \hreg{R}}}\otimes\qop{O}_n)(\alice{n}\otimes\bob{n} \otimes  \Idt_\hreg{R})\\
&\ldots(\Idt_{\linop{\hreg{A}'_1 \otimes \hreg{B}'_1\otimes \hreg{R}}}\otimes\qop{O}_1)(\alice{1}\otimes\bob{1} \otimes  \Idt_\hreg{R})(\ensuremath{\rho_{\mathrm{in}}}) \enspace.
\end{split}
\]
\end{definition}
Step $i$ of the strategy corresponds to the actions of $\alice{i}$ and
$\bob{i}$ followed by the oracle call $\qop{O}_i$.

Note that we consider input states defined on the input systems
together with a reference system $\hreg{R}$; this allows us to show
the correctness and privacy of the protocol not only for pure inputs,
but also for inputs that are entangled with a third party. This is the
most general case allowed by quantum mechanics.

A two-party strategy is therefore defined by quantum operation tuples
$(\alice{1},\ldots,\alice{n})$, $(\bob{1},\ldots,\bob{n})$, and
$(\qop{O}_1,\ldots,\qop{O}_n)$. These operations also
define working spaces ${\hreg{A}}_0,\ldots,{\hreg{A}}_n,
{\hreg{B}}_0,\ldots,{\hreg{B}}_n$ together with the input-output spaces to the oracle calls
 $\hreg{A}_i^{\qop{O}}$ and $\hreg{B}_i^{\qop{O}}$ for $1\leq i \leq n$.

A \emph{communication oracle} from Alice to Bob is modeled by having
$\ao{i} \approx \bo{i}$ and letting $\qop{O}_i$ move the state in
$\ao{i}$ to $\bo{i}$ and erase $\ao{i}$. Similarly for
communication in the other direction. We define a \emph{bare model}
protocol to be one which only uses communication oracles.

\section{Specious Quantum Adversaries}\label{semihonest}

\subsection{Protocols for  two-party evaluation}\label{protdef}

Let us consider two-party protocols for the quantum evaluation of
unitary transform $U\in \unit{{\hreg{A}}_0\otimes{\hreg{B}}_0}$
between parties \ensuremath{\mathscr{A}}\ and \ensuremath{\mathscr{B}}\ upon joint input state
$\ensuremath{\rho_{\mathrm{in}}}\in\dens{{\hreg{A}}_0\otimes{\hreg{B}}_0 \otimes \hreg{R}}$\fullv{.
We define these protocols as two-party interactive strategies with
placeholder for the output as follows:}{:}

\begin{definition}\label{twopartyprot}
  A \emph{two-party protocol $\puq{U}=(\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ for
  $U\in \unit{{\hreg{A}}_0\otimes{\hreg{B}}_0}$} is an $n$--step
  two-party strategy with oracle calls, where $\hreg{A}_{n}\approx
  \hreg{A}_0$ and $\hreg{B}_n \approx \hreg{B}_0$. It is said to be
  \emph{$\varepsilon$--correct} if
  \[ \Delta\left([\ensuremath{\mathscr{A}}\circledast\ensuremath{\mathscr{B}}](\ensuremath{\rho_{\mathrm{in}}}),
     (U \otimes \Idt_{\hreg{R}})\cdot\ensuremath{\rho_{\mathrm{in}}}\right)
     \leq \varepsilon\,\,\,\,\,\, \text{ for all } \ensuremath{\rho_{\mathrm{in}}}\in
     \dens{{\hreg{A}}_0\otimes{\hreg{B}}_0 \otimes \hreg{R}}\enspace .
     \]
  We denote by $\pu{U}$ a two-party protocol in the {\em bare model}
  where, without loss of generality, we assume that $\qop{O}_{2i+1}$
  ($0\leq i \leq \lfloor \frac{n}{2} \rfloor$) implements a
  communication channel from \ensuremath{\mathscr{A}}\ to \ensuremath{\mathscr{B}}\ and $\qop{O}_{2i}$
  ($1\leq i \leq \lfloor \frac{n}{2} \rfloor$) implements a
  communication channel from \ensuremath{\mathscr{B}}\ to \ensuremath{\mathscr{A}}. Communication oracles
  are said to be {\em trivial}.
\end{definition}
In other words, a two-party protocol $\puq{U}$ for unitary $U$ is a
two-party interactive strategy where, at the end, the output of the
computation is stored in the memory of the players. $\puq{U}$ is
correct if, when restricted to the output registers (and $\hreg{R}$),
the final quantum state shared by \ensuremath{\mathscr{A}}\ and \ensuremath{\mathscr{B}}\ is $(U \otimes
\Idt_{\hreg{R}})\cdot \ensuremath{\rho_{\mathrm{in}}}$.

As it will become clear when we discuss privacy in
Sect.~\ref{privacy}, we need to consider the joint state at any step
during the evolution of the protocol\fullv{.  We define,}{:}
\begin{align}
  \hstatei{1}{\ensuremath{\rho_{\mathrm{in}}}} & := (\Idt_{\linop{\hreg{A}'_1\otimes
      \hreg{B}'_1\otimes\hreg{R}}}\otimes \qop{O}_1) (\alice{1}\otimes
      \bob{1}\otimes \Idt_{\linop{\hreg{R}}})(\ensuremath{\rho_{\mathrm{in}}}), \nonumber \\
  \hstatei{i+1}{\ensuremath{\rho_{\mathrm{in}}}} &:= (\Idt_{\linop{\hreg{B}'_{i+1} \otimes
       \hreg{A}'_{i+1}\otimes\hreg{R}}}\otimes\qop{O}_{i+1})(\alice{i+1}\otimes
       \bob{i+1} \otimes\Idt_{\linop{\hreg{R}}}) (\hstatei{i}{\ensuremath{\rho_{\mathrm{in}}}})
       \enspace , \label{statei}
\end{align}
for $1\leq i <n$.
We also write the final state of $\puq{U}$  upon input state $\ensuremath{\rho_{\mathrm{in}}}$ as
$\hstatei{n}{\ensuremath{\rho_{\mathrm{in}}}} = [\ensuremath{\mathscr{A}}\circledast\ensuremath{\mathscr{B}}](\ensuremath{\rho_{\mathrm{in}}})$.

\subsection{Modeling Specious Adversaries}

\newcommand{\ensuremath{t_\aprot}}{\ensuremath{t_\ensuremath{\mathscr{A}}}}
\newcommand{\ensuremath{t_\bprot}}{\ensuremath{t_\ensuremath{\mathscr{B}}}}

Intuitively, a specious adversary acts in any way apparently
indistinguishable from the honest behavior, in the sense that
no audit can distinguish the behavior of the adversary from
the honest one.

More formally, a specious adversary in
$\puq{U}=(\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ may use an arbitrary large quantum
memory space. However, at any step $1\leq i\leq n$, the adversary can
transform its own current state to one that is indistinguishable from
the honest joint state. These transforms are modeled by quantum
operations, one for each step of the adversary in $\puq{U}$, and are
part of the adversary's specification. We denote by
$(\trans{1},\ldots,\trans{n})$ these quantum operations where
$\trans{i}$ produces a valid transcript at the end of the $i$--th
step.

Let $\ensuremath{\ad{A}}$ and $\ensuremath{\ad{B}}$ be adversaries in $\puq{U}$.  We denote by
$\puq{U}(\ensuremath{\ad{A}}) = (\ensuremath{\ad{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ and
$\puq{U}(\ensuremath{\ad{B}})=(\ensuremath{\mathscr{A}},\ensuremath{\ad{B}},\qop{O},n)$ the resulting $n$--step
two-party strategies.  We denote by $\astatei{i}{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}$ the
state defined in (\ref{statei}) for protocol $\puq{U}(\ensuremath{\ad{A}})$ and
similarly by $\astatei{i}{\ensuremath{\ad{B}}}{\ensuremath{\rho_{\mathrm{in}}}}$ that state for protocol
$\puq{U}(\ensuremath{\ad{B}})$.

Adding the possibility for the adversary to be
$\varepsilon$-\emph{close} to honest, we get the following definition:

\begin{definition}\label{specious}
  Let $\puq{U} = (\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ be an $n$--step two-party
  protocol with oracle calls for $U \in \unit{{\hreg{A}}_0\otimes
  {\hreg{B}}_0}$. We say that:
  \begin{itemize}
  \item

    \ensuremath{\ad{A}}\ is \emph{$\varepsilon$--specious} if $\puq{U}(\ensuremath{\ad{A}}) =
    (\ensuremath{\ad{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ is an $n$--step two-party strategy with
    $\tilde{\hreg{A}}_0={\hreg{A}}_0$ and there exists a sequence of
    quantum operations $(\trans{1},\ldots,\trans{n})$ such that:
    \begin{enumerate}
    \item

      for every $1\leq i \leq n$, $\trans{i}:\linop{\tilde{\hreg{A}}_i}
      \mapsto \linop{{\hreg{A}}_i}$,

    \item

      for every input state $\ensuremath{\rho_{\mathrm{in}}} \in \dens{{\hreg{A}}_0\otimes
	{\hreg{B}}_0 \otimes \hreg{R}}$, and for all $1\leq i \leq n$,
      \[ \Delta\left((\trans{i}\otimes \Idt_{\linop{\hreg{B}_i \otimes
	\hreg{R}}})
      \left(\astatei{i}{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}\right),
      \hstatei{i}{\ensuremath{\rho_{\mathrm{in}}}}\right) \leq \varepsilon\enspace .
      \]
    \end{enumerate}

  \item

    \ensuremath{\ad{B}}\ is \emph{$\varepsilon$--specious} if $\puq{U}(\ensuremath{\ad{B}}) =
    (\ensuremath{\mathscr{A}},\ensuremath{\ad{B}},\qop{O},n)$ is a $n$--step two-party strategy with
    $\tilde{\hreg{B}}_0={\hreg{B}}_0$ and there exists a sequence of
    quantum operations $(\trans{1},\ldots,\trans{n})$ \fullv{such that:
    \begin{enumerate}
    \item

      for every $1\leq i \leq n$,
      $\trans{i}:\linop{\tilde{\hreg{B}}_{i}} \mapsto
      \linop{{\hreg{B}}_{i}}$,

    \item

      for every input state $\ensuremath{\rho_{\mathrm{in}}} \in \dens{{\hreg{A}}_0\otimes
	{\hreg{B}}_0 \otimes \hreg{R}}$, and for all $1\leq i \leq n$,
      \[ \Delta\left((\Idt_{\linop{\hreg{A}_i \otimes
	  \hreg{R}}}\otimes\trans{i})
          \left(\astatei{i}{\ensuremath{\ad{B}}}{\ensuremath{\rho_{\mathrm{in}}}}\right),
          \hstatei{i}{\ensuremath{\rho_{\mathrm{in}}}}\right) \leq \varepsilon\enspace .
      \]
    \end{enumerate}}{defined as before with $\hreg{B}_i, \tilde{\hreg{B}}_{i}$, and $\astatei{i}{\ensuremath{\ad{B}}}{\ensuremath{\rho_{\mathrm{in}}}}$
    replacing $\hreg{A}_i, \tilde{\hreg{A}}_{i}$, and  $\astatei{i}{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}$ respectively.}
  \end{itemize}
  If a party is $\varepsilon(m)$--specious with $\varepsilon(m)$
  negligible for $m$ a security parameter then we say that this party
  is {\em statistically specious}.
\end{definition}

\subsection{Privacy}\label{privacy}

Privacy for $\puq{U}$ is defined as the ability for a simulator,
having only access to the adversary's input and the ideal
functionality $U$, to reproduce the state of the adversary at any step
in the execution of $\puq{U}$. Our definition is similar to the one
introduced in \cite{Watrous02} for statistical zero-knowledge proof
systems.

A simulator for an adversary in $\puq{U}$ is represented by a sequence
of quantum operations $( \simul{i} )_{i=1}^n$, where $\simul{i}$
re-produces the view of the adversary after step $i$.  \simul{i}
initially receives the adversary's input and has access to the ideal
functionality for $U$ evaluated upon the joint input of the adversary
and the honest player. Because of no-cloning, a simulator calling $U$
loses its input, and the input might be required to simulate
e.g.~early steps in the protocol, so we have to allow that $\simul{i}$
does not call $U$. For this purpose we introduce a bit
$q_i\in\{0,1\}$. When $q_i=0$, \simul{i}\ does not call $U$ and when
$q_i=1$, $\simul{i}$ must first call the ideal functionality $U$
before performing some post-processing. More precisely,

\begin{definition}\label{sim}
  Let $\puq{U}=(\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ be an $n$--step two-party
  protocol for $U\in \dens{\hreg{A}_0\otimes\hreg{B}_0}$. Then,
  \begin{itemize}
  \item

    \emph{$\simulator{\ensuremath{\ad{A}}}=\langle (\simul{1},\ldots, \simul{n}), q
      \rangle$ is a simulator for adversary \ensuremath{\ad{A}}\ in \puq{U}} if it
      consists of:
      \begin{enumerate}
      \item

	a sequence of quantum operations
	$(\simul{1},\ldots,\simul{n})$ where for $1\leq i \leq n$,
	$\simul{i} : \linop{\hreg{A}_0} \mapsto
	\linop{\tilde{\hreg{A}}_i}$,\label{cc1}

      \item

	a sequence of bits $q\in \{0,1\}^n$ determining if the simulator calls the ideal functionality at step $i$: $q_i = 1$ iff the simulator calls the ideal functionality.
        \label{cc2}
      \end{enumerate}

    \item

      Similarly, \emph{$\simulator{\ensuremath{\ad{B}}}=\langle (\simul{1},\ldots,
	\simul{n}), q' \rangle$ is a simulator for adversary \ensuremath{\ad{B}}\ in
	\puq{U}} \fullv{if it consists of:
      \begin{enumerate}
      \item

	a sequence of quantum operations
        $(\simul{1},\ldots,\simul{n})$ where for $1\leq i\leq n$,
        $\simul{i} : \linop{\hreg{B}_0} \mapsto
        \linop{\tilde{\hreg{B}}_{i}}$

      \item

	a sequence of bits $q'\in \{0,1\}^{n}$ determining if the simulator calls the ideal functionality at step $i$: $q'_i = 1$ iff the simulator calls the ideal functionality.

      \end{enumerate}}{if it satisfies conditions \ref{cc1} and \ref{cc2} above with $q', \hreg{B}_0, \hreg{B}_i$, and $\tilde{\hreg{B}}_i$
      replacing $q,\hreg{A}_0, \hreg{A}_i$, and $\tilde{\hreg{A}}_i$ respectively. }
  \end{itemize}
\end{definition}
Given an input state $\ensuremath{\rho_{\mathrm{in}}} \in \dens{\hreg{A}_0 \otimes \hreg{B}_0
\otimes \hreg{R}}$, we define the \ensuremath{\ad{A}}'s respectively \ensuremath{\ad{B}}'s simulated views  as:
\begin{align*}
	  \view{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}{i}&:=\trace[\hreg{B}_0]{(\simul{i}\otimes
	  \Idt_{\linop{\hreg{B}_0 \otimes \hreg{R}}})\left( (U^{q_i}
	  \otimes \Idt_{\hreg{R}})\cdot \ensuremath{\rho_{\mathrm{in}}}\right)}\ ,\\
	  \view{\ensuremath{\ad{B}}}{\ensuremath{\rho_{\mathrm{in}}}}{i}&:=\trace[\hreg{A}_0]{(\Idt_{\linop{\hreg{A}_0
	  \otimes \hreg{R}}}\otimes \simul{i})\left( (U^{q'_i} \otimes
	  \Idt_{\hreg{R}})\cdot \ensuremath{\rho_{\mathrm{in}}}\right)}\enspace .
\end{align*}
We say that protocol $\puq{U}$ is private against specious adversaries
if there exits a simulator for the view at any step of any such
adversary. In more details,

\begin{definition}\label{privdef}
  Let $\puq{U}=(\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},\qop{O},n)$ be a protocol for $U\in
  \unit{\hreg{A}_0\otimes {\hreg{B}}_0}$ and let $0 \leq \delta\leq
  1$.  We say that $\puq{U}$ is {\em $\delta$--private against
  $\varepsilon$--specious \ensuremath{\ad{A}}} if there exists a simulator
  $\simulator{\ensuremath{\ad{A}}}$ such that for all input states $\ensuremath{\rho_{\mathrm{in}}} \in
  \dens{\hreg{A}_0\otimes \hreg{B}_0 \otimes \hreg{R}}$ and for all $1
  \leq i \leq n$, $\Delta\left(\view{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}{i},
  \trace[\hreg{B}_i]{\astatei{i}{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}} \right) \leq \delta.$
  Similarly, we say that $\pu{U}$ is {\em $\delta$--private against
  $\varepsilon$--specious \ensuremath{\ad{B}}} if there exists a simulator
  $\simulator{\ensuremath{\ad{B}}}$ such that for all input states $\ensuremath{\rho_{\mathrm{in}}} \in
  \dens{\hreg{A}_0\otimes \hreg{B}_0 \otimes \hreg{R}}$ and for all $1
  \leq i \leq n$, $\Delta\left(\view{\ensuremath{\ad{B}}}{\ensuremath{\rho_{\mathrm{in}}}}{i},
  \trace[\hreg{A}_{i}]{\astatei{i}{\ensuremath{\ad{B}}}{\ensuremath{\rho_{\mathrm{in}}}}} \right) \leq
  \delta.$ Protocol $\puq{U}$ is {\em $\delta$--private against
  $\varepsilon$--specious adversaries} if it is $\delta$--private
  against both\delete{$\varepsilon$--specious} \ensuremath{\ad{A}}\ and \ensuremath{\ad{B}}. For
  $\gamma>0$, if $\puq{U}$ is $2^{-\gamma
  m}$--private\delete{against specious adversaries} for $m\in \N^+$ a
  security parameter then we say that $\puq{U}$ is \emph{statistically
  private\delete{ against specious adversaries}}.
\end{definition}

\fullv{One should keep in mind that $\delta$ should be kept small compared to the number of rounds, since the protocol is only secure if we can ensure that, with high probability, the adversary cannot behave differently in the simulated world at \emph{any} of the rounds. If $\delta n$ is kept small, we can use the union bound over all the rounds to ensure this.}{}

We show next that for some unitary, statistical privacy cannot be
satisfied by any protocol
 in the bare model.

\section{Unitaries with no private protocols}\label{impossiblesect}

In this section, we show that no statistically private protocol for
the swap gate exists in the bare model.
The swap gate, denoted {\ensuremath{\sf SWAP}},  is the following unitary transform:
\[ {\ensuremath{\sf SWAP}} : \ket{\phi_A}^{\hreg{A}_0} \ket{\phi_B}^{\hreg{B}_0} \mapsto
   \ket{\phi_B}^{\hreg{A}_0}\ket{\phi_A}^{\hreg{B}_0}\enspace ,
\]
for any one qubit states $\ket{\phi_A}\in \hreg{A}_0$ and
$\ket{\phi_B}\in \hreg{B}_0$ (i.e.,
$\dim{(\hreg{A}_0)}=\dim{(\hreg{B}_0)}=2$).  Notice that {\ensuremath{\sf SWAP}}\ is in
the Clifford group since it can be implemented with three {\sf CNOT}\
gates.  It means that universality is not required (gates in the
Clifford groups are not universal for quantum computation) for a
unitary to be impossible to evaluate privately. The impossibility of
{\ensuremath{\sf SWAP}}\ essentially follows from no cloning.

\begin{theorem}[Impossibility of swapping] \label{noswap}
  There is no correct and statistically private two-party protocol
  $\pu{{\ensuremath{\sf SWAP}}}=(\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}},\qop{O},n(m))$ in the bare model.
\end{theorem}

\fullv{}{
\begin{proof}
Suppose that there exists an $\varepsilon$-correct, $\varepsilon$-private protocol in the bare model for ${\ensuremath{\sf SWAP}}$ for sufficiently small $\varepsilon$; we will show that this implies that one of the two players must \emph{lose} information upon receiving a message, which is clearly impossible.

We will consider the following particular pure input state: $\ket{\varphi} := \ket{\Psi_{0,0}}^{\hreg{A}_0 \hreg{R}_{\hreg{A}}} \otimes \ket{\Psi_{0,0}}^{\hreg{B}_0 \hreg{R}_{\hreg{B}}}$, a maximally entangled state between $\hreg{A}_0 \otimes \hreg{B}_0$ and the reference system $\hreg{R}_{\hreg{A}} \otimes \hreg{R}_{\hreg{B}}$ that is broken down into two subsystems for convenience. Furthermore, we will consider the ``purified'' versions of the honest players for this protocol; in other words, we will assume that the super-operators $\ensuremath{\mathscr{A}}_1,\dots,\ensuremath{\mathscr{A}}_n$ and $\ensuremath{\mathscr{B}}_1,\dots,\ensuremath{\mathscr{B}}_n$ are in fact linear isometries and that therefore the players never discard any information unless they have to send it to the other party. The global state $\hstatei{i}{\varphi}$ after step $i$ is therefore a pure state on $\hreg{A}_i \otimes \hreg{B}_i \otimes \hreg{R}_{\hreg{A}} \otimes \hreg{R}_{\hreg{B}}$.

After step $i$ of the protocol (i.e., after the $i$th message has been sent), Alice's state must either depend only on her own original input (if $q_i = 0$ for her simulator), or on Bob's original input (if $q_i=1$). More precisely, by the definition of privacy (Definition \ref{privdef}), we have that
\[
\Delta\left( \view{\ensuremath{\mathscr{A}}}{\varphi}{i}, \tr_{\hreg{B}_i}[\hstatei{i}{\varphi}] \right) \leq \varepsilon \enspace ,
\]
where $\view{\ensuremath{\mathscr{A}}}{\varphi}{i}$ is \ensuremath{\mathscr{A}}'s simulated view after step $i$ and $\hstatei{i}{\varphi}$ is the global state in the real protocol after step $i$. Now, suppose that $q_i=0$, and let $\ket{\xi} \in \hreg{A}_i \otimes \hreg{R}_{\hreg{A}} \otimes \hreg{R}_{\hreg{B}}' \otimes \hreg{Z}$ be a purification of $\view{\ensuremath{\mathscr{A}}}{\varphi}{i}$ with $\hreg{Z}$ being the purifying system, and $\hreg{R}_{\hreg{B}}$ renamed for upcoming technical reasons. The pure state $\ket{\xi} \otimes \ket{\Psi_{0,0}}^{\hreg{R}_{\hreg{B}} \hreg{B}_0}$ has the same reduced density matrix as $\view{\ensuremath{\mathscr{A}}}{\varphi}{i}$ on $\hreg{A}_i \otimes \hreg{R}_{\hreg{A}} \otimes \hreg{R}_{\hreg{B}}$. Hence, by Uhlmann's theorem, there exists a linear isometry $V : \hreg{B}_i \rightarrow \hreg{B}_0 \otimes \hreg{Z} \otimes \hreg{R}_{\hreg{B}}'$ such that
\[
V \view{\ensuremath{\mathscr{A}}}{\varphi}{i} V^\dagger  = \ket{\xi}\bra{\xi} \otimes \ket{\Psi_{0,0}}\bra{\Psi_{0,0}}^{\hreg{B}_0\hreg{R}_{\hreg{B}}}
\]
and hence
\[
\Delta\left( V \hstatei{i}{\varphi} V^\dagger, \ket{\xi}\bra{\xi} \otimes \ket{\Psi_{0,0}}\bra{\Psi_{0,0}}^{\hreg{B}_0\hreg{R}_{\hreg{B}}} \right) \leq \sqrt{2\varepsilon}
\enspace .
\]
This means that if $q_i = 0$, then Bob is still capable of reconstructing his own input state after step $i$ by applying $V$ to his working register. Clearly, this means that $q_i' = 0$ (i.e., Bob's simulator must also not call ${\ensuremath{\sf SWAP}}$), and therefore, by the same argument, Alice must also be able to reconstruct her own input with an isometry $V_A : \hreg{A}_i \rightarrow \hreg{B}_0 \otimes \hreg{Z} \otimes \hreg{R}'_{\hreg{A}}$. The same argument also holds if $q_i = 1$: we then conclude that $q_i' = 1$ and that Alice and Bob must have each other's inputs; no intermediate situation is possible. We conclude that, at every step $i$ of the protocol, $q_i = q'_i$.

Now, before the protocol starts, Alice must have her input, and Bob must have his, hence, $q_0 = q_0' = 0$. At the end, the two inputs must have been swapped, which means that $q_n = q'_n = 1$; there must therefore be a step $k$ in the protocol after which the two inputs are swapped but not before, meaning that $q_k = 1$ and $q_{k-1} = 0$. But at each step, only one player receives information, which means that at this step $k$, the player who received the message must lose the ability to reconstruct his own input, which is clearly impossible. \qed
\end{proof}
}

Using this line of reasoning, Theorem~\ref{noswap} can be extended to apply to any protocol for almost any unitary preventing both parties to recover their input states from its output.

\subsubsection{Sufficient Assumptions for Private {\ensuremath{\sf SWAP}}.}
A private protocol for {\ensuremath{\sf SWAP}}\ in the bare model would exist if the
players could rely on special relativity and a lower bound on
their separation in space: they simply send their messages
simultaneously. The fact that messages cannot travel faster than the
speed of light ensures that the messages are independent of each
other.
It is also straightforward to devise a private protocol for {\ensuremath{\sf SWAP}}\
based on commitment schemes.  \ensuremath{\mathscr{A}}\ sends one half EPR-pair to
\ensuremath{\mathscr{B}}\ while keeping the other half. \ensuremath{\mathscr{A}}\ then teleports (without
announcing the outcome of the measurement) her register and commits on
the outcome of the Bell measurement. \ensuremath{\mathscr{B}}\ sends his register to
\ensuremath{\mathscr{A}}\ before she opens her commitment. \fullv{This allows \ensuremath{\mathscr{B}}\ to
reconstruct \ensuremath{\mathscr{A}}'s initial state.}{}

\section{The Protocol}\label{prot}

\newcommand{\qcol}[1]{\ensuremath{\mathbf{Co}_{#1}}}
\newcommand{\ensuremath{\mathbf{AND}}}{\ensuremath{\mathbf{AND}}}
\newcommand{\ensuremath{n_U}}{\ensuremath{n_U}}

We now describe a private protocol for the two-party evaluation of any
unitary $U\in \unit{\hreg{A}_0\otimes\hreg{B}_0}$ denoted by
$\pup{U}^{\qop{O}}=(\ensuremath{\aprot^*},\ensuremath{\bprot^*},\qop{O},n_U+1)$ where $U$ is represented by
a circuit $C_U$ with $u$ gates in \ensuremath{{\cal UG}}.
We slightly abuse the notation with respect to the parameter $n_U+1$.
Given circuit $C_U$, we let $n_U$ be the number of oracle
calls (including calls to communication oracles). Setting the last
parameter to $n_U+1$ instead of $n_U$ comes from the fact
that in our protocol, \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ have to perform a last
operation each in order to get their outcome. These last operations
do not involve a call to any oracle.
Let $G_j$ be the $j$-th gate
in $C_U = G_{u} G_{u-1} \ldots G_1$.  The protocol is obtained by
composing sub-protocols for each gate similarly to well-known
classical constructions\cite{Yao86,kilian88}.  Notice that
$\pup{U}^{\qop{O}}$ will not be presented in the form of
Definition~\ref{twopartyprot}.  \ensuremath{\aprot^*}\ is not necessarily sending
the first and the last messages. This can be done without consequences
since we provide a simulation for each step where a message from the
honest party is received or the output of a call to an ideal
functionality is available. Putting $\pup{U}^{\qop{O}}$ in the
standard form of Definition~\ref{twopartyprot} is straightforward and
changes nothing to the proof of privacy.

The evaluation of each gate is performed over shared encrypted states.
Each wire in $C_U$ will be updated from initially holding the input
$\ensuremath{\rho_{\mathrm{in}}} \in \dens{\hreg{A}_0\otimes\hreg{B}_0\otimes\hreg{R}}$ to
finally holding the output $(U\otimes\Idt_{\hreg{R}} )\cdot \ensuremath{\rho_{\mathrm{in}}} \in
\dens{\hreg{A}_0\otimes \hreg{B}_0\otimes\hreg{R}}$.  The state of
wires $\wire{w}\in \hreg{A}_0\cup\hreg{B}_0$ after the evaluation of
$G_j$ are stored at \ensuremath{\aprot^*}'s or \ensuremath{\bprot^*}'s according if $\wire{w}\in
\hreg{A}_0$ or $\wire{w}\in \hreg{B}_0$.  The shared encryption keys
for wire $\wire{w}\in \hreg{A}_0 \cup \hreg{B}_0$ updated after the
evaluation of $G_j$ are denoted by
$\keya{w}{j}=(\kxa{w}{j},\kza{w}{j})\in \{0,1\}^2$ and
$\keyb{w}{j}=(\kxb{w}{j},\kzb{w}{j})\in \{0,1\}^2$ for
\ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ respectively and are held privately in internal
registers of each party.

The final phase of the protocol is where a call to an ideal
functionality is required.  \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ exchange their own
part of each encryption key for the other party's wires. In order
to do this, the {\em key-releasing phase} invokes an ideal {\ensuremath{\sf SWAP}}-gate
as functionality:
$\qop{O}_{\ensuremath{n_U}}:\linop{\hreg{A}^{\qop{O}}_{\ensuremath{n_U}}\otimes
   \hreg{B}^{\qop{O}}_{\ensuremath{n_U}}} \mapsto
   \linop{\hreg{A}^{\qop{O}}_{\ensuremath{n_U}}\otimes
   \hreg{B}^{\qop{O}}_{\ensuremath{n_U}}}$,
where $\qop{O}_{\ensuremath{n_U}}(\rho):= {\ensuremath{\sf SWAP}}\cdot \rho$.  Upon
joint input state $\ensuremath{\rho_{\mathrm{in}}}\in
\dens{\hreg{A}_0\otimes\hreg{B}_0\otimes\hreg{R}}$, protocol
$\pup{U}^{\qop{O}(U)}$ runs the following phases:
\begin{description}
\item[Initialization:]

  We assume that \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ have agreed upon a description
  of $U$ by a circuit $C_U$ made out of $u$ gates $(G_1,\ldots,
  G_{u})$ in \ensuremath{{\cal UG}}.  For all wires $\wire{w}\in\hreg{A}_0\cup
  \hreg{B}_0$, \ensuremath{\aprot^*}\ and $\ensuremath{\bprot^*}$ set their initial encryption
  keys as $\keya{w}{0}=(\kxa{w}{0},\kza{w}{0}):=(0,0)$ and
  $\keyb{w}{0}=(\kxb{w}{0},\kzb{w}{0}):=(0,0)$ respectively.

\item[Evaluation:]

  For each gate number $1\leq j \leq u$, \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\
  evaluate $G_j$ as described in details below.  This evaluation
  results in shared encryption under keys
  $\keya{w}{j}=(\kxa{w}{j},\kza{w}{j})$ and
  $\keyb{w}{j}=(\kxb{w}{j},\kzb{w}{j})$ for all wires $\wire{w}\in
  \hreg{A}_0\cup \hreg{B}_0$, which at that point hold a shared
  encryption of $((G_j G_{j-1} \ldots
  G_{1})\otimes\Idt_{\hreg{R}})\cdot \ensuremath{\rho_{\mathrm{in}}}$. Only the evaluation of
  the {\sf R}-gate requires a call to an ideal functionality (i.e., an
  {\sc and-box}).

\item[Key-Releasing:]

  Let $\hreg{A}^{\qop{O}}_{\ensuremath{n_U}}$ and $\hreg{B}^{\qop{O}}_{\ensuremath{n_U}}$ be
  the set of registers holding respectively
  $\keya{w}{u}=(\kxa{w}{u},\kza{w}{u})$ for $\wire{w}\in \hreg{B}_0$
  and $\keyb{w}{u}=(\kxb{w}{u},\kzb{w}{u})$ for $\wire{w}\in
  \hreg{A}_0$. We assume w.l.g that dimensions of both sets of
  registers are identical\footnote{Otherwise, add enough registers
  initially in state $\ket{0}$ to the smaller set.}:
  \begin{enumerate}
  \item

    \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ run the ideal functionality for the
    {\ensuremath{\sf SWAP}}-gate upon registers $\hreg{A}^{\qop{O}}_{\ensuremath{n_U}}$ and
    $\hreg{B}^{\qop{O}}_{\ensuremath{n_U}}$.

  \item

    \ensuremath{\aprot^*}\ applies the decryption operator
    $\keya{w}{}=(\kxa{w}{u}\oplus \kxb{w}{u}, \kza{w}{u}\oplus
    \kzb{w}{u})$ to each of her wires $\wire{w}\in \hreg{A}_0$.

  \item

    \ensuremath{\bprot^*}\ applies the decryption operator for key
    $\keyb{w}{}=(\kxa{w}{u}\oplus \kxb{w}{u}, \\ \kza{w}{u}\oplus
    \kzb{w}{u})$ to each of his wires $\wire{w}\in \hreg{B}_0$.

  \end{enumerate}
\end{description}
\fullv{In the following subsections \ref{sect:crypt} to
\ref{sect:rgate}, we describe the evaluation phase
for each gate in $\ensuremath{{\cal UG}}$.}{}

\subsubsection{Swapping for key-releasing.}
Notice that the key-releasing phase only uses the {\ensuremath{\sf SWAP}}-gate with classical input states. The reader might therefore wonder why this functionality is defined quantumly when a classical swap would work equally well.  The reason is that, perhaps somewhat surprisingly, a classical swap is a potentially stronger primitive than a quantum swap. From a classical swap one can build a quantum swap by encrypting the quantum states with classical keys, exchange the encrypted states using quantum communication, and then using the classical swap to exchange the keys. Obtaining a classical swap from a quantum one, however, is not obvious.  Suppose that registers \hreg{A}\ and \hreg{B}\ should be swapped classically while holding quantum states beforehand. These registers could be entangled with some purification registers before being swapped.  Using a quantum swap between \hreg{A}\ and \hreg{B}\ will always leave these registers entangled with the purification registers until they become measured while a classical swap will ensure that \hreg{A}\ and \hreg{B}\ become unentangled with the purification registers after its invocation. In other words, a classical swap could prevent an adversary from exploiting entanglement in his attack.

\subsubsection{The ideal AND-box functionality.}

As we are going to see next, a call to an ideal AND-box is required
during the evaluation of the {\sf R}-gate. Unlike the ideal {\ensuremath{\sf SWAP}}\ used
for key-releasing, the AND-box will be modeled by a purely classical
primitive denoted {\sc and-box}.  This is required for privacy of our protocol
since any implementation of it by some unitary will necessarily
leak\cite{SSS09}.  The quantum operation implementing it will first
measure the two one-qubit input registers in the computational basis
in order to get classical inputs $x,y \in\{0,1\}$ for \ensuremath{\aprot^*}\ and
\ensuremath{\bprot^*}\ respectively. The classical output bits are then set to
$a\in_R\{0,1\}$ for \ensuremath{\aprot^*}\ and $b=a\oplus x y$ for \ensuremath{\bprot^*}.

\subsection{Computing over Encrypted States}\label{sect:crypt}

Before the execution of $G_{j+1}$ in $C_U$, \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\
share an encryption of $\rho_j = \left((G_j\cdot G_{j-1} \cdot \ldots
\cdot G_1)\otimes \Idt_{\hreg{R}}\right) \cdot \ensuremath{\rho_{\mathrm{in}}}$ in registers\footnote{To ease the notation in
the following, we assume $\rho_j\in \dens{\hreg{A}_0 \otimes
\hreg{B}_0}$ rather than in $\dens{\hreg{A}_0 \otimes
\hreg{B}_0\otimes\hreg{R}}$. It is easy to see that this can be done
without loss of generality.}
holding wires $\wire{w}\in \hreg{A}_0\cup \hreg{B}_0$.  Each wire
$\wire{w}\in \hreg{A}_0 \cup \hreg{B}_0$ is encrypted by a shared
quantum one-time pad as
\begin{equation}\label{encrypt}
  \left(
  \left(
  \bigotimes_{\wire{w}\in \hreg{A}_0 \cup \hreg{B}_0}
  X^{X_{\ensuremath{\aprot^*}}^j(\wire{w})
    \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
  Z_{\ensuremath{\bprot^*}}^j(\wire{w})}\right)\otimes \Idt_{\hreg{R}} \right) \cdot
  \rho_j\enspace ,
\end{equation}
where $K_{\ensuremath{\aprot^*}}^{j}(\wire{w}) :=
(X_{\ensuremath{\aprot^*}}^j(\wire{w}),Z_{\ensuremath{\aprot^*}}^j(\wire{w}))\in \{0,1\}^2$ and
$K_{\ensuremath{\bprot^*}}^j(\wire{w}) :=
(X_{\ensuremath{\bprot^*}}^j(\wire{w}),Z_{\ensuremath{\bprot^*}}^j(\wire{w}))\in \{0,1\}^2$ are
two bits of secret keys for \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ respectively.  In
other words, wires $\wire{w}\in \hreg{A}_0 \cup \hreg{B}_0$ are
encrypted by $X^{x}Z^{z}$ where $x=X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus
X_{\ensuremath{\bprot^*}}^j(\wire{w})$ and $z=Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
Z_{\ensuremath{\bprot^*}}^j(\wire{w})$ are additive sharings for the encryption of
$\wire{w}$.  Then, evaluating $G_{j+1}$ upon state (\ref{encrypt})
will produce a new sharing
$K_A^{j+1}(\wire{w}):=(X_A^{j+1}(\wire{w}),Z_A^{j+1}(\wire{w}))$ and
$K_B^{j+1}(\wire{w}):= (X_B^{j+1}(\wire{w}),Z_B^{j+1}(\wire{w}))$ for
the encryption of state $\rho_{j+1} =
(G_{j+1}\otimes\Idt_{\hreg{R}})\cdot \rho_j $.  In the following, we
describe how to update the keys for the wires involved in the current
gate to be evaluated---all other wires retain their previous
values.

\subsection{Evaluation of Gates in the Pauli and Clifford Groups}\label{cliffeval}

\fullv{\subsubsection{Pauli gates.}}{}
Non-trivial Pauli gates (i.e., $X,Y,$ and $Z$) can easily be computed
on encrypted quantum states since they commute or anti-commute pairwise.
Let $G_{j+1}\in \{X,Y,Z\}$ be the Pauli gate to be executed on wire
$\wire{w}$.
\fullv{We have:
\begin{equation*}\label{paul}
  G_{j+1}   \left(X^{X_{\ensuremath{\aprot^*}}^i(\wire{w})
    \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
    Z_{\ensuremath{\bprot^*}}^j(\wire{w})}\right)

 = \pm \left( X^{X_{\ensuremath{\aprot^*}}^j(\wire{w})
    \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
    Z_{\ensuremath{\bprot^*}}^j(\wire{w})}\right) G_{j+1}

\enspace.
\end{equation*}}{}
It means that up to an irrelevant phase factor, it suffices for the
owner of \wire{w}\ to apply $G_{j+1}$ without the need for neither
party to update their shared keys, i.e.,
$K_{\ensuremath{\aprot^*}}^{j+1}(\wire{w}):=K_{\ensuremath{\aprot^*}}^{j}(\wire{w})$ and
$K_{\ensuremath{\bprot^*}}^{j+1}(\wire{w}):=K_{\ensuremath{\bprot^*}}^{j}(\wire{w})$.

\fullv{
\subsubsection{{\sf H},  {\sf P}{}, and {\sf CNOT}\   on local wires.}}{}
Now, suppose  that $G_{j+1}\in \{{\sf H}, {\sf P}\}$.
Each of these one-qubit gates applied upon
wire \wire{w}\
will be computed  by simply letting the party owning \wire{w}\
apply $G_{j+1}$.
\fullv{Since
\begin{eqnarray*}
{\sf H}\, \left(  X^{X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
          Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
          Z_{\ensuremath{\bprot^*}}^j(\wire{w})}\right)
&=&  \left( X^{Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus Z_{\ensuremath{\bprot^*}}^j(\wire{w})}
     Z^{X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
          X_{\ensuremath{\bprot^*}}^j(\wire{w})}\right)\, {\sf H}
          \enspace ,
          \mbox{ and }\\
 {\sf P}{}\, \left( X^{X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
           Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
          Z_{\ensuremath{\bprot^*}}^j(\wire{w})}\right
&=&  \left( X^{X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
     Z^{X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus
          Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus Z_{\ensuremath{\bprot^*}}^j(\wire{w})}
     \right) {\sf P} \enspace
\end{eqnarray*}
the encryption keys are updated as follows:}{Encryption
keys are updated locally as:}
\begin{eqnarray*}
{\sf H} &:&
K_{\ensuremath{\aprot^*}}^{j+1}
=
(X_{\ensuremath{\aprot^*}}^{j+1}(\wire{w}),Z_{\ensuremath{\aprot^*}}^{j+1}(\wire{w}))
:=
(Z_{\ensuremath{\aprot^*}}^i(\wire{w}),X_{\ensuremath{\aprot^*}}^j(\wire{w}))\enspace ,\\
& &
K_{\ensuremath{\bprot^*}}^{j+1}=(X_{\ensuremath{\bprot^*}}^{j+1}(\wire{w}),Z_{\ensuremath{\bprot^*}}^{j+1}(\wire{w}))
:=
(Z_{\ensuremath{\bprot^*}}^j(\wire{w}),X_{\ensuremath{\bprot^*}}^j(\wire{w}))\enspace ,\\
{\sf P}{} &:& K
_{\ensuremath{\aprot^*}}^{j+1}=(X_{\ensuremath{\aprot^*}}^{j+1}(\wire{w}),Z_{\ensuremath{\aprot^*}}^{j+1}(\wire{w}))
:=
(X_{\ensuremath{\aprot^*}}^j(\wire{w}),X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
   Z_{\ensuremath{\aprot^*}}^j(\wire{w}))\enspace ,\\
& &
K_{\ensuremath{\bprot^*}}^{j+1}
=
(X_{\ensuremath{\bprot^*}}^{j+1}(\wire{w}), Z_{\ensuremath{\bprot^*}}^{j+1}(\wire{w}))
:=
(X_{\ensuremath{\bprot^*}}^j(\wire{w}),X_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus
   Z_{\ensuremath{\bprot^*}}^j(\wire{w}))\enspace .
\end{eqnarray*}
Any one-qubit gate in the Clifford group can be implemented the same
way using their own commutation relations with the Pauli operators
used for encryption.  A {\sf CNOT}-gate on local wires can be evaluated in
a similar way.  That is, whenever both wires \wire{w}\ and \wire{w'}\
feeding the {\sf CNOT}\ belong to the same party.  Assume that \wire{w}\ is
the control wire while \wire{w'}\ is the target and that \ensuremath{\aprot^*}\
holds them both\fullv{(i.e., $\wire{w},\wire{w'} \in \hreg{A}_0$)}{}.  Then,
\ensuremath{\aprot^*}\ simply applies {\sf CNOT}{}\  on wires \wire{w}\ and
\wire{w'}. Encryption keys are updated as:
\begin{eqnarray*}
{\sf CNOT}{} &:&
K_{\ensuremath{\aprot^*}}^{j+1}(\wire{w})
=
(X_{\ensuremath{\aprot^*}}^{j+1}(\wire{w}), Z_{\ensuremath{\aprot^*}}^{j+1}(\wire{w}))
:=
(X_{\ensuremath{\aprot^*}}^j(\wire{w}),Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
   Z_{\ensuremath{\aprot^*}}^j(\wire{w'}))\enspace ,\\
& & K_{\ensuremath{\aprot^*}}^{j+1}(\wire{w'})
=
(X_{\ensuremath{\aprot^*}}^{j+1}(\wire{w'}), Z_{\ensuremath{\aprot^*}}^{j+1}(\wire{w'}))
:=
(X_{\ensuremath{\aprot^*}}^j(\wire{w'})\oplus X_{\ensuremath{\aprot^*}}^{j}(\wire{w}),
   Z_{\ensuremath{\aprot^*}}^j(\wire{w'}))\ ,\\
& & K_{\ensuremath{\bprot^*}}^{j+1}(\wire{w})
:=
K_{\ensuremath{\bprot^*}}^{j}(\wire{w}) \mbox{ and } K_{\ensuremath{\bprot^*}}^{j+1}(\wire{w'})
:=
K_{\ensuremath{\bprot^*}}^{j}(\wire{w'})\enspace .
\end{eqnarray*}
When \ensuremath{\bprot^*}\ holds both wires, the procedure is simply performed with
the roles of \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ reversed.

\subsubsection{Nonlocal {\sf CNOT}{}.}\label{sect:cnot}
We now look at the case where $G_{j+1}={\sf CNOT}$
upon wires $\wire{w}$ and $\wire{w'}$,  one of which is owned by \ensuremath{\aprot^*}\
while the other is owned by \ensuremath{\bprot^*}.
In this case, interaction is unavoidable
for the evaluation of the gate.  Let us assume w.l.g that \ensuremath{\aprot^*}\ holds
the control wire \wire{w}\ while \ensuremath{\bprot^*}\ holds the target wire \wire{w'}
(i.e., $\wire{w}\in \hreg{A}_0$ and $\wire{w'}\in \hreg{B}_0$).
We start from a construction introduced in \cite{GC99a} in the context
of fault tolerant quantum computation.

\begin{wrapfigure}{r}{0.4\textwidth}
\vspace{-20pt}
\centering
{
        \mbox{\scriptsize \Qcircuit @C=1em @R=.7em {
      \lstick{\wire{w}} & \multigate{1}{Bell} & \ustick{a_x} \cw & \cw             & \control\cw & & &\\
      \twowire{\ket{\Psi_{0,0}}}  & \ghost{Bell}        & \ustick{a_z} \cw & \control\cw     & \cwx  \\
                            & \ctrl{1}            & \qw            & \gate{Z}\cwx    & \gate{X}\cwx & \gate{Z}     & \qw \\
      \twowire{\ket{\Psi_{0,0}}}  & \targ               & \qw            & \gate{X}        & \gate{X}\cwx & \gate{Z}\cwx & \qw \\
                            & \multigate{1}{Bell} & \ustick{b_x} \cw & \control\cw\cwx &              & \cwx \\
      \lstick{\wire{w'}} & \ghost{Bell}        & \ustick{b_z} \cw & \cw             & \cw          & \control\cwx\cw
        \gategroup{1}{4}{6}{6}{2em}{--}
        }}
      }
        \small{\caption{Evaluation of {\sf CNOT}.}
	\label{fig:postteleportation}}
\vspace{-10pt}
\end{wrapfigure}

The idea behind the sub-protocol is depicted in
Fig.~\ref{fig:postteleportation}. The effect of the Bell measurement
is to {\em teleport} the input state of wires $\wire{w}$ and
$\wire{w'}$ {\em through} the {\sf CNOT}-gate\cite{GC99a}.  The input to
the {\sf CNOT}\ appearing in the circuit of Fig.~\ref{fig:postteleportation} is
independent of both input wires \wire{w}\ and \wire{w'} (they are just
two half \textsc{epr}-pairs).

The sub-protocol for the evaluation of {\sf CNOT}\ simply consists in
executing the circuit of Fig.~\ref{fig:postteleportation} without the
decryption part (i.e., the part inside the dotted rectangle).  The
state $\ket{\xi} := (\Idt_{\reg{A}} \tensor CNOT \tensor
\Idt_{\reg{B}}) \ket{\Psi_{0,0}} \ket{\Psi_{0,0}}$ can be prepared by
one party.  We let the holder of the {\em control wire} (i.e., \ensuremath{\aprot^*}\
in Fig.~\ref{fig:postteleportation}) prepare $\ket{\xi}$ before
sending its two rightmost registers to the other party.  The
decryption in the dotted-rectangle is used to update the encryption
keys according to the measurement outcomes $(a_x,a_z,b_x,b_z)$:
\begin{eqnarray*}
{\sf CNOT}{} &:&
K_{\ensuremath{\aprot^*}}^{j+1}(\wire{w})
:=
(X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus a_x,Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus
a_z)\enspace ,\\
& &
K_{\ensuremath{\bprot^*}}^{j+1}(\wire{w})
:=
(X_{\ensuremath{\bprot^*}}^i(\wire{w}),Z_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus b_z)\enspace ,\\
& & K_{\ensuremath{\aprot^*}}^{j+1}(\wire{w'})
:=
(X_{\ensuremath{\aprot^*}}^j(\wire{w'})\oplus a_x, Z_{\ensuremath{\aprot^*}}^j(\wire{w'}))\enspace ,\\
& &
K_{\ensuremath{\bprot^*}}^{j+1}(\wire{w'})
:=
(X_{\ensuremath{\bprot^*}}^j(\wire{w'})\oplus b_x, Z_{\ensuremath{\bprot^*}}^j(\wire{w'})\oplus
b_z)\enspace .
\end{eqnarray*}
As for all previous gates, the key updating phase is performed
locally without the need for communication.

\subsection{Evaluation of the {\sf R}-Gate}\label{sect:rgate}

The only gate left in \ensuremath{{\cal UG}}\ is $G_{j+1}:={\sf R}$.  We assume without
loss of generality that \ensuremath{\aprot^*}\ owns wire \wire{w}\ upon which
{\sf R}{}\ is applied (i.e., $\wire{w}\in \hreg{A}_0$).  The subprotocol
needs a call to an ideal {\sc and-box}\ in order to guarantee privacy during the
key updating process. Observe first that the {\sf R}-gate commutes with
Pauli encryption operator $Z$.  It means that
applying the {\sf R}-gate upon a state encrypted with $Z$ produces the
correct output state still encrypted with $Z$. However,
the equality ${\sf R}{}\cdot X = e^{-i\pi/4}Y{\sf P}{}\cdot {\sf R}{}$
tells us that a {\sf P}{}-gate should be applied for the decryption of
the output when the input has been encrypted using $X$. This breaks
the invariant that wires after each gate are all encrypted by Pauli
operators. We remove the {\sf P}{}-gate by converting it into a
sequence of Pauli operators.

\fullv{Suppose \ensuremath{\mathscr{A}}'s wire \wire{w}\ is encrypted as usual by shared keys
$K_{\ensuremath{\aprot^*}}^{j}(\wire{w}) :=
(X_{\ensuremath{\aprot^*}}^j(\wire{w}),Z_{\ensuremath{\aprot^*}}^j(\wire{w}))$, and
$K_{\ensuremath{\bprot^*}}^{j}(\wire{w}) :=
(X_{\ensuremath{\bprot^*}}^j(\wire{w}),Z_{\ensuremath{\bprot^*}}^j(\wire{w}))$. }{}  Ignoring an irrelevant global phase, the result of
applying {\sf R}{}\ on wire \wire{w}\ is
\begin{align}\label{comr}
\begin{split}
{\sf R}{} &
Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus Z_{\ensuremath{\bprot^*}}^i(\wire{w})} X^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus
   X_{\ensuremath{\bprot^*}}^j(\wire{w})}
  = \\
 & Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus Z_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
X^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
{\sf P}^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})} {\sf R}{} \enspace ,
\end{split}\end{align}
\fullv{
}{}
\begin{wrapfigure}{r}{0.55\textwidth}
  \centering
  \mbox{\scriptsize \Qcircuit @C=1em @R=.7em {
                            &          & \ustick{{X_{\ensuremath{\aprot^*}}^j(\wire{w})}} & \ustick{r} & \ustick{r'} &      & & & & &     & \\
      \lstick{\wire{w}} & \gate{R} & \gate{P}\cwx & \gate{X}\cwx & \gate{Z}\cwx & \qw  & & & & & \qw & \\
                            &          &          &          &          & \qwx & \gate{P} & \gate{X} & \gate{Z} & \qwx \qw \\
                            &          &          &          &  &  &
\dstick{{X_{\ensuremath{\bprot^*}}^j(\wire{w})}}\cwx & \dstick{s}\cwx & \dstick{s'}\cwx\\
                            &
    }
    }

  \small{\caption{Implementation of the {\sf R}{}-gate.}
  \label{fig:postrotation}}
  \vspace{-20pt}
\end{wrapfigure}
To remove the {\sf P}{}-gate, we let each party remove his part of
${\sf P}{}^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}$ in
a private interactive process.  To do this, \ensuremath{\aprot^*}\ picks random bits
$r$ and $r'$, and \ensuremath{\bprot^*}\ picks random bits $s$ and $s'$.  \ensuremath{\aprot^*}\
applies the operator $X^{r}Z^{r'}P^{X_{\ensuremath{\aprot^*}}^i(\wire{w})}$ and
sends the resulting quantum state to \ensuremath{\bprot^*}. \ensuremath{\bprot^*}\ applies the
operator $X^{s}Z^{s'}P^{ X_{\ensuremath{\bprot^*}}^j(\wire{w})}$ and sends the
result back to \ensuremath{\aprot^*}. The resulting protocol is shown in
Fig.~\ref{fig:postrotation}.  It starts with \ensuremath{\aprot^*}\ applying
{\sf R}{}\ upon the encrypted state before the one-round interactive
process described above starts.

After \ensuremath{\aprot^*}'s application of {\sf R}{}, the resulting state is as
described on the right-hand side of (\ref{comr}). At the end of the
process (i.e., circuit of Fig.~\ref{fig:postrotation}), the encryption
becomes:
\begin{align}\label{lg}
\begin{split}
Z^{s'}& X^{s} {\sf P}{}^{X_{\ensuremath{\bprot^*}}^j(\wire{w})}Z^{r'}
X^{r} {\sf P}{}^{X_{\ensuremath{\aprot^*}}^j(\wire{w})} \\

Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus Z_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
X^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
{\sf P}{}^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}\enspace .
\end{split}
\end{align}
\fullv{Since $Z$ and {\sf P}{}\ commute and ${\sf P}\cdot X=X Z\cdot{\sf P}$, we
can re-write (\ref{lg}) (i.e., up to an irrelevant phase factor)
as
\begin{align*}
\begin{split}
Z^{s'\oplus r' \oplus r\cdot X_{\ensuremath{\bprot^*}}^j(\wire{w}) } &
X^{s\oplus r}{\sf P}{}^{X_{\ensuremath{\aprot^*}}^j(\wire{w})+X_{\ensuremath{\bprot^*}}^j(\wire{w})} \\
&
 Z^{Z_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus Z_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
X^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})
      X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}\enspace .
\end{split}
\end{align*}
Using the fact that for $a,b\in\{0,1\}$, ${\sf P}{}^{a+b}=Z^{ab}{\sf P}{}^{a\oplus b}$,
the previous equation can be re-written as
\begin{equation}\label{lg3}
\begin{split}
Z^{s'\oplus r' \oplus Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus Z_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\aprot^*}}(\wire{w})\oplus X_{\ensuremath{\bprot^*}}(\wire{w})\oplus (r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}))\cdot X_{\ensuremath{\bprot^*}}^j(\wire{w}) } & \\
 X^{s\oplus r}
{\sf P}{}^{X_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}
X^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})} &
{\sf P}{}^{X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})}.
\end{split}
\end{equation}
Moving the leftmost {\sf P}{}-gate to the right results in Pauli encryption,}{Now, we use the fact that
$Z$ commutes with {\sf P}{}\ and ${\sf P}\cdot X=X Z\cdot{\sf P}$. In addition, since
for $a,b\in\{0,1\}$, ${\sf P}{}^{a+b}=Z^{ab}{\sf P}{}^{a\oplus b}$ we re-write (\ref{lg}) as}
\begin{equation}\label{lg4}
\begin{split}
Z^{s'\oplus r'\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus Z_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus (r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}))\cdot X_{\ensuremath{\bprot^*}}^j(\wire{w}) } \\ X^{s\oplus r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}) \oplus X_{\ensuremath{\bprot^*}}^j(\wire{w})} \enspace .
\end{split}
\end{equation}
Encryption (\ref{lg4}) is not a proper additive sharing since the
$Z$-operator depends on $(r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}))\cdot
X_{\ensuremath{\bprot^*}}^j(\wire{w})$; the logical {\sc and} between a value known
only by \ensuremath{\aprot^*}\ (i.e., $r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w})$) and a value
known only by \ensuremath{\bprot^*}\ (i.e., $X_{\ensuremath{\bprot^*}}^j(\wire{w})$).
\begin{wrapfigure}{r}{0.4\textwidth}
\vspace{-15pt}\hspace{0.5in}
\centering
  \mbox{\scriptsize \Qcircuit @C=1em @R=.7em {
      \lstick{{r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w})}} \ar[r] &
      \multigate{1}{\mbox{{\sc and-box}}} \ar[r] & \rstick{\alpha} \\
      \lstick{X_{\ensuremath{\bprot^*}}^j(\wire{w})} \ar[r] & \ghost{\mbox{{\sc and-box}}} \ar[r] &
           \rstick{\beta}\\
    }}
 \small{\caption
$\alpha\oplus\beta=(r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}))\cdot X_{\ensuremath{\bprot^*}}^{j}(\wire{w})$ from an {\sc and-box}.}
  \label{fig:resharingand}}
\vspace{-10pt}
\end{wrapfigure}
To get back to an additive sharing, \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ can simply
call the {\sc and-box}\ once with inputs $r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w})$ and
$X_{\ensuremath{\bprot^*}}^j(\wire{w})$ respectively as depicted in
Fig.~\ref{fig:resharingand}. After this, \ensuremath{\aprot^*}\ and \ensuremath{\bprot^*}\ share a
proper encryption of the resulting state. The new encryption key for
\ensuremath{\aprot^*}'s wire $\wire{w}$ becomes:
\begin{eqnarray*}
{\sf R} &:&
K_{\ensuremath{\aprot^*}}^{j+1}(\wire{w})
:=
(r\oplus X_{\ensuremath{\aprot^*}}^j(\wire{w}),r'\oplus \alpha \oplus
Z_{\ensuremath{\aprot^*}}^j(\wire{w})\oplus  X_{\ensuremath{\aprot^*}}^j(\wire{w}))\ ,\\
& &
K_{\ensuremath{\bprot^*}}^{j+1}(\wire{w})
:=
(s\oplus X_{\ensuremath{\bprot^*}}^j(\wire{w}),s'\oplus \beta \oplus
Z_{\ensuremath{\bprot^*}}^j(\wire{w})\oplus X_{\ensuremath{\bprot^*}}^j(\wire{w}))\ .
\end{eqnarray*}

\subsection{On the Necessity of Swapping Privately}

One may ask whether relying upon {\ensuremath{\sf SWAP}}\ is necessary for the protocol
to be private against specious adversaries. For instance, what would happen if one party
announces the encryption keys before the other party?
We now show that as soon as one party gets the other party's decryption key before having announced
its own, a specious adversary  can break privacy.

Consider the protocol for a quantum circuit made out of one single {\sf CNOT}-gate.
Suppose that \ensuremath{\aprot^*}\ holds the control wire \wire{w}\ while \ensuremath{\bprot^*}\
holds the target wire \wire{w'}. Suppose also the key-releasing phase first asks
 \ensuremath{\bprot^*}\  to announce the encryption keys $\keyb{w}{}$ before \ensuremath{\aprot^*}\ announces $\keya{w'}{}$.
 Suppose \ensuremath{\ad{A}}'s input state is $\ket{0}$.

 The adversary \ensuremath{\ad{A}}\ can now act as follows. \ensuremath{\ad{A}}\ runs the protocol for {\sf CNOT}\ without
 performing the Bell measurement until she receives the encryption key $b_z$ from \ensuremath{\bprot^*}.
 Clearly, \ensuremath{\ad{A}}'s behavior is specious up to that point since she could re-produce the
 honest state by just applying the Bell measurement on her input state \fullv{stored in register
 $\hreg{A}_0$}{}.
 However,  given $b_z$ she could also
 in principle compute the {\sf CNOT}\ upon any input state of her choice. This means that
 the state she holds after $b_z$ has been announced and before applying her Bell measurement
 contains information about \ensuremath{\bprot^*}'s input.
 On the one hand,
 when \ensuremath{\ad{A}}'s input state is $\ket{0}$ no information whatsoever on \ensuremath{\bprot^*}'s
 input state should be available to her (i.e., in this case {\sf CNOT}\ behaves like the
 identity). On the other hand, had her input state been
 $\ket{-}$,  information about  \ensuremath{\bprot^*}'s state would have become available since
 the control and target wires exchange their roles when the input states are in the Hadamard basis.
 However,
 when \ensuremath{\ad{A}}'s input state is $\ket{0}$,
 any simulation of her view can only call the ideal functionality  with
 input state $\ket{0}$.\delete{and  no information about \ensuremath{\bprot^*}'s state
 is available to the simulator.} It follows that no simulator can
 reproduce   \ensuremath{\ad{A}}'s state right after the announcement
 of $b_z$

 \fullv{}{
 \section{Proof of Privacy}
 \subsubsection{Privacy of the Evaluation Phase.}
 We start by showing privacy of protocol $\pup{U}^{\qop{O}}=(\ensuremath{\aprot^*},\ensuremath{\bprot^*},n_U+1)$
 at all steps $1\leq i \leq n_U-1$ occurring during
the {\em evaluation  phase}
of quantum
circuit $C_U$ implementing $U$ with $u$ gates in \ensuremath{{\cal UG}}.
The last step of the evaluation phase is $n_U-1$ since only
one oracle call is left to complete the execution.
This phase is the easy part of the simulation since
all transmissions  are
independent of the joint input state $\ensuremath{\rho_{\mathrm{in}}} \in \dens{\hreg{A}_0\otimes\hreg{B}_0\otimes \hreg{R}}$.
The lemma below can easily be proven and provides a
perfect simulation of  any adversary's view generated
during the evaluation of any gate in $C_U$. No call to the ideal functionality for $U$
is required.

\begin{lemma}\label{induct}
$\pup{U}^{\qop{O}}=(\ensuremath{\aprot^*},\ensuremath{\bprot^*},n_U+1)$
admits a simulator $\simulator{\ensuremath{\ad{A}}}$ for any adversary \ensuremath{\ad{A}}\ (not necessarily specious)
that does not
call the ideal functionality for $U\in \unit{\hreg{A}_0 \otimes \hreg{B}_0}$ such that
for any joint input state $\ensuremath{\rho_{\mathrm{in}}} \in \dens{\hreg{A}_0 \otimes\hreg{B}_0\otimes \hreg{R}}$,
every $1\leq i \leq n_U-1$:
\begin{equation*
\Delta\left(\view{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}{i},\trace[\hreg{B}_i]{\astatei{i}{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}} \right) = 0 \enspace .
\end{equation*}
The same holds against any adversary \ensuremath{\ad{B}}.
\end{lemma}

 \subsubsection{Privacy of the Key-Releasing Phase.}
 Before proving privacy of the key-releasing phase, we need the following lemma
 establishing that at the end of the protocol,
specious adversaries must leave their extra working registers (used to implement the attack)
independent of the joint input state.
In other words, no extra information is available to the adversary at the very end of any correct  protocol. Hence, if the adversary can break the privacy of a protocol, then he must ``rush'' to do so before the last step.

\begin{lemma}[Rushing Lemma]\label{rushing}
	Let $\puq{U} = (\ensuremath{\mathscr{A}},\ensuremath{\mathscr{B}}, n)$ be a correct protocol for the two party evaluation of $U$.  Let \ensuremath{\ad{A}}\ be any $\varepsilon$--specious adversary in $\puq{U}$. Then, there exists an isometry $T : \tilde{\hreg{A}}_n \rightarrow \hreg{A}_n \otimes \widehat{\hreg{A}}$ and a mixed state $\tilde{\varrho} \in \dens{\widehat{\hreg{A}}}$ such that for all joint input states $\ensuremath{\rho_{\mathrm{in}}} \in \dens{\hreg{A}_0\otimes\hreg{B}_0 \otimes \hreg{R}}$,
\begin{equation*
	\Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}})\cdot\left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\ensuremath{\rho_{\mathrm{in}}})\right),\tilde{\varrho}\otimes
	(U \otimes \Idt_{\hreg{R}})\cdot\ensuremath{\rho_{\mathrm{in}}} \right)\leq 12 \sqrt{2\varepsilon} \enspace .
\end{equation*}
The same also applies to any $\varepsilon$--specious adversary $\ensuremath{\ad{B}}$.
\end{lemma}

\begin{proof}
	We shall only prove the statement for an $\varepsilon$--specious \ensuremath{\ad{A}}; the statement for an $\varepsilon$--specious \ensuremath{\ad{B}}\ is identical. Furthermore, by convexity, it is sufficient to prove the theorem for pure $\ensuremath{\rho_{\mathrm{in}}}$.

Consider any pair of pure input states $\ket{\psi_1}$ and $\ket{\psi_2}$ in $\hreg{A}_0 \otimes \hreg{B}_0 \otimes \hreg{R}$. Now, let $\hreg{R}' := \hreg{R} \otimes \hreg{R}_2$, where $\hreg{R}_2 = \Span\{\ket{1}, \ket{2}\}$ represents a single qubit, and define the state $\ket{\psi} := \frac{1}{\sqrt{2}}(\ket{\psi_1}\ket{1} + \ket{\psi_2}\ket{2}) \in \hreg{A}_0 \otimes \hreg{B}_0 \otimes \hreg{R}'$. Note that $\trace[\hreg{R}_2]{\proj{\psi}} = \frac{1}{2} \ket{\psi_1}\bra{\psi_1} + \frac{1}{2} \ket{\psi_2}\bra{\psi_2}$. Due to the correctness of the protocol and to the speciousness of $\ensuremath{\ad{A}}$, there exists a quantum operation $\trans{n} : \linop{\tilde{\hreg{A}_n}} \rightarrow \linop{ \hreg{A}_n}$ such that
\begin{equation*}
	\Delta\left( (\trans{n} \otimes \Idt_{\linop{\hreg{B}_n \otimes \hreg{R}'}})([\ensuremath{\ad{A}} \circledast \ensuremath{\mathscr{B}}](\proj{\psi})) , (U \otimes \Idt_{\hreg{R}'})\cdot \proj{\psi}  \right) \leq 2\varepsilon\enspace .
\end{equation*}
Now, consider any isometry $T : \tilde{\hreg{A}}_n \rightarrow \hreg{A}_n \otimes \widehat{\hreg{A}}$ such that $\trans{n}(\sigma) = \trace[\widehat{\hreg{A}}]{T \sigma T^\dagger}$ for every $\sigma \in \linop{\tilde{\hreg{A}}_n}$ --- in other words, any operation that implements $\trans{n}$ while keeping any information that would otherwise be destroyed in $\widehat{\hreg{A}}$. By Uhlmann's theorem, there must exist a state $\tilde{\varrho} \in \dens{\widehat{\hreg{A}}}$ such that
\begin{equation*}
	\Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}'})\cdot \left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\ket{\psi}\bra{\psi})\right),
	\tilde{\varrho}\otimes \left((U \otimes \Idt_{\hreg{R}'})\cdot\proj{\psi}\right) \right)\leq 2 \sqrt{2 \varepsilon}\enspace .
\end{equation*}
Now, the trace distance is monotonous under completely positive, trace non-increasing maps. In particular, we can apply the projector $P_1 = \Idt_{\linop{\hreg{A}_n \otimes \hreg{B}_n \otimes \hreg{R}}} \otimes \ket{1}\bra{1}$ to both states in the above trace distance and the inequality will still hold. In other words, we project both states onto $\ket{1}$ on $\hreg{R}_2$, thereby turning $\ket{\psi}\bra{\psi}$ into $\frac{1}{2} \ket{\psi_1}\bra{\psi_1}$. Factoring out the $\frac{1}{2}$, we get that
\begin{equation*}
	\Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}})\cdot\left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\proj{\psi_1})\right),
	\tilde{\varrho}\otimes \left( (U \otimes \Idt_{\hreg{R}})\cdot \proj{\psi_1} \right) \right)\leq 4 \sqrt{2 \varepsilon}\enspace .
\end{equation*}
Likewise, projecting onto $\ket{2}$ yields
\begin{equation*}
	\Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}})\cdot\left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\proj{\psi_2})\right),
	\tilde{\varrho}\otimes \left( (U \otimes \Idt_{\hreg{R}})\cdot \proj{\psi_2} \right) \right)\leq 4 \sqrt{2 \varepsilon}\enspace .
\end{equation*}
Our only problem at this point is that $\tilde{\varrho}$ in principle depends on $\ket{\psi_1}$ and $\ket{\psi_2}$. However, repeating the above argument with $\ket{\psi_1}$ and $\ket{\psi_3}$ for any $\ket{\psi_3}$ will yield a $\tilde{\varrho}'$ with
\begin{equation*}
	\Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}})\cdot \left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\ket{\psi_1}\bra{\psi_1})\right),
	\tilde{\varrho}'\otimes \left( (U \otimes \Idt_{\hreg{R}})\cdot \proj{\psi_1} \right) \right)\leq 4 \sqrt{2 \varepsilon}
\end{equation*}
and hence, by the triangle inequality, $\Delta(\tilde{\varrho}, \tilde{\varrho}') \leq 8 \sqrt{2\varepsilon}$. Therefore, for any state $\ket{\varphi} \in \hreg{A}_0 \otimes \hreg{B}_0 \otimes \hreg{R}$, there exists a state $\tilde{\rho} \in \widehat{\hreg{A}}$ with $\Delta(\tilde{\rho}, \tilde{\varrho}) \leq 8 \sqrt{2\varepsilon}$ such that
\begin{equation*}
	\Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}})\cdot \left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\ket{\varphi}\bra{\varphi})\right),
	\tilde{\rho}\otimes \left( (U \otimes \Idt_{\hreg{R}})\cdot \proj{\varphi} \right) \right)\leq 4 \sqrt{2 \varepsilon} \enspace .
\end{equation*}
The lemma then follows by the triangle inequality:
\begin{multline*}
	\Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}})\cdot \left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\proj{\varphi}\right),
	\tilde{\varrho}\otimes \left( (U \otimes \Idt_{\hreg{R}})\cdot \proj{\varphi} \right) \right)\\
	\begin{split}
		&\leq \Delta\left((T \otimes \Idt_{\hreg{B}_n \otimes \hreg{R}})\cdot \left([\ensuremath{\ad{A}}\circledast\ensuremath{\mathscr{B}}](\proj{\varphi})\right),
		\tilde{\rho}\otimes \left( (U \otimes \Idt_{\hreg{R}})\cdot \proj{\varphi} \right) \right) + \Delta(\tilde{\rho}, \tilde{\varrho})\\
		&\leq 4 \sqrt{2\varepsilon} + 8 \sqrt{2\varepsilon} = 12 \sqrt{2\varepsilon} \enspace .
	\end{split}
\end{multline*}
\qed
\end{proof}

In order to conclude the privacy of $\pup{U}^{\qop{O}}$, families $\simulator{\ensuremath{\ad{A}}}$
and $\simulator{\ensuremath{\ad{B}}}$
need one more simulator each: $\simul{n_U}\in  \simulator{\ensuremath{\ad{A}}}$
and $\simul{n_U}' \in  \simulator{\ensuremath{\ad{B}}}$  corresponding
to the simulation of the key-releasing phase.
This time, these simulators
need to query the ideal functionality for $U$ and also
need the adversary to be specious.
We show that privacy of the key-releasing phase
follows from the ``Rushing Lemma'' (Lemma~\ref{rushing}).
This is the role of the ideal {\ensuremath{\sf SWAP}}\ to make sure that
before the adversary  gets the output of the computation, the information
needed by the honest player to recover its own output has been given away
by the adversary.

It should be mentioned that we're not explicitly simulating the
final state of the adversary since simulating the
{\ensuremath{\sf SWAP}}\ allows also to get \ensuremath{\ad{A}}'s final state
by simply adding \ensuremath{\ad{A}}'s last quantum operation to the simulated
view. We therefore set step $n_U$ in $\pup{U}^{\qop{O}}$
to be the step reached after the call to {\ensuremath{\sf SWAP}}. This abuses the notation
a  bit since after {\ensuremath{\sf SWAP}}, \ensuremath{\ad{A}}\ and \ensuremath{\bprot^*}\ must each apply
a final quantum operation with no more oracle call. We'll denote
by $\ensuremath{\ad{A}}_{n_U+1}$ and $\ensuremath{\bprot^*}_{n_U+1}$ these last operations
allowing to reconstruct the output of the computation (no comunication).

\begin{lemma}\label{release}
For any $\varepsilon$-specious quantum adversary \ensuremath{\ad{A}}\
against $\pup{U}^{\qop{O}}=(\ensuremath{\aprot^*},\ensuremath{\bprot^*},n_U+1)$, there
exist  simulators $\simul{n_U}\in \simulator{\ensuremath{\ad{A}}}$
such that for all
$\ensuremath{\rho_{\mathrm{in}}} \in \dens{\hreg{A}_0\otimes \hreg{B}_0\otimes\hreg{R}}$,
\begin{equation*
\Delta\left(\view{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}{n_U},\trace[\hreg{B}_{n_U}]{\astatei{n_U}{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}} \right) \leq
24\sqrt{2\varepsilon} \enspace .
\end{equation*}
Simulator $\simul{n_U}$
calls the ideal functionality for $U$
and can be used directly to simulate  step $n_U+1$ as well. The same holds
for adversary \ensuremath{\ad{B}}.
\end{lemma}

\begin{proof}[sketch]
We only prove privacy against adversary \ensuremath{\ad{A}},
privacy against \ensuremath{\ad{B}}\ follows directly since the key-releasing phase
is symmetric.  The idea behind the proof is to run
\ensuremath{\ad{A}}\ and \ensuremath{\bprot^*}\ upon a dummy joint input state until the end
of the protocol. Since the adversary is specious, it can re-produce
the honest state at the end. The Rushing Lemma tells us that
at this point, the output of the computation is essentially in tensor
product with all the other registers. Moreover, the state of all other
registers is independent of the input state upon which the protocol
is executed. The {\em dummy output} can then be replaced
by the output of the ideal functionality for $U$ before \ensuremath{\ad{A}}\
goes back to the stage reached just after {\ensuremath{\sf SWAP}}.

More formally,
we define a simulator $\simul{n_U}\in \simulator{\ensuremath{\ad{A}}}$ producing
\ensuremath{\ad{A}}'s view just after the call to {\ensuremath{\sf SWAP}}.
Let $\ensuremath{\ad{A}}_{{\ensuremath{\sf SWAP}}}\in \lin{\hreg{A}_0}{\tilde{\hreg{A}}_{n_U}}$ and
$\ensuremath{\bprot^*}_{{\ensuremath{\sf SWAP}}}\in \lin{\hreg{B}_0}{\tilde{\hreg{B}}_{n_U}}$ be the
quantum operations run by \ensuremath{\ad{A}}\ and \ensuremath{\bprot^*}\  respectively until after {\ensuremath{\sf SWAP}}\ is executed.
Notice that at this point, \ensuremath{\ad{A}}'s and \ensuremath{\bprot^*}'s registers
do not  have any further oracle registers
since no more communication or oracle call will take place.
Let $\tilde{A}_{n_U}\in\lin{\tilde{\hreg{A}}_{n_U}}{\tilde{\hreg{A}}_{n_U+1}\otimes \hreg{Z}}$ be the isometry
implementing \ensuremath{\ad{A}}'s  last quantum operation  taking
place after the call to {\ensuremath{\sf SWAP}}\ (and producing her final state) and
let   ${B}_{n_U}\in\lin{{\hreg{B}}_{n_U}}{{\hreg{B}}_{n_U+1}\otimes \hreg{W}}$ be the isometry
implementing \ensuremath{\bprot^*}'s  last quantum operation.  Finally,
let $T\in \lin{\tilde{\hreg{A}}_{n_U+1}}{\hreg{A}_{n_U+1}\otimes\hat{\hreg{A}}}$ be the isometry
implementing $\trans{n_U+1}$ as defined in Lemma~\ref{rushing}
(i.e., the transcript produced at the very end of the protocol).
As usual, let $\ensuremath{\rho_{\mathrm{in}}} \in \dens{\hreg{A}_0\otimes\hreg{B}_0\otimes\hreg{R}}$
be the joint input state.
The simulator $\simul{n_U}$  performs the following operations:
\begin{enumerate}
\item $\simul{n_U}$ generates
the quantum state $\sigma(\phi^*)=[\ensuremath{\ad{A}}_{{\ensuremath{\sf SWAP}}}\circledast\ensuremath{\bprot^*}_{{\ensuremath{\sf SWAP}}}](\proj{\phi^*})
\in \dens{\tilde{\hreg{A}}_{n_U}\otimes \hreg{B}_{n_U}}$
 implementing
\ensuremath{\ad{A}}\ interacting with \ensuremath{\bprot^*}\ until {\ensuremath{\sf SWAP}}\  is applied. The execution
is performed  upon a predetermined (dummy)
arbitrary input state
$\ket{\phi^*} \in \hreg{A}_0\otimes\hreg{B}_0$. \label{s1}

\item $\simul{n_U}$ sets $\sigma'(\phi^*) = (T \tilde{A}_{n_U}\otimes {B}_{n_U})\cdot
\sigma(\phi^*) \in \dens{\hreg{A}_{n_U+1}\otimes \hreg{B}_{n_U+1}
\otimes \hreg{Z}\otimes\hat{\hreg{A}}\otimes\hreg{W}}$.\label{s2}

\item \simul{n_U}\ replaces register $\hreg{A}_{n_U+1}\approx \hreg{A}_0$
by \ensuremath{\aprot^*}'s output
of the ideal functionality for $U$ evaluated upon \ensuremath{\rho_{\mathrm{in}}}.
That is, \simul{n_U}\ generates the state
$\sigma'(\ensuremath{\rho_{\mathrm{in}}})= (U\otimes \Idt_{\hreg{R}})\cdot\rhoi
\otimes \trace[\hreg{A}_{n_U+1}\hreg{B}_{n_U+1}]{\sigma'(\phi^*)}
\in \dens{\hreg{A}_{n_U+1}\otimes \hreg{B}_{n_U+1}\otimes\hreg{R}
\otimes \hreg{Z}\otimes\hat{\hreg{A}}\otimes\hreg{W}}$.
\label{s3}

\item \simul{n_U}\ finally sets $\view{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}{n_U}=\trace[\hreg{B}_{n_U+1}\hreg{W}]
{(T \tilde{A}_{n_U}\otimes \Idt_{\hreg{B}_{n_U+1}\hreg{R}})^{\dagger}\cdot \sigma'(\ensuremath{\rho_{\mathrm{in}}})}
\in \dens{\tilde{\hreg{A}}_{n_U}\otimes\hreg{R}}$.
 \label{s4}
\end{enumerate}
Notice that execution of  the ideal {\ensuremath{\sf SWAP}}\ ensures that
the keys swapped are independent of each other
and of the joint input state $\ensuremath{\rho_{\mathrm{in}}}$. This is because
for any input state, all these keys are uniformly distributed
bits if they are outcomes of Bell measurements and otherwise
are set to $0$.  By Lemma~\ref{rushing} and the fact
that \ensuremath{\ad{A}}\ is $\varepsilon$--specious,
we have:
\[
\begin{split}
 \Delta\left( \trace[\hreg{Z}\hat{\hreg{A}}\hreg{W}]{\sigma'(\phi^*)}, \tilde{\varrho}\otimes U\cdot \proj{\phi^*}\right) \leq
12\sqrt{2\varepsilon} \mbox{ and \hspace{0in}}  &    \\
 \Delta\left( (\trans{n_U+1}\otimes\Idt_{\linop{\hreg{B}_{n_U+1}}}) \left([\ensuremath{\ad{A}}\circledast \ensuremath{\bprot^*}](\ensuremath{\rho_{\mathrm{in}}})\right), \tilde{\varrho}\otimes U\cdot\ensuremath{\rho_{\mathrm{in}}}\right)  \leq
12\sqrt{2\varepsilon}\enspace .
\end{split}
\]
It follows using the triangle inequality  that,
\begin{equation}\label{wow}
 \Delta\left( (\trans{n_U+1}\otimes\Idt_{\linop{\hreg{B}_{n_U+1}}}) \left([\ensuremath{\ad{A}}\circledast \ensuremath{\bprot^*}](\ensuremath{\rho_{\mathrm{in}}})\right),
\trace[\hreg{Z}\hat{\hreg{A}}\hreg{W}]{\sigma'(\ensuremath{\rho_{\mathrm{in}}})}
\right) \leq 24 \sqrt{2\varepsilon}\enspace .
\end{equation}
Using the fact that isometries cannot increase the trace-norm distance and
that $(T\tilde{A}_{n_U})^{\dagger}$ allows \ensuremath{\ad{A}}\  to go back from the end of the protocol
to the step reached after {\ensuremath{\sf SWAP}},
we get from (\ref{wow}) that
\[
\begin{split}
&\Delta\left(\view{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}{n_U},\trace[\hreg{B}_{n_U}]{\astatei{n_U}{\ensuremath{\ad{A}}}{\ensuremath{\rho_{\mathrm{in}}}}} \right)
 = \\ & \Delta\left(
(\trans{n_U+1}\otimes\Idt_{\linop{\hreg{B}_{n_U+1}}}) \left([\ensuremath{\ad{A}}\circledast \ensuremath{\bprot^*}](\ensuremath{\rho_{\mathrm{in}}})\right),
\trace[\hreg{Z}\hat{\hreg{A}}\hreg{W}]{\sigma'(\ensuremath{\rho_{\mathrm{in}}})}
\right)
\leq 24\sqrt{2\varepsilon}   \enspace .
\end{split}\]
The proof of the statement follows.
\qed
\end{proof}}

\section{Main Result and Open Questions}

Putting Lemma~\ref{induct} and Lemma~\ref{release} together gives
the desired result:

\begin{theorem}[Main Result]\label{final}
  Protocol $\pup{U}^{\qop{O}}$ is
  statistically private against any statistically specious quantum
  adversary and for any $U\in \unit{\hreg{A}_0\otimes
  \hreg{B}_0}$. If $U$ is in the Clifford group then the only
  non-trivial oracle call in \qop{O}\ is one call to an ideal {\ensuremath{\sf SWAP}}.
  If $U$ is not in the Clifford group then \qop{O}\ contains an
  additional oracle call to {\sc and-box}\ for each {\sf R}-gate in the circuit
  for $U$.
\end{theorem}

It should be mentioned that it is not too difficult to modify our
protocol in order to privately evaluate quantum operations rather than
only unitary transforms. Classical two party computation together with
the fact that quantum operations can be viewed as unitaries acting in
larger spaces can be used to achieve this extra functionality. Privacy
can be preserved by keeping these extra registers encrypted after the
execution of the protocol. We leave this discussion to the full version of the paper.

A few interesting questions remain open:
\begin{itemize}

\item

  It would be interesting to know whether there exists a unitary
  transform that can act as a universal primitive for private
  two-party evaluation of unitaries.  This would allow to determine
  whether classical cryptographic assumptions are required for this
  task.

\item

  Finally, is there a way to compile quantum protocols secure against
  specious adversaries into protocols secure against arbitrary
  quantum adversaries? An affirmative answer would allow to simplify
  greatly the design of quantum protocols. Are extra assumptions needed
  to preserve privacy against any adversary?

\end{itemize}

\section{Acknowledgements}

The authors would like to thank the referees for their comments
and suggestions.
We would also like to thank Thomas Pedersen for numerous
helpful discussions in the early stage of this work.

\addcontentsline{toc}{chapter}{Bibliography}
\bibliographystyle{plain}