Transcript ((x 1 ,y 1 ),(y 2 ,x 2 )) - Weizmann Institute of Science

General
Cryptographic
Protocols
(aka secure multi-party computation)
Oded Goldreich
Weizmann Institute of Science
Joachim (and Claus)
(and me)
A general framework (for casting crypto problems)
An m-ary (randomized) functionality (desired process)
F:({0,1}n)m → ({0,1}n)m (where m2 denotes the # of parties).
P1
x1
P2
x2
Pm
xm
(local inputs)
y1
y2
ym
(local outputs)
(y1,y2,…,ym) = F(x1,x2,…,xm)
Desired solution: delivery of outputs as if the
operation was performed by a trusted party.
Secure Multi-Party Computation (Crypto Protocols)
A secure protocol obtains the same effect as the
operation of a trusted party.
Thus, mutually distrustful parties emulate the effect of a trusted party.
On the feasibility of General Secure MPC
Meta-THM: General Secure MPC is possible
under a variety of natural assumptions.
• Assuming an honest majority + TDP
• Allowing abort + TDP
(i.e., not considering early termination as breach of security)
[reflected in the ideal model]
• Assuming a 2/3-majority + private channels.
TDP == Trapdoor Permutations (which exist, e.g.,
assuming the intractability of factoring integers).
Two-Step construction of General Secure MPC
E.g., assuming an honest majority + TDP
1. Constructing protocols that are secure wrt semi-honest
(“honest-but-curious”) adversaries. [“privacy only”]
2. Enforcing semi-honest behavior via ZK proofs (+commit)
T = public information (transcript)
Sender (secret input s)
Supposed to send y = f(T,s)
Receiver
y’
Idea: provide a ZK proof that s’ s.t y’=f(T,s’)
Secure (private) MPC in the semi-honest model.
We assume a TDP (trapdoor permutation).
Reduce to deterministic functionalities with same outputs.
Let C be a GF(2) circuit for computing the m-ary function.
Idea: The parties propagate shares of the values of all
wires in C from the input wires of C to its output wires.
x
y
x1
y1
x2
y2
x3
y3
xm
ym
z1
z2
z3
zm
(x = x1+x2+x3 +… +xm
y = y1+y2+y3 +… +ym)
z = z1+z2+z3 +… +zm
Secure (private) MPC of the gate functionality.
The parties need to
propagate shares of the
values through each gate.
(Shares with subscript i
belong to party i.)
x
y
x1
x2
x3
xm
y1
y2
y3
ym
z1
z2
z3
zm
(x = x1+x2+x3 +… +xm
y = y1+y2+y3 +… +ym)
z = z1+z2+z3 +… +zm
Easy case – addition gate: Set zi  xi+yi (local computation).
Similarly for negation: zi  xi+1 if i=1 and zi  xi o.w.
Hard case – multiplication gate: we wish
z1+z2+… +zm = (x1+x2 +… +xm) ∙ (y1+y2 +… +ym)
(use algebra)
(x1+x2+… +xm) ∙ (y1+y2+… +ym) = ∑i xiyi + ∑i≠j (xiyj+xjyi)
local
z
(i )
i
2PC
zi( j )  z (ji )
( j)
(i )
( j)
(i )
(
x
y
,
x
y
)

(
z
,
z
)
z

z
Secure 2-PC of
s.t. i
i i
j j
i
j
j  xi y j  x j yi
Recall: General secure MPC “reduces” to secure 2PC
of ((x1,y1),(y2,x2)) → (z1,z2), where (z1,z2) is random
subject to z1+z2 = x1x2+y2y1.
Inputs:
Outputs:
1st
x1,y1
r
2nd
x2,y2
r+x1x2+y1y2
1st
Inputs:
x,z
Outputs: -
2nd
y
z+xy
In the i-th invocation use
inputs (xi,ri) and yi,
where ri is a random bit.
Each party sets its final
output = sum of both
intermediate outputs.
(OT)
Sender
Sender sets
= z+yx.
sy
Inputs: s0,s1
Outputs: -
Receiver
c
sc
Sender
Implementing OT
Receiver
Inputs: s0,s1
Outputs: -
(OT = Oblivious Transfer)
c
sc
Background: assuming a collection of TDP {fi:Di→Di}
with hardcore predicate b
Inputs:
Sender
s0,s1
Receiver
c
selects a permutation f
(with trapdoor)
select xc,y1-cDi
compute yc=fi(xc)
find the f-preimages of both
denoted z0 , z1, and send
b(z0)+s0 , b(z1)+s1
recover by + b(xc)
Conclusion: General Secure MPC is feasible
• MPC
for an honest majority, assuming TDP
• Similar ideas (+more) yield MPC wo honest majority, but
when “allowing abort” (i.e., not considering early termination as
breach of security). (Also assuming TDP).
• Assuming a 2/3-majority + private channels.
Meta-THM: General Secure MPC
(i.e., secure emulation of trusted parties)
is possible under a variety of natural
assumptions.
The End
The slides of this talk are available at
http://www.wisdom.weizmann.ac.il/~oded/T/mpc.ppt
A related survey is available at
http://www.wisdom.weizmann.ac.il/~oded/s_mpc.html
Zero-Knowledge Proofs
zi( j )
A secure protocol (i.e., ZK proof) obtains the same
effect as the operation of a trusted party.
Thus, mutually distrustful parties emulate the effect of a trusted party.
Secure 2-PC of the Inner Product mod 2 of two vectors
Recall: General secure MPC “reduces” to secure 2PC
of the inner product mod 2 of two input vectors
held by the two parties. (For us n=2 suffices.)
1st
Inputs: x1,…,xn
Outputs:
r
In the ith invocation
use inputs (xi,ri) and
yi, where ri is a
random bit.
2nd
y1,…,yn
r+∑ixiyi
1st
Inputs:
x,z
Outputs: -
2nd
y
z+xy
Final output = sum of
all n outputs.
Sender
Inputs: s0,s1
Outputs: -
Receiver
c
sc