Vo Minh Thien Long

What is Secure Multi-Party Computation?

Written by

in

Imagine that several people want to compute something together, but nobody wants to reveal their private data.

For example, suppose Alice and Bob want to know who is richer.

  • Alice has $100,000.
  • Bob has $80,000.

They want to learn only the answer:

Alice is richer than Bob.

But Alice does not want Bob to know that she has exactly $100,000, and Bob does not want Alice to know that he has $80,000.

Is it possible for them to compute the comparison without revealing their actual numbers to each other?

Surprisingly, the answer is yes.

This is the basic idea behind Secure Multi-Party Computation, usually abbreviated as MPC or SMPC.

What is Secure Multi-Party Computation?

Secure Multi-Party Computation is an area of cryptography that allows multiple parties to jointly compute a function over their private inputs while keeping those inputs secret.

P1,P2,…,PnP_1, P_2, \ldots, P_n

and each party holds some private data:

x1,x2,…,xn.x_1, x_2, \ldots, x_n.

They want to compute a function:

y=f(x1,x2,…,xn)y = f(x_1, x_2, \ldots, x_n)

without revealing their individual inputs.

Ideally, each participant learns only what can be inferred from the final output (y).

In other words, MPC attempts to reproduce the result that we would obtain if there were a perfectly trusted third party.

Without MPC, we could imagine doing this:

  1. Everyone sends their private data to a trusted server.
  2. The server computes the function.
  3. The server returns the result.
  4. The server deletes all private data.

The obvious problem is that everyone must trust the server.

Secure Multi-Party Computation tries to achieve the same functionality without requiring such a trusted party.

A Simple Example: The Millionaires’ Problem

One of the most famous examples in MPC is the Millionaires’ Problem, introduced by Andrew Yao.

Alice and Bob are millionaires and want to determine who is richer.

Alice owns:

aa

million dollars, while Bob owns:

bb

million dollars.

They want to compute:

a>b?a > b?

without revealing (a) or (b).

A secure protocol should reveal only one bit of information:

f(a,b)={1if a>b0otherwisef(a,b) = \begin{cases} 1 & \text{if } a > b \\ 0 & \text{otherwise} \end{cases}

Neither participant should learn the other person’s exact wealth.

This simple example captures the core philosophy of MPC:

Compute on private data without exposing the private data itself.

What Does “Secure” Actually Mean?

The word secure can be vague, so cryptography gives it a more precise interpretation.

A secure MPC protocol generally tries to provide several properties.

Privacy

A participant should not learn anything about another participant’s input beyond what can logically be inferred from the result.

If Alice learns only that:

a>ba > b

she should not suddenly be able to determine Bob’s exact value of (b).

Correctness

The protocol should compute the correct result.

If:

f(x1,x2)=y,f(x_1, x_2) = y,

the parties should receive (y), rather than some incorrect value caused by the protocol itself.

Independence of Inputs

A malicious participant should not be able to select their input after learning information about another participant’s secret input.

Fairness

Ideally, either everyone receives the output or nobody does.

In practice, fairness can be difficult to guarantee, especially in two-party computation.

How Can We Compute Without Seeing the Data?

At first, MPC sounds almost impossible.

If nobody sees the inputs, how can anyone perform the computation?

The trick is that cryptographic protocols transform the computation into operations on protected representations of the data.

Several major techniques are used.

1. Secret Sharing

One of the most intuitive ideas is secret sharing.

Suppose Alice has a secret value:

x=10.x=10.

Instead of sending 10 directly, she splits it into random shares.

For example, modulo 100:

x1=37x_1=37

and

x2=73x_2=73

Because:

37+73=110≡10(mod100).37 + 73 = 110 \equiv 10 \pmod{100}.

Party 1 receives 37 and Party 2 receives 73.

Individually, neither share reveals the original value.

But together:

x=x1+x2(mod100).x = x_1 + x_2 \pmod{100}.

More sophisticated secret-sharing schemes allow computations such as addition and multiplication to be performed directly on these shares.

This means the parties can compute a function while the underlying values remain distributed among them.

2. Garbled Circuits

Another famous technique is Yao’s Garbled Circuits, commonly used for secure two-party computation.

The idea is to represent a computation as a Boolean circuit consisting of gates such as:

  • AND
  • OR
  • XOR
  • NOT

Suppose we want to compute:

f(a,b).f(a, b).

Instead of executing the circuit normally, one participant creates an encrypted, or garbled, version of the circuit.

The other participant receives cryptographic labels corresponding to their input values.

They can evaluate the circuit using these labels without learning the intermediate values.

At the end, they recover only the intended result.

The remarkable part is that the evaluator can perform the computation without understanding the meaning of the values moving through the circuit.

3. Oblivious Transfer

Another important cryptographic building block is Oblivious Transfer, usually called OT.

Consider a sender who has two messages:

m0,m1.m_0, m_1.

The receiver chooses a bit:

b∈0,1. b \in {0,1}.

The receiver obtains:

mb.m_b.

However:

  • the sender does not learn (b);
  • the receiver does not learn (m_{1-b}).

In simple terms:

The receiver secretly chooses one message, while the sender remains unaware of which message was selected.

Oblivious Transfer is an extremely powerful primitive and appears in many secure computation protocols.

For example, it is commonly used together with garbled circuits to allow a participant to obtain the circuit labels corresponding to their private input without revealing those input bits.

4. Homomorphic Encryption

Homomorphic encryption provides another way to compute on protected information.

Normally, encryption works like this:

m→Enc(m).m \rightarrow Enc(m).

To perform a computation, we usually decrypt the message first.

Homomorphic encryption allows certain computations to happen directly on ciphertexts.

For example, in an additively homomorphic encryption scheme:

Enc(a)⋅Enc(b)Enc(a) \cdot Enc(b)

may produce something equivalent to:

Enc(a+b).Enc(a+b).

The party performing the operation never needs to learn (a) or (b).

This property can be extremely useful in privacy-preserving protocols.

Semi-Honest vs. Malicious Adversaries

An important question in MPC is:

What happens if one of the participants cheats?

Cryptographic protocols usually define an adversary model.

Two common models are the semi-honest and malicious models.

Semi-Honest

A semi-honest participant follows the protocol correctly but attempts to learn additional information from everything they observe.

For example, Bob follows every instruction exactly but records all received messages and tries to analyze them afterward.

Semi-honest security is often easier and more efficient to achieve.

It is therefore frequently used as the starting point when designing new MPC protocols.

Malicious

A malicious participant can behave arbitrarily.

They might:

  • send incorrect values;
  • modify messages;
  • skip protocol steps;
  • use malformed cryptographic objects;
  • choose inputs strategically;
  • attempt to manipulate the output.

Protecting against malicious participants usually requires additional mechanisms such as:

  • commitments;
  • zero-knowledge proofs;
  • consistency checks;
  • message authentication;
  • cut-and-choose techniques.

As a result, maliciously secure MPC protocols are usually more expensive than their semi-honest counterparts.

An Important Idea: Simulation-Based Security

One of the most elegant concepts behind modern MPC is simulation-based security.

Imagine an ideal world where a completely trusted party exists.

Alice sends (x) to the trusted party.

Bob sends (y).

The trusted party computes:

f(x,y)f(x, y)

and returns the result.

Nobody learns anything else.

This is clearly secure, assuming the trusted party behaves perfectly.

The goal of an MPC protocol is to make the real-world protocol behave essentially like this ideal scenario.

Very roughly, we want to show:

Real Protocol≈Ideal Trusted Party.\text{Real Protocol} \approx \text{Ideal Trusted Party}.

If everything an attacker sees in the real protocol could have been generated using only the information available in the ideal world, then the attacker has not learned anything extra.

This simulation-based definition is one of the foundations of modern cryptographic security proofs.

Where Is MPC Useful?

MPC becomes particularly useful when multiple organizations want to collaborate but cannot directly share their datasets.

Consider several hospitals.

Each hospital has private patient data.

They might want to calculate statistics across all hospitals:

Average treatment success rate\text{Average treatment success rate}

without creating one centralized database containing every patient’s medical records.

MPC potentially allows them to jointly compute the statistic while keeping individual datasets private.

Another example is fraud detection.

Two banks may want to identify suspicious accounts appearing in both databases.

However, neither bank wants to expose its entire customer list.

This leads to an important special case of MPC called Private Set Intersection.

Private Set Intersection

Suppose Alice has a set:

A=1,3,5,7A = {1,3,5,7}

and Bob has:

B=2,3,6,7.B = {2,3,6,7}.

They want to calculate:

A∩B.A \cap B.

The answer is:

3,7.{3,7}.

A Private Set Intersection protocol allows them to discover these common elements without revealing the other elements in their sets.

Ideally, Alice does not learn:

2,6{2,6}

and Bob does not learn:

1,5.{1,5}.

PSI has many practical applications, including:

  • contact discovery;
  • fraud detection;
  • private database matching;
  • advertising measurement;
  • cybersecurity threat intelligence;
  • medical data collaboration.

Private Set Union

A closely related problem is Private Set Union, or PSU.

Instead of calculating:

A∩B,A \cap B,

the participants want:

A∪B.A \cup B.

For example:

A=1,3,5A = {1,3,5}

and

B=3,4,6.B = {3,4,6}.

The union is:

A∪B=1,3,4,5,6.A \cup B = {1,3,4,5,6}.

At first glance, PSU may appear simple, but designing efficient protocols that reveal only the union and nothing more about the participants’ datasets can be surprisingly challenging.

Both PSI and PSU are examples of how the broad idea of MPC can be specialized for particular applications.

Is MPC the Same as Homomorphic Encryption?

Not exactly.

Homomorphic encryption is a cryptographic primitive or technique, while MPC is a broader cryptographic problem and framework.

An MPC protocol might use:

  • secret sharing;
  • oblivious transfer;
  • garbled circuits;
  • homomorphic encryption;
  • pseudorandom functions;
  • zero-knowledge proofs;

or combinations of several techniques.

Different approaches make different trade-offs between:

Computation\text{Computation}
Communication\text{Communication}
Security\text{Security}

and

Scalability\text{Scalability}

There is rarely one protocol that is optimal for every application.

Why Isn’t MPC Used Everywhere?

The main problem is efficiency.

Imagine a normal computation taking:

1 second.1 \text{ second}.

Transforming the same computation into a cryptographically secure MPC protocol may require much more:

  • CPU computation;
  • network communication;
  • memory;
  • cryptographic operations;
  • interaction between participants.

Network latency can become especially important because many protocols require multiple communication rounds.

For large datasets containing millions of elements, seemingly small overheads can quickly become significant.

As a result, a large part of MPC research focuses not only on proving that secure computation is possible, but also on making it practical.

The Bigger Idea

Secure Multi-Party Computation challenges a very traditional assumption in computing.

Normally, we assume:

To compute on data, somebody must see the data.

MPC shows that this assumption is not always necessary.

Cryptography allows us to separate:

having access to data\text{having access to data}

from

being able to compute with data.\text{being able to compute with data}.

That distinction is extremely powerful.

As more organizations depend on collaboration across sensitive datasets, technologies such as MPC, private set operations, homomorphic encryption, and zero-knowledge proofs are becoming increasingly important.

The long-term goal is simple to describe, even if it is difficult to achieve:

Allow people to benefit from shared computation without requiring them to surrender their private information.

And that is essentially what Secure Multi-Party Computation is about.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

More posts