Multi-Party Computing

I. Introduction

Multi-Party Computation (MPC) is a cryptographic task where a set of players (two or more) with private data, wish to jointly compute a function on collective data, without having to reveal their private data to each other.

A particularly intuitive instantiation of two-party MPC is Homomorphic Encryption, where one of the parties encrypts and sends their data two the second party, in such a way that computations on encrypted data lead to computations on the plaintext, without the computing party learning anything about the plaintext. Restriction of MPC to particular functions parties might want to evaluate, such as set intersection, are also commonly studied.

However, in this work we will work with the most general possible MPC capable of computing any function. Although the performance of protocols computing a restricted subset of functions is possibly higher, the goal of this report is to compare the resource requirements and outcomes of classical MPC versus MPC when some quantum resources are available, but literature on MPC in presence of quantum adversaries is still not as advanced as the classical one and mostly general protocols have been considered.

Therefore, we will do the comparison between classical and quantum protocols by classifying the literature with respect to available hardware (see Subsection 1.1) and protocol characteristics (see Subsection 1.2). We include a compilation of known limitations of quantum-safe MPC in Subsection 1.3.

1.1 Classification according to hardware

In presence of quantum resources, we need to consider the most conservative scenario in which dishonest parties, also called ``adversaries’’ when considering not only parties participating in a computation, but also a dishonest environment, have access to unlimited quantum resources. However, we have more knowledge of the honest participating parties and their access to hardware.

In this work we will explicitly distinguish between three types of MPC attending to the type of hardware available to the honest parties:

  • Classical quantum-secure MPC (qs-MPC): Refers to MPC tasks that are purely classical (both the interaction between the parties and the computations are classical), but security holds also against quantum adversaries.
  • Quantum MPC (QMPC): Refers to MPC tasks where the interaction between the parties can be quantum, but the function they are trying to evaluate (and the computation) are classical. Security must still hold against quantum adversaries. This is what we call near-term quantum network stage, where parties have access to memory nodes which can prepare, transmit and measure quantum states as well as generate entanglement, but cannot do quantum computations.
  • Multi-Party Quantum Computation (MPQC): Refers to MPC tasks where both the communication and the computation are quantum, as well as the adversary. In this case the participating parties might also be computing quantum operations on their secret data. This is what we call long-term quantum network stage, where parties have access to memory nodes which can prepare, transmit and measure quantum states as well as generate entanglement, and can perform fault-tolerant quantum operations on their states.

1.2 Classification according to protocol characteristics

However, there are many variants of MPC that can be considered depending on the use case in mind. In order to classify and compare these variants, we further consider the following categories:

Number of parties: we can either consider (1) a network where only of the parties might be corrupted, called a honest-majority setting or (2) a network where all the participants initially distrust each other, called a dishonest-majority setting. On the one hand, honest-majority MPC is much simpler to obtain and can even be information-theoretically achievable using only classical resources. On the other hand, the simplest case of dishonest-majority MPC is when there are just 2 distrusting players (2PC), and in particular, it is not always possible to build an MPC protocol from a 2PC protocol.

Number of rounds: given that each round of communication increases the chance of an adversarial attack (not necessarily decrypting the data but possibly forcing the protocol to abort, and hence drastically reducing efficiency), protocol developers try to lower the number of communication rounds as much as possible, regardless of the actual number of (qu)bits sent on each round.

Set-up conditions: although the ideal security proof is obtained without any set-up assumption, called the plain-model, many of our cryptographic proofs rely on preconditions of the environment. __We stress that set-up assumptions refer to models of the proof-techniques, and not to… Typical set-up conditions include:

  • The Quantum Random Oracle Model (QROM) is a model where an idealized random function exists and is widely accepted as a proof technique. Attention must be paid if a proof of security is in the classical random oracle model (RO) or in the QROM, as the QROM captures the possibility of an adversary querying the oracle in superposition, and is essential for post-quantum security. The QROM is widely believed to be "standard" by theorists, and many NIST PQC proposals are proven secure in the QROM.
  • A Common Reference String (CRS) is a model where a random common bitstring (honestly sampled) is accessible to all parties. In practice, a CRS can be implemented via quantum coin-flipping, but its implementation adds rounds of communication.
  • Shared EPR pairs; the assumption here is that the EPR pairs are pre-shared between the parties, and hence honestly sampled. In practice, a shared-EPR pair can be securely generated by adding rounds of communication.
  • The Bounded Quantum Storage Model (BQSM) is a model where, as the name suggests, the quantum memory of the parties is considered to be bounded. Although this is very likely in the near term, the security of the protocols will weaken with advancements on quantum storage technology.

Assumptions: instead of building MPC from scratch, we can assume the existence of a simpler primitive and construct MPC from it. The downside of this approach is that the properties of a consequent MPC will depend on the properties of the underlying primitives (the set-up, the number of rounds etc). If a functionality can be constructed from scratch, it is said to be information-theoretically secure (ITS), however, this is not always possible and typically certain problems are first assumed to be hard to solve in order to prove the existence of a building-block functionality. For example, classical MPC is sometimes misslabelelled as ITS, this is because once point-to-point authenticated channels are assumed, then the computation itself can be ITS, however, point-to-point authenticated channels cannot be constructed without any set-up assumption! Here are some typical assumptions:

  • One-Way Functions (OWF): functions that are easy to compute but hard to invert, also called symmetric cryptography. The existence of OWF is the minimal assumption necessary for most interesting applications in classical cryptography, with hash functions being a practical implementation not yet broken by quantum computers.
  • Trapdoor One-Way Functions: OWF with an extra property that there is side-information someone can get which would help invert the function, also called asymmetric cryptograhy. The typical assumption for the existence of point-to-point security, as particular instantiations of trapdoor-OWFs were believed to be RSA, DH etc, all vulnerable to quantum computer attacks. However, a possible solution is to construct post-quantum secure trapdoor OWFs, with NIST proposals such as Learning With Errors (LWE) or elliptic curves.
  • Oblivious Transfer (OT): a two-party protocol where a receiver picks one message out of many from the receiver, without revealing which one and without learning anything about the rest. Although classically OT was believed to be impossible without assuming the existence of trapdoor-OWF, with the use of quantum communication one can construct OT assuming only the existence of OWF.

Security: given that most protocols will not be used in a vacuum, but as sub-protocols for more complex tasks, it is important to prove that the security of a protocol is maintained even when running it in parallel or concurrently, which we call universal composability. However, this might be very difficult proof, and in practice weaker notions are widely accepted:

  • Stand-alone security: this means that the protocol can be run one-after-the-other (but not necessarily in parallel) [HSS11].
  • Concurrency: this means that the protocol can be run along other protocols (in parallel). However, composition with other protocols is more limited than in universal composability.

Type of participants: we can consider two types of participants in the protocol, depending on how much trust we are willing to place on them:

  • Semi-honest adversaries: in this context we assume that the dishonest participants will follow the protocol rules, but they might still try to learn as much information as possible from others.
  • Malicious adversaries: here we really mean that the dishonest participants will do anything allowed by quantum mechanics in order to learn the data of the rest of the participants and/or disrupt the protocol.

1.3 Limitations of MPC

There are also some impossibility results to keep in mind when considering different types of MPC:

  • There cannot be fully black-box secure constant-round qs-MPC [CCL+21], even if parties have access to quantum communication [CCL+25]. This means that we have to either (1) sacrifice black-boxness, i.e. we need to work with specific underlying primitives (like OT) and make use of their structure instead of seeing them as input-output boxes or (2) we need to add round complexity.
  • There cannot be concurrently secure 2PQC protocols (even with quantum computation and/or communication) solely based on post-quantum OWF [GLM23]. Concurrency is essential if we want to use MPC as part of a bigger task, therefore in practice it means that we have to either (1) consider weaker security notions like eps-simulation security, but this adds security threats, or (2) we need specific instances of OWF like LWE.
  • Note that classically quantum-secure OT cannot be based solely on post-quantum OWF, for that quantum communication is necessary, this is why all the below protocols for MPC are either OT-hybrids or assume a variant of LWE.

II. Classical quantum-secure MPC (qs-MPC)

An essential note to keep in mind is that quantum security is not trivially obtained by replacing insecure classical assumptions by post-quantum assumptions (see [ABG+21] page 1). Among other things, this is due to classical provable security usually implicitly making use of techniques that do not translate to the quantum case, such as "rewinding" (one cannot create two copies of an arbitrary quantum state). Therefore, in order to prove that a classical construction is quantum-secure one must first give a full proof of security, even if the original proof was considered “information-theoretically secure” (since rewinding can also be part of ITS proofs).

Regardless of how vast the classical literature on MPC and its variants is, here we only include articles that explicitly state their security against quantum adversaries.

Reference Parties Rounds Set-up Assumptions Security Notes
[HSS11] 2 poly plain model LWE stand-alone
static adversaries		 their proof involves constructing qs-ZK
[HSS11] 2 poly plain model UC-ZK UC
[BDK+20] 2 constant QROM qs-HE
ring-LWE		 game-based
semi-honest adversaries		 their proof involves constructing qs-OT from qs-HE, and showing that Yao’s GC are post-quantum secure
[GS22] (implicit) dishonest majority 2 CRS 2-round qs-OT UC alternatively, without CRS they are only secure against semi-honest adversaries
[ABG+21] dishonest majority constant plain model super-pol LWE
LWE-circularity
classical authenticated channels
classical broadcast channels		 stand-alone their proof involves constructing a CRS in constant rounds (using qs-coin flipping), and constructing constant-round non-malleable commitments (from super-pol LWE)
[ABF+22] 2 2 plain model sub-exp LWE concurrent super-pol simulation their proof involves constructing two-round non-malleable commitments
[LPY23] dishonest majority constant plain model LWE
LWE-circularity		 stand-alone their proof involves constructing constant-round non-malleable commitments (from qs-OWF) and plugging it in [ABG+21]
[GLM23] dishonest majority ? plain model LWE bounded-concurrent
static adversaries		 their proof involves constructing qs-ZK
[CCL+23] 2 constant plain model semi-honest qs-OT eps-sim their proof involves constructing constructing extractable commitments (from qs-OT)
[GLP+25] 2 constant plain model constant-round semi-honest qs-OT concurrent super-pol simulation
[ABF+23] 2 2 plain model super-pol LWE concurrent super-pol simulation
[CLP+25] dishonest majority poly plain model semi-honest qs-OT ? invoke IPS08 in 2PC below
[CLP+25] 2 super-constant plain model semi-honest qs-OT ? their proof involves constructing extractable commitments (from qs-OT)
[CLP+25] dishonest majority constant plain model ? eps-sim their proof involves constructing (a type of) non-malleable commitments (from qs-OWF)

III. Quantum MPC (QMPC)

Recall that quantum MPC refers to Multi-Party Computation where parties can make use of quantum communication in order to jointly evaluate a classical function on private data. The interest on QMPC arises from the fact that classically MPC is proven to be as hard as public-key cryptography (asymmetric cryptography), regardless of the construction (secret sharing, OT, FHE…) but quantumly QMPC is equivalent to Oblivious Transfer [Kil88] which is only as hard as One-Way Functions (symmetric cryptography) [DFL+09]. That is, quantum MPC does not need of public-key cryptosystems to remain secure, and is therefore not threatened by quantum computers.

For the construction of QMPC to maintain the lowered security requirements of QOT, we need (1) the QOT to have a composable security and (2) the QMPC construction to be information-theoretically secure in the OT-hybrid. The prototypical example of a malicious dishonest-majority QMPC construction in the OT-hybrid by Ishai, Prabhakaran and Sahai [IPS08] has the following structure:

  1. Implement a semi-honest majority MPC in the OT-hybrid (say [GMW97]).
  2. Implement a fixed-fraction malicious MPC (say [DI05,DI06]).
  3. Implement IPS' compiler to turn any semi-honest MPC in combination with a fixed-fraction malicious MPC into a malicious dishonest-majority MPC in the OT-hybrid.

Note that although IPS' construction is classical, [Unr10] proved that its UC-security holds in the quantum realm. Moreover, DFL proved that a particular type of commitment ``extractable and equivocal'' are enough in combination with quantum communication to build QOT from OWF. Therefore, we include here a list of articles that construct extractable and equivocal commitments:

Reference Rounds Set-up Assumptions Security Notes
[DFL+09] poly plain model LWE indistinguishable cte with CRS
[BCK+21b] poly plain model qs-OWF stand-alone cte with CRS
bb use of qs-OWF
[GLS+20] poly plain model qs-OWF stand-alone non-bb use of qs-OWF
[GLS+20] constant CRS qs-OWF UC
[CCL+23] constant plain model qs-OWF eps-sim bb
eps-OT → eps-2PC only
[DGI+24] poly plain model qs-OWF stand-alone less states than GLS

Although sufficient, extractable and equivocal commitments are not necessary to build QOT. The articles below consider other paths to construct QOT:

Reference Rounds Set-up Assumptions Security Notes
[Unr07] CRS UC-commitments UC not sure if correct info ?
[LMS23] k+1 like ZK model k-round ZK
(qs-OWF)		 stand-alone if QROM +NIZK → k=1
[LMS23] constant>2 plain model LWE stand-alone UC ?
[BKS23] non-int EPR sub-exp LWE sim random-input OT
[ABK22] non-int QROM
EPR		 random-input OT
can simulate QROM via qs-OWF
[ABK22] 2 QROM random-input OT
can simulate QROM via qs-OWF
[ABK22] 3 QROM can simulate QROM via qs-OWF
[Unr11] linear in circuit depth BQSM poly-bounded UC works only for 2PC

Recently, Bartusek, Khurana and Srinivasan [BKS23] proposed using shared-EPR pairs (from a trusted source) as a resource for building QMPC from quantum communication, promising lower round complexity than the commitment construction. In particular, their proof relies in a special type of QOT built also in the shared-EPR model [ABK+23].

IV. Multi-Party Quantum Computing (MPQC)

Recall that MPQC refers to Multi-Party Computation where parties can make use of quantum communication and computation in order to jointly evaluate a quantum operations on private data. Fortunately, there are compilers to transform any quantum-secure 2PC into a 2PQC [DNS12] and any MPC into MPQC respectively [DGJ+20]. Moreover, the following work analyzed the round-complexity of the compilers:

Reference Parties Rounds Set-up Assumptions Security Notes
[BCK+21a] dishonest majority 5 CRS qs-OT straight-line sim 3 rounds for 2PQC
[BCK+21a] dishonest majority 4 CRS sub-exp LWE
LWE-circularity		 straight-line sim 3 rounds for 2PQC

Therefore, all the works from Section 3 imply 2PQC, just with an additional constant number of rounds, and their security being lifted to the MPQC functionality. In particular, some of these results are explicitly mentioned in the literature:

Reference Parties Rounds Set-up Assumptions Security Notes
[GLP+25] 2 constant plain model constant-round semi-honest qs-OT
auth channel		 concurrent super-pol simulation
[LPY23] dishonest majority constant plain model LWE
LWE-circularity		 constant round implementation of [BCK+21a]’s CRS
[GLM23] 2 or multi LWE bounded-concurrent
[BCK+21b] dishonest majority poly plain model authenticated channels
qs-OWF		 stand-alone

There are also other constructions of MPQC:

Reference Parties Rounds Assumptions Security Notes
[BCG+09] honest majority broadcast channels ITS proof involves verifiable secret sharing
[ACC+21] dishonest majority grow with number of parties qs-MPC

V. Conclusions

In short, quantum-secure MPC without quantum resources requires public-key cryptography (also called or asymmetric cryptography or the existence of trapdoor One Way Functions). In contrast, if we have access to quantum communication, we do not need public-key cryptography and we can build MPC from just One Way Functions (symmetric key). If we have access to quantum computing, we can further construct MPQC in constant added rounds. The general construction of such protocols goes as follows:

  1. First you construct quantum Oblivious Transfer (most likely from a special type of commitments in the plain model, or some other assumption).
  2. Then you build a semi-honest MPC in the OT-hybrid.
  3. You need malicious fraction-dishonest participants MPC.
  4. Finally you can compile the above two MPC constructions in the OT-hybrid to obtain Quantum MPC.
  5. If you have access to a quantum computer, you can further compile your protocol into a MPQC.

The trade-off between quantum-secure MPC and QMPC is that:

  • Quantum-secure MPC con be ensured in 2 rounds of communication assuming the hardness of LWE.
  • We can obtain QMPC just from quantum-secure OWF, in constant rounds of communication if we assume the existence of a CRS or otherwise in polynomial rounds. If we instead consider the QROM, then we can obtain QMPC just from 3 rounds of communication, but using the RO in the construction, not just in the proof technique.

The next steps are to see the relationships between the rest of the parameters such as: the exact number of rounds, the number of qubits etc. And understand in which situation we potentially have quantum advantage.