text:
\section{Introduction}

Validating an accusation is a challenge in our daily lives, from court to cryptographic applications. It could be extremely harmful if either an actual malevolent behavior or a false accusation occurs. Hence, giving sufficient evidence to a trusted party or the general public becomes an important issue. Consider the following scenario: Alice, a food delivery driver, picks up a Bento Box from a Japanese restaurant and delivers it to Bob, the recipient. If Alice and Bob are both truthful, they will be satisfied. But what if one of them is malicious? For example, Alice may open the lunchbox, eat a bit, and then send it to Bob. Or Bob simply refuses to pay and accuses Alice of not delivering it to him. It turns out to be ``Rashomon''. If they end up going to court, the judge or the jury in court lacks adequate evidence and eyewitness testimony to reach a judgment. This is a toy example of \emph{public verifiability} {i.e.,\ } everyone, including non-participants such as the jury, can verify who the malicious party is \cite{BDO14,BOS+20}.

This deliveryman problem can happen to \emph{quantum message transmission} (QMT), where someone has to deliver a quantum message. Thanks to the long arm of quantum law, we are able to present a generic transformation,\emph{ Auditable Quantum Authentication} (AQA), to deal with it. In our AQA, Alice must take responsibility for her delivery, and everyone will receive a checksum for verification. The judge and jury (outside observer with only classical computational power) can now verify the entire process independently in the event of a dispute. Although AQA can realize public verifiable identifiable abort QMT, more sophisticated tasks, including multiparty computation (MPC), are preferable.

Secure multiparty computation (MPC) allows two or more parties to compute a function on their joint private inputs securely \cite{Yao86}. Most of the MPC literature studies classical functionality over classical inputs in different notions of security, such as \emph{full security}, \emph{security with abort}, and \emph{security with identifiable abort} \cite{RB89,GMW87,IOZ14}.

Recently, secure multiparty quantum computation (MPQC) has raised research interest. Most of the works are in the fully quantum setting {i.e.,\ } the functionality, including inputs and outputs, are quantum. While \cite{CGS02,BCG06} achieved full security with an honest majority, it is impossible to obtain MPQC with full security in general without an honest majority \cite{ABDR04}. To circumvent this impossibility, MPQC protocols with a dishonest majority, such as \cite{DNS12,DGJ+20,BCKM21}, seek the weaker notion of security with abort, which allows all honest parties to abort when they observe an attack. However, such a notion is vulnerable to a \emph{denial-of-service attack} because an attacker can repeatedly invoke aborts. In light of this, \cite{ACC+21} proposed an MPQC protocol with identifiable abort (MPQC-SWIA), allowing all honest parties to agree on an identity of a corrupted party as an output in case of an abort. Still, their identification mechanism only allows inside MPQC participants to identify a malicious player. Returning to the deliveryman problem from earlier, MPQC-SWIA is unable to provide sufficient evidence to the jury, who is absent from this matter. Given the state of affairs, we ask:
\begin{quote}
    {\it Is it possible to construct MPQC with public verifiable identifiable abort?}
\end{quote}

In the classical setting, one can turn MPC-SWIA into MPC-PVIA. Obtaining a public verifiable protocol requires each participant to broadcast committed messages to outsider observers. However, it is impossible to broadcast quantum states due to the no-cloning theorem, so the classical technique cannot be applied in the quantum setting. A recent line of work that also aims for public verifiability is classical verification of quantum computation (CVQC) \cite{CVQC}. However, due to its restriction to quantum computation that is performed by a single server with classical outputs, CVQC cannot fit in general MPQC.

It is widely believed that the no-cloning theorem and the traditional sender-receiver mechanism in the quantum authentication code prevent quantum techniques from realizing an MPQC-PVIA protocol. As a result, we design a transformation for public verifiability that subverts the traditional sender-receiver rationale. We will close the gap in our technical overview section later on.

Along the line of dishonest majority setting, cryptographers have considered MPQC against $n-1$ malicious parties among $n$ participating parties with some sort of security with abort because full security is impossible in this case.
Another interesting setting is to reduce the maximal number of malicious parties while conditionally requiring full security. Such a notion is called best-of-both-worlds (BoBW) security\footnote{There are different flavors of best-of-both-worlds\xspace security. For example, \cite{BoBW-neg,BoBW-1/p} consider MPC protocols with full security against $\lfloor \frac{n-1}{2} \rfloor$ malicious parties and $(1\slash p)$-security with abort against $n-1$ malicious parties. The notion of $(1\slash p)$-security only requires an inverse polynomial error in distinguishing the real/ideal world.}. In the classical setting, \cite{BoBW-pos} constructs for every $\thres \le \lfloor \frac{n-1}{2} \rfloor$ an MPC protocol that achieves security with abort against $n-1-\thres$ malicious parties and achieves full security tolerating $\thres$ malicious parties. \cite{BoBW-neg} proved that these corruption thresholds are optimal. In the quantum setting, none of the existing MPQC protocols can be extended to satisfy BoBW security. It is unclear in MPQC whether best-of-both-worlds security is achievable. We ask:
\begin{quote}
    {\it Is it possible to construct a single MPQC that achieves full security under an honest majority, and is secure with abort under a dishonest majority?}
\end{quote}
\subsection{Our results}
\begin{itemize}
    \item {\bf Generic Transformation:} We provide a generic AQA transformation that equips quantum authentication codes with public verifiability. The transformation works with various authentication codes, including Clifford and Trap codes \cite{CliffordCodes,Trapcode}. It opens up the feasibility of constructing MPQC protocols using the Trap authentication code, whereas existing MPQC works in the dishonest majority setting follow only a rule of thumb along the line of the Clifford authentication code \cite{DNS12,DGJ+20,ACC+21,BCKM21}.
    \item {\bf Best-of-Both-Worlds MPQC-PVIA:}
    We build the first best-of-both-worlds MPQC-PVIA protocol obtaining either full security or security with public verifiable identifiable abort. Our construction is based on our AQA transformation and MPQC-SWIA. The key to arriving at best-of-both-worlds security is our protocol's compatibility with decentralized quantum computation. In particular, no single participant in our protocol holds all the quantum information of a piece of data during the computation step, as opposed to prior security-with-abort protocols \cite{DGJ+20,ACC+21,BCKM21}.
    \item {\bf Classical Online Communication} Our MPQC protocol consists of an offline phase and an online phase. Our MPQC protocol requires just classical communication during the online phase, whereas many previous MPQC protocols \cite{DGJ+20,ACC+21} require a quantum network.
\end{itemize}
Following \cite{DNS12,DGJ+20}, our protocol assumes a classical MPC-PVIA as an ideal functionality, and we refer the reader to \cref{sec:MPC-hybrid} for more details on the model. Our protocol is proven under the standard real/ideal paradigm.

\begin{theorem}\label{thm:main_informal1}
There exists a best-of-both-worlds\xspace multi-party quantum computation protocol secure with public verifiable identifiable abort of threshold $\thres$ over poly-size
\ifdefined\FullVersion quantum \fi
circuits for every $\thres \le \lfloor \frac{n-1}{2} \rfloor$ in the preprocessing MPC-hybrid model .
\end{theorem}
We then remove the trusted preprocessing for circuits with only private outputs.

\begin{theorem}\label{thm:main_informal2}
There exists a best-of-both-worlds\xspace multi-party quantum computation protocol secure with public verifiable identifiable abort of threshold $\thres$ over
\ifdefined\FullVersion poly-size quantum \fi
circuits with only private outputs for every $\thres \le \lfloor \frac{n-1}{2} \rfloor$ in the MPC-hybrid model.
\end{theorem}

\subsection{Open Problems}
\begin{itemize}
    \item {\bf MPQC-PVIA with different security.} Our protocols have been proven in the real/ideal paradigm. MPQC-PVIA with universally composable (UC) security remains an unsolved topic. In addition, our protocols only consider static adversaries {i.e.,\ } all the malicious players are decided before the game starts. MPQC-PVIA against adaptive adversaries remains unclear.

    \item {\bf Trap-code form MPQC-PVIA.} Existing MPQC with dishonest majority protocols are mostly in Clifford Authentication Code. Using our Trap-form AQA to create Trap-code form MPQC protocols with desirable properties could also be a good open problem.

    \item {\bf Applications of AQA.} There are many public verifiable primitives in classical cryptography, but their quantum counterparts are unknown. Our AQA may facilitate the development; for example, public verifiable quantum fully homomorphic encryption (pvQFHE).
\end{itemize}
\section{Technical overview}
In this section, we explain the reason public verifiability does not follow directly from existing works. Then, we introduce our new primitive, Auditable Quantum Authentication (AQA), which plays a crucial role in sending a quantum message securely. Afterward, we show how to apply AQA to construct MPQC-PVIA. At the end of the section, we discuss the difficulty and our method of achieving best-of-both-worlds\xspace (BoBWs) security.

\ifdefined\FullVersion

\subsection{Quantum Background}
Before our discussion, we recall some quantum backgrounds for unfamiliar readers. Those who are experienced in quantum computing can skip this part.

\paragraph{Quantum States and Gates}
We use lowercase Greek alphabets, {e.g.,\ } $\rho,\sigma,\tau$, to denote the density matrix of a quantum state. The notation $U \cdot \rho$ stands for the result $U \rho U^\dag$ of applying a unitary transformation $U$ to a quantum state $\rho$. The bit flip gate $\ensuremath{X} = [\begin{smallmatrix}0&1\\1&0\end{smallmatrix}]$, phase flip gate $\ensuremath{Z} = [\begin{smallmatrix}1&0\\0&-1\end{smallmatrix}]$ and bit-phase flip gate $\ensuremath{Y} = [\begin{smallmatrix}0&-i\\i&0\end{smallmatrix}]$ generates the single-qubit Pauli group $\mathscr{P}_1$. The $n$-qubit Pauli group $\mathscr{P}_n$ is the $n$-fold tensor of $\mathscr{P}_1$. The $n$-qubit Clifford group $\mathscr{C}_n$ is the normalizer of $\mathscr{P}_n$ among the group of unitary transformations.

\paragraph{Quantum One-Time Pad}
A quantum one-time pad is a symmetric encryption scheme that provides information-theoretic security. It is very similar to the classical one-time pad. The key space is the Pauli group $\mathscr{P}_n$. Encryption of an $n$-qubit state $\phi$ under $P \in \mathscr{P}_n$ results in the ciphertext $P \cdot \phi$.

\paragraph{Quantum Teleportation}
Quantum teleportation transmits quantum information from sender to receiver by sending only classical messages. The sender and the receiver pre-share an EPR pair $(e_S, e_R)$. The sender holds an input state $\phi$ and half of the EPR pair $e_S$, executes the teleportation circuit that ends with measurements, and sends the classical measurement outcomes $z$ and $x$ to the receiver for recovery. The receiver applies $\ensuremath{Z}^z \ensuremath{X}^x$ to the other half of the EPR pair $e_R$ to obtain $\psi$.

\paragraph{Quantum Authentication Code}
Quantum authentication code prevents adversarial parties from making unauthorized alterations to the data. A specific code is the Clifford authentication code, whose encoding process augments a quantum state $\phi$ into a larger quantum state with traps, $\phi \otimes 0^t$, and applies a secret Clifford key $E$ on it. No one can successfully alter the resulting state without knowing the Clifford key $E$. The key holder can tell whether the quantum state was tampered with by applying $E^\dag$ and checking the trap measurement result.

\paragraph{Quantum Error Correction Code}
Quantum error correction code (QECC) protects quantum states from errors. QECC works by encoding a logical qubit in a particular entangled way into physical qubits, which are resilient against the effects of noise as a whole. The physical qubits can later be decoded to recover the original logical qubit. One usually prefers QECC that supports transversal computations, {i.e.,\ } certain computations on logical qubits can be realized as parallel computations on the corresponding physical qubits.

\paragraph{Universal Quantum Computation}
A set of quantum gates realizes universal quantum computation if they can approximate every unitary operator. Sometimes, a gate can be reduced to other gates with the help of auxiliary states. In this paper, we will take the set of transversal gates of a QECC together with magic states to fulfill universal quantum computation. An example is to take the Clifford group with T magic states.

\fi

\subsection{Public Verifiability is Hard to Achieve on MPQC}

A first observation is that classical techniques for public verifiability cannot apply to their quantum counterparts. Existing methods for classical MPC-PVIA protocols are to commit to classical messages, provide zero-knowledge arguments over the commitments, and let outside observers check whether any party deviates from the protocol. When adapting to MPQC in the fully quantum setting, there are several issues. If one considers using classical commitments to quantum messages \cite{CVQC}, one cannot fulfill MPQC that has purely quantum outputs because such classical commitment schemes always end with measurements. Instead, one may have to consider quantum commitments, which are rather lacking in the literature. Even if there are quantum commitments, they are unlikely to be duplicated and broadcast to each party for verification because of the no-cloning theorem. In addition, zero-knowledge arguments for quantum computation ({e.g.,\ } \cite{ZKP-QMA}) only apply to problems that have a classical description. They cannot prove relations involving quantum commitments.

Another difficulty arises because we require the outside observers of MPQC to have only classical computational power, but still verify quantum behaviors. Although there is research on classical verification of quantum computation (CVQC), a seemingly similar task, CVQC is too restrictive because it can only resolve computations with classical outputs conducted by a single quantum prover. The techniques of CVQC break down in the fully quantum setting. Moreover, CVQC already produces an inverse polynomial soundness error when extended from solving decisional problems \cite{CVQC} to solving sampling problems \cite{CVQCKM}. Thus, there is little hope that CVQC can aid the construction of MPQC-PVIA.

One may try to build MPQC-PVIA upon MPQC-SWIA protocols, but there is still a gap between them. The MPQC-SWIA protocol by \cite{ACC+21} is based on a Sequential Authentication primitive that outputs two suspects whenever message tampering is detected. However, it gives no information about the \emph{exact} party that deviates from the protocol. The resulting MPQC-SWIA allows honest participants to agree on the same malicious party when protocol aborts, but an outside observer only sees two groups of people accusing each other. This is a result of how quantum authentication codes have typically been used: the sender encrypts a message with a random key before sending it to the receiver, who then checks to see if the checksum or traps match the consented randomness. This type of standard sender-receiver mechanism, however, has no advantage in terms of public verifiability because both ``sending" and ``receiving" are behaviors that must be validated, and both sender and receiver have the right to make accusations. One or both of them may be lying, but there is no rule to separate these cases and make the right judgment.

\subsection{Our Solution: Auditable Quantum Authentication (AQA)}

\ifdefined\FullVersion
In previous MPQC works \cite{DGJ+20,ACC+21,BCKM21}, the receiver of a quantum authenticated message is in charge of detecting malicious actions of the sender. The issue is that the receiver is unable to offer public evidence for the sender's misdeeds of causing an authentication failure. To address this, we
\else We \fi abandon the conventional sender-receiver pattern, and focus only on whether the sender sends an untampered message. To this end, we introduce Auditable Quantum Authentication (AQA), a generic transformation that works with many types of quantum authentication codes. The primary goal of AQA is to hold the sender of an authenticated message accountable for its actions via a test while keeping the receiver in place. There are two requirements of AQA. First, the receiver should always obtain a legitimate authenticated message (lunchbox) when the sender (deliveryman) passes the test. Second, everyone should learn that the sender is malicious if the test fails. With these guarantees, everyone can identify the exact party that attacks an AQA-based protocol.

We can integrate quantum teleportation and quantum message authentication scheme into an AQA scheme in the preprocessing model. A high-level idea is as follows. In the preprocessing phase, the trusted setup will generate EPR pairs with embedded secret keys, and distribute them to the sender and the receiver while giving the keys to classical MPC. The whole component is called portals.

Here, we divide the portals into three categories: sending portal, receiving portal, and checking portal. The sender can teleport the desired authenticated message using the sending portal. If the sender reports a valid teleportation measurement result, the receiving portal enables the receiver to retrieve a newly authenticated message. The checking portal, which the sender must measure and publish, indicates whether the sender has altered the teleportation measurement result or not. The actual detection process is carried out by classical MPC, which knows the secret key and produces a publicly verifiable detection outcome.

\paragraph{Warm-up} To build intuition, we provide a protocol sketch of AQA as follows.
\ifdefined\Thirty
We will use the Clifford authentication code as an example in our AQA. Clifford authentication code augments a quantum state $\phi$ into a larger quantum state with traps, $\phi \otimes 0^t$, and applies a secret Clifford key $E$ on it. To decode, one applies $E^\dag$ on the ciphertext and measures the traps to see whether there has been an attack. Please take notice that although we present our AQA in Clifford-code form, the readers are welcome to use the Trap-code form AQA ($\ref{Sec:AQATP}$) instead. Below, $U \cdot \rho$ stands for the result of applying unitary $U$ to state $\rho$.
\else
Please take notice that although we present our AQA under the Clifford authentication code, the readers are welcome to instantiate AQA with the Trap authentication code ($\ref{Sec:AQATP}$) instead.
\fi

In the preprocessing phase, the trusted setup will generate EPR pairs $(e_S, e_R)$, random Clifford authentication keys $E, E'$, and random Pauli keys $P_S, P_C, P_R$. The trusted party then pretends that $e_R$ is a ciphertext under Clifford code and parses $(E^{\dagger} \cdot e_R)$ into the plaintext part $\mu$ and the trap part $\tau$, and distributes $(\mathcal{S}, \mathcal{C}) = (P_S \cdot e_S, P_C \cdot \tau)$ to the sender and $\mathcal{R} = P_R \cdot (E' \cdot (\mu \otimes 0^t))$ to the receiver. The states $(\mathcal{S},\mathcal{C},\mathcal{R})$ are what we refer to as portals.
\ifdefined\Thirty
\begin{figure}[b]
     \centering
     \scalebox{0.95}{
     $$
     \Qcircuit @C=1.2em @R=0.7em {
     &&&&&&&&&&&&&\\
    &\quad&\quad&\quad&\quad&\lstick{\ket{0}} &\ustick{t}\qw & {/}\qw  & \qw &\qw  &\multigate{1}{E'}&\multigate{1}{P_R} & \qw & \qw \barrier{1}& \qw\\
   \lstick{e_S} &\ustick{1}\qw & {/}\qw &  \qw & {e_{R}} & & \qw &\qw & \qw &\multigate{1}{E^\dag} &\ghost{E'}&\ghost{P_R}\qw & \qw & \qw & \rstick{\sigma'}\qw\\
   \lstick{e_S} &\ustick{t}\qw & {/}\qw &  \qw & {e_{R}} & & \qw &\qw &\qw &\ghost{E^\dag}
   &\gate{P_C}\qw & \qw & \qw & \qw &\meter &\rstick{r_c}\qw\\
   &&&&&&&&&&&&&\text{ }
    \gategroup{1}{4}{5}{13}{.7em}{--}
    }
    $$}
    \caption{{\bf Auditable Quantum Authentication in Clifford code form.}}
    \label{fig:AQA}
\end{figure}

\else

\begin{figure}[H]
     \centering
     \scalebox{0.95}{
     $$
     \Qcircuit @C=1.2em @R=0.7em {
     &&&&&&&&&&&&&\\
    &\quad&\quad&\quad&\quad&\lstick{\ket{0}} &\ustick{t}\qw & {/}\qw  & \qw &\qw  &\multigate{1}{E'}&\multigate{1}{P_R} & \qw & \qw \barrier{1}& \qw\\
   \lstick{e_S} &\ustick{1}\qw & {}\qw &  \qw & {e_{R}} & & \qw &\qw & \qw &\multigate{1}{E^\dag} &\ghost{E'}&\ghost{P_R}\qw & \qw & \qw & \rstick{\sigma'}\qw\\
   \lstick{e_S} &\ustick{t}\qw & {/}\qw &  \qw & {e_{R}} & & \qw &\qw &\qw &\ghost{E^\dag}
   &\gate{P_C}\qw & \qw & \qw & \qw &\meter &\rstick{r_c}\qw\\
   &&&&&&&&&&&&&\text{ }
    \gategroup{1}{4}{5}{13}{.7em}{--}
    }
    $$}
    \caption{{\bf Auditable Quantum Authentication in Clifford code form.}

    }
    \label{fig:AQA}
\end{figure}
\fi

In the online phase, the sender receives an additional quantum state $\sigma=E \cdot (\rho \otimes 0^t)$ for some $\rho$ without knowing the key $E$. To remove $E$ from $\sigma$, the sender can teleport $\sigma$ through $\mathcal{S}$, and publishes the teleportation measurement result $(z, x)$. If we look at the post-teleportation state of $E^\dagger \cdot e_R$, it is $E^\dagger \ensuremath{X}^x \ensuremath{Z}^z P_S^\dag E \cdot (\rho \otimes 0^t)$. Since $E$ is a Clifford gate, conjugation of a Pauli gate by $E$ is again a Pauli, so the state can be rewritten as $(\hat{P}_{\mu} \cdot \rho) \otimes (\hat{P}_{\tau} \cdot 0^t)$ for some Pauli $\hat{P}_{\mu}, \hat{P}_{\tau}$. Using the fact that $E'$ is also a Clifford gate, we can then derive the receiving portal as $\mathcal{R} = P_R \cdot  (E' \cdot ((\hat{P}_{\mu} \cdot \rho) \otimes 0^t)) = \hat{P}_R  E' \cdot (\rho \otimes 0^t)$ and the checking portal as $\mathcal{C} = P_C \hat{P}_{\tau} \cdot 0^t = \hat{P}_C  \cdot 0^t$ for some Pauli $\hat{P}_R, \hat{P}_C$.

As soon as the receiver learns $\hat{P}_R$, it can obtain the state $\sigma' = E'\cdot(\rho \otimes 0^t)$ out of $\mathcal{R}$. The classical MPC can compute $\hat{P}_R$ for the receiver from $E', E, P_R, P_S, (z,x)$. However, the sender can deviate from the honest behavior either by altering $\sigma$ or modifying $(z,x)$, which corrupts the receiver's final state. To prevent this attack, we require that the sender also measures $\mathcal{C}$ and outputs the result $r_c$ to the classical MPC. The expected measurement outcome of $\mathcal{C}$ depends on the traps within $\sigma$ and the actual teleportation measurement result $(z,x)$ and the secret random gate $E$, so verifying $r_c$ acts as a randomized check on the sender's choice of  $\sigma$ and $(z,x)$. In our analysis, we show that the check is sound so that the classical MPC can detect malicious actions of the sender effectively.

Although the above AQA requires a trusted setup in the preprocessing phase, we will later instantiate the preprocessing phase with MPQC-SWIA {e.g.,\ } \cite{ACC+21}. The resulting scheme becomes a two-stage protocol where PVIA is only guaranteed in the second stage. As we will see, this weaker security suffices for MPQC-PVIA as long as the circuit produces only private outputs.

\subsection{From AQA to MPQC-PVIA}

So far, we have developed AQA that achieves public verifiable identification in the context of quantum message transmission. Here, we describe how to use AQA to fulfill the task of MPQC while achieving PVIA. We proceed in two steps, by first assuming a trusted setup, and then removing this extra assumption.

\paragraph{Preprocessing MPQC-PVIA}
At the start of MPQC, the parties have to authenticate their inputs using keys known only by classical MPC. To do this in a PVIA manner, we resort to an input-independent trusted setup. The trusted setup can provide everyone with EPR pairs, half of which are authenticated using some secret keys. During the online phase, each party teleports its input to convert it into an authenticated message. We call this step input encoding (IE). So now, we have IE to encode our inputs and AQA to transmit message ciphertexts.

Another vital component of MPQC is performing computation on authenticated data, which is supported by many quantum authentication codes on a set of gates and measurements. For instance, using the Clifford authentication code, Clifford gates can be performed on a single ciphertext without any interaction. Furthermore, one can obtain verifiable measurement results on Clifford ciphertexts, as shown by \cite{DGJ+20}. Thus, the parties can perform Clifford gates and measurements on their authenticated joint inputs. More generally, the protocol can allow universal quantum computation if the trusted setup additionally produces and distributes authenticated magic states in advance.

We now move on to examine security. In our protocol, each quantum computation unit is performed by a single party, so attacks during the computation step would only ruin the authentication code held by the attacker. The attacker will ultimately be identified when asked to transmit the message in a subsequent AQA. As a result, a protocol combining IE, AQA, and computation can achieve MPQC while maintaining PVIA security.

The protocol sketch of our preprocessing MPQC-PVIA is as follows. First, all parties execute IE so that a delegated party \footnote{There could be multiple delegated parties, but here we assign only one party for clear presentation.}, say $\mathsf{P}_1$, obtains the authenticated joint input. Next, $\mathsf{P}_1$ performs computation instructed by classical MPC and executes AQA to send the authenticated outputs back. Finally, the classical MPC reveals the authentication keys to each party, and each party decodes its output. Whenever AQA fails, the classical MPC publicly outputs the sender's identity and halts the protocol.

\paragraph{MPQC-PVIA}
Next, we show how to obtain an MPQC-PVIA protocol by combining our preprocessing MPQC-PVIA with the MPQC-SWIA protocol of \cite{ACC+21} and removing the trusted setup assumption. However, we must restrict ourselves to computing circuits with only private outputs. In this case, public verifiability only applies to verifying the malicious identity.

Recall that when MPQC-SWIA aborts, the classical MPC will output a partition of parties with all honest parties staying in the same division. Our approach is to run MPQC-SWIA hierarchically to prepare the preprocessing data needed for the preprocessing MPQC-PVIA. The hierarchical MPQC-SWIA maintains a grouping between parties, where all parties are initially in the same group. Each group will try to run MPQC-SWIA by themselves, and a group breaks into two whenever MPQC-SWIA fails. At some point, all parties must have succeeded in running MPQC-SWIA within their group (or they will continue running MPQC-SWIA within descent subgroups), so they can proceed to run their instance of the preprocessing MPQC-PVIA protocol. With the guarantees of MPQC-SWIA and preprocessing MPQC-PVIA, the whole protocol achieves MPQC-PVIA.

\begin{figure}[H]
    \centering
    \caption{{\bf Hierarchical MPQC-SWIA} Players try to generate portals and ancilla states with MPQC-SWIA. $G$ contains the total players in the MPQC game. When the first MPQC-SWIA terminates with a failure, players separate into two groups $G_0$ and $G_1$. Then, players in $G_0$ and players in $G_1$ run MPQC-SWIA with players in their group. In this figure, $G_{1}$ completes the MPQC-SWIA task successfully and obtains output. Players in group $G_{1}$ can proceed to execute preprocessing MPQC-PVIA.}
    \label{fig:Hierarchical MPQC-SWIA}
\begin{tikzpicture}
\tikzset{grow'=right,level distance=32pt}
\tikzset{execute at begin node=\strut}
\tikzset{every tree node/.style={anchor=base west}}
\Tree [.$G$   [.$G_{0}$ [.$G_{00}$ ... ]
                 [.$G_{01}$ ... ] ]
             [.$G_{1}$ Output ] ]
\end{tikzpicture}
\end{figure}
\subsection{Difficulty of Best-of-Both-Worlds Security}

One advantage of our protocol design is its flexibility to provide best-of-both-worlds security. That is, we construct an MPQC protocol that also achieves full security against at most $\thres \le \lfloor \frac{n-1}{2} \rfloor$ corruptions as long as we require security with public verifiable identifiable abort against at most $n-1-\thres$ malicious parties. In contrast, none of the existing MPQC protocols satisfy BoBW security.

The two worlds of honest majority and dishonest majority were once separated because of a tension between spreading information and extracting information. We elaborate on it as follows. MPQC protocols that obtain full security in an honest majority setting $\cite{BCG06}$ are based on quantum secret sharing (QSS) \cite{QSS}. The problem is that the secret shares sent between malicious parties are private information. Once the number of corrupted players reaches one-half, the simulator has no way to extract the adversary's input from the available secret shares. It also explains why existing MPQC protocols in the dishonest majority setting require each quantum message to pass through all parties. In this case, the quantum message must have gone through some honest player, and the simulator can extract input at this moment. As a result, these protocols are unable to divide every piece of information across multiple parties, and a single malicious party is sufficient to destroy the information subjected to the computation.

Our solution to this tension is to combine the hierarchical MPQC-SWIA with quantum error correction codes (QECC), which  is a relaxation of QSS. In the beginning, parties use the hierarchical MPQC-SWIA to prepare QECC codewords that encode EPR pairs and distribute every codeword evenly to the parties. Afterward, the parties can perform distributed computation over QECC codewords. Full security can be achieved when only a few qubits of QECC are in the control of corrupted parties. One can view the hierarchical MPQC-SWIA as a vital piece of machinery that allows information extraction while contributing to the setup for distributed computation.

Our BoBW MPQC protocol is reminiscent of the classical BoBW MPC protocols \cite{BoBW-pos,BoBW-neg,BoBW-1/p} that combine MPC-SWIA with secret sharing. A key difference is that the classical protocols need to either broadcast secret sharings or invoke the ideal functionality on the inputs multiple times, both of which are infeasible in MPQC due to no-cloning. Our protocol does not follow the same pattern, and we achieve the same goal in the merit of quantum teleportation and transversal computation.

\section{Preliminary}\label{sec:prelim}

Let $[n] = \{1, \cdots, n\}$.
For a vector $v$, its first $n$ elements form the vector $v[:n]$, and the remaining form $v[n:]$. $1$-norm is denoted as $||v||_1$. Given a set $S$, $s\leftarrow S$ means that $s$ is uniformly sampled from $S$. A function $f \colon \mathbb{N} \to [0,1]$ is called negligible, if for every polynomial $p(\cdot)$ and all sufficiently large $n$, it holds that $f(n)<\frac{1}{|p(n)|}$. We use $\operatorname{negl}(\cdot)$ to denote an unspecified negligible function. {\sc qpt}\xspace stands for quantum polynomial-time.

\ifdefined\FullVersion
\paragraph{Quantum Notations}
\fi

Density matrices are written in lowercase Greek alphabets, {e.g.,\ } $\rho,\sigma,\tau$. The set of density matrices over the Hilbert space of $n$ qubits is $\Den{n}$.
\ifdefined\FullVersion
The notation $(\rho, \sigma)$ denotes a state on two registers that may be entangled.
\fi
We sometimes write $0^n \in \Den{n}$ to represent $\ketbra{0}^{\otimes n}$. The shorthand $U \cdot \rho$ stands for the result $U \rho U^\dag$ of applying a unitary $U$ to $\rho$. Measurement in the computational basis is denoted by $\mathsf{\Pi}$. States $g(n), h(n) \in \Den{\poly(n)}$ are statistically indistinguishable, denoted $g \approx h$, if they have trace distance $\tr|g(n)-h(n)| = \operatorname{negl}(n)$.
\ifdefined\FullVersion
States $g(n), h(n)$ are computationally indistinguishable, denoted $g \approx_c h$, if for any {\sc qpt}\xspace distinguisher $D$ outputting $1$ bit, it holds that $|| D(g(n)) - D(h(n)) ||_1 = \operatorname{negl}(n)$.
\fi

The Pauli group $\mathscr{P}_n$ acting on $n$ qubits is the $n$-fold tensor of the group generated by $\ensuremath{X} = [\begin{smallmatrix}0&1\\1&0\end{smallmatrix}],~ \ensuremath{Z} = [\begin{smallmatrix}1&0\\0&-1\end{smallmatrix}]$ and $i\identity = [\begin{smallmatrix}i&0\\0&i\end{smallmatrix}]$. An element $P\in \mathscr{P}_n$ can be written as $P= \pm i \bigotimes_{j\in[n]}\ensuremath{X}^{x_j}\ensuremath{Z}^{z_j}$. We denote the $X, Z$ exponents of a Pauli $P$ as $x(P), z(P)$.
The Clifford group $\mathscr{C}_n$ acting on $n$ qubits is the normalizer of $\mathscr{P}_n$.
\ifdefined\FullVersion
That is, $C \in \mathscr{C}_n$ if and only if for all $A \in \mathscr{P}_n$, $CAC^\dag \in \mathscr{P}_n$. Intuitively, it means that with a reasonable update of the Pauli operation, we can swap the order where a Clifford and a Pauli are applied.
\fi
An EPR pair $(e_S, e_R)$ of length $n$ is the first and second halves of $\ketbra{\Phi^{+}}^{\otimes n}$ where $\ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$. The abbreviation $\onreg{\mathsf{CNOT}_{(b_1,\cdots,b_n)}}{R_0,\cdots,R_n}$ stands for the composition $\onreg{\mathsf{CNOT}^{b_1}}{R_0,R_1} \cdots \onreg{\mathsf{CNOT}^{b_n}}{R_0,R_n}$.

\subsection{Quantum Teleportation}\label{prelim:teleport}

\ifdefined\FullVersion

\begin{dfn}[Quantum Teleportation]
Let $(e_S, e_R)$ be an EPR pair of length $n$ pre-shared between a sender holding input $\psi \in \Den{n}$ and a receiver. Quantum teleportation consists of two algorithms:
\begin{itemize}
    \item  $\mathsf{TP.Send}(\onreg{\psi}{M}, \onreg{e_S}{S}):=$ $\onreg{\mathsf{\Pi}}{M,S} \onreg{\ensuremath{H}}{M} \onreg{\mathsf{CNOT}}{M,S}(\psi, e_S)$ which yields strings $(z,x)$.
    \item  $\mathsf{TP.Receive}(z,x,e_R):=$ Apply $(\ensuremath{X}^x\ensuremath{Z}^z)^\dag$ on $e_R$ which yields the state $\psi$.
\end{itemize}
Define also the unitary $\onreg{\mathsf{TP}}{M,S} := \onreg{\ensuremath{H}}{M} \onreg{\mathsf{CNOT}}{M,S}$ for sending without measurement. It always holds that $\mathsf{TP.Receive}(\mathsf{TP.Send}(\psi, e_S), e_R) = \psi$ and $\mathsf{TP.Send}$ has uniformly random outputs.
\end{dfn}

\begin{figure}[H]
     \centering
     $$
     \Qcircuit @R=1em @C=1em{
     \lstick{\psi}
     &\ctrl{1}&\gate{\ensuremath{H}}&\meter&\qw&\qw&\rstick{z}\qw\\
     \lstick{e_S} &\targ&\qw&\meter&\qw&\qw&\rstick{x}\qw\\
     \lstick{e_R}&\qw&\qw&\qw&\gate{\ensuremath{X}^x}&\gate{\ensuremath{Z}^z}&\rstick{\psi}\qw
    \inputgroupv{2}{3}{0.2em}{1.2em}{}
     \gategroup{1}{2}{2}{4}{1em}{--}
     \gategroup{3}{5}{3}{6}{1em}{--}
     }
     $$
     \caption{single-qubit quantum teleportation}
     \label{fig:QT}
\end{figure}

\else

\begin{dfn} Let $(e_S, e_R)$ be an EPR pair of length $n$ pre-shared between a sender holding input $\psi \in \Den{n}$ and a receiver. Quantum teleportation consists of:
\begin{itemize}
    \item  $\mathsf{TP.Send}(\onreg{\psi}{M}, \onreg{e_S}{S}):=$ $\onreg{\mathsf{\Pi}}{M,S} \onreg{\ensuremath{H}}{M} \onreg{\mathsf{CNOT}}{M,S}(\psi, e_S)$ which yields strings $(z,x)$.
    \item  $\mathsf{TP.Receive}(z,x,e_R):=$ Apply $(\ensuremath{X}^x\ensuremath{Z}^z)^\dag$ on $e_R$ which yields the state $\psi$.
\end{itemize}
Define the unitary $\onreg{\mathsf{TP}}{M,S} := \onreg{\ensuremath{H}}{M} \onreg{\mathsf{CNOT}}{M,S}$ for sending without measurement.
\end{dfn}

\fi

\ifdefined\FullVersion
\subsection{Quantum One-Time Pad}
\begin{dfn}[Quantum One-Time Pad (QOPT)] Let $\rho \in \Den{n}$. A QOPT with keys $x,z \in \{0,1\}^n$ is a symmetric-key encryption scheme that consists following two algorithms.
\begin{itemize}
    \item Encryption
    $$\mathsf{QOPT.Enc}(\rho):= (\ensuremath{X}^x \ensuremath{Z}^z) \rho (\ensuremath{X}^x \ensuremath{Z}^z)^\dag$$
    \item Decryption
    $$\mathsf{QOPT.Dec}(\rho):= (\ensuremath{X}^x \ensuremath{Z}^z)^\dag \rho (\ensuremath{X}^x \ensuremath{Z}^z) $$
\end{itemize}
\end{dfn}
\begin{lemma}[Security of QOPT]
The QOTP is information-theoretic secure ,{i.e.,\ } the ciphertext is maximally mixed to a player without keys.
$$\frac{1}{2^n}\underset{x,z}{\Sigma}(\ensuremath{X}^x \ensuremath{Z}^z) \rho (\ensuremath{X}^x \ensuremath{Z}^z)^\dag=(\frac{\identity}{2})^{\otimes n}$$
\end{lemma}
\fi

\subsection{Twirling}

\ifdefined\Thirty
Twirling \cite{Twirl} of a state $\rho$ is to perform a random operator $U$ among a group $G$ of unitary operators on $\rho$, and tracing out $U$. It is defined as the CPTP map
${\cal T}_G(\rho) := \frac{1}{|G|} \underset{{U\in G}}{\Sigma} (U \cdot \rho)$.
Twirling a state over Pauli group or Clifford group results in the fully mixed state. That is, $\mathcal{T}_{\mathscr{P}}(\rho) = \mathcal{T}_{\mathscr{C}}(\rho)= (\frac{\identity}{2})^{\otimes n}$.

\else

Twirling \cite{Twirl} of a state $\rho$ is to perform a random operator $U$ among a group $G$ of unitary operators on $\rho$, and tracing out $U$. It is defined as the CPTP map
$${\cal T}_G(\rho) := \frac{1}{|G|} \underset{{U\in G}}{\Sigma} U \cdot \rho.$$
Twirling a state over Pauli group or Clifford group results in the fully mixed state $(\frac{\identity}{2})^{\otimes n}$. That is, $\mathcal{T}_{\mathscr{P}}(\rho) = \mathcal{T}_{\mathscr{C}}(\rho)= (\frac{\identity}{2})^{\otimes n}$. On the other hand, twirling of an operator $V$ is defined as the CPTP map
$${\cal T}_G(V) := \frac{1}{|G|} \underset{{U\in G}}{\Sigma} U^\dag V U \cdot \rho.$$
The following lemma on Pauli twirl implies that any quantum attack against quantum one-time pad is equivalent to a probabilistic combination of Pauli attacks.

\begin{lemma}[Pauli Twirl]
Let $\rho \in \Den{n}$. For every Pauli operators $P, P'$, it holds that
$$\frac{1}{4^n}\underset{x,z \in \{0,1\}^n}{\Sigma} (\ensuremath{X}^x \ensuremath{Z}^z)^\dag P (\ensuremath{X}^x \ensuremath{Z}^z) \rho (\ensuremath{X}^x \ensuremath{Z}^z)^\dag P^{'\dag} (\ensuremath{X}^x \ensuremath{Z}^z) =
\begin{cases}
P \rho P^\dag,\text{ if } P=P'\\
0, \text{ otherwise.}
\end{cases}
$$
\end{lemma}

\fi

\subsection{Quantum Error-Correcting Codes}

Quantum error correcting code protects quantum states from errors. The encoding algorithm ${\mathsf{QECC.Enc}}$ of a $[[\Qnum,1,d]]$ QECC code encodes a $1$-qubit message into a $\Qnum$-qubit codeword. Through the decoding procedure $\mathsf{QECC.Dec}$, the QECC code can correct arbitrary errors on $\lfloor\frac{d-1}{2}\rfloor$ qubits, or ${d-1}$ erasure-errors on known positions.
\ifdefined\FullVersion
\begin{dfn}[Quantum Error Correction Code]
A $[[\Qnum,1,d]]$-QECC consists of an {\sc qpt}\xspace encoding algorithm ${\mathsf{QECC.Enc}}:\Den{1}\rightarrow\Den{\Qnum}$ and a {\sc qpt}\xspace decoding algorithm $\mathsf{QECC.Dec}:\Den{\Qnum}\rightarrow\Den{1}$ such that for all quantum channel $\Delta$ acting on $\lfloor\frac{d-1}{2}\rfloor$ qubits and for all $\rho \in\Den{1}$, it holds that
\[
(\mathsf{QECC.Dec} \circ \Delta\circ{\mathsf{QECC.Enc}})(\rho) = \rho.
\]
\end{dfn}
\fi
We consider CSS codes in particular due to the following properties. First, the encoding process consists only of Clifford gates, which we denote by $\mathsf{QECC}$. Second, they allow certain Clifford gates to be transversally computed over codewords. Third, measurement can be transversally performed over codewords by running the classical decoding algorithm of the linear code associated with the CSS code over the measurement outcome of codewords.

To arrive at best-of-both-worlds security for any threshold $\thres \le \lfloor \frac{n-1}{2} \rfloor$, we can use quantum polynomial codes such as the quantum secret sharing scheme of \cite{QSS}. Such codes exist for every $\Qnum = 2d-1$ over qudits, which can satisfy the condition $\frac{d-1}{\Qnum} > \frac{\thres}{n}$ needed for full security against $\thres$ corruptions. For simplicity, we present our main arguments over qubits, and set $q = n$ or any multiple of $n$.

\subsection{Quantum Authentication Code}
\label{section:CliffordCode}
Quantum authentication code prevents adversarial parties from making unauthorized alterations to the data.
Here, we introduce Clifford code \cite{CliffordCodes} and Trap code \cite{Trapcode}.
\ifdefined\FullVersion Below, \fi
$\bot$ will denote a reject symbol. It is actually stored in a separate flag register, but for simplicity we will just put it in the original state register.
\ifdefined\FullVersion
Encoding of $\bot$ is always defined as $\bot$. \fi

\ifdefined\Thirty
Clifford authentication code augments the message state $\onreg{\phi}{M} \in \Den{1}$ with traps $\onreg{{0}^t}{T}$, and applies a secret random Clifford gate $E \leftarrow \mathscr{C}_{1+t}$ on them. The decoding procedure is to apply $E^\dag$ followed by measuring the register $\gray{T}$. If the measurement result are not all zero, the content in $\gray{M}$ is replaced with $\bot$.

Trap authentication code augments the message state $\phi$ into a larger quantum state, ${\mathsf{QECC.Enc}}({\phi})\otimes \ketbra{0}^t \otimes \ketbra{+}^t$, and applies a permutation $\Pi$ followed by a quantum one-time pad $\ensuremath{X}^x \ensuremath{Z}^z$. It has a similar decoding procedure.

\else

\subsubsection{Clifford Code}
\begin{dfn}[Clifford Code \cite{CliffordCodes}]
    \label{dfn:Clifford_code}
    Let $M$ be the message register, $T$ be the trap register. The set of keys is the Clifford group $\mathscr{C}_{|MT|}$.

    Define the projectors $P_{{\mathsf{Acc}}}:=\ketbra{0^t}$ and $P_{{\mathsf{Rej}}}:=\identity^{t} - P_{{\mathsf{Acc}}}$. The Clifford authentication code $\CAuth=(\mathsf{C.Enc}, \mathsf{C.Dec})$ is defined as follows.
    \begin{itemize}
        \item {\bf Encoding}
        \[
        \mathsf{C.Enc}_E(\onreg{\rho}{M}):=E(\onreg{\rho}{M}\otimes\onreg{\ketbra{0^t}}{T})E^{\dagger}.
        \]
        \item {\bf Decoding}
        \ifdefined\LLNC
        \begin{align*}
        \mathsf{C.Dec}_E(\onreg{\sigma}{MT})
        :=
        \tr_{T}\left(
        \onreg{P}{T}_{{\mathsf{Acc}}} E{^\dagger}\onreg{\sigma}{MT} E
        \right)\otimes\ketbra{{\mathsf{Acc}}}
        + \tr_{MT}\left( \onreg{P}{T}_{{\mathsf{Rej}}}E{^\dagger}\onreg{\sigma}{MT} E  \right)\onreg{\ketbra{\bot}}{M}\otimes\ketbra{{\mathsf{Rej}}}.
        \end{align*}
        \else
        \begin{align*}
        \mathsf{C.Dec}_E(\onreg{\sigma}{MT})
        :=
        \tr_{T}\left(
        \onreg{P}{T}_{{\mathsf{Acc}}} E{^\dagger}\onreg{\sigma}{MT} E
        \right)
        + \tr_{MT}\left( \onreg{P}{T}_{{\mathsf{Rej}}}E{^\dagger}\onreg{\sigma}{MT} E  \right)\onreg{\bot}{M}.
        \end{align*}
        \fi
\end{itemize}
\end{dfn}

In other words, Clifford code augments the message state $\onreg{\phi}{M}$ with traps $\onreg{\ketbra{0^t}}{T}$, and applies a secret random Clifford gate $E$ on them. The decoding procedure is to apply $E^\dag$ followed by measuring the register $\gray{T}$. If the measurement result are not all zero, the content in $\gray{M}$ is replaced with $\bot$. The scheme is secure in the sense that the authentication result is either the original state or a rejection.

\begin{thm}[Security of Clifford Code, Appendix C of \cite{DGJ+20}]
    \label{thm:security_Clifford_code}
     For all CPTP map $\onreg{{\mathcal{A}}}{MTR}$ there exists two CP maps $\onreg{\mathscr{A}}{R}_{{\mathsf{Acc}}}$ and $\onreg{\mathscr{A}}{R}_{{\mathsf{Rej}}}$ satisfying  $\onreg{\mathscr{A}}{R}_{{\mathsf{Acc}}} + \onreg{\mathscr{A}}{R}_{{\mathsf{Rej}}}$ is trace preserving, such that for any input $\onreg{\rho}{MR}$ it holds that
    \begin{align*}
        \norm{
        \underset{k\in\mathscr{C}_{|MT|}}{\mathbb{E}}[\mathsf{Dec}_{k}(\onreg{{\mathcal{A}}}{MTR}\mathsf{Enc}_{k}(\rho))]
        -
        \bigl(\onreg{\mathscr{A}}{R}_{{\mathsf{Acc}}}(\rho) +\onreg{\ketbra{\bot}}{M}\otimes\tr_{M}[\onreg{\mathscr{A}}{R}_{{\mathsf{Rej}}}(\rho)]  \bigl)}\leq \operatorname{negl}{|T|}
    \end{align*}

\end{thm}

\subsubsection{Trap Authentication Code}

\begin{dfn}[Trap Code \cite{Trapcode}]
    \label{dfn:Trap_code}The key set of a trapcode that uses $[[t,1,d]]$-QECC is $Sym_{3t}\times \{0,1\}^{3t}\times\{0,1\}^{3t}$.
    Let $M$ be the 1-qubit register,  $\tilde{M}$ be the QECC codeword register, $C=\tilde{M}T_XT_Z$ be the ciphertext register, where $T_X$ and $T_Z$ are trap registers.
    Define the projectors $P_{{\mathsf{Acc}}}:=\ketbra{0}^{\ott}\otimes\ketbra{+}^{\ott}$ and $P_{{\mathsf{Rej}}}:=\identity^{2t} - P_{{\mathsf{Acc}}}$. Trap authentication code $\TAuth=(\mathsf{T.Enc}, \mathsf{T.Dec})$ is defined as follows.
    \begin{itemize}
        \item {\bf Encryption}
        \[
        \mathsf{T.Enc}_{\Pi,x,z}(\onreg{\rho}{M}):=X^x Z^z\Pi({\mathsf{QECC.Enc}}(\onreg{\rho}{M})\otimes\onreg{\ketbra{0}^t}{T_X}\otimes\onreg{\ketbra{+}^t}{T_Z})(X^x Z^z\Pi)^{\dagger}.
        \]
        \item {\bf Decryption}
        \ifdefined\LLNC
        \begin{align*}
        \mathsf{T.Dec}_{\Pi,x,z}(\onreg{\sigma}{\tilde{M}T_X T_Z})
        :=
        \mathsf{QECC.Dec}(\tr_{T_X T_Z}\left(I^{\ott} \otimes
        \onreg{P}{T}_{{\mathsf{Acc}}} (X^x Z^z\Pi)^\dag\onreg{\sigma}{\tilde{M}T_X T_Z}(X^x Z^z\Pi)
        \right))\otimes\ketbra{{\mathsf{Acc}}}
        + \onreg{\ketbra{\bot}}{M}\tr_{\tilde{M}T_X T_Z}\left( \onreg{P}{T}_{{\mathsf{Rej}}}\otimes(X^x Z^z\Pi)^\dag\onreg{\sigma}{\tilde{M}T_X T_Z} (X^x Z^z\Pi)  \right).
        \end{align*}
        \else
                \begin{align*}
        \mathsf{T.Dec}_{\Pi,x,z}(\onreg{\sigma}{\tilde{M}T_X T_Z})
        :=
        \mathsf{QECC.Dec}(\tr_{T_X T_Z}\left(I^{\ott}
        \onreg{P}{T}_{{\mathsf{Acc}}} \otimes (X^x Z^z\Pi)^\dag\onreg{\sigma}{\tilde{M}T_X T_Z}(X^x Z^z\Pi)
        \right))\\
        \otimes\ketbra{{\mathsf{Acc}}}
        + \onreg{\ketbra{\bot}}{M}\tr_{\tilde{M}T_X T_Z}\left( \onreg{P}{T}_{{\mathsf{Rej}}}\otimes(X^x Z^z\Pi)^\dag\onreg{\sigma}{\tilde{M}T_X T_Z} (X^x Z^z\Pi)  \right).
        \end{align*}
        \fi
\end{itemize}
\end{dfn}

In other words, Trap code augments the message state $\phi$ into a larger quantum state, ${\mathsf{QECC.Enc}}({\phi})\otimes \ketbra{0}^t \otimes \ketbra{+}^t$, and applies a random permutation $\Pi$ followed by a quantum one-time pad $\ensuremath{X}^x \ensuremath{Z}^z$. By checking the trap measurement result, trap code provides authentication against message tampering. The next theorem quantifies its security.

\begin{thm}[Security of Trap Code \cite{Trapcode}]
A trapcode using $[[t,1,d]]$-QECC is a $\frac{2}{3}^{\frac{d}{2}}$-secure quantum authentication scheme {i.e.,\ } it holds that for each fixed choice of $3n$-qubit Pauli operation $P$, the probability that $P$ operates nontrivially on logical data but has no error syndrome is at most $(\frac{2}{3})^\frac{d}{2}$.

\end{thm}

\fi

\section{Model and Definition}
We focus on interactive protocols between $n$ parties with quantum capabilities. They can communicate using pairwise quantum channels or a public broadcast channel for classical messages. We work in the synchronous communication model where the protocol proceeds in rounds, and each message will certainly arrive at the end of each round. In addition, we consider the presence of a protocol observer who passively receives and records classical information from the broadcast channel all the time. The adversary can statically corrupt up to $n-1$ parties. Sometimes we consider the preprocessing model, which allows an input-independent trusted setup to be executed prior to the actual protocol.

\subsection{Best-of-Both-Worlds Multi-Party Quantum Computation Secure with Public Verifiable Identifiable Abort}\label{sec:MPQC-def}

A multi-party quantum computation protocol is defined using the real vs. ideal paradigm. In the ideal world, the parties delegate the task of interest to a trusted party $\mathsf{T}$.
Let $\mathsf{P}_1, \cdots, \mathsf{P}_n$ be the parties involved in the computation, and $I$ be the set of corrupted parties controlled by an adversary ${\mathcal{A}}_I$. There is an observer $\mathsf{O}$ that receives public information from $\mathsf{T}$. Let $C$ be a quantum circuit taking $(\ell_1,\cdots,\ell_n)$ input qubits and $\ell_{\mathsf{anc}}$ ancilla qubits, a total of $\ell = \Sigma_{i} \ell_i + \ell_{\mathsf{anc}}$ qubits, and outputs $\ell'$ qubits along with some classical string $r'_{\operatorname{out}}$.
The ideal functionality
\ifdefined\Thirty\else we would like to achieve \fi
for multi-party quantum computation over a circuit $C$ is as follows.

\begin{idealmodel}{${\mathsf{Ideal}}^{{\mathsf{MPQC}}}$: Multi-party Quantum Computation Secure with Public Verifiable Identifiable Abort}
\begin{description}
\item[Common Input:]\quad\\
The security parameter $1^{\secparam}$.
\item[Input:]\quad\\
$\mathsf{P}_i$ holds private input $\rho_i \in \Den{\ell_i}$.

\item[$\mathsf{T}$ receives inputs and performs computation:]\quad\\
Each party $\mathsf{P}_i$ sends some $\tilde{\rho}_i$ as input to $\mathsf{T}$. Honest parties choose $\tilde{\rho}_i = \rho_i$.\\
$\mathsf{T}$ samples $\rho_{{\mathsf{anc}}}$ and computes $(\rho'_1, \cdots, \rho'_n, r'_{\operatorname{out}}) = C(\tilde{\rho}_1, \cdots, \tilde{\rho}_n; \rho_{\mathsf{anc}})$.

\item[$\mathsf{T}$ sends back outputs:]\quad\\
$\mathsf{T}$ sends $\rho'_i$ to all $\mathsf{P}_i \in I$.\\
$\mathsf{P}_i$ in $I$ can send $\normalfont{\texttt{abort}}$ message to $\mathsf{T}$. If so, $\mathsf{T}$ publicly aborts to $\mathsf{P}_i$.\\
If there is no $\normalfont{\texttt{abort}}$, $\mathsf{T}$ sends $\rho'_i$ to all $\mathsf{P}_i \not \in I$ and publicly outputs $r'_{\operatorname{out}}$.

\item[Outputs:]\quad\\ Honest parties output whatever output received from $\mathsf{T}$.\\
The observer $\mathsf{O}$ outputs whatever public information received from $\mathsf{T}$.\\
The adversary ${\mathcal{A}}_I$ outputs a function of its view.
\end{description}
\end{idealmodel}

We also consider ${\mathsf{Ideal}}^{{\mathsf{MPQC-Full}}}$, the ideal world of MPQC with full security. It is obtained by not allowing any abort messages to take place in the ideal world ${\mathsf{Ideal}}^{\mathsf{MPQC}}$. We denote by ${\mathsf{Ideal}}^{{\mathsf{MPQC}}}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n)$ the joint output of the honest parties, the observer, and the adversary at the end of ${\mathsf{Ideal}}^{{\mathsf{MPQC}}}$ when it is run by $\mathsf{T}$ and $\mathsf{P}_i(\rho_i)$ in the presence of an adversary ${\mathcal{A}}_I(\rho_{{\mathsf{aux}}})$ corrupting parties in $I$. We also define ${\mathsf{Ideal}}^{{\mathsf{MPQC-Full}}}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n)$ in a similar way.

For a protocol $\Pi$, we denote by ${\mathsf{Real}}^{\Pi}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, \rho_1, \cdots, \rho_n)$ the joint output of the honest parties, the observer, and the adversary at the end of protocol $\Pi$ when it is run by ${\mathsf{cMPC}}$ and $\mathsf{P}_i(\rho_i)$ in the presence of an adversary ${\mathcal{A}}_I(\rho_{{\mathsf{aux}}})$ corrupting parties in $I$. For a protocol $\Pi$ with trusted preprocessing $\Sigma$, we define ${\mathsf{Real}}^{\Pi \circ \Sigma}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})} (1^{\secparam}, {\rho_1, \cdots, \rho_n})$ similarly with $\Sigma$ executed by a trusted party.

\begin{dfn}\label{dfn:mpqc}
We say that a protocol $\Pi$ is a multi-party quantum computation secure with public verifiable identifiable abort (MPQC-PVIA) over a circuit $C$, if for every non-uniform ({\sc qpt}\xspace) adversary ${\mathcal{A}}_I$ corrupting $I$, there is a non-uniform ({\sc qpt}\xspace) simulator $\mathsf{Sim}_I$ corrupting $I$, such that for any quantum inputs $\rho_i \in \Den{\ensuremath{1}} %{\ensuremath{m}} %{{\ensuremath{\ell_{\mathsf{in}}}}_i}$,
$$ {\mathsf{Real}}^{\Pi}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n) \approx {\mathsf{Ideal}}^{{\mathsf{MPQC}}}_{\mathsf{Sim}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n)$$
Furthermore, we say that a protocol $\Pi$ is a best-of-both-worlds\xspace multi-party quantum computation secure with public verifiable identifiable abort\xspace (BoBW-MPQC-PVIA) of threshold $\thres$ if the indistinguishability condition is modified as
\begin{align*}
    {\mathsf{Real}}^{\Pi}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})} & \approx {\mathsf{Ideal}}^{{\mathsf{MPQC-Full}}}_{\mathsf{Sim}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n) \text{ when } |I| \le \thres
    \\
    {\mathsf{Real}}^{\Pi}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})} & \approx {\mathsf{Ideal}}^{{\mathsf{MPQC}}}_{\mathsf{Sim}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n) \text{ when } |I| \le n-1-\thres
\end{align*}
\end{dfn}
We can also define these versions of multiparty quantum computation for protocols $(\Sigma, \Pi)$ with trusted setup.
\ifdefined\LLNCS
One simply replaces ${\mathsf{Real}}^{\Pi}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n)$ with ${\mathsf{Real}}^{\Pi \circ \Sigma}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n)$ in the definitions.
\else
One simply replaces ${\mathsf{Real}}^{\Pi}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}$ with ${\mathsf{Real}}^{\Pi \circ \Sigma}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}$ in the definitions.
\fi

\subsection{MPC-Hybrid Model}\label{sec:MPC-hybrid}

Following \cite{DNS12,DGJ+20,ACC+21,BCKM21}, we assume a \emph{reactive}\footnote{It can be equipped with an internal state that may be taken into account when it is called next time.} BoBW-MPC-PVIA ideal functionality ${\mathsf{cMPC}}$ for classical multiparty computation within our MPQC protocol. We refer this setting as the MPC-hybrid model. The ideal world of MPC is similar to that of MPQC defined in section \cref{sec:MPQC-def}, but allows only classical messages and classical computations. We will simply view ${\mathsf{cMPC}}$ as a trusted classical party. One can also instantiate the BoBW-MPC-PVIA ideal functionality using a post-quantum universally-composable BoBW-MPC-PVIA protocol. A concrete construction of such a protocol is to plug the universally-composable MPC-PVIA protocol of \cite{BOS+20} into the compiler of \cite{BoBW-pos} to attain best-of-both-worlds\xspace security, and then apply \cite{Unr10}'s lifting theorem to obtain post-quantum security.

\section{Auditable Quantum Authentication}\label{Sec:AQA}

This section presents a new primitive called \emph{Auditable Quantum Authentication} (AQA) that lets a sender send quantum messages to a receiver and be accountable for its sending action. AQA is designed to identify the malicious sender only, while the receiving behavior is automatically guaranteed by successfully passing the test. For simplicity, we present Clifford-code form AQA. One can feel free to replace it with Trap-code form AQA (\cref{fig:AQATP}). We now formally define the ideal world of AQA. Let $\mathsf{T}$ be the trusted party, $\mathsf{P_{s}}$ be the sender, $\mathsf{P_{r}}$ be the receiver, and $\mathsf{O}$ be the observer.

\begin{idealmodel}{${\mathsf{Ideal}}^{\mathsf{AQA}}$: Ideal World of Auditable Quantum Authentication}\label{ideal:aqa}
	\begin{description}
	    \item[Common Input:]\quad\\
	    The security parameter $1^{\secparam}$ and the number of traps $t=t(\secparam)$.
		\item[Input:]\quad\\
		$\mathsf{T}$ holds key $E \in \mathscr{C}_{\ensuremath{1}} %{\ensuremath{m}+t}$, and $\mathsf{P_{s}}$ holds ciphertext $\sigma = E \cdot (\rho \otimes 0^t) \in \Den{\ensuremath{1}} %{\ensuremath{m} + t}$.

		\item[$\mathsf{T}$ receives quantum state]\quad\\
		$\mathsf{P_{s}}$ sends $\sigma$ to $\mathsf{T}$. If $\mathsf{P_{s}}$ is corrupted, it can send $\bot$ to $\mathsf{T}$ instead.

		\item[$\mathsf{T}$ re-authenticates and forwards the quantum state
		]\quad\\
		If $\mathsf{T}$ receives $\bot$ from $\mathsf{P_{s}}$, it publicly aborts to $\mathsf{P_{s}}$.\\
		Otherwise, $\mathsf{T}$ sends $\sigma' = E' E^\dag \cdot \sigma$ to $\mathsf{P_{r}}$ using fresh key $E' \leftarrow \mathscr{C}_{\ensuremath{1}} %{\ensuremath{m}+t}$.

		\item[Output:]\quad\\
        $\mathsf{P_{s}}, \mathsf{P_{r}}, \mathsf{O}$ output whatever they received from $\mathsf{T}$.\\
        $\mathsf{T}$ outputs $E'$, where $E'$ is replaced with $\bot$ upon abort.\\
        ${\mathcal{A}}$ outputs its view.
	\end{description}
\end{idealmodel}

We denote by ${\mathsf{Ideal}}^{\mathsf{AQA}}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}(1^{\secparam}, E, \rho)$ the joint output of ${\mathsf{Ideal}}^{\mathsf{AQA}}$ run by $\mathsf{T}(E)$, $\mathsf{P_{s}}(E \cdot (\rho \otimes 0^t))$, $\mathsf{P_{r}}$ in the presence of an adversary ${\mathcal{A}}(\rho_{{\mathsf{aux}}})$ that may corrupt both $\mathsf{P_{s}}$ and $\mathsf{P_{r}}$.

\subsection{Protocol}\label{sec:AQA-protocol}
To realize the ideal functionality of AQA, we first consider a preprocessing protocol where the sender indeed gets a ciphertext $\sigma = E \cdot (\rho \otimes 0^t)$ as online input. In section \ref{sec:AQA-twist}, we show how the protocol can be generalized to deal with a somewhat twisted online input.

The whole procedure of our AQA protocol consists of two parts: a trusted offline phase and an online protocol. In the offline phase, the trusted setup $\Sigma^\mathsf{AQA}$ generates triple portals by applying quantum one-time pad encryption and re-authentication operation on EPR pairs. The trusted setup stores the keys in cMPC. The sender $\mathsf{P_{s}}$ receives the sending portal $\mathcal{S}$ and the checking portal $\mathcal{C}$, whereas the receiver $\mathsf{P_{r}}$ receives the receiving portal $\mathcal{R}$.

Based on this pre-shared information, the online protocol $\Pi^\mathsf{AQA}$ goes as follows. The sender $\mathsf{P_{s}}$ teleports his/her ciphertext input $\sigma$ via the sending portal $\mathcal{S}$ and measures the checking portal $\mathcal{C}$. There are two steps for cMPC to check the consistency of the sender's teleportation result $(r_z, r_x)$ and measurement result $r_c$. First, cMPC XORs $(r_z, r_x, r_c)$ with $(s_z, s_x, s_c)$ to cancel out the effect of quantum one-time pads present in $\sigma, \mathcal{S}, \mathcal{C}$. Second, cMPC verifies whether the resulting values satisfy a conjugation relation defined by the secret key $E$. Any inconsistency indicates that the sender is malicious. On the other hand, cMPC can produce a correct key from consistent measurement results, which guarantees the authenticity of the receiver's receiving portal $\mathcal{R}$

\begin{protocol}{$(\Sigma^\mathsf{AQA}, \Pi^{\mathsf{AQA}})$ for Auditable Quantum Authentication}\label{proto:aqa}
\centerline{{\bf Parameters:} $t$}
{\bf Preprocessing $\Sigma^\mathsf{AQA}(\mathsf{P_{s}}, \mathsf{P_{r}}, E)$:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item Generate coordinate-wise EPR pair $(e_S, e_R)$ of length ${\ensuremath{1}} %{\ensuremath{m}+t}$.
    \item Sample random Pauli gates $P_M, P_S, P_R \leftarrow \mathscr{P}_{\ensuremath{1}} %{\ensuremath{m}+t}$, $P_C \leftarrow \mathscr{P}_{t}$.\\
    Sample random authentication key $E' \leftarrow \mathscr{C}_{\ensuremath{1}} %{\ensuremath{m}+t}$.
    \item Set $\tilde{E} = P_M^\dag E$ and parse $\tilde{E}^{\dagger} \cdot e_R$ into $(\mu, \tau)$ where $\mu \in \Den{\ensuremath{1}} %{\ensuremath{m}}$ and $\tau \in \Den{t}$.
    \item Send to $\mathsf{P_{s}}$ the sending portal $\mathcal{S} = P_S \cdot e_S$ and the checking portal $\mathcal{C} = P_C \cdot \tau$.\\
    Send to $\mathsf{P_{r}}$ the receiving portal $\mathcal{R} = P_R E' \cdot (\mu \otimes 0^t)$.\\
    Send to ${\mathsf{cMPC}}$ the secret $(P_M, P_S, P_R, P_C, E, E')$.
\end{enumerate}
{\bf Online Input:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item $\mathsf{P_{s}}$ holds private online input $\sigma = E \cdot (\rho \otimes 0^t)$ for some $\rho \in \Den{\ensuremath{1}} %{\ensuremath{m}}$.
\end{enumerate}

{\bf Protocol $\Pi^\mathsf{AQA}$:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item $\mathsf{P_{s}}$ teleports $\sigma$ via sending portal $\mathcal{S}$ and measures traps on the checking portal $\mathcal{C}$, and then $\mathsf{P_{s}}$ sends $(r_z, r_x) \leftarrow \mathsf{TP.Send}(\sigma, \mathcal{S})$ and $r_c \leftarrow \mathsf{\Pi}(\mathcal{C})$ to ${\mathsf{cMPC}}$.
    \item ${\mathsf{cMPC}}$ derives classical one-time pads $(s_z, s_x, s_c) = x(\mathsf{TP} (P_M \otimes P_S) \mathsf{TP}^{\dagger} \otimes P_C)$.\\
    ${\mathsf{cMPC}}$ decrypts the measurement result $(r'_z, r'_x, r'_c) \leftarrow (r_z, r_x, r_c) \oplus (s_z, s_x, s_c)$.\\
    ${\mathsf{cMPC}}$ parses $\tilde{E}^{\dagger} \ensuremath{X}^{r'_x} \ensuremath{Z}^{r'_z} \tilde{E} \in \mathscr{P}_{\ensuremath{1}} %{\ensuremath{m}+t}$ into $P_\mu \otimes P_\tau$ where $P_\mu \in \mathscr{P}_{\ensuremath{1}} %{\ensuremath{m}}$ and $P_\tau \in \mathscr{P}_{t}$.
    \\
    If $r'_c \neq x(P_\tau)$, ${\mathsf{cMPC}}$ publicly outputs $\mathsf{P_{s}}$ and all parties abort to $\mathsf{P_{s}}$.\\
    ${\mathsf{cMPC}}$ sends the correction Pauli $P' = P_R E' (P_\mu \otimes \identity_t) E'^\dag$ to $\mathsf{P_{r}}$.

\end{enumerate}

{\bf Output:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item $\mathsf{P_{r}}$ outputs $\sigma' = P'^\dag \cdot \mathcal{R}$.
    \item ${\mathsf{cMPC}}$ outputs $E'$.
\end{enumerate}
\end{protocol}

\subsection{Security}\label{sec:AQA-security}

\begin{lemma}\label{lemma:aqa}
For every non-uniform ({\sc qpt}\xspace) adversary ${\mathcal{A}}$ corrupting player set $I$, there is a non-uniform ({\sc qpt}\xspace) adversary $\mathsf{Sim}_{\mathcal{A}}$ corrupting $I$, such that for any states $\rho, \rho_{{\mathsf{aux}}}$,
\begin{align*}
    \{{\mathsf{Real}}^{\Pi^{\mathsf{AQA}} \circ \Sigma^{\mathsf{AQA}}}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}(1^{\secparam}, E, \rho) | E \leftarrow \mathscr{C}_{\ensuremath{1}} %{\ensuremath{m}+t} \} \approx \{{\mathsf{Ideal}}^{\mathsf{AQA}}_{\mathsf{Sim}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}}(1^{\secparam}, E, \rho)| E \leftarrow \mathscr{C}_{\ensuremath{1}} %{\ensuremath{m}+t} \}
\end{align*}
\end{lemma}

We split the security argument of our AQA protocol into two parts. In the first part, we analyze for any adversary the final state of the real protocol. In the second part, we show for any adversary a simulator that produces an indistinguishable final state. Our simulation technique is similar to that of \cite{BW16}.

\paragraph{Analysis of the Real World}
The following analysis will hold for every $E'$.
Denote by $(\gray{M, S, C, R, W})$ the registers that are used to store $(\sigma, \mathcal{S}, \mathcal{C}, \mathcal{R}, \rho_{{\mathsf{aux}}})$. In the most general case, the adversary has access to all these registers. Without loss of generality, it suffices to consider attacks that happen in protocol step 1 of the form $\onreg{\mathsf{\Pi}}{M,S,C} \onreg{A}{M,S,C,R,W} \onreg{\mathsf{TP}}{M,S}$ for some completely positive map $A: \rho \mapsto A\rho A^\dag$. After the attack is applied, ${\mathsf{cMPC}}$ learns the values $(r_z, r_x, r_c)$ stored in $(\gray{M,S,C})$ and decides whether to abort the sender. We analyze the final state when ${\mathsf{cMPC}}$ does not abort the sender as follows. First, we simplify the state before attack $A$ is applied.
\begin{equation}\label{AQA:Analysis-step1}
\begin{aligned}[b]
&\onreg{\mathsf{TP}}{M,S}  \cdot (\sigma, \mathcal{S}, \mathcal{C}, \mathcal{R})
\\
= & \onreg{\mathsf{TP}}{M,S} \onreg{P_M}{M} \onreg{P_S}{S} \onreg{P_C}{C} \onreg{P_R E'}{R} \onreg{\pi}{C,R} \cdot ( \onreg{ \tilde{E} \cdot (\rho \otimes 0^t) }{M}, \onreg{e_S}{S}, \onreg{((\tilde{E}^{\dagger} \cdot e_R) \otimes 0^t)}{C,R})
\\
= & \onreg{P}{M,S,C} \onreg{P_R E'}{R} \onreg{\pi}{C,R} \onreg{\mathsf{TP}}{M,S}\cdot ( \onreg{ \tilde{E} \cdot (\rho \otimes 0^t) }{M}, \onreg{e_S}{S}, \onreg{((\tilde{E}^{\dagger} \cdot e_R) \otimes 0^t)}{C,R})
\end{aligned}
\end{equation}
where $\onreg{\pi}{C,R}$ is the operation that exchanges the
first qubit with the following $t$ qubits, {i.e.,\ } $(\mu , \tau, \xi) \mapsto (\tau, \mu, \xi)$ for $\mu \in \Den{\ensuremath{1}} %{\ensuremath{m}}$ and $\tau \in \Den{t}$.
The Pauli $\onreg{P}{M,S,C}$ in (\ref{AQA:Analysis-step1}) is the conjugation of $\onreg{P_M}{M} \onreg{P_S}{S} \onreg{P_C}{C}$ by the Clifford operation $\onreg{\mathsf{TP}}{M,S}$. Then we expand the teleportation operator in (\ref{AQA:Analysis-step1}) as
\begin{align*}
& \onreg{\mathsf{TP}}{M,S} \cdot ( \onreg{ \tilde{E} \cdot (\rho \otimes 0^t) }{M}, \onreg{e_S}{S}, \onreg{((\tilde{E}^{\dagger} \cdot e_R) \otimes 0^t)}{C,R})
\\
= & \frac{1}{2^N}\underset{\alpha, \beta, \alpha', \beta'}{\Sigma} \onreg{\ket{\beta}\bra{\beta'}}{M} \otimes \onreg{\ket{\alpha}\bra{\alpha'}}{S} \otimes \onreg{(( \tilde{E}^{\dagger} \ensuremath{X}^\alpha \ensuremath{Z}^\beta \tilde{E} (\rho \otimes 0^t) \tilde{E}^{\dagger} \ensuremath{Z}^{\beta'} \ensuremath{X}^{\alpha'} \tilde{E} ) \otimes 0^t)}{C,R}
\end{align*}
where $N = 2(\ensuremath{1}} %{\ensuremath{m}+t)$ . To ease notation, we will write $\delta = (\beta, \alpha)$ and define the Pauli $P_{\tilde{E},\delta} = (\tilde{E}^{\dagger} \ensuremath{X}^\alpha \ensuremath{Z}^\beta \tilde{E})[\ensuremath{1}} %{\ensuremath{m}]$ as the first
component of the conjugated Pauli and the bit string $L_{\tilde{E},\delta} = x(\tilde{E}^{\dagger} \ensuremath{X}^\alpha \ensuremath{Z}^\beta \tilde{E})[\ensuremath{1}} %{\ensuremath{m}:]$ as the $x$-coordinate of the remaining components of the conjugated Pauli. Now the state can be written as
\begin{align*}
\frac{1}{2^N}\underset{\delta, \delta'}{\Sigma} \onreg{\ket{\delta} \bra{\delta'}}{M,S} \otimes \onreg{( P_{\tilde{E},\delta} (\rho) P_{\tilde{E},\delta'}^\dag \otimes \ket{L_{\tilde{E},\delta}}\bra{L_{\tilde{E},\delta'}} \otimes 0^t)}{C,R}
\end{align*}
and (\ref{AQA:Analysis-step1}) becomes
\begin{equation}
\begin{aligned}[b]
& \onreg{P}{M,S,C} \onreg{P_R E'}{R} \onreg{\pi}{C,R} \cdot (\frac{1}{2^N}\underset{\delta, \delta'}{\Sigma} \onreg{\ket{\delta} \bra{\delta'}}{M,S} \otimes \onreg{( P_{\tilde{E},\delta} (\rho) P_{\tilde{E},\delta'}^\dag \otimes \ket{L_{\tilde{E},\delta}}\bra{L_{\tilde{E},\delta'}} \otimes 0^t)}{C,R})
\\
& = \onreg{P}{M,S,C} \cdot  (\frac{1}{2^N}\underset{\delta, \delta'}{\Sigma} \onreg{\ket{\delta} \bra{\delta'}}{M,S} \otimes \onreg{\ket{L_{\tilde{E},\delta}}\bra{L_{\tilde{E},\delta'}}}{C} \otimes \onreg{P_R E'\cdot(P_{\tilde{E},\delta} (\rho) P_{\tilde{E},\delta'}^\dag \otimes 0^t)}{R})\\
& = \onreg{P}{M,S,C} \cdot  (\frac{1}{2^N}\underset{\delta, \delta'}{\Sigma} \onreg{\ket{L^*_{\tilde{E}}(\delta)} \bra{L^*_{\tilde{E}}(\delta')}}{M,S,C} \otimes \onreg{\tilde{\sigma}_{\delta, \delta'}}{R}) \label{AQA:Analysis-step2}
\end{aligned}
\end{equation}
\ifdefined\Thirty
The last equality is simplified using the abbreviation $L^*_{\tilde{E}}(\delta) = (\delta, L_{\tilde{E},\delta})$ and $\onreg{\tilde{\sigma}_{\delta, \delta'}}{R,W} = \onreg{(P_R E'\cdot(P_{\tilde{E},\delta} (\rho) P_{\tilde{E},\delta'}^\dag \otimes 0^t))}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W}$.
\else
The last equality is simplified using the abbreviation $L^*_{\tilde{E}}(\delta) = (\delta, L_{\tilde{E},\delta})$ as the concatenated string and $\onreg{\tilde{\sigma}_{\delta, \delta'}}{R,W} = \onreg{(P_R E'\cdot(P_{\tilde{E},\delta} (\rho) P_{\tilde{E},\delta'}^\dag \otimes 0^t))}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W}$ as the state in registers $(\gray{R,W})$.
\fi
Below, denote $\gray{\tilde{S}}$ as the union of registers $(M,S,C)$.
Now we expand $\onreg{P}{\tilde{S}} = \onreg{(\ensuremath{Z}^{b} \ensuremath{X}^{a})}{\tilde{S}}$
and decompose the attack \ifdefined\Thirty $A$ as \fi
$\onreg{A}{\tilde{S},R,W} = \underset{x}{\Sigma} \text{ } \onreg{A_x}{\tilde{S},R,W} (\onreg{\ensuremath{X}^x}{\tilde{S}} \otimes \onreg{\identity}{R,W})$ where $\onreg{A_x}{\tilde{S},R,W} = \underset{z}{\Sigma} \text{ } \onreg{\ensuremath{Z}^{z}}{\tilde{S}}\otimes \onreg{A_{x,z}}{R,W}$. Then from (\ref{AQA:Analysis-step2}),
\begin{align*}
& \onreg{\mathsf{\Pi}}{\tilde{S}} \onreg{A}{\tilde{S},R,W} \onreg{\mathsf{TP}}{M,S} \cdot (\sigma, \mathcal{S}, \mathcal{C}, \mathcal{R}, \rho_{{\mathsf{aux}}})
\\
= & \onreg{\mathsf{\Pi}}{\tilde{S}} \onreg{A}{\tilde{S},R,W} \onreg{P}{\tilde{S}} \cdot  (\frac{1}{2^N}\underset{\delta, \delta'}{\Sigma} \onreg{\ket{L^*_{\tilde{E}}(\delta)} \bra{L^*_{\tilde{E}}(\delta')}}{\tilde{S}} \otimes \onreg{\tilde{\sigma}_{\delta, \delta'}}{R,W})
\\
= & \onreg{\mathsf{\Pi}}{\tilde{S}} \frac{1}{2^N} \underset{x,x'}{\Sigma} A_{x} \onreg{(\ensuremath{X}^{x} \ensuremath{Z}^b \ensuremath{X}^{a})}{\tilde{S}} \big( \underset{\delta, \delta'}{\Sigma} \onreg{{\ket{L^*_{\tilde{E}}(\delta)} \bra{L^*_{\tilde{E}}(\delta')}}}{\tilde{S}} \otimes \onreg{\tilde{\sigma}_{\delta, \delta'}}{R,W} \big) \onreg{(\ensuremath{X}^{a} \ensuremath{Z}^b \ensuremath{X}^{x'})}{\tilde{S}}  A_{x'}^\dagger{}
\\
= & \onreg{\mathsf{\Pi}}{\tilde{S}} \frac{1}{2^N} \underset{x,x'}{\Sigma} \underset{\delta, \delta'}{\Sigma} {(-1)}^{\inner{b, x\oplus x'}} \onreg{\ensuremath{Z}^b}{\tilde{S}} A_{x} \big( {\ket{L^*_{\tilde{E}}(\delta) \oplus x \oplus a} \bra{L^*_{\tilde{E}}(\delta') \oplus x' \oplus a)}} \otimes {\tilde{\sigma}_{\delta, \delta'}} \big) {A}_{x'}^\dagger{} \onreg{\ensuremath{Z}^b}{\tilde{S}}
\end{align*}
The $\ensuremath{Z}^b$ operator takes no effect right before measurement. Moreover, if $m$ is the measurement result on registers $\tilde{S}$ and that $m$ passes ${\mathsf{cMPC}}$'s test, we have $m \oplus a \in \textsc{Range}(L^*_{\tilde{E}})$. Then $x = L^*_{\tilde{E}}(\delta) \oplus a \oplus m \in \textsc{Range}(L^*_{\tilde{E}})$ since $L^*_{\tilde{E}}$ is a linear function. The post-measurement state when passing ${\mathsf{cMPC}}$'s test becomes
\begin{align*} \frac{1}{2^N} \underset{y,x,x' \in \textsc{Range}(L^*_{\tilde{E}})}{\Sigma} {(-1)}^{\inner{b, x\oplus x'}} \onreg{A_{x}}{\tilde{S},R,W} \big( \onreg{\ketbra{y \oplus a}}{\tilde{S}} \otimes \onreg{{\tilde{\sigma}_{\delta, \delta'}}}{R,W} \big) \onreg{{A}_{x'}^\dagger{}}{\tilde{S},R,W}
\end{align*}
where $\delta, \delta'$ are the initial $N$ bits of $(x\oplus y), (x' \oplus y)$. Next, ${\mathsf{cMPC}}$ discards the information of $P$ {i.e.,\ } taking $\underset{P}{\mathbb{E}}[\cdot]$ on the state. We first take $\underset{b}{\mathbb{E}}[\cdot]$ to get
\begin{align*}
\frac{1}{2^N} \underset{y,x \in \textsc{Range}(L^*_{\tilde{E}})}{\Sigma} \onreg{A_{x}}{\tilde{S},R,W} \big( \onreg{\ketbra{y \oplus a}}{\tilde{S}} \otimes \onreg{{\tilde{\sigma}_{\delta, \delta}}}{R,W} \big) \onreg{{A}_{x}^\dagger{}}{\tilde{S},R,W}
\end{align*}
Then we take $\underset{a}{\mathbb{E}}[\cdot]$ to get
\begin{align*}
& \frac{1}{2^N} \underset{y,x \in \textsc{Range}(L^*_{\tilde{E}})}{\Sigma} \onreg{A_{x}}{\tilde{S},R,W} \big( \onreg{(\frac{\mathbbm{1}}{2})^{\otimes (N+t)}}{\tilde{S}} \otimes \onreg{{\tilde{\sigma}_{\delta, \delta}}}{R,W} \big) \onreg{{A}_{x}^\dagger{}}{\tilde{S},R,W}
\\
=& \underset{\delta}{\mathbb{E}} \big[ \underset{x \in \textsc{Range}(L^*_{\tilde{E}})}{\Sigma} \onreg{A_{x}}{\tilde{S},R,W} \big( \onreg{(\frac{\mathbbm{1}}{2})^{\otimes (N+t)}}{\tilde{S}} \otimes \onreg{{\tilde{\sigma}_{\delta, \delta}}}{R,W} \big) \onreg{{A}_{x}^\dagger{}}{\tilde{S},R,W} \big]
\end{align*}
Finally, ${\mathsf{cMPC}}$ discards extra information of $\tilde{E}, P_R$ except for the \ifdefined\FullVersion correction \fi Pauli operator $P_R E' (P_{\tilde{E},(m \oplus a)[:N]} \otimes \identity^t)E'^\dag = P_R E' (P_{\tilde{E},\delta \oplus x[:N]} \otimes \identity^t)E'^\dag$, which we denote as $P'_{\tilde{E}, \delta, x}$. Augmented with this last message from ${\mathsf{cMPC}}$ in $\gray{O}$, the end state is
\begin{equation}
\begin{aligned}[b]
& \underset{\tilde{E}, P_R,\delta}{\mathbb{E}} \text{ } \big[ \underset{x \in \textsc{Range}(L^*_{\tilde{E}})}{\Sigma} \onreg{A_{x}}{\tilde{S},R,W} \big( \onreg{(\frac{\mathbbm{1}}{2})^{\otimes (N+t)}}{\tilde{S}} \otimes \onreg{{\tilde{\sigma}_{\delta, \delta}}}{R,W} \big) \onreg{{A}_{x}^\dagger{}}{\tilde{S},R,W} \otimes \onreg{\ketbra{P'_{\tilde{E},\delta,x}}}{O} \big]
\\
= & \bigg( \underset{x=0}{\Sigma} \text{ } \underset{\tilde{E}}{\mathbb{E}} \text{ } (\cdots)\bigg) + \bigg(\underset{x: \text{ }x[:N] \neq 0}{\Sigma} \operatorname{negl}(t) \text{ } \text{ } \underset{\tilde{E}: \text{ } x \in \textsc{Range}(L^*_{\tilde{E}})}{\mathbb{E}} (\cdots)\bigg)
\label{eq:aqa-proof-split}
\end{aligned}
\end{equation}
We split it into a sum of terms corresponding to different values of $x$. The expression uses the fact that $0 \in \textsc{Range}(L^*_{\tilde{E}})$ for every $\tilde{E}$, and that every non-zero value of $x$ has only negligible probability over $\tilde{E}$ of lying in $\textsc{Range}(L^*_{\tilde{E}})$ (lemma 3.4 in \cite{CliffordCodes}). As the second parenthesis is negligible, the end state is indistinguishable from the first term:
\begin{equation}
\begin{aligned}[b]
\approx & \underset{\tilde{E}, P_R, \delta}{\mathbb{E}} \text{ } \big[  A_{0} \big( \onreg{(\frac{\mathbbm{1}}{2})^{\otimes (N+t)}{}}{\tilde{S}} \otimes \onreg{P_R E' \cdot ((P_{\tilde{E},\delta} \cdot \rho) \otimes 0^t)}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W} \big) {A}_{0}^\dagger{} \otimes \onreg{\ketbra{P'_{\tilde{E},\delta,0}}}{O} \big]
\\
= & \underset{P' \in \mathscr{P}_{\ensuremath{1}} %{\ensuremath{m}+t}}{\mathbb{E}} \text{ } \big[ A_{0} \big( \onreg{(\frac{\mathbbm{1}}{2})^{\otimes (N+t)}{}}{\tilde{S}} \otimes \onreg{P' E' \cdot (\rho \otimes 0^t)}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W} \big) {A}_{0}^\dagger{} \otimes \onreg{\ketbra{P'}}{O} \big] \label{AQA:Analysis-step-end}
\end{aligned}
\end{equation}

On the other hand, the protocol aborts when an adversary chooses to abort ${\mathsf{cMPC}}$, or an adversarial sender fails the test. In these cases, the quantum one-time pad $P_R$ on register $\gray{R}$ is never handed out, so $\gray{R}$ stays maximally mixed. The end state is indistinguishable from
$A \big( \onreg{(\frac{\mathbbm{1}}{2})^{\otimes (N+t)}{}}{\tilde{S}} \otimes \onreg{(\frac{\mathbbm{1}}{2})^{\otimes(\ensuremath{1}} %{\ensuremath{m}+t)}}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W} \big) {A}^\dagger$ for the former \ifdefined\Thirty case \fi and $\underset{x \neq 0}{\Sigma} A_{x} \big( \onreg{(\frac{\mathbbm{1}}{2})^{\otimes (N+t)}{}}{\tilde{S}} \otimes \onreg{(\frac{\mathbbm{1}}{2})^{\otimes(\ensuremath{1}} %{\ensuremath{m}+t)}}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W} \big) {A}_{x}^\dagger$ for the \ifdefined\Thirty latter. \else latter case. \fi

\paragraph{Simulating the Real World}

The simulator for an adversary that corrupts both the sender and the receiver is as follows. The other cases follow similarly.

\begin{simulator}{$\mathsf{Sim}^{\mathsf{AQA}}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}$ for AQA}\label{sim:aqa}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item Input: $\sigma = E\cdot(\rho \otimes 0^t)$
    \item Create EPR pair $(\tilde{e}_S,\tilde{e}_R)$ of size $(N+t)$. Send $(\onreg{\mathsf{TP}^\dag}{M,S}\cdot \onreg{\tilde{e}_S}{M,S,C})$ to sender.\\
    Create EPR pair $(\hat{e}_S, \hat{e}_R)$ of size $(\ensuremath{1}} %{\ensuremath{m}+t)$. Send $\onreg{\hat{e}_R}{R}$ to receiver.
    \item Receive the measurement results $r = (r_z, r_x, r_c)$ from the sender.\\
    Measure $\tilde{e}_R$ and compare the measurement result $\tilde{r} \leftarrow \mathsf{\Pi} (\tilde{e}_R)$ with $r$.
    \item Invoke ideal functionality: \\
    If $\tilde{r} = r$, send $\sigma$ to $\mathsf{T}$.
    Otherwise, send $\bot$ to $\mathsf{T}$.
    \item Output recovery:\\
    Upon receiving $\sigma'$ from $\mathsf{T}$, teleport $\sigma'$ into $\hat{e}_S$.\\
    Send $(z,x) \leftarrow \mathsf{TP.Send}(\sigma', \hat{e}_S)$ to the receiver.
    \item Output: the final output of ${\mathcal{A}}$.
\end{enumerate}
\end{simulator}

Consider again the attack $\onreg{\mathsf{\Pi}}{\tilde{S}} \onreg{A}{\tilde{S},R,W} \onreg{\mathsf{TP}}{M,S}$ on $(\onreg{\mathsf{TP}^\dag}{M,S}\cdot \onreg{\tilde{e}_S}{M,S,C}, \onreg{\hat{e}_R}{R}, \onreg{\rho_{{\mathsf{aux}}}}{W})$, where $\onreg{A}{\tilde{S},R,W} = \underset{x}{\Sigma} \text{ } \onreg{A_{x}}{\tilde{S},R,W} \onreg{\ensuremath{X}^{x}}{\tilde{S}}$. The resulting state together with $\tilde{r}$ is
\begin{align*}
& \onreg{\mathsf{\Pi}}{\tilde{S}} (\underset{x,x'}{\Sigma} \onreg{A_x}{\tilde{S},R,W}\onreg{\ensuremath{X}^x}{\tilde{S}} (\onreg{\tilde{e}_S}{\tilde{S}} \otimes \onreg{\hat{e}_R}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W}) \onreg{\ensuremath{X}^{x'}}{\tilde{S}} \onreg{A_{x'}^\dag}{\tilde{S},R,W}) \otimes \mathsf{\Pi}(\tilde{e}_R)
\\
= & \underset{\tilde{r}}{\mathbb{E}} \text{ } \big[ \underset{x}{\Sigma}\text{ }  \onreg{A_x}{\tilde{S},R,W} (\onreg{\ketbra{x+\tilde{r}}}{\tilde{S}} \otimes \onreg{\hat{e}_R}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W}) \onreg{A_{x}^\dag}{\tilde{S},R,W} \otimes \ketbra{\tilde{r}} \big]
\end{align*}
Conditioned on no abort so that $r = \tilde{r}$, the state of the adversary is
\begin{align*}
\onreg{A_0}{\tilde{S},R,W} (\onreg{(\frac{\mathbbm{1}}{2})^{N+t}}{\tilde{S}} \otimes \onreg{\hat{e}_R}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W}) \onreg{A_{0}^\dag}{\tilde{S},R,W}
\end{align*}
In this case, the simulator chooses to send $\sigma = E\cdot(\rho \otimes 0^t)$ to $\mathsf{T}$ and receives $\sigma' = E' \cdot (\rho \otimes 0^t)$ in return. After the simulator teleports $\sigma'$ through $\hat{e}_S$ and sends over the measurement result $(z,x)$ which defines the Pauli $P = \ensuremath{X}^x \ensuremath{Z}^z$, the state of the adversary becomes
\begin{align*}
\underset{P}{\mathbb{E}} \text{ }\big[ \onreg{A_0}{\tilde{S},R,W} (\onreg{(\frac{\mathbbm{1}}{2})^{N+t}{}}{\tilde{S}} \otimes \onreg{P E' \cdot (\rho \otimes 0^t)}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W}) \onreg{A_{0}^\dag}{\tilde{S},R,W} \otimes \onreg{\ketbra{P}}{O} \big]
\end{align*}
which is indistinguishable from (\ref{AQA:Analysis-step-end}). When there is an abort, $\gray{R}$ holds half an EPR pair with the other half unused throughout the simulation. Thus, $\gray{R}$ is maximally mixed, and the end states are again indistinguishable from the real world.

\subsection{Generalized Online Input}\label{sec:AQA-twist}
In protocol \ref{proto:aqa}, the sender's online input is a fresh ciphertext $\sigma = E \cdot (\rho \otimes 0^t)$. In our application, the ciphertext may come from a previous teleportation result where the attacker is partly involved.
To capture this case, we first introduce some notation describing quantum teleportation under attack \cite{Trapcode}. Suppose $(e_S, e_R)$ is an EPR pair of length $n$, and a unitary map $A = \underset{P_M, P_S}{\Sigma} \onreg{P_M}{M} \otimes \onreg{P_S}{S} \otimes \onreg{A_{P_M,P_S}}{R}$, decomposed in the Pauli basis, is applied on $(\onreg{\psi}{M}, \onreg{e_S}{S}, F(\onreg{e_R}{R}))$ right before the normal teleportation algorithm $\mathsf{TP.Send}$.
\ifdefined\Thirty
The resulting state can be expanded as
$
\frac{1}{2^n} \underset{\begin{smallmatrix} z, P_M, P_S\\ x, P'_M, P'_S \end{smallmatrix}}{\Sigma} \onreg{\ketbra{z}}{M}\otimes \onreg{\ketbra{x}}{S}\otimes A_{P_M, P_S}(F(\onreg{P^\dag_S (\ensuremath{X}^x \ensuremath{Z}^z) P_M \psi P'^\dag_M (\ensuremath{X}^x \ensuremath{Z}^z)^\dag P'_S}{R})) A_{P'_M,P'_S}^\dag.
$
\else
The resulting state becomes
$$
\frac{1}{2^n} \underset{\begin{smallmatrix} z, P_M, P_S\\ x, P'_M, P'_S \end{smallmatrix}}{\Sigma} \onreg{\ketbra{z}}{M}\otimes \onreg{\ketbra{x}}{S}\otimes A_{P_M, P_S}(F(\onreg{P^\dag_S (\ensuremath{X}^x \ensuremath{Z}^z) P_M \psi P'^\dag_M (\ensuremath{X}^x \ensuremath{Z}^z)^\dag P'_S}{R})) A_{P'_M,P'_S}^\dag
$$
\fi
We make the following abbreviation.
\begin{equation}
\begin{aligned}[b]
\Delta &:= (z,x,P_M,P_S,P'_M,P'_S)\\
\psi^{\Delta^*} &:= P^\dag_S (\ensuremath{X}^x \ensuremath{Z}^z) P_M \psi P'^\dag_M (\ensuremath{X}^x \ensuremath{Z}^z)^\dag P'_S\\
\psi^\Delta &:= (\ensuremath{X}^x \ensuremath{Z}^z)^\dag \psi^{\Delta^*} (\ensuremath{X}^x \ensuremath{Z}^z)\\
A^{\Delta^*}(\psi \text{ }; F(\cdot)&):= \frac{1}{2^n} \text{ } \underset{\Delta}{\Sigma} \text{ } \onreg{\ketbra{z}}{M}\otimes \onreg{\ketbra{x}}{S}\otimes A_{P_M, P_S}(F(\onreg{\psi^{\Delta^*}}{R})) A_{P'_M,P'_S}^\dag \\
A^{\Delta} (\psi \text{ }; F(\cdot)) &:= \frac{1}{2^n} \text{ } \underset{\Delta}{\Sigma} \text{ } \onreg{\ketbra{z}}{M}\otimes \onreg{\ketbra{x}}{S}\otimes A_{z,x,P_M, P_S}(F(\onreg{\psi^\Delta}{R})) A_{z,x,P'_M,P'_S}^\dag
\label{abbrev:teleport}
\end{aligned}
\end{equation}
where $A_{z,x,P_M,P_S}$ is the conjugation of $A_{P_M,P_S}$ by $F$ and $\ensuremath{X}^x \ensuremath{Z}^z$. The notations $A^{\Delta^*}, A^\Delta$ are useful for representing the teleportation result under attack $A$.

In the general case, we allow the sender's initial offline and online state to take the form $A^{\Delta}(\rho \text{ }; (E\cdot(\cdot, 0), \mathcal{S},\mathcal{C},\mathcal{R}, \rho_{\mathsf{aux}}))$ instead of $E\cdot(\rho,0)$, where $\rho, \rho_{{\mathsf{aux}}}$ are inputs independent of the preprocessing data $(E,\mathcal{S},\mathcal{C},\mathcal{R})$ and $A$ is any attack. Sections \ref{sec:AQA-protocol}, \ref{sec:AQA-security} correspond to the case $A= \mathbbm{1}$. For an arbitrary $A$, the security guarantee can be reformulated as indistinguishability between the following two hybrids. In hybrid $1$, the simulator teleports $\sigma$ to ${\mathcal{A}}$ and then ${\mathcal{A}}$, who now holds $A^{\Delta}(\rho \text{ }; (E\cdot(\cdot, 0), \mathcal{S},\mathcal{C},\mathcal{R}, \rho_{\mathsf{aux}}))$, runs $\Pi^\mathsf{AQA}$. In hybrid $2$, the simulator sends $\sigma$ to the ideal functionality and simulates the adversary with $\mathsf{Sim}^\mathsf{AQA}$.

\begin{multicols}{2}
\begin{framed}
\centerline{Hybrid $1$}\hrule
\begin{enumerate}[leftmargin=*]
    \item Input:
    \begin{itemize}[leftmargin=*]
        \item ${\mathcal{A}}$: $A^{\Delta}(\rho \text{ }; (e_R, \mathcal{S},\mathcal{C},\mathcal{R}, \rho_{\mathsf{aux}}))$
        \item $\mathsf{Sim}$: $\sigma= E\cdot(\rho^\Delta \otimes 0^t), e_S$
    \end{itemize}
    \item $\mathsf{Sim}$ runs $\mathsf{TP.Send}(\sigma, e_S)$ and sends the result $(z,x)$ to ${\mathcal{A}}$
    \item ${\mathcal{A}}$ runs $\Pi^\mathsf{AQA}$ using ${\mathsf{cMPC}}$
\end{enumerate}
\end{framed}
\begin{framed}
\centerline{Hybrid $2$}\hrule
\begin{enumerate}[leftmargin=*]
    \item Input:
    \begin{itemize}[leftmargin=*]
        \item ${\mathcal{A}}$: $A^{\Delta}(\rho \text{ }; (\hat{e}_R, \mathsf{TP}^\dag\cdot\tilde{e}_S, \rho_{\mathsf{aux}}))$
        \item $\mathsf{Sim}$: $\sigma= E\cdot(\rho^\Delta \otimes 0^t), \hat{e}_S, \tilde{e}_R$
    \end{itemize}
    \item[\label={}]
    \item $\mathsf{Sim}$ runs $\mathsf{Sim}^{\mathsf{AQA}}_{\mathcal{A}}$ using ${\mathsf{Ideal}}^{\mathsf{AQA}}$\\
\end{enumerate}
\end{framed}
\end{multicols}

The security proof is the same as \cref{lemma:aqa} once we write $A^\Delta$ back in its original form in (\ref{abbrev:teleport}). The only change is to replace $\rho$ with $\rho^\Delta$. When no abort happens, both hybrids end in the state $A'^{\Delta}(\rho \text{ }; E'\cdot(\cdot))$ for some $A'$ that depends only on $A$, ${\mathcal{A}}$, and the random Pauli that ${\mathcal{A}}$ receives at the end of the hybrids. In case of an abort, both hybrids end in the state $A'^{\Delta}(\rho \text{ }; \mathcal{T}_{\mathscr{P}}(\cdot))$ instead.

\subsection{Compatibility of Quantum Authentication Code}

We have already seen AQA in Clifford-code form above. In general, our AQA can be realized under a variety of quantum authentication codes as long as the following criteria are met:
\begin{itemize}
\item The encoding procedure takes the form $\rho \mapsto E \cdot (\rho \otimes 0^\lambda)$ for some Clifford $E$.
\item There is a decoding procedure that performs $E^\dag$, measures part of the ancilla, and determines authenticity from the measurement result. Then apply a Clifford $D$ on the remaining qubits and trace out all ancilla to recover $\rho$.
\end{itemize}
Requiring $E, D$ to be Clifford gates are essential because we have to change their order with quantum teleportation and quantum one-time pad, both of which produce Pauli operators. The security proof of \cref{lemma:aqa} are mostly independent of the underlying authentication scheme. The only place where we explicitly relied on Clifford code is in equation (\ref{eq:aqa-proof-split}), which is exactly the property that makes Clifford code a secure quantum authentication code. One can make corresponding modifications to that part of the proof for other authentication codes. Below we demonstrate the Trap code form AQA as an example.

\paragraph{AQA in Trap Code Form} \label{Sec:AQATP}

Suppose QECC encodes $1$ qubit into $t$ qubits and corrects $d$ errors. Trap code meets the criteria with $\lambda=3t-1$, $E = (\ensuremath{X}^x \ensuremath{Z}^z \pi) \circ (\mathsf{QECC} \otimes \identity^t \otimes \ensuremath{H}^t)$, and $D = \mathsf{QECC.Dec} \circ \mathsf{QECC}$. Initially, the trusted setup prepares an EPR pair $(e_S, e_R)$ of length $3t$, pretends $e_R$ to be a Trap code codeword, and applies $D \circ E^\dag$ to $e_R$, Denote the result as $(\mu, \alpha, \tau)$, where $\mu \in \Den{1}$ is the alleged message, $\alpha \in \Den{t-1}$ is the alleged ancilla for QECC, and $\tau \in \Den{2t}$ is the alleged traps. The trusted setup authenticates $\mu$ with fresh ancilla into the receiving portal, discards $\alpha$, and turns $\tau$ into the checking portal. In the online phase, classical MPC counts $u = || x(E^\dag \ensuremath{X}^{r'_x} \ensuremath{Z}^{r'_z} E) [t:] - r'_c ||_1$ as the difference between the expected and the actual bit-flips on traps. It chooses to abort the sender if $u \ge d$; otherwise, it calculates the correction Pauli for the receiving portal. It is the conjugation of $\ensuremath{X}^{r'_x} \ensuremath{Z}^{r'_z}$ by $E$ and $D$. For the security, note that some terms in equation (\ref{eq:aqa-proof-split}) becomes non-negligible. Still, all these terms satisfy $||x||_1 < d$ by the security of Trap code. The end state of the real world in acceptance is now indistinguishable from
$$
\underset{P}{\mathbb{E}} \text{ }\big[ \underset{||x||_1<d}{\Sigma} \onreg{A_x}{\tilde{S},R,W} (\onreg{(\frac{\mathbbm{1}}{2})^{N+t}{}}{\tilde{S}} \otimes \onreg{P E' \cdot (\rho \otimes 0^t)}{R} \otimes \onreg{\rho_{{\mathsf{aux}}}}{W}) \onreg{A_{x}^\dag}{\tilde{S},R,W} \otimes \onreg{\ketbra{P}}{O} \big]
$$
which can be simulated using a similar strategy to \cref{lemma:aqa} and \cite{BW16}.

\begin{figure}[H]
     \centering
     \scalebox{0.85}{
     $$
     \Qcircuit @C=1.3em @R=1.3em {
    &\quad&\quad&\quad&\lstick{\ket{0},\ket{+}} & {/^{2t}}\qw &\qw&\qw  &\qw&\multigate{2}{\ensuremath{X}^{x'} \ensuremath{Z}^{z'} \pi'}  & \qw \barrier{2}& \qw\\
    &\quad&\quad&\lstick{\ket{0}} &\qw & {/^{t-1}}\qw  & \qw &\qw  &\multigate{1}{{\mathsf{QECC.Enc}}}&\ghost{\ensuremath{X}^{x'} \ensuremath{Z}^{z'} \pi'}  & \qw& \qw\\
   \lstick{e_S} & {/^{3t}}\qw & \qw & \quad & \lstick{e_{R}} &\qw &\multigate{1}{(\ensuremath{X}^{x}\ensuremath{Z}^{z}\pi)^{-1}\mathsf{QECC.Dec}} & {/^1}\qw &\ghost{{\mathsf{QECC.Enc}}}&\ghost{\ensuremath{X}^{x'} \ensuremath{Z}^{z'} \pi'}\qw & \qw & \rstick{\sigma'}\qw\\
   \quad&\quad & \quad & \quad &  \quad&\quad& \ghost{\ensuremath{X}^{x}\ensuremath{Z}^{z}\pi)^{-1}\mathsf{QECC.Dec}} &\qw  &\qw {/^{2t}}  & \gate{P_C \text{ } \mathsf{CNOT}_r}\qw &\meter &\rstick{r_c}\qw
    \gategroup{1}{2}{4}{10}{.7em}{--}
    }
     $$}
     \caption{{\bf Auditable Quantum Authentication in Trap code form} }
    \label{fig:AQATP}
\end{figure}

\section{BoBW-MPQC-PVIA in the Preprocessing Model}\label{Sec:2PQC-PVIA}
In this section, we construct a best-of-both-worlds\xspace multi-party quantum computation protocol secure with public verifiable identifiable abort\xspace (BoBW-MPQC-PVIA) from the building block AQA under a trusted setup. We break down the whole protocol into three subsections. It is useful to define the following ideal world as an intermediate step towards ${\mathsf{Ideal}}^{\mathsf{MPQC}}$. Roughly speaking, the ideal world of redistributed quantum computation (RQC) also computes the circuit, but keeps the result distributed and encrypted across all parties.

\begin{idealmodel}{${\mathsf{Ideal}}^{\mathsf{RQC}}$: Ideal World of Redistributed Quantum Computation}\label{ideal:RQC}
	\begin{description}
	    \item[Common Input:]\quad\\
		The security parameter $1^{\secparam}$, the circuit $C$ with input size $(\ell_1, \cdots, \ell_n)$ and total quantum output size $\ell'$, the number of traps $t=t(\secparam)$ on each share, and the fault-tolerant threshold $\thres$.
		\item[Input:]\quad\\
		$\mathsf{P}_i$ holds a state $\rho_i \in \Den{\ell_i}$.

		\item[$\mathsf{T}$ receives inputs and performs computation]\quad\\
		Each party $\mathsf{P}_i$ sends some $\tilde{\rho}_i$ as input to $\mathsf{T}$. Honest parties choose $\tilde{\rho}_i = \rho_i$.\\
		$\mathsf{T}$ samples $\rho_{{\mathsf{anc}}}$ and computes $(\rho'_1, \cdots, \rho'_n, \rho'_{{\mathsf{anc}}}, r') = C(\tilde{\rho}_1, \cdots, \tilde{\rho}_n; \rho_{{\mathsf{anc}}})$.\\
		$\mathsf{T}$ encodes the output into $(s_1, \cdots, s_n) = {\mathsf{QECC.Enc}}(\rho'_1, \cdots, \rho'_n, \rho'_{{\mathsf{anc}}})$.\\
		$\mathsf{T}$ samples $E_j \leftarrow \mathscr{C}_{\ell'(\ensuremath{1}} %{\ensuremath{m}+t)}$ and creates ciphertext $\sigma_j = E_j (s_j \otimes 0^{\ell' t})$.

		\item[$\mathsf{T}$ sends encrypted shares to malicious parties
		]\quad\\
		$\mathsf{T}$ sends $\sigma_j$ to $\mathsf{P}_j \in I$.

		\item[$\mathsf{T}$ receives abort messages from malicious parties
		]\quad\\
		$\mathsf{T}$ initializes the identified corruption set $\normalfont{\texttt{Corr}} = \{\}$.\\
		Each $\mathsf{P}_j$ in $I$ can send $\normalfont{\texttt{abort}}$ message to $\mathsf{T}$.\\
		If so, $\mathsf{T}$ adds $\mathsf{P}_j$ to $\normalfont{\texttt{Corr}}$ and sets $E_j = \bot$.

		\item[$\mathsf{T}$ either aborts or sends encrypted shares to honest parties
		]\quad\\
		Once $|\normalfont{\texttt{Corr}}| > \thres$, $\mathsf{T}$ publicly aborts to all parties in $\normalfont{\texttt{Corr}}$.\\
		Otherwise, $\mathsf{T}$ sends $\sigma_j$ to $\mathsf{P}_j \not \in I$.

		\item[Output:]\quad\\
        $\mathsf{P}_1, \cdots, \mathsf{P}_n, \mathsf{O}$ output whatever they received from $\mathsf{T}$.\\
        $\mathsf{T}$ outputs $(E_1, \cdots, E_n)$ and $r'$ if there is no abort.\\
        ${\mathcal{A}}$ outputs its view.
	\end{description}
\end{idealmodel}

\subsection{Input Encoding and Ancilla Preparation}
The first stage of our protocol is input encoding (IE), which transforms all inputs and proper ancilla qubits into distributed and encrypted data. One can also view IE as a simplified RQC that computes the identity circuit $C = \identity$.

\ifdefined\Thirty
\else
Some previous works also use QECC and authentication codes for input encoding, but let us look closer into what is missing in their procedures. On the one hand, MPQC with an honest majority \cite{BCG06} only authenticates states under user-sampled keys, so the malicious parties have more control over their information. On the other hand, MPQC with a dishonest majority \cite{ACC+21} allows users to submit incorrect QECC codewords without consequences, which hinders transversal computation on the alleged codewords. Here, we can avoid these two issues at the same time.
\fi

Our preprocessing protocol for
\ifdefined\FullVersion IE \else  input encoding \fi
work as follows. For simplicity, we will use a QECC scheme that encodes every qubit into $n$ qubits. The trusted party performs QECC encoding, quantum authentication under secret keys, and quantum one-time pad on half EPR pair. Together with the other half EPR pair, they form the sending and receiving portals $\mathcal{S}_i ,\mathcal{R}_i$, which are given to the respective parties. In the online phase, party $\mathsf{P}_i$ can teleport its input $\rho_i$ through the sending portal $\mathcal{S}_i$ to fill in the contents of the receiving portals

\begin{protocol}{$(\Sigma^{\mathsf{IE}}, \Pi^{\mathsf{IE}})$ for Input Encoding}\label{proto:ie}
\centerline{
\textbf{Parameters:} $n, t, (\ell_1, \cdots, \ell_n), \ell_{{\mathsf{anc}}}, \ell'$}\\
{\bf Preprocessing $\Sigma^{\mathsf{IE}}$:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item For each $i \in [n]$, generate coordinate-wise EPR pair $(e_{S,i}, e_{R,i})$ of length $\ell_i$.\\
    Compute $(f_{i,1}, \cdots, f_{i,n}) \leftarrow {\mathsf{QECC.Enc}}(e_{R,i})$.
    \item Create auxiliary state $\phi_h \in \Den{\ell_{\mathsf{anc}}}$ consisting of ancilla and magic states.\\
    Compute $(f^{{\mathsf{anc}}}_{1}, \cdots, f^{{\mathsf{anc}}}_{n}) \leftarrow {\mathsf{QECC.Enc}}(\phi_h)$.
    \item Sample random Pauli $P_{j} \leftarrow \mathscr{P}_{\ell(\ensuremath{1}} %{\ensuremath{m}+t)}$ and random Clifford $E_{j} \leftarrow \mathscr{C}_{\ell(\ensuremath{1}} %{\ensuremath{m}+t)}$.\\
    Compute $\mathcal{R}_{j} = P_{j} E_{j} \cdot ((f_{1,j} \otimes 0^{\ell_1 t}) \otimes \cdots \otimes (f_{n,j} \otimes 0^{\ell_n t}) \otimes (f^{{\mathsf{anc}}}_{j} \otimes 0^{\ell_{\mathsf{anc}} t}))$.
    \item Send to $\mathsf{P}_i$ the sending portal $\mathcal{S}_i = e_{S,i}$ and the receiving portal $\mathcal{R}_{i}$.
    \item Send to ${\mathsf{cMPC}}$ the secret $\{P_{j}, E_{j}\}_{j \in [n]}$.
\end{enumerate}

\textbf{Online Input:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}

    \item Each $\mathsf{P}_i$ holds private input $\rho_i \in \Den{\ell_i}$.
\end{enumerate}
\textbf{Protocol $\Pi^{\mathsf{IE}}$:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item $\mathsf{P}$ teleports $\rho_i$ via sending portal $\mathcal{S}_i$.\\
    $\mathsf{P}$ then sends $(z_i, x_i) \leftarrow \mathsf{TP.Send}(\rho_i, \mathcal{S}_i)$ to ${\mathsf{cMPC}}$.
    \item ${\mathsf{cMPC}}$ computes $P'_{i,1} \otimes \cdots \otimes P'_{i,n} = \mathsf{QECC} (\ensuremath{X}^{x_i} \ensuremath{Z}^{z_i} \otimes \identity^{(n-1)\ell_i}) \mathsf{QECC}^\dag$.\\
    ${\mathsf{cMPC}}$ computes $P''_j = P_j E_{j} \big((P'_{1,j} \otimes \identity^{\ell_1 t}) \otimes \cdots \otimes (P'_{n,j} \otimes \identity^{\ell_n t}) \otimes \identity^{\ell_{{\mathsf{aux}}}(1+t)} \big) E_j^\dag$.\\
    ${\mathsf{cMPC}}$ sends the swapped out correction Pauli $P''_j$ to $\mathsf{P}_j$ for $j \in [n]$.
\end{enumerate}
\textbf{Output:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item $\mathsf{P}_j$ outputs $\sigma_j = P''^{\dag}_j \mathcal{R}_j$ for $j \in [n]$.
    \item ${\mathsf{cMPC}}$ outputs $\{E_j\}_{j \in [n]}$.
\end{enumerate}
\end{protocol}

The input encoding protocol realizes the task of redistributed quantum computation for the identity circuit $C = \identity$. Below we analyze the end state of the real protocol, and postpone its simulation to the next section.
\ifdefined\Thirty
\else

\begin{lemma}\label{lemma:ie}
For every non-uniform ({\sc qpt}\xspace) adversary ${\mathcal{A}}_I$ corrupting $I$, there is a non-uniform ({\sc qpt}\xspace) simulator $\mathsf{Sim}_{{\mathcal{A}}_I}$ corrupting $I$, such that for any states $\rho_1, \cdots, \rho_n, \rho_{{\mathsf{aux}}}$,
\begin{align}
    \{{\mathsf{Real}}^{\Pi^{\mathsf{IE}} \circ \Sigma^{\mathsf{IE}}}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}(1^{\secparam}, \rho_1, \cdots, \rho_n) \} \approx \{{\mathsf{Ideal}}^{\mathsf{RQC}}_{\mathsf{Sim}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}}(1^{\secparam}, \identity, \rho_1, \cdots, \rho_n) \}
\end{align}
\end{lemma}
It suffices to consider attacks on the protocol that happen in protocol step $1$.
\fi
Say registers $(\gray{S_i, R_j, I_i, W, O_j})$ store $(\mathcal{S}_i,\mathcal{R}_j, \rho_i, \rho_{{\mathsf{aux}}}, P''_j)$ respectively. We can always rewrite the attack as $(\mathsf{TP.Send} \circ A)$ for some unitary map $A$.
Using the abbreviation of (\ref{abbrev:teleport}), the end state of the real protocol is
\begin{equation}
\begin{aligned}[b]
& A^{\Delta^*} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes} P_j E_j)  ({\mathsf{QECC.Enc}}(\cdot, \phi_h), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)\\
= & A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}P''_j E_j )  ({\mathsf{QECC.Enc}}(\cdot, \phi_h), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\label{eq:ie-real-world}
\end{aligned}
\end{equation}
\ifdefined\Thirty
\else

The real protocol can be simulated with the following simulator.
\begin{simulator}{$\mathsf{Sim}^{\mathsf{IE}}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}$ for Input Encoding}
\begin{enumerate}
    \setlength{\itemsep}{1pt}    \item Create EPR pair $(\onreg{\tilde{e}_{S_i}}{S_i},\onreg{\tilde{e}_{R,i}}{R'_i})$ of size $\ell_i$.\\ Send $\tilde{e}_S$ in register $\gray{S_i}$ to party $\mathsf{P}_i$ for $i \in [n]$.
    \item Create EPR pair $(\hat{e}_{S,j}, \onreg{\hat{e}_{R,j}}{R_j})$ of size $\ell(\ensuremath{1}} %{\ensuremath{m}+t)$, and sample $\hat{P}_j \leftarrow \mathscr{P}_{\ell(\ensuremath{1}} %{\ensuremath{m}+t)}$.\\
    Send $\hat{P}_j \cdot \hat{e}_{R,j}$ in register $\gray{R_j}$ to party $\mathsf{P}_j$ for $j \in [n]$.
    \item On input $\rho_i \in \Den{\ell_i}$, send $\rho_i$ in register $\gray{I_i}$ to party $\mathsf{P}_i$.\\
    Receive the teleportation  measurement result $(z_i, x_i)$ from party $\mathsf{P}_i$.\\
    Obtain the teleported input $\rho'_i \leftarrow \mathsf{TP.Receive}(z_i, x_i, \tilde{e}_{R,i})$.
    \item Invoke ideal functionality:\\
    Send $\rho'_i$ to $\mathsf{T}$. Do not send any $\normalfont{\texttt{abort}}$ message to $\mathsf{T}$. Receive $\sigma_j$ from $\mathsf{T}$.
    \item Teleport $\sigma_j$ into $\hat{e}_{S,j}$, resulting in the outcomes $(z'_j,x'_j) \leftarrow \mathsf{TP.Send}(\sigma_j, \hat{e}_{S,j})$.\\
    Send $P''_j = \hat{P}_j \ensuremath{X}^{x'_j} \ensuremath{Z}^{z'_j}$ to party $\mathsf{P}_j$.
    \item Output the final output of ${\mathcal{A}}$.
\end{enumerate}
\end{simulator}
Let $\gray{R'_i}$ denote the register holding $\tilde{e}_{R,i}$. Using notation (\ref{abbrev:teleport}), simulation step $3$ ends with
$$\underset{\Delta}{\Sigma} \text{ }\big(\onreg{\ketbra{z_i}}{I_i}, \onreg{\ketbra{x_i}}{S_i}, \onreg{\underset{i\in [n]}{\cup} \rho_i^\Delta}{R'_i}, \onreg{U_{P_{I_i}, P_{S_i}}}{R_j, W}
(\onreg{\hat{P}_j \cdot \hat{e}_{R,j}}{R_j}, \onreg{\rho_{{\mathsf{aux}}}}{W}) \onreg{U_{P'_{I_i}, P_{S'_i}}^\dag}{R_j, W}\big)$$

After steps $4, 5$, the values in registers $\gray{R'_i}$ is correctly QECC encoded, securely authenticated, and being teleported. The end state of the simulation becomes
\begin{align*}
& A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}\hat{P}_j \ensuremath{X}^{x'_j} \ensuremath{Z}^{z'_j} E_j )  ( {\mathsf{QECC.Enc}}(\cdot, \phi_h), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\\
= & A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}P''_j E_j )  ( {\mathsf{QECC.Enc}}(\cdot, \phi_h), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\end{align*}
which is the same as the real world state.
\fi
Since the adversary learns $P''_j$ in the end, we can also rewrite the state as
\begin{align*}
A'^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes} E_j )  ( {\mathsf{QECC.Enc}}(\cdot, \phi_h), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\end{align*}
for some $A'$ that depends on the random Pauli operators $P''_j$.

\subsection{Distributed Circuit Evaluation}
After spreading out QECC codewords of the inputs across parties, the players proceed to evaluate a circuit $C$ in a distributed manner. As long as there are enough additional ancilla and magic states, $C$ can be computed using only certain Clifford gates and measurements. To come up with a protocol for this task, we combine ideas from \cite{DGJ+20} with transversal computation over QECC codewords.

\begin{protocol}{$(\Sigma^\mathsf{RQC}, \Pi^{\mathsf{RQC}})$ for Redistributed Quantum Computation}
\textbf{Preprocessing: $\Sigma^\mathsf{RQC} = \Sigma^\mathsf{IE}$}\\

\textbf{Online Input:}
\begin{enumerate}
\setlength{\itemsep}{1pt}

    \item Everyone holds the circuit description $C$.
    \item Each $\mathsf{P}_i$ holds private input $\rho_i \in \Den{\ell_i}$.
\end{enumerate}
\textbf{Protocol $\Pi^\mathsf{RQC}$:}
\begin{enumerate}
\setlength{\itemsep}{1pt}
\item Parties run $\Pi^\mathsf{IE}$.
${\mathsf{cMPC}}$ initializes the set $\normalfont{\texttt{Corr}} = \{\}$.\\
At any time if $|\normalfont{\texttt{Corr}}| > \thres$, ${\mathsf{cMPC}}$ publicly aborts to all players in $\normalfont{\texttt{Corr}}$.
\item Iteratively, ${\mathsf{cMPC}}$ decides whether a Clifford gate $G$ has to be applied on the joint logical state, or some logical qubit has to go through a measurement.
\item To perform Clifford gate $G$ on the $l$ logical qubits, do for every $\mathsf{P}_j \not \in \normalfont{\texttt{Corr}}$:
\begin{enumerate}
\setlength{\itemsep}{1pt}
    \item Suppose ciphertext $\sigma_j$ held by party $\mathsf{P}_j$ is authenticated under key $E_j$.
    \item ${\mathsf{cMPC}}$ updates the key with $E'_j = E_j (G \otimes \identity^{lt})^\dag$.

\end{enumerate}
\item To perform a measurement on $1$ of $l$ logical qubits, do for every $\mathsf{P}_j \not \in \normalfont{\texttt{Corr}}$:
\begin{enumerate}
\setlength{\itemsep}{1pt}
    \item Suppose ciphertext $\sigma_j$ held by party $\mathsf{P}_j$ is authenticated under key $E_j$.
    \item ${\mathsf{cMPC}}$ samples strings $c^z_j, c^x_j, c^t_j\in \{0,1\}^{\ensuremath{1}} %{\ensuremath{m}+t}$ and key $E'_j \in \mathscr{C}_{(l-1)(\ensuremath{1}} %{\ensuremath{m}+t)}$.\\

    ${\mathsf{cMPC}}$ sends $V_j = (E'_j \otimes \ensuremath{Z}^{c^z_j} \ensuremath{X}^{c^x_j} \mathsf{CNOT}_{c^t_j}) E_j^\dag$ to $\mathsf{P}_j$.
    \item $\mathsf{P}_j$ calculates and parses $(\sigma'_j, \tau'_j) = V_j \cdot \sigma_j$ where $\tau'_j \in \Den{\ensuremath{1}} %{\ensuremath{m}+t}$.\\
    $\mathsf{P}_j$ measures $\tau'_j$ and sends the outcome $r_j \leftarrow \mathsf{\Pi}({\tau'_j})$ to ${\mathsf{cMPC}}$.
    \item ${\mathsf{cMPC}}$ sets bit $b_j$ if $r_j \oplus c^x_j = b_j (1, c^t_j)$ has a solution.\\ Otherwise, set $b_j = \bot$ and add $\mathsf{P}_j$ into $\normalfont{\texttt{Corr}}$.\\
    ${\mathsf{cMPC}}$ computes $b \leftarrow \mathsf{QECC.Dec}(b_1, \cdots, b_n)$ as the measurement result.
    \item $\mathsf{P}_j$ now holds ciphertext $\sigma'_j$ authenticated under key $E'_j$.
\end{enumerate}
\end{enumerate}

\textbf{Output:}
\begin{enumerate}
\setlength{\itemsep}{1pt}
    \item $\mathsf{P}_j$ outputs the ciphertext it currently holds.
    \item ${\mathsf{cMPC}}$ outputs the authentication key of each party (set to $\bot$ if party $\in \normalfont{\texttt{Corr}}$).
\end{enumerate}
\end{protocol}

Our protocol $(\Sigma^\mathsf{RQC}, \Pi^\mathsf{RQC})$ can perform redistributed quantum computation as specified by ${\mathsf{Ideal}}^\mathsf{RQC}$ on any circuit. This is captured by the following lemma.

\begin{lemma}\label{lemma:rqc}
For every non-uniform ({\sc qpt}\xspace) adversary ${\mathcal{A}}_I$ corrupting $I$, there is a non-uniform ({\sc qpt}\xspace) simulator $\mathsf{Sim}_{{\mathcal{A}}_I}$ corrupting $I$, such that for any states $\rho_1, \cdots, \rho_n, \rho_{{\mathsf{aux}}}$,
\begin{align}
    \{{\mathsf{Real}}^{\Pi^{\mathsf{RQC}} \circ \Sigma^{\mathsf{RQC}}}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}(1^{\secparam}, C, \rho_1, \cdots, \rho_n) \} \approx \{{\mathsf{Ideal}}^{\mathsf{RQC}}_{\mathsf{Sim}_{{\mathcal{A}}_I(\rho_{{\mathsf{aux}}})}}(1^{\secparam}, C, \rho_1, \cdots, \rho_n) \}
\end{align}
\end{lemma}

\begin{proof}
First, we construct the simulator as follows.

\begin{simulator}{$\mathsf{Sim}^{\mathsf{RQC}}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}$ for Redistributed Quantum Computation}\label{sim:rqc}
\begin{enumerate}
\setlength{\itemsep}{1pt}    \item Generate preprocessing data:
    \begin{itemize}
        \item Create EPR pair $(\onreg{\tilde{e}_{S_i}}{S_i},\onreg{\tilde{e}_{R,i}}{R'_i})$ of size $\ell_i$ for input encoding.
        \item Create EPR pair $(\hat{e}_{S,j}^{(0)}, \hat{e}_{R,j}^{(0)})$ of size $\ell'(\ensuremath{1}} %{\ensuremath{m}+t)$ for output recovery.
        \item Create EPR pair $(\hat{e}_{S,j}^{(l)}, \hat{e}_{R,j}^{(l)})$ of size $(\ensuremath{1}} %{\ensuremath{m}+t)$ for measurement.
        \item Sample $\hat{P}_j \leftarrow \mathscr{P}_{\ell(\ensuremath{1}} %{\ensuremath{m}+t)}$ and $\hat{E}_j^{(l)} \leftarrow \mathscr{C}_{\ensuremath{1}} %{\ensuremath{m}+t}$ for $l \in \{\ell'+1, \cdots, \ell\}$.
        \item Send $\tilde{e}_{S_i}$ in register $\gray{S_i}$ to $\mathsf{P}_i$.
        \item Send $\hat{P}_j \cdot \big(\hat{e}_{R,j}^{(0)}, (\hat{E}_j^{(\ell'+1)} \cdot \hat{e}_{R,j}^{(\ell'+1)}), \cdots, (\hat{E}_j^{(\ell)} \cdot \hat{e}_{R,j}^{(\ell)})\big)$ in register $\gray{R_j}$ to $\mathsf{P}_j$.
    \end{itemize}
    \item Input extraction:
    \begin{itemize}
        \item On input $\rho_i \in \Den{l}$, send $\rho_i$ in register $\gray{I_i}$ to party $\mathsf{P}_i$.
        \item Receive the teleportation measurement result $(z_i, x_i)$ from party $\mathsf{P}_i$.
        \item Extract the input $\rho'_i \leftarrow \mathsf{TP.Receive}(z_i, x_i, \tilde{e}_{R,i})$ and send it to $\mathsf{T}$.
    \end{itemize}

    \item Output recovery:
    \begin{itemize}
        \item Upon receiving $\sigma_j$ from $\mathsf{T}$, teleport $\sigma_j$ into the first component $\hat{e}_{S,j}^{(0)}$.
        \item Obtain $(z'_j,x'_j) \leftarrow \mathsf{TP.Send}(\sigma_j, \hat{e}_{S,j}^{(0)})$.
        \item Send $P''_j = \hat{P}_j (\ensuremath{X}^{x'_j} \ensuremath{Z}^{z'_j} \otimes \identity^{(\ell-\ell')(\ensuremath{1}} %{\ensuremath{m}+t)})$ to $\mathsf{P}_j$.
    \end{itemize}

    \item For each measurement step of $C$, do the following (with $l$ from $\ell$ to $\ell'+1$):
    \begin{itemize}
        \item Send to $\mathsf{P}_j$ the gate $\hat{E}_j^{(l)}$.
        \item Receive the measurement result $r_j \in \{0,1\}^{\ensuremath{1}} %{\ensuremath{m}+t}$ from party $\mathsf{P}_j$.
        \item Measure $\hat{e}_{S,j}^{(l)}$ and compare the result $\tilde{r}_j = \mathsf{\Pi}(\hat{e}_{S,j}^{(l)})$ with $r_j$.
        \item If $\tilde{r}_j \neq r_j$, let $\mathsf{P}_j$ send $\normalfont{\texttt{abort}}$ to $\mathsf{T}$.
    \end{itemize}
\end{enumerate}
\textbf{Output:} the final output of ${\mathcal{A}}$.\newline\text{}
\end{simulator}

We prove by induction on the number of circuit steps $|C|$ that the real protocol can be simulated by the simulator $\mathsf{Sim}^{\mathsf{RQC}}$. We also prove in the induction that the end state of both the real and ideal world when $\mathsf{P}_j$ is not being marked as corrupted are indistinguishable from a state where ${\mathsf{cMPC}}$ holds random Clifford keys $\{E_j\}_{j \in [n]}$ and the adversary holds
\begin{equation}
\begin{aligned}[b]
A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}E_j )  ({\mathsf{QECC.Enc}}(C(\cdot, \phi_h)), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\label{eq:rqc-state}
\end{aligned}
\end{equation}
for some map $A$. For the base case $C = \mathbbm{1}$, the protocol is equal to $(\Sigma^\mathsf{IE}, \Pi^\mathsf{IE})$. From the analysis of the previous section, it remains to show that $\mathsf{Sim}^{\mathsf{RQC}}(\identity)$ ends in state (\ref{eq:ie-real-world}). Using notation (\ref{abbrev:teleport}), the state at the end of simulator step $2$ is
$$\underset{\Delta}{\Sigma} \text{ }\big(\onreg{\ketbra{z_i}}{I_i}, \onreg{\ketbra{x_i}}{S_i}, \onreg{\underset{i\in [n]}{\cup} \rho_i^\Delta}{R'_i}, \onreg{U_{P_{I_i}, P_{S_i}}}{R_j, W}
(\onreg{\hat{P}_j \cdot \hat{e}_{R,j}^{(0)}}{R_j}, \onreg{\rho_{{\mathsf{aux}}}}{W}) \onreg{U_{P'_{I_i}, P_{S'_i}}^\dag}{R_j, W}\big)$$
After step $3$, the values in registers $\gray{R'_i}$ is correctly QECC-encoded, securely authenticated, and being teleported. The end state of the simulation becomes
\begin{align*}
& A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}\hat{P}_j \ensuremath{X}^{x'_j} \ensuremath{Z}^{z'_j} E_j )  ( {\mathsf{QECC.Enc}}(\cdot, \phi_h), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\\
= & A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}P''_j E_j )  ( {\mathsf{QECC.Enc}}(\cdot, \phi_h), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\end{align*}
which is equal to (\ref{eq:ie-real-world}). (When $C=\identity$, the simulator does nothing in step $4$.)

Suppose the parties are going to run a further computation step under our induction hypothesis. For the protocol of performing a Clifford gate $G$, ${\mathsf{cMPC}}$ updates the keys to $\{E'_j = E_j (G \otimes \identity^{lt})^\dag\}_{j \in [n]}$. These keys are still random Clifford keys. We can rewrite the state of the real-protocol adversary in terms of $\{E'_j\}_{j \in [n]}$ as
\begin{equation}
\begin{aligned}[b]
& A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}E'_j (G \otimes \identity^{l t}))  ({\mathsf{QECC.Enc}}(C(\cdot, \phi_h)), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)\\
= & A^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}E'_j) ({\mathsf{QECC.Enc}}(G\circ C(\cdot, \phi_h)), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big) \label{equation:compute-clifford}
\end{aligned}
\end{equation}
since the QECC supports transversal computation on these Clifford gates. As the only difference between $\mathsf{Sim}^{\mathsf{RQC}}(C)$ and $\mathsf{Sim}^{\mathsf{RQC}}(G \circ C)$ is the ideal functionalities they interact with, we see that $\mathsf{Sim}^{\mathsf{RQC}}(G \circ C)$ also ends with state (\ref{equation:compute-clifford}).

For the protocol of measuring a logical qubit
shared over registers $\gray{Q_j} \subseteq \gray{R_j}$, the adversary receives $V_j = (E'_j \otimes \ensuremath{Z}^{c^z_j} \ensuremath{X}^{c^x_j} \mathsf{CNOT}_{c^t_j}) E_j^\dag$, so its state can be described as
\begin{align*}
& A'^{\Delta} \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes}(E'_j \otimes \ensuremath{Z}^{c^z_j} \ensuremath{X}^{c^x_j} \mathsf{CNOT}_{c^t_j} ))  ({\mathsf{QECC.Enc}}(C(\cdot, \phi_h)), 0^{l n t})}{R_{j}}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\end{align*}
for some $A'$ that can depend on $V_j$. Next, the adversary measures $\gray{Q_j}$. To analyze ${\mathsf{cMPC}}$'s examination, we decompose the attack $A'$ according to Pauli basis on registers $\gray{Q_j}$. That is, we write $A' = {\Sigma_{x_j}} \onreg{A'_{x_j}}{R_j,W}  \onreg{\ensuremath{X}^{x_j}}{Q_j}$ where $A'_{x_j} = {\Sigma_{z_j}} \onreg{A'_{x_j, z_j}}{R_j \backslash Q_j, W} \onreg{\ensuremath{Z}^{z_j}}{Q_j}$.
Similar to \cite{DGJ+20}, all Pauli $P$ with $x(P) \neq 0$ would fail ${\mathsf{cMPC}}$'s test with overwhelming probability over random $(c^z_j, c^x_j, c^t_j)$. Thus, the residual state passing the test would be indistinguishable from
\begin{align}
A'^{\Delta}_0 \big( \underset{i \in [n]}{\cup} \rho_i \text{ }; \text{ } \onreg{(\underset{j \in [n]}{\otimes} E'_j)  ({\mathsf{QECC.Enc}}( C(\cdot, \phi_h))_{[:l-1]}, 0^{(l-1) n t})}{R_{j}\backslash Q_j}, \onreg{\rho_{{\mathsf{aux}}}}{W} \big)
\label{equation:compute-measurement}
\end{align}
while the string $r_j$ provided by $\mathsf{P}_j$ is $(\mathsf{\Pi}( {\mathsf{QECC.Enc}}(C(\cup_i \rho_i, \phi_h)_{[l]})_{[j]}) (1, c^t_j) \oplus x_j )$. Then the bit $b$ recovered by ${\mathsf{cMPC}}$ is $\mathsf{\Pi}( C(\cup_i \rho_i, \phi_h){[l]} )$ because measurement is transversal on our QECC. Now we turn to the simulated end state. There are two main differences between $\mathsf{Sim}^{\mathsf{RQC}}(C)$ and $\mathsf{Sim}^{\mathsf{RQC}}((\identity \otimes \mathsf{\Pi}) \circ C)$.
First, the latter simulator encrypts part of the receiving portals under key $\hat{E}_j^{(l)}$. Second, the latter simulator performs an additional measurement step. As neither simulators give $\hat{e}_{S,j}^{(l)}$ to the adversary, both $\hat{e}_{R,j}^{(l)}$ and $\hat{E}_j^{(l)} \cdot \hat{e}_{R,j}^{(l)}$ are maximally mixed states and are indistinguishable from the view of ${\mathcal{A}}$. Next, we decompose $A' = {\Sigma_{x_j}} \onreg{A'_{x_j}}{R_j,W} \onreg{\ensuremath{X}^{x_j}}{Q_j}$.
The only possible Pauli operators on $\gray{Q_j}$ that can yield equal measurements on $\hat{e}_{S,j}^{(l)}$ and $\hat{e}_{R,j}^{(l)}$ are those without any bit-flips. Hence, conditioned that the simulator does not make $\mathsf{P}_j$ send $\normalfont{\texttt{abort}}$, the attack reduces to $A'_0$, and the end state is equal to (\ref{equation:compute-measurement}).
\ifdefined\Thirty\else

Finally, we analyze the case when some corruptions are detected. If party $\mathsf{P}_j$ is identified as corrupted, the output key $E_j$ will be replaced with $\bot$ in both the real and simulated worlds, so that the $j$-th share in (\ref{eq:rqc-state}) becomes the maximally mixed state in both worlds. When $\mathsf{P}_j$ is added into the list $\normalfont{\texttt{Corr}}$ because the measurement step failed, one easily sees that both worlds have residual states (indistinguishably) described by $(A'^\Delta-A'^\Delta_0)(\cdot)$.
\fi

\end{proof}

\subsection{Multiparty Quantum Computation}

The final step is to transit from RQC to MPQC. After the computation, the evaluators must send the encrypted and encoded outputs back to their owners. Apparently, the outputs could turn out ruined when the owner unpacks the messages. This situation is where AQA comes into play, which guarantees public verifiable identifiable abort when some sender modifies the message. If no such problem happens, the parties have accomplished their MPQC task. Our MPQC protocol will be a direct concatenation of RQC and AQA.

\begin{protocol}{$(\Sigma^{{{\mathsf{BoBW}}_0}}, \Pi^{{{\mathsf{BoBW}}_0}})$ for the Preprocessing Best-of-Both-Worlds Multiparty Quantum Computation with Public Verifiable Identifiable Abort}\label{proto:bobw}
\centerline{\textbf{Parameters:} $n,t,\thres,(\ell_1, \cdots, \ell_n), \ell_{{\mathsf{anc}}}, \ell'$}
\textbf{Preprocessing $\Sigma^{{\mathsf{BoBW}}_0}$:}
\begin{enumerate}
\setlength{\itemsep}{1pt}
    \item Run $\Sigma^{\mathsf{RQC}}$. Then run $\Sigma^{\mathsf{AQA}}(\mathsf{P}_j, \mathsf{P}_i)$ for every pair of parties $i,j \in [n]$.
\end{enumerate}
{\bf Online Input:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item Everyone holds the circuit description $C$.
    \item $\mathsf{P}_i$ holds private input $\rho_i \in \Den{\ell_i}$.
\end{enumerate}
{\bf Protocol $\Pi^{{\mathsf{BoBW}}_0}$:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item All parties run the protocol $\Pi^{\mathsf{RQC}}$ to compute $C$.\\
    At any time if $|\normalfont{\texttt{Corr}}| > \thres$, ${\mathsf{cMPC}}$ publicly aborts to all players in $\normalfont{\texttt{Corr}}$.

    \item Suppose $\sigma_j$ that $\mathsf{P}_j$ obtains from step 1 is authenticated under key $E_j \neq \bot$.\\
    ${\mathsf{cMPC}}$ retrieves key pair $(E'_{i,j}, E''_{i,j})$ that was given by $\Sigma^{\mathsf{AQA}}(\mathsf{P}_j, \mathsf{P}_i)$.\\
    ${\mathsf{cMPC}}$ sends $V_j = (E'_{1,j} \otimes \cdots \otimes E'_{1,n}) E^{\dag}_j $ to $\mathsf{P}_j$.\\
    $\mathsf{P}_j$ calculates $V_{j} \cdot \sigma_{j}$ and parses the result into $(\sigma'_{1,j}, \cdots, \sigma'_{n,j})$.

    \item AQA from party $\mathsf{P}_j$ to party $\mathsf{P}_i$: run $\Pi^\mathsf{AQA}(\mathsf{P}_j(\sigma'_{i,j}), \mathsf{P}_i, {\mathsf{cMPC}})$ for $i, j \in [n]$.\\
    $\mathsf{P}_i$ collects what it received $\{\sigma''_{i,j}\}_{j \in [n]}$ from the other parties.\\
    If AQA identifies $\mathsf{P}_j$ as malicious, put $\mathsf{P}_j$ into $\normalfont{\texttt{Corr}}$.
    \item ${\mathsf{cMPC}}$ sends keys $\{E''_{i,j}\}_{j \in [n]}$ to $\mathsf{P}_i$ and publicly outputs classical output $r'$.
\end{enumerate}
{\bf Output:}
\begin{enumerate}
\setlength{\itemsep}{1pt}
    \item $\mathsf{P}_i$ outputs $\rho'_i \leftarrow \mathsf{QECC.Dec} \big( E''^\dag_{i,1} \cdot \sigma''_{i,1}, \cdots, E''^\dag_{i,n} \cdot \sigma''_{i,n} \big)$ and $r'$.
\end{enumerate}
\end{protocol}

\begin{theorem}\label{thm:bobw}
$(\Sigma^{{\mathsf{BoBW}}_0}, \Pi^{{{\mathsf{BoBW}}_0}})$ is a best-of-both-worlds\xspace multi-party quantum computation secure with public verifiable identifiable abort\xspace of threshold $\thres$ in the preprocessing MPC-hybrid model as defined in \cref{dfn:mpqc}.

\end{theorem}

\begin{proof}

In short, the simulator runs a concatenation of $\mathsf{Sim}^\mathsf{RQC}$ with $\mathsf{Sim}^\mathsf{AQA}$. ${\mathsf{Ideal}}^{{\mathsf{MPQC}}}$ is invoked in $\mathsf{Sim}^\mathsf{RQC}$ to get $\{\rho'_i\}_{i\in I}$. In the output recovery phase of $\mathsf{Sim}^\mathsf{RQC}$, the simulator teleports $\mathsf{TP}^\dag \cdot \tilde{e}_S$ prepared by $\mathsf{Sim}^\mathsf{AQA}$ instead of $\hat{e}_{S}^{(0)}$. Whenever $|\normalfont{\texttt{Corr}}| > \thres$, the simulator sends $\normalfont{\texttt{abort}}$ message from parties in $|\normalfont{\texttt{Corr}}|$ to ${\mathsf{Ideal}}^{\mathsf{MPQC}}$. In the output recovery phase of $\mathsf{Sim}^\mathsf{AQA}$, the simulator authenticates $\rho'_i$ with fresh random keys, teleports the result to $\mathsf{P}_i$, and sends the key out.

When $|I|\le \thres$, the protocol never reaches the abort condition. By \cref{lemma:rqc} and \cref{lemma:aqa}, the honest parties will certainly receive at least a proportion $1-\frac{\thres}{n}$ of their output codewords. Our requirement on QECC then implies that the honest parties can recover their outputs. From \cref{lemma:rqc} and \cref{lemma:aqa}, we deduce that the protocol is indistinguishable from simulation using ${\mathsf{Ideal}}^{{\mathsf{MPQC-Full}}}$ when $|I| \le \thres$ and using ${\mathsf{Ideal}}^{\mathsf{MPQC}}$ when $|I|\le n-1-\thres$.

\iffalse
\begin{simulator}{$\mathsf{Sim}^{{\mathsf{BoBW}}_0}_{{\mathcal{A}}(\rho_{{\mathsf{aux}}})}$ for the Preprocessing BoBW MPQC-PVIA}\label{sim:prep-bobw}
\begin{enumerate}
\setlength{\itemsep}{1pt}
    \item Output: the final output of ${\mathcal{A}}$.
\end{enumerate}
\end{simulator}
\fi

\end{proof}

\section{BoBW-MPQC-PVIA without Trusted Setup}\label{Sec:SWIA+PVIA}
So far, we have shown an MPQC-PVIA protocol in the preprocessing model. This section presents how we discard the trusted setup and obtain an MPQC-PVIA protocol without preprocessing. The idea here is to instantiate the preprocessing phase with MPQC-SWIA {e.g.,\ } \cite{ACC+21}.

\paragraph{Hierarchical MPQC-SWIA}

We quickly recall the SWIA property of \cite{ACC+21}. When the \cite{ACC+21} protocol aborts, their classical MPC outputs a partition of all parties into two mutually distrusting groups. By observation, one of the two groups comprises only malicious players, and the other group contains all honest players, with some malicious players pretending to be honest. We can take advantage of this information to get an MPQC-PVIA protocol. First, we replace the trusted setup of our preprocessing MPQC-PVIA by running MPQC-SWIA, where it can create preprocessing data (including portals, magic states, and ancilla) for each party. Then, if the protocol fails, we allow those two groups to run their MPQC-SWIA protocols independently. The parties will ultimately obtain reliable preprocessing data within subgroups by iterating this procedure.
Note that we do not publicly identify anyone during this stage.

After generating enough reliable preprocessing data, every party can run the protocol $\Pi^{{\mathsf{BoBW}}_0}$ within its group to obtain the output.
Since the honest parties are always in the same group, they will jointly evaluate their outputs in the $\Pi^{{\mathsf{BoBW}}_0}$. Our approach circumvents the false accusation problem encountered in \cite{ACC+21} because the parties in our protocol no longer accuse between groups. Instead, each group runs its own $\Pi^{{\mathsf{BoBW}}_0}$, which only aborts dishonest members.

\ifdefined\Thirty\else
We emphasize that the parties may divide into groups when the protocol executes successfully. In this situation, if the circuit of interest involves public output, the legitimacy of each group must be determined, and the public output selected accordingly. Our protocol does not attempt to address this. We take a step back and consider only circuits with private outputs. At the end of our protocol, either a public verifiable identifiable abort occurs, or each party is satisfied with its private outcome. Dealing with circuits with public outputs remains an intriguing open problem for one who would like to achieve a stronger PVIA notion.
\fi

Now, we formulate our protocol. Let $\Pi^{\mathsf{SWIA}}$ be \cite{ACC+21}'s MPQC-SWIA protocol.

\begin{protocol}{$\Pi^{{\mathsf{BoBW}}_1}$ for the Best-of-Both-Worlds MPQC-PVIA}\label{proto:swia+pvia}
{\bf Input:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item Everyone holds the circuit description $C$ which has only private outputs.
    \item Party $\mathsf{P}_i$ holds private input $\rho_i \in \Den{\ell_i}$.
\end{enumerate}

{\bf Protocol:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item Put $G = \{\{\mathsf{P}_1, \cdots, \mathsf{P}_n\}\}$ as the initial partition of parties ({i.e.,\ } no partition).\\
    Mark the set $\{\mathsf{P}_1,\cdots,\mathsf{P}_n\} \in G$ as unfinished.
    \item Repeat the following until all sets in $G$ are marked as finished:\\
    For unfinished $S \in G$, the parties in $S$ run $\Pi^{\mathsf{SWIA}}$ together on the circuit $\Sigma^{{\mathsf{BoBW}}_0}(C_S)$, where $C_S$ is the circuit that prepares default inputs for parties $\not \in S$ and runs $C$.
    \begin{enumerate}
        \item If the protocol succeeds, parties in $S$ obtain the required preprocessing data. In this case, mark $S$ as finished.
        \item Otherwise, the MPQC-SWIA protocol outputs a partition $\{S_0, S_1\}$ of $S$.\\
        In this case, replace $S$ with the unfinished $S_0$ and $S_1$ in partition $G$.
    \end{enumerate}

    \item Run $\Pi^{{\mathsf{BoBW}}_0}$ within every set $S \in G$.\\
    Abort to all identified parties if any execution of $\Pi^{{\mathsf{BoBW}}_0}$ aborts.
\end{enumerate}
{\bf Output:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item Upon abort, all parties output the identities collected from all $\Pi^{{\mathsf{BoBW}}_0}$.
    \item Otherwise, $\mathsf{P}_i$ outputs the result obtained from his/her execution of $\Pi^{{\mathsf{BoBW}}_0}$.
\end{enumerate}
\end{protocol}

\begin{theorem}\label{thm:swia+pvia}
$\Pi^{{\mathsf{BoBW}}_1}$ is a best-of-both-worlds\xspace multi-party quantum computation secure with public verifiable identifiable abort\xspace over circuits with only private outputs in the MPC-hybrid model as defined in \cref{dfn:mpqc}.
\end{theorem}

\begin{proof}
Since our protocol makes only sequential calls to MPQC-SWIA protocols, the security of MPQC-SWIA allows one to replace these protocol executions with the ideal functionality of MPQC-SWIA. The resulting hybrid world $\mathcal{H}_1$ is indistinguishable from the real world. The ideal functionality of MPQC-SWIA in $\mathcal{H}_1$ translates to the following game. At the beginning of $\mathcal{H}_1$, the adversary chooses how to partition all parties step by step, but cannot partition the honest parties. Afterward, there is a trusted setup on $\Sigma^{{\mathsf{BoBW}}_0}$ followed by $\Pi^{{\mathsf{BoBW}}_0}$ for each group of the partition. Since these preprocessing BoBW protocols are independent instances, \cref{thm:bobw} implies that they can be replaced with the ideal world of BoBW-MPQC-PVIA. It is easy to see that the resulting hybrid $\mathcal{H}_2$ preserves the PVIA property\ifdefined\Thirty and full security.\else.
To argue full security when $|I|\le \thres$, one observes that the group containing all the honest parties has at least a $1-\frac{\thres}{n}$ proportion of honest parties, so the full security of BoBW-MPQC-PVIA is also preserved.
\fi
\end{proof}
\section{Extentions}

\subsection{Constant Round MPQC-PVIA in the Preprocessing Model}

When aiming only for MPQC-PVIA, our BoBW-MPQC-PVIA protocol in the preprocessing model can be made round efficient. The reason is that we no longer need to keep the data distributed across parties, which eliminates the need for information exchange during computation. Instead, a designated party can hold all the data, and the entire process can become constant-round using quantum garbled circuits for computation as in \cite{BCKM21}.
\ifdefined\Thirty
We refer readers to the full version of our paper in the supplementary material for the details of the constant-round protocol with computational security due to page limit.

\else

\begin{theorem}
There is a constant-round multi-party quantum computation secure with public verifiable identifiable abort\xspace in the preprocessing MPC-hybrid model.
\end{theorem}

\begin{protocol}{$(\Sigma^{{{\mathsf{Const}}{\mathsf{MPQC}}}}, \Pi^{{{\mathsf{Const}}{\mathsf{MPQC}}}})$ for the Preprocessing Constant-Round MPQC-PVIA}\label{proto:cpvia}

\textbf{Preprocessing $\Sigma^{{{\mathsf{Const}}{\mathsf{MPQC}}}}$:}
\begin{enumerate}
\setlength{\itemsep}{1pt}
    \item Run $\Sigma^{\mathsf{IE}}$. Then run $\Sigma^{\mathsf{AQA}}(\mathsf{P}_i, \mathsf{P}_1)$ for every party $i \in [n]$.
\end{enumerate}

{\bf Protocol $\Pi^{{{\mathsf{Const}}{\mathsf{MPQC}}}}$:}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item All parties run the input encoding protocol $\Pi^\mathsf{IE}$.\\
    The designated evaluator $\mathsf{P}_1$ obtains ciphertext $\sigma$ under key $E$.

    \item ${\mathsf{cMPC}}$ generates quantum garbled circuit:
    \begin{enumerate}
    \setlength{\itemsep}{0pt}
        \item Retrieve key pair $(E'_{i}, E''_{i})$ that was created by $\Sigma^{\mathsf{AQA}}(\mathsf{P}_i, \mathsf{P}_1)$.
        \item Define the augmented circuit $C'$ as:
        \begin{itemize}
        \setlength{\itemsep}{0pt}
            \item Measure all the traps. If any trap is non-zero, end by outputting $\bot$.
            \item Evaluate $C$ on the inputs and ancilla states, and apply $E'_1 \otimes \cdots \otimes E'_n$.
        \end{itemize}
        \item Run $(\hat{E}, \hat{C}) \leftarrow \mathsf{QG.Garble}(C')$.
        \item Send the gate $V = \hat{E} E^\dag$ and the garbled circuit $\hat{C}$ to the evaluator $\mathsf{P}_1$.
    \end{enumerate}

    \item $\mathsf{P}_1$ evaluates the garbled circuit $\sigma' \leftarrow \mathsf{QG.Eval}(V\cdot \sigma, \hat{C})$.\\
    $\mathsf{P}_1$ parses the result into $(\sigma'_1, \cdots, \sigma'_n)$.

    \item AQA from party $\mathsf{P}_1$ to party $\mathsf{P}_i$ for $i\in [n]$: run $\Pi^\mathsf{AQA}(\mathsf{P}_1(\sigma'_{i}), \mathsf{P}_i, {\mathsf{cMPC}})$.\\
    If any $\Pi^\mathsf{AQA}$ fails, ${\mathsf{cMPC}}$ publicly aborts to $\mathsf{P}_1$.\\
    Otherwise, $\mathsf{P}_i$ receives the ciphertext $\sigma''_i$ successfully.
    \item ${\mathsf{cMPC}}$ sends key $E''_{i}$ to $\mathsf{P}_i$.
\end{enumerate}
\text{ }{\bf Output:} $\mathsf{P}_i$ outputs $\rho'_i \leftarrow \mathsf{C.Dec}_{E''_{i}}(\sigma''_{i})$.\\\text{ }
\end{protocol}

The security follows from adapting the proof of \cref{thm:bobw} with the proofs \cite{BCKM21,YB20} that use garbled circuits to perform the computation.

\fi

\subsection{MPQC-PVIA from Trap-code AQA}
We also discover the possibility of constructing MPQC-PVIA using Trap-code form AQA (\cref{fig:AQATP}). Existing MPQC protocols against a dishonest majority \cite{DGJ+20,ACC+21,BCKM21} only consider Clifford authentication code because of the obstruction of the Trap authentication code's checking step. For example, if we replace the Clifford code in \cite{ACC+21} with Trap code, the player will not know if the errors are caused by the previous player or other prior players. This is because trap code requires a permutation to hide the input qubits' information. By only considering the Trap authentication code, one cannot guarantee the secrecy of the qubits' location while still identifying the suspect.
\ifdefined\Thirty
Thanks to our AQA, by slightly twisting Trap-code and plugging it into our AQA, we can construct the first MPQC-PVIA protocol from Trap-code form AQA in the preprocessing model.
We refer readers to the full version of our paper in the supplementary material for the details of the Trap-code form MPQC-PVIA due to page limit.

\else

Thanks to our AQA, by slightly twisting Trap-code and plugging it into our AQA, we can construct the first MPQC-PVIA protocol from Trap-code form AQA in the preprocessing model.
The protocol will be very similar to the Clifford-form protocol (\cref{proto:bobw}) but with Trap-form IE and AQA (\cref{fig:AQATP}). Similar to \cite{ACC+21}, we make use of a verifiable quantum fully homomorphic encryption scheme (vQFHE) \cite{vQFHE} for computation on Trap code

\begin{protocol}{$(\Sigma^{{\mathsf{BoBW}}_{\mathsf{TP}}}, \Pi^{{\mathsf{BoBW}}_{\mathsf{TP}}})$ for the Trap-form Preprocessing MPQC-PVIA}
\textbf{Preprocessing: $\Sigma^{{\mathsf{BoBW}}_{\mathsf{TP}}}$}
\begin{enumerate}
    \setlength{\itemsep}{1pt}
    \item Run $\Sigma^\mathsf{IE}$, distributing not only Trap-code ciphertexts on EPR pairs and ancilla states, but also gadgets required for vQFHE computation under secret key $\mathsf{sk}$ given to ${\mathsf{cMPC}}$.
    \item Run $\Sigma^\mathsf{AQA}(\mathsf{P}_j, \mathsf{P}_i)$ for all pairs $i,j \in [n]$.
\end{enumerate}
\textbf{Protocol: $\Pi^{{\mathsf{BoBW}}_{\mathsf{TP}}}$}
\begin{enumerate}
\setlength{\itemsep}{1pt}
\item All parties run $\Pi^{\mathsf{IE}}$. so that each $\mathsf{P}_i$ obtains several Trap-code ciphertexts $\{\sigma_{i,l}\}$ corresponding to QECC codewords of inputs, under the same permutation key $\pi_i$.
\item ${\mathsf{cMPC}}$ initializes the set $\normalfont{\texttt{Corr}} = \{\}$.\\
At any time if $|\normalfont{\texttt{Corr}}| > \thres$, ${\mathsf{cMPC}}$ publicly abort to all parties in $\normalfont{\texttt{Corr}}$.
\item $\mathsf{P}_i$ computes via $(\{\Tilde{\sigma}_{i,l}\}, \mathsf{log}_i)\leftarrow \mathsf{TrapTP.Eval}(C,\{\sigma_{i,l}\})$ and sends $\mathsf{log}_i$ to ${\mathsf{cMPC}}$.
\item ${\mathsf{cMPC}}$ runs $\mathsf{CheckLog}(\mathsf{log}_i,\mathsf{sk})$
If the output is $\bot$, ${\mathsf{cMPC}}$ publicly abort $\mathsf{P}_i$.
\item $\mathsf{P}_i$ sends $\Tilde{\sigma}_{i,l}$ to the respective receiver $\mathsf{P}_j$ via $\Pi^\mathsf{AQA}$. The receiver $\mathsf{P}_j$ gets $\sigma'_j$.
\item ${\mathsf{cMPC}}$ sends the decoding instruction $V_{\mathsf{Dec},i}$ to the respective party $\mathsf{P}_i$.
\end{enumerate}

\textbf{Output:} $\mathsf{P}_i$ outputs $\rho'_i \leftarrow V_{\mathsf{Dec},i}(\sigma'_i)$.

\end{protocol}

The Trap-form protocol $(\Sigma^{{\mathsf{BoBW}}_{\mathsf{TP}}}, \Pi^{{\mathsf{BoBW}}_{\mathsf{TP}}})$ satisfies the statement of \cref{thm:bobw}. We omit the proof because of its similarity to the Clifford-code form MPQC-PVIA while basing on the security guarantee of Trap-code form AQA.

\fi

\section*{Acknowledgement}
We would like to thank Kai-Min Chung and Jiapeng Zhang for their helpful discussions. This research is partially supported by NSTC QC project under Grant no. NSTC 111-2119-M-001-004- and partially supported by NSF CAREER award 2141536.
\fi

\ifdefined\LLNCS
\bibliographystyle{splncs04}
\else
\bibliographystyle{alpha}
\fi

redpajama_set_name: RedPajamaArXiv