 Secure Multi-Party Computations
Secure Multi-Party Computations
An Introduction
Christian Zielinski
Last updated in 2015
1 / 52 Secure Multi-Party Computations
Outline
1 Introduction
The problem
Motivation and applications
2 Basic Terminology
Corrupted parties
Deﬁnitions of security
3 Protocols for Multi-Party Computations
Overview
Passive secure protocol
Active secure protocol
References
2 / 52 Secure Multi-Party Computations
Introduction
Outline
1 Introduction
The problem
Motivation and applications
2 Basic Terminology
Corrupted parties
Deﬁnitions of security
3 Protocols for Multi-Party Computations
Overview
Passive secure protocol
Active secure protocol
References
3 / 52 Secure Multi-Party Computations
Introduction
The problem
Secure multi-party computations
Consider n parties, with private inputs x
1
,. .. ,x
n
They want to compute a function f (x
1
,. .. ,x
n
) in a secure way
Security means here
Privacy: The respective inputs remain private
Correctness: The output is guaranteed to be correct
Fairness: Each party learns the result
This should even hold when some parties try to cheat
The following presentation is primarily based on Ref. [1, 2]
4 / 52 Secure Multi-Party Computations
Introduction
The problem
Questions at hand
How to carry out computations without revealing the inputs?
How to deal with cheating (corrupted) parties?
How to deﬁne security formally?
What is the upper limit of corrupted parties allowed?
attacker?
5 / 52 Secure Multi-Party Computations
Introduction
Motivation and applications
Motivation and applications
Multi-party computations (MPCs) have a wide
range of applications
Auctions
Several parties are bidding for a product
Winning party and maximum bid should be determined, without
revealing bids of other parties
Electronic voting schemes
Each party votes for a candidate
Yao’s Millionaires’ Problem, c.f. Ref. 
A group of millionaires wants to ﬁnd out who is the richest
Nobody wants to reveal how wealthy they are
6 / 52 Secure Multi-Party Computations
Basic Terminology
Outline
1 Introduction
The problem
Motivation and applications
2 Basic Terminology
Corrupted parties
Deﬁnitions of security
3 Protocols for Multi-Party Computations
Overview
Passive secure protocol
Active secure protocol
References
7 / 52 Secure Multi-Party Computations
Basic Terminology
Corrupted parties
To discuss secure MPCs, we have to deﬁne security
Hence we have to make assumptions about cheating parties
Typically one models them by considering an adversary
This adversary can take over (corrupt) certain subsets of parties
We assume one adversary, assuming the worst-case scenario of
We assume that at the beginning of the protocol honest (i.e. not
corrupted) parties do not know which parties are corrupted
8 / 52 Secure Multi-Party Computations
Basic Terminology
Corrupted parties
Passive and active security
We distinguish two cases of corruption
Deﬁnitions
Passive corruption:
Adversary has full information of corrupted parties
However, corrupted parties still follow the protocol
Active corruption:
Adversary has full control over the corrupted parties
Might deviate from the protocol to obtain sensitive data
9 / 52 Secure Multi-Party Computations
Basic Terminology
Corrupted parties
Communication channels
Parties have to communicate and coordinate
Deﬁnitions
The information-theoretic model:
All parties have pairwise secure channels
The cryptographic model:
Messages cannot be altered, i.e. the communication channel is
authenticated
Sometimes we take a broadcast channel into account:
All honest parties are assumed to receive the message
10 / 52 Secure Multi-Party Computations
Basic Terminology
Corrupted parties
We deﬁne an adversary structure A P (P ) as a family of
subsets of the parties P
An A-adversary can only corrupt subsets of parties in A
A is monotone
Typically we consider threshold adversaries, i.e. A contains all
subsets of up to some cardinality t
execution, if the total set is in A (otherwise call it static)
11 / 52 Secure Multi-Party Computations
Basic Terminology
Deﬁnitions of security
Security in an ideal world
How to deﬁne security in general?
Here we introduce the concept of an ideal world
real world about the computations then in the ideal case
More formal: Consider a function f, which should be securely
evaluated in a MPC setting
We introduce an ideal functional F
f
SFE
, which is incorruptible
and leaks no private information
Then the MPC problem reduces to the parties securely sending
their inputs to F
f
SFE
12 / 52 Secure Multi-Party Computations
Basic Terminology
Deﬁnitions of security
Secure implementations
In the real world F
f
SFE
is implemented by a protocol π
f
SFE
We call π
f
SFE
a secure implementation of F
f
SFE
world (without help of trusted parties)
More formally assume an A-adversary and let
I = IDEAL
A
F
f
SFE
denote what an adversary learns in the ideal world
Similarly deﬁne
R = REAL
A
π
f
SFE
for the execution of the protocol in the real world
13 / 52 Secure Multi-Party Computations
Basic Terminology
Deﬁnitions of security
Degrees of security
With SIM(I) we denote a simulated protocol using only the
information of I, which we can compare with the real world
protocol R
π
f
SFE
is a perfect secure implementation
No unwanted information leaks
If R only contains additional statistical deviations from SIM(I):
π
f
SFE
is a statistically secure implementation
If R is only computationally indistinguishable from SIM(I):
π
f
SFE
is a computationally secure implementation
Adversary cannot distinguish due to computational bounds
14 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Outline
1 Introduction
The problem
Motivation and applications
2 Basic Terminology
Corrupted parties
Deﬁnitions of security
3 Protocols for Multi-Party Computations
Overview
Passive secure protocol
Active secure protocol
References
15 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Overview
any set of parties up to cardinality t
following results:
Passive Active w/ BC Active w/o BC
Perfect n/2 n/3 n/3
Statistical n/2 n/2 n/3
Computational n n/2 n/2
Table: Maximal obtainable threshold t with n parties (taken from Ref. )
Here we do not discuss general A-adversaries, see Ref. 
16 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Assume n parties and a passive threshold adversary
with threshold t
We construct a perfectly secure protocol in the information-model
theoretic for t < n/2
We employ Shamir’s (t + 1,n)-scheme, calculating
in a ﬁnite ﬁeld F
Assume parties agreed to calculate s
0
= O (s) with secret s
Secret s has been securely shared, so that party i has share s
i
Carry out operations s
0
i
= O
i
(s
i
)
Shares {s
0
i
} allow to uniquely reconstruct s
0
by t + 1 parties
17 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Recap: Shamir’s scheme
Assume n parties and threshold 1 t n
Take a ﬁnite ﬁeld F with |F| n + 1
Let s F be the secret and deﬁne distinct elements
P
1
,. .. ,P
n
F\{0}
Sample a random polynomial p with deg p t 1 and p (0) = s
Protocol:
Distribution phase: dealer shares s
i
= p(P
i
) privately with party i
Reconstruction phase: t parties can reconstruct p(x)
(and hence p(0) = s)
18 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Assume P
i
has share a
i
and b
i
Assume a and b have been shared with (random) polynomials p
a
and p
b
of degree t
We want to securely evaluate c = a + b
i
= a
i
+ b
i
locally
The {c
i
} uniquely determine the polynomial p
c
= p
a
+ p
b
Polynomial p
c
encodes the result as
p
c
(0) = p
a
(0) + p
b
(0) = a + b = c
As degp
c
t we ﬁnd that t + 1 parties can reconstruct c
In the special case of adding a (public) constant k party i just
calculates s
0
i
= s
i
+ k
19 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Recap: Multiplication
The case of multiplying by a (public) constant k is similar
To securely evaluate s
0
= k · s, every party calculates s
0
i
= s
i
· k
Shares {s
0
i
} determine polynomial p
s
0
= k · p
s
, which encodes
p
s
0
(0) = k · p
s
(0) = k · s = s
0
What about the general case of c = a · b with a and b secretly
shared?
Every party can calculate a
i
· b
i
Uniquely determines the polynomial p
c
= p
a
· p
b
Decodes the result as p
c
(0) = p
a
(0) · p
b
(0) = a · b = c
But is of degree deg p
c
2t!
20 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Secure degree reduction (I)
As t < n/2 we can at least uniquely deﬁne p
c
Now securely reduce the degree of p
c
, so that degp
c
t
First observe by means of Lagrange interpolation
a · b =
X
1in
Q
j6=i
1jn
(P
j
)
Q
j6=i
1jn
(P
i
P
j
)
| {z }
r
i
a
i
· b
i
Hence we have a linear combination of the result c in terms of
shares {a
i
· b
i
} at hand
The recombination vector r
1
,. .. ,r
n
can be calculated from
public information
21 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Secure degree reduction (II)
In the next step each party acts as a dealer and re-shares their
share a
i
· b
i
using a polynomial c
i
of degc
i
t
This results in party i having shares u
ji
(j = 1,...,n)
We can then consider the polynomial
c =
X
1in
r
i
· c
i
Observe that degc t and
c (0) =
X
1in
r
i
· c
i
(0) =
X
1in
r
i
· a
i
b
i
= a · b = c
Hence party i computes
c
i
=
X
1`n
r
`
· u
`i
=
X
1`n
r
`
· c
`
(P
i
) = c (P
i
),
which is a (t + 1,n)-SSS share c
i
of c = a · b
22 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Privacy
Party i only deals with their respective shares
After reconstruction party i has share c
i
of result c = a + b or
c = a · b
Shares belong to a (t + 1,n)-SSS, but adversary can only corrupt
up to t parties
No information about other parties’ input besides what is implied
by their shares and the ﬁnal result
23 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
General functions (I)
Using addition and multiplication we can compute more general
functions
We represent the function as an arithmetic circuit:
Figure: A simple arithmetic circuit
24 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
General functions (II)
We can do this without loss of generality (if f is feasible)
Well known in the special case of F = {0,1}, so called Boolean
circuits
Any computable function can be represented using only and and
not gates
a and b can be represented by a · b
not a can be represented by 1 a
The computer is a “proof by example”
In the general case represent a function f : F
n
F by an
arithmetic circuit consisting of addition and multiplication gates
Calculations proceed gate by gate
25 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
The protocol
To compute a function y = f (x
1
,. .. ,x
n
), we represent it as an
arithmetic circuit
Each party begins with private input x
i
F and shares it using a
(t + 1,n)-SSS with all participants
The calculation proceeds gate by gate, so that at each point all
inputs and intermediate results are shared with a (t + 1,n)-SSS
From all remaining gates we randomly choose one for which all
inputs are available
At the end P
i
i
of the ﬁnal result
y = f (x
1
,. .. ,x
n
)
26 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Correctness and privacy
Correctness follows from correctness of Shamir’s scheme and
Privacy follows from the facts that:
The adversary was assumed to only corrupt up to t parties
All values are shared with a (t + 1,n)-scheme, so the adversary
cannot interfere anything about the honest party’s inputs
The corrupted parties only learn their own inputs and outputs
Everybody learns the ﬁnal result (fairness)
27 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Tightness of bound (I)
What if t n/2?
Then there is no protocol with perfect privacy and perfect
correctness
Assuming correctness, a inﬁnite powerful passive advisor can
violate privacy!
An example:
Consider two parties P
i
with input bit b
i
(i = 1, 2)
They want to securely compute r = b
1
b
2
i
{0,1}
?
28 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Passive secure protocol
Tightness of bound (II)
Both are exchanging messages m
ij
, j = 1,...,N.
Deﬁne the transcript
T = (m
11
,m
21
,m
12
,m
22
,. .. ,m
1N
,m
2N
,r)
Let T (b
1
,b
2
) be the set of transcripts for given b
1
and b
2
Can then show that
T (0,0) T (0,1) = Ø
Hence if b
1
= 0 party P
1
can check if T T (0,0) or
T T (0,1) and deduce b
2
Might be unfeasible in the real world
29 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
We now want to deal with an active adversary
We assume that t < n/2 for this part
cannot be taken for granted
Corrupted party might send diﬀerent things to diﬀerent parties
However, in the case discussed here there are eﬀective protocols to
emulate a BC
Corrupted parties can now:
Deviate from the protocol
Give wrong inputs
Might even refuse to respond
30 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Veriﬁable secret sharing schemes
We need a Veriﬁable Secret Sharing (VSS) scheme
A VSS is a SSS, that allows the parties to verify that they have
consistent shares
We implement the active secure protocol by emulating the
previous protocol and:
We make all parties committed to their respective shares
We ensure that all shares are computed correctly
31 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Modeling security
In the ideal world all a corrupted party can do is specify an
alternative input x
0
i
for F
f
SFE
We require that all deviations of the protocol can be modeled by
choosing alternative inputs
What if a corrupted party refuses to give any input?
Possible solution: other parties simulate this party with input
x
i
= 0
32 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Commitments
How can a party P
i
commit to a value a F?
To model this we introduce another ideal functional F
COM
In the real world this will be implemented collectively by the other
parties
Can then commit to a and access a via F
COM
using a interface
with given commands
33 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Interface of F
COM
We now deﬁne an interface for F
COM
consisting of commands
For execution all honest parties have to agree on the command
send to
F
COM
as the implementation will require them to actively
participate
Basic commands for committing and revealing of values
Values committed to not known by other parties than the
committer
Also implementing manipulation commands
Allows us to eventually to emulate F
f
SFE
by F
COM
34 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Basic commands of F
COM
commit of P
i
to a F, denoted by P
i
: [a]
i
a
After successful execution F
COM
stores (P
i
,a)
public commit of all parties to a F
By [a]
i
a we denote the use of the public commit command
to force P
i
to commit to a
F
COM
stores a for all P
i
open
of
a F
to all parties assuming some
[a]
i
is stored, denoted
by a [a]
i
All parties learn a
designated open of a F to party P
j
assuming some [a]
i
is
stored, denoted by P
j
: a [a]
i
Party P
j
learns a
35 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Manipulation commands of F
COM
add of two values a,b F, assuming some [a]
i
and [b]
i
is stored
Denoted by [a + b]
i
[a]
i
+ [b]
i
multiplication by a constant of a F with an α F,
assuming some [a]
i
is stored
Denoted by [αa]
i
α[a]
i
transfer of a F to all parties assuming some [a]
i
is stored
P
j
learns a and commits to it, denoted by [a]
j
[a]
i
multiplication of two values a,b F, assuming some [a]
i
and
[b]
i
is stored
Denoted by [a · b]
i
[a]
i
· [b]
i
36 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Implementation
The transfer and multiplication commands are high level
commands
Can be implemented using the other commands
As an example we show how to implement the multiplication
command
For brevity we omit here the implementation of the transfer
command
Details can be found in 
37 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
The multiplication command
We implement [a · b]
i
[a]
i
· [b]
i
1 P
i
: [c]
i
a · b (P
i
knows a and b)
If P
i
is honest, c will be correct. But P
i
might cheat. Hence every P
k
carries out the following consistency check:
1 P
i
chooses α F uniform at random
2 P
i
: [α]
i
α (commit to α)
3 P
i
: [γ]
i
αb (commit to αb)
4 P
k
broadcasts a challenge e F uniform at random
5 [A]
i
e[a]
i
+ [α]
i
; A [A]
i
(open A)
6 [D]
i
A[b]
i
e[c]
i
[γ]
i
; D [D]
i
(open D)
7 The proof is accepted if D = 0
38 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
The multiplication command
If [c]
i
= [a]
i
· [b]
i
then D = 0.
If P
i
cheated and committed to a c = a · b + ,
then D 6= 0 with probability |F|
1
As F is ﬁnite, D = 0 can still happen coincidentally
There are n t > n/2 honest parties, so probability that all proofs
of honest parties are accepted in the case of cheating is
|F|
n/2
By repeating the proof several times, probability can be further
reduced
We now present the actual protocol using F
COM
39 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
The active secure protocol (I)
Input sharing
Party P
i
holds input x
i
and shares it using Shamir’s scheme
Ensure correct shares and that parties are committed to their
shares
Protocol
1 P
i
: [x
i
]
i
x
i
(commit to input)
2 P
i
chooses a polynomial P
i
(z) = x
i
+
P
t
j=1
α
j
z
j
uniform at random
3 P
i
: [α
j
]
i
α
j
, j (commit to coeﬃcients)
4 P
i
: [P
i
(P
`
)]
i
x
i
+
P
t
j=1
[α
j
]
i
P
j
`
, ` = 1,.. ., n
(evaluating the shares for all parties)
5 [P
i
(P
`
)]
`
[P
i
(P
`
)]
i
, ` = 1,.. ., n
(transfer of all shares to the respective parties)
40 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
The active secure protocol (II)
Arithmetic operations
Function
f
was assumed to be represented by an arithmetic circuit
1 [c]
i
[a]
i
+ [b]
i
Multiplication
1 [d
i
]
i
[a
i
]
i
· [b
i
]
i
(local multiplication)
2 P
i
shares [d
i
]
i
(like in input sharing part),
hence P
`
is committed to [d
i`
]
`
3 [c
`
]
`
P
n
i=1
r
i
[d
i`
]
`
(recombination with recombination vector r
1
,. .. ,r
n
)
41 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
The active secure protocol (III)
Reconstruction
Party P
i
committed to share y
i
If P
j
is supposed to learn y:
1 P
j
: y
i
[y
i
]
i
, i = 1,.. ., n
Note:
If share y
i
is stored in F
COM
, it is consistent
If P
i
cheats, it might be not recorded and the opening fails
As there are n t > t honest parties, still can reconstruct y
42 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Security of the protocol
The protocol ensures correct and consistent shares at every point
However, a corrupted party might refuse to carry out a given
command
If this happens with party P
j
:
Input phase: other parties take input x
j
= 0
and 0-polynomial for P
j
Multiplication: if P
j
has been disqualiﬁed, open its input and
restart the calculation and openly simulate this party
43 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Implementation of F
COM
(I)
Import question: how to implement the ideal functional
F
COM
by
a protocol π
COM
?
We will emulate it by all (honest) parties
Assume information-theoretic scenario with t < n/3
In the cryptographic scenario can relax to t < n/2
We just give an outline of the realization
44 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Implementation of F
COM
(II)
Idea: can implement commit of party P
j
to a F by using a SSS
Then we easy to implement open, add and multiplication by
a constant (and hence transfer and multiplication)
If P
j
is honest, adversary will not learn a
But: If P
j
is corrupted, might give inconsistent shares
Hence we have to force consistent shares
45 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Corrupted shares
Note that if even < n/3 shares are corrupted, the secret is still
uniquely deﬁned
Consider secret s F shares with polynomial p with degp t
The shares are
s = (p(P
1
), .. ., p(P
n
))
Consider an error e F
n
with Hamming-weight w
H
(e) t
Then both s and
˜
s = s + e uniquely deﬁne the same s
46 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Forcing consistent shares (I)
In principle can check for consistent shares, if dealer broadcasts
the polynomial
But this reveals the secret
1 P
j
shares secret s F with shares {s
i
}
2 P
j
picks a r F uniform at random and shares {r
i
}
3 A challenge e F is chosen and i party P
i
computes
a
i
= e · s
i
+ r
i
4 Then make consistency check of {a
i
} for value a = e · s + r
47 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Forcing consistent shares (II)
Value a is randomly distributed, revealing is unproblematic
If shares {s
i
} and {r
i
} are consistent, so are the {a
i
}
Otherwise probability that the {a
i
} are consistent by
coincident is |F|
1
What if the {a
i
} are consistent, but a corrupted party broadcasts
a value ˜a
i
6= a
i
?
We employ dispute control
48 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Dispute control (I)
With each party we associate a public dispute set
D
i
{P
1
,. .. ,P
n
}
At the beginning D
i
= Ø
If some party P
j
j
:
P
j
i
(P
i
is dealer)
If dealer P
i
is honest P
j
D
i
means that P
j
is corrupted
Test is repeated with a
j
= 0 (corrected sharing)
49 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Dispute control (II)
If in one of the repetitions:
P
i
j
) 6= 0 for P
j
D
i
|D
i
| > t (at least one honest party is in dispute with P
i
)
Then: remaining parties accuse dealer P
i
of being corrupt
All messages from P
i
will be ignored from now on
Employing dispute control allows us to ensure consistent shares
and to implement F
COM
(which emulates F
f
SFE
)
50 / 52 Secure Multi-Party Computations
Protocols for Multi-Party Computations
Active secure protocol
Conclusions
We showed how to implement MPCs using Shamir’s Scheme
For a passive threshold adversary we have to require t < n/2
For an active threshold adversary in the information-theoretic
scenario we need t < n/3
Protect against active attacks with VSSs and dispute control
51 / 52 Secure Multi-Party Computations
Appendix
Bibliography
Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen.
Multiparty computation, an introduction.
Contemporary cryptology, pages 41–87, 2009.
Martin Hirt and Ueli Maurer.
Complete characterization of adversaries tolerable in secure
multi-party computation.
In Proceedings of the sixteenth annual ACM symposium on
Principles of distributed computing, pages 25–34. ACM, 1997.
Andrew Chi-Chih Yao.
Protocols for secure computations.
In FOCS, volume 82, pages 160–164, 1982.
52 / 52 