I am covering Quantum Secure Multiparty Computation (QSMPC) in this document, which extends the classical idea of secure multiparty computation into the quantum setting. In classical secure multiparty computation, I want several parties, each holding private input data, to jointly compute a function over their combined inputs without revealing anything about their individual inputs beyond what the output itself reveals. In the quantum version, I use quantum states, quantum channels, and quantum cryptographic primitives to achieve this goal, often gaining stronger security guarantees (grounded in the laws of physics rather than just computational hardness assumptions) or enabling entirely new capabilities like computing on genuinely quantum data.
History and Background
Secure multiparty computation was first formalized classically by Andrew Yao in 1982 with his “Millionaires’ Problem,” and extended into general secure computation protocols by Goldreich, Micali, and Wigderson in 1987. The quantum extension of this idea began emerging in the late 1990s and early 2000s, once quantum cryptography itself matured following the introduction of quantum key distribution by Bennett and Brassard in 1984. Researchers like Crépeau, Gottesman, and Smith published foundational work around 2002 on secure multiparty quantum computation, showing how quantum error correction and quantum secret sharing techniques could be combined to tolerate dishonest participants while computing on quantum information. Since then, the field has expanded to cover both “quantum computation on classical inputs with quantum security” and “quantum computation on genuinely quantum inputs,” with continued research into practical implementations as quantum hardware improves.
Problem Statement
I have $n$ parties, each holding a private input (which may be classical or quantum data), and I want them to jointly compute some function $f(x_1, x_2, \ldots, x_n)$ and learn only the output, while no party (or coalition of up to some threshold $t$ dishonest parties) learns anything about the other parties’ private inputs beyond what is implied by the output itself. The quantum version additionally requires that this security holds against adversaries with quantum computational power and potentially quantum side information, and in the case of quantum inputs, requires correctly computing on superposition and entangled states without collapsing or corrupting them inappropriately.
Core Concepts
- Secret sharing: splitting a private value into pieces (shares) distributed among parties, such that only a sufficient subset of shares can reconstruct the original value.
- Quantum secret sharing: the quantum analog, where a quantum state is split across parties such that only an authorized subset can reconstruct it, exploiting the no-cloning theorem to prevent unauthorized copying.
- Verifiable quantum secret sharing (VQSS): a scheme that additionally allows parties to verify their shares are consistent, protecting against a dishonest dealer distributing corrupted shares.
- Threshold security: the guarantee that the protocol remains secure as long as no more than $t$ out of $n$ parties are dishonest, for some threshold $t$ typically satisfying $t < n/2$ or $t < n/3$ depending on the adversary model.
- No-cloning theorem: the quantum mechanical principle that an unknown quantum state cannot be copied exactly, which underlies much of the extra security quantum protocols can achieve compared to classical ones.
- Quantum error correction: techniques used to protect quantum information from noise and adversarial tampering during distributed computation.
How It Works
I describe the general structure of a quantum secure multiparty computation protocol based on quantum secret sharing and verifiable quantum secret sharing, following the Crépeau-Gottesman-Smith style approach:
- Each party encodes its private input (classical or quantum) using a quantum secret sharing scheme, distributing shares among all $n$ participants.
- The parties use a verifiable quantum secret sharing sub-protocol to confirm that the distributed shares are consistent, catching any party who tries to distribute corrupted or inconsistent shares.
- The parties collaboratively perform the desired computation using quantum gates applied across their distributed shares, following a technique analogous to how classical secure computation applies gates to secret-shared classical bits.
- At intermediate steps, the parties use quantum error-correcting codes and verification procedures to detect and correct any tampering or noise introduced by dishonest parties or the physical quantum channel.
- Once the computation completes, the parties reconstruct the final output from their shares, again using verification to ensure the reconstructed result is correct, without revealing anything about intermediate states beyond the final output.
Working Principle
The core reason this works is that quantum secret sharing, when combined with quantum error correction, allows me to distribute a computation across parties in such a way that no individual party (or small coalition) ever holds enough information to reconstruct another party’s private data, yet the collective computation can still proceed correctly. The no-cloning theorem plays a crucial defensive role: a dishonest party cannot simply copy quantum shares to analyze them without disturbing the state in a detectable way, which is fundamentally different from classical secret sharing where a dishonest party could in principle copy classical bits without detection. Verification steps interleaved throughout the protocol let honest parties catch cheating early, since quantum error-correcting codes are specifically designed so that a limited number of corrupted shares can be detected and corrected without compromising the overall computation.
Mathematical Foundation
I represent a quantum state to be shared as $|\psi\rangle$ in a Hilbert space. A $(t, n)$-threshold quantum secret sharing scheme encodes $|\psi\rangle$ into $n$ shares such that any $t$ or more shares can reconstruct $|\psi\rangle$ exactly, while any fewer than $t$ shares yield no information about $|\psi\rangle$, formally expressed using the reduced density matrix condition:
$$ \rho_{S} = \text{Tr}_{\bar{S}}(|\psi\rangle\langle\psi|) = \frac{I}{d^{|S|}} \quad \text{for any unauthorized set } S \text{ with } |S| < t $$
meaning the reduced state on any unauthorized subset of shares is maximally mixed and independent of the actual encoded state, mathematically guaranteeing zero information leakage. For error correction against dishonest parties who may corrupt up to $t_e$ shares, the quantum error-correcting code used must satisfy the quantum Singleton bound:
$$ n – k \geq 2(d – 1) $$
where $n$ is the total number of shares, $k$ is the number of logical qubits encoded, and $d$ is the code’s minimum distance, which determines how many errors it can correct as $t_e = \lfloor (d-1)/2 \rfloor$.
Diagrams
flowchart TD
A[Each party encodes private input via quantum secret sharing] --> B[Distribute shares among all n parties]
B --> C[Run verifiable quantum secret sharing check]
C --> D{Shares consistent and verified?}
D -- No --> E[Flag dishonest dealer, abort or exclude party]
D -- Yes --> F[Perform quantum gates collaboratively over shares]
F --> G[Apply quantum error correction during computation]
G --> H[Reconstruct final output from shares with verification]
H --> I[Output revealed only to authorized parties]graph TD
Input((Private Input)) --> Encode[Quantum Secret Sharing Encoder]
Encode --> P1[Share to Party 1]
Encode --> P2[Share to Party 2]
Encode --> P3[Share to Party 3]
P1 --> Compute[Joint Quantum Computation]
P2 --> Compute
P3 --> Compute
Compute --> Output((Reconstructed Output))Pseudocode
function QUANTUM_SECURE_MPC(parties, inputs, function_f):
shares = {}
for each party p with input x_p in parties:
shares[p] = QUANTUM_SECRET_SHARE(x_p, threshold_t, num_parties_n)
DISTRIBUTE(shares[p], all parties)
if not VERIFY_SHARE_CONSISTENCY(shares):
ABORT("Dishonest dealer detected")
computation_state = INITIALIZE_JOINT_STATE(shares)
for each gate g in CIRCUIT_FOR(function_f):
computation_state = APPLY_DISTRIBUTED_GATE(g, computation_state, parties)
computation_state = QUANTUM_ERROR_CORRECT(computation_state)
result = RECONSTRUCT_OUTPUT(computation_state, parties)
if not VERIFY_OUTPUT(result):
ABORT("Computation integrity check failed")
return result
Step-by-Step Example
I walk through a simplified conceptual example with 3 parties (Alice, Bob, Carol) computing a joint function over quantum-encoded bits using a (2,3)-threshold scheme, meaning any 2 of the 3 shares can reconstruct information, but 1 alone reveals nothing.
- Alice has private qubit input $|\psi_A\rangle$, Bob has $|\psi_B\rangle$, and they want to compute a joint quantum operation without revealing their individual states to Carol or each other beyond the final result.
- Alice encodes $|\psi_A\rangle$ into 3 shares using a (2,3)-threshold quantum secret sharing code, and distributes one share to herself, one to Bob, and one to Carol. Bob does the same for $|\psi_B\rangle$.
- All three parties run a verification sub-protocol, exchanging syndrome measurement information (without revealing the actual quantum states) to confirm no party distributed a corrupted share.
- The parties collaboratively apply the required quantum gates (say, a controlled-NOT operation representing the joint function) across their respective shares, using distributed quantum gate protocols that operate correctly on secret-shared data.
- After the computation, the parties combine their resulting shares (any 2 of the 3 suffice, since this is a (2,3) threshold scheme) to reconstruct the final output state, while individually, no single party’s share revealed anything about $|\psi_A\rangle$, $|\psi_B\rangle$, or the intermediate computation.
- The final measurement, performed jointly, reveals only the intended output, such as a classical bit representing the result of the computed function.
Time Complexity
The time complexity is typically expressed in terms of the number of quantum gates in the circuit implementing $f$, denoted $|C|$, the number of parties $n$, and the error-correcting code parameters. Each logical gate in the original circuit requires simulating the corresponding operation across the distributed shares, which for many known constructions costs $O(n^2)$ classical and quantum communication per gate due to the interactive verification steps, giving a total protocol complexity of roughly $O(|C| \cdot n^2)$ rounds of communication, with additional polynomial overhead from the quantum error-correcting code’s encoding and decoding circuits, which typically scale polynomially in the code’s block length $n$.
Space Complexity
Each party needs to store $O(1)$ logical qubits worth of share data per input, though the physical qubit overhead depends on the quantum error-correcting code used, typically scaling as $O(n)$ physical qubits per logical qubit for an $n$-party threshold scheme. Across the whole protocol, if the circuit has $|C|$ gates and needs to maintain shares for all intermediate values, the total space usage scales as $O(n \cdot |C|)$ physical qubits distributed across all parties.
Correctness Analysis
Correctness of these protocols is established through a security proof structure borrowed from classical secure multiparty computation, adapted to the quantum setting: I show that the protocol is both correct (honest parties following the protocol correctly compute $f$) and secure (any adversary controlling up to $t$ parties, even with quantum computational power, learns nothing beyond the intended output, formalized using quantum versions of the “ideal-world/real-world” simulation paradigm). The verification steps and error correction at each stage ensure that even if some parties actively deviate from the protocol (an actively malicious, rather than merely curious, adversary model), the honest majority can detect and correct the resulting errors, as long as the number of dishonest parties stays below the code’s correction threshold.
Advantages
- Security guarantees can be grounded in fundamental physical laws (such as the no-cloning theorem) rather than solely computational hardness assumptions, offering resistance even against adversaries with quantum computers.
- It naturally supports computing on genuinely quantum data, which classical secure multiparty computation cannot handle at all.
- Combined with quantum error correction, it can tolerate both noise and active malicious behavior simultaneously.
- It integrates naturally with other quantum cryptographic primitives like quantum key distribution for building comprehensive secure quantum communication and computation infrastructure.
Disadvantages
- Current quantum hardware has limited qubit counts, coherence times, and gate fidelities, making practical large-scale implementations extremely challenging today.
- The communication and computational overhead per logical gate is significantly higher than classical secure multiparty computation.
- Maintaining and correcting quantum states across a distributed protocol over lossy, noisy quantum channels is far more technically demanding than classical error correction over similarly noisy classical channels.
- The theoretical protocols are often studied under idealized assumptions (perfect quantum channels, synchronous communication) that do not yet match real-world quantum networking conditions.
Applications
I see this technology positioned for future use in secure quantum cloud computing, where clients could delegate genuinely quantum computations to remote quantum computers without revealing their private quantum data. It also applies to collaborative scientific research involving sensitive quantum-encoded data, secure quantum voting and auction protocols, and multi-institution collaborative machine learning or data analysis where classical cryptographic guarantees are insufficient against future quantum-capable adversaries, a concern often referred to as long-term “harvest now, decrypt later” threats.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
/* Note: true quantum computation requires quantum hardware or a quantum
simulator library (e.g. Qiskit in Python, or QuEST in C). This C
implementation demonstrates the CLASSICAL secret-sharing backbone
(Shamir's scheme) that underlies the share-distribution structure
used conceptually in quantum secret sharing, since finite-field
secret sharing math is the same pattern quantum threshold schemes
are built on top of (with additional quantum encoding layered on). */
#define PRIME 257 /* small prime field for demonstration */
#define MAX_PARTIES 10
int coefficients[MAX_PARTIES]; /* coefficients[0] = secret, rest are random */
int degree; /* threshold t - 1 */
int mod_pow(int base, int exp, int mod) {
int result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
exp >>= 1;
base = (base * base) % mod;
}
return result;
}
int evaluate_polynomial(int x) {
int result = 0;
int x_power = 1;
for (int i = 0; i <= degree; i++) {
result = (result + coefficients[i] * x_power) % PRIME;
x_power = (x_power * x) % PRIME;
}
return result;
}
void generate_shares(int secret, int threshold, int num_parties, int shares_x[], int shares_y[]) {
degree = threshold - 1;
coefficients[0] = secret;
for (int i = 1; i <= degree; i++)
coefficients[i] = rand() % PRIME;
for (int i = 0; i < num_parties; i++) {
shares_x[i] = i + 1;
shares_y[i] = evaluate_polynomial(shares_x[i]);
}
}
/* Lagrange interpolation at x=0 to reconstruct the secret from t shares */
int reconstruct_secret(int shares_x[], int shares_y[], int t) {
int secret = 0;
for (int i = 0; i < t; i++) {
int num = 1, den = 1;
for (int j = 0; j < t; j++) {
if (i == j) continue;
num = (num * (-shares_x[j] + PRIME)) % PRIME;
den = (den * (shares_x[i] - shares_x[j] + PRIME)) % PRIME;
}
int inv_den = mod_pow(den, PRIME - 2, PRIME); /* modular inverse via Fermat */
int term = (shares_y[i] * num) % PRIME;
term = (term * inv_den) % PRIME;
secret = (secret + term) % PRIME;
}
return (secret + PRIME) % PRIME;
}
int main() {
int secret = 42; /* private input to be shared, standing in for a quantum share's classical analog */
int threshold = 2, num_parties = 3;
int shares_x[MAX_PARTIES], shares_y[MAX_PARTIES];
generate_shares(secret, threshold, num_parties, shares_x, shares_y);
printf("Distributed shares:\n");
for (int i = 0; i < num_parties; i++)
printf("Party %d: (x=%d, y=%d)\n", i + 1, shares_x[i], shares_y[i]);
/* Reconstruct using any 2 of the 3 shares (threshold = 2) */
int recon_x[2] = {shares_x[0], shares_x[2]};
int recon_y[2] = {shares_y[0], shares_y[2]};
int recovered = reconstruct_secret(recon_x, recon_y, threshold);
printf("Recovered secret using parties 1 and 3: %d\n", recovered);
return 0;
}
Sample Input and Output
Running this classical secret-sharing backbone demonstration with secret value 42 gives output similar to (the exact share values vary since coefficients are randomized):
Distributed shares:
Party 1: (x=1, y=193)
Party 2: (x=2, y=87)
Party 3: (x=3, y=238)
Recovered secret using parties 1 and 3: 42
The recovered secret always equals the original secret value regardless of which two of the three shares I use for reconstruction, demonstrating the (2,3)-threshold property that underlies the quantum secret sharing scheme conceptually.
Optimization Techniques
I reduce communication overhead by batching multiple gate operations together before running verification sub-protocols, rather than verifying after every single gate. I use more efficient quantum error-correcting codes, such as CSS (Calderbank-Shor-Steane) codes, which simplify the encoding and decoding circuits compared to generic quantum codes. For near-term hardware with limited qubits, I favor protocols specifically designed for noisy intermediate-scale quantum (NISQ) devices, which trade some theoretical security margin for feasibility on today’s limited quantum computers.
Common Mistakes
I have seen people conflate quantum key distribution (which secures communication) with quantum secure multiparty computation (which secures joint computation), treating them as interchangeable when they solve fundamentally different problems and are often used together rather than as substitutes for each other. Another common mistake is assuming that using quantum techniques automatically eliminates the need for classical secret sharing and verification concepts, when in practice most quantum secure multiparty computation protocols are built directly on top of classical secure multiparty computation theory, extended with quantum-specific primitives layered in. I also notice people underestimate the practical noise and decoherence challenges, assuming theoretical protocols are immediately deployable without accounting for current hardware limitations.
Further Reading
- Crépeau, C., Gottesman, D., Smith, A., “Secure Multi-party Quantum Computation,” STOC 2002. https://dl.acm.org/doi/10.1145/509907.509980
- Ben-Or, M., Crépeau, C., Gottesman, D., Hassidim, A., Smith, A., “Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority,” FOCS 2006. https://ieeexplore.ieee.org/document/4031365
- Broadbent, A., Fitzsimons, J., Kashefi, E., “Universal Blind Quantum Computation,” FOCS 2009. https://arxiv.org/abs/0807.4154
- Hillery, M., Bužek, V., Berthiaume, A., “Quantum secret sharing,” Physical Review A, 1999.
- Wikipedia overview: https://en.wikipedia.org/wiki/Secure_multi-party_computation
- Nielsen, M.A., Chuang, I.L., “Quantum Computation and Quantum Information,” Cambridge University Press. https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE
