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?

•

How does this bound depend on the assumption made about the

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

•

Only the result is made public, the votes remain secret

•

Yao’s Millionaires’ Problem, c.f. Ref. [3]

•

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

Corrupted parties

Adversaries

•

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

coordinated corrupted parties (monolithic adversary)

•

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

•

Adversary has no access to messages sent between honest parties

The cryptographic model:

•

The adversary has access to all messages sent

•

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

(consensus broadcast)

10 / 52

Secure Multi-Party Computations

Basic Terminology

Corrupted parties

A-adversaries

•

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

•

An adaptive A-adversary can corrupt a new party during

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

•

A protocol is secure if an adversary does not learn more in the

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

and receive the ﬁnal result

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

if an adversary

is unable to learn more about the computations than in the ideal

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

•

If R contains no more information than SIM(I):

•

π

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

Overview

Threshold adversaries

•

We focus on threshold adversaries, i.e. the adversary can corrupt

any set of parties up to cardinality t

•

In the information-theoretic with adaptive adversaries we have the

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. [1])

•

Here we do not discuss general A-adversaries, see Ref. [1]

16 / 52

Secure Multi-Party Computations

Protocols for Multi-Party Computations

Passive secure protocol

Perfect security with passive adversary

•

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

Recap: Addition

•

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

•

Each party adds c

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

1≤i≤n

Q

j6=i

1≤j≤n

(−P

j

)

Q

j6=i

1≤j≤n

(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

1≤i≤n

r

i

· c

i

•

Observe that degc ≤ t and

c (0) =

X

1≤i≤n

r

i

· c

i

(0) =

X

1≤i≤n

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 (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

broadcasts its share y

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

algorithms for addition and multiplication

•

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

•

Both have additional randomness r

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

Active adversaries

•

We now want to deal with an active adversary

•

We assume that t < n/2 for this part

•

In the presence of an active adversary a broadcast (BC) channel

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?

•

The protocol can potentially deadlock

•

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

•

Add and multiply committed shares

•

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 [1]

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

Addition

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

•

Addition cannot fail

•

Multiplication: if P

j

has been disqualiﬁed, open its input and

restart the calculation and openly simulate this party

•

Reconstruction was already discussed

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

Instead use algorithm:

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

broadcasts an inconsistent share ˜a

j

:

•

P

j

is added to D

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

broadcasts a polynomial with p(P

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

•

For more information refer to Ref. [1, 2]

51 / 52

Secure Multi-Party Computations

Appendix

For Further Reading

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