> k(
/00DTimes New Romanvx:0DComic Sans MSnvx:0B DSymbolans MSnvx:00DWingdings MSnvx:0C .
@n?" dd@ @@`` :iF(U 2 50]A107%0,+* 56789:;=>?@BDEFGHIJKLMNOPSTVWX/[,\^,$B$cd$f+ijklmnoprstuvwxy0e0e
A A> 8c8c
?1 d0u0@Ty2 NP'p<'pA)BCDES"p33!33@9ʚ;F%6ʚ;g4@d@d,x:0pppp@<4!d!dX
0v<4ddddX
0v<4ddddX
0U+0___PPT10
v___PPT9XP?%̕*RoundOptimal Secure TwoParty Computation++
L
MotivationRound complexity is a central measure of protocol efficiency.
Minimizing the number of rounds is often important in practice.
Lower and upper bounds have deepened our understanding of various tasks& pY9For example& ZK [FS89, GO94, GK96a, GK96b, BLV03, etc.], NIZK [BFM88, etc.], WI [FS89,DN00,BOV03]
Concurrent ZK [DNS98, KPR01, CKPR01, PRS02]
Commitment, identification schemes, &
&
2party and multiparty computation [BMR90, IK00, GIKR01, L01, KOS03, etc.]*
"#) This workWe concentrate on secure twoparty computation
Encompasses many functionalities of independent interest (e.g., ZK)
Important special case of MPC without honest majority
Interestingly, exact round complexity of 2PC was not previously known!/G
d
This work (1)PWe exactly characterize blackbox round complexity of secure 2PC!
THM1: Impossibility result for any blackbox 4round cointossing (also XOR, other functionalities& )8CeDe
This work (2)
THM2: 5round secure 2PC protocol for any functionality, based on trapdoor perms* (e.g. RSA, Rabin) or Homomorphic Encryption (e.g. DDH).
J!a
This work (3)o
THM3: 5round secure 2PC protocol an adaptive adversary corrupting any one party without erasure in 5 rounds. Zp$Prior work (2PC)Honestbutcurious setting
4 rounds using trapdoor perms. [Yao86]
3 rounds using numbertheoretic assumptions (optimal) [Folklore]
Malicious case
Compiler for any protocol secure in honestbutcurious setting [GMW87]
Round complexity?rdhZd[ZhIRound complexity of 2PC?Upper bounds
O(k) rounds [GMW87]
O(1) rounds [Lindell01]
Unspecified, but roughly 2030 rounds
Lower bounds (blackbox)
No 3round ZK [GK96]
No 3round cointossing [Lindell01]
,&9
&9Security definition~We use the standard definitions of [GMW87, GL90, MR91, Ca00]
This will be an informal review, focusing on a static adversary0?(SetupFunctionality F = (F1, F2), possibly randomized; player Pi gets Fi(x, y)
In real world, players execute a protocol to compute F
In ideal world, a trusted party computes F for the players~ y@wIdeal model8Players send x, y to TTP
Malicious player can send any value it likes; honest party sends its input value
If no value sent, a default value is used
TTP chooses uniformlyrandom r; sends v1 = F1(x, y; r) to P1
If P1 aborts, TTP sends v2 = ^ to P2
Else, TTP sends v2 = F2(x, y; r) to P2d{Z=dLZ
{'Ideal modelLet Viewi denote the view of Pi
Let (B1, B2) be strategies
Define IDEAL = (B1(View1), B2(View2))
Note: for Bi honest, Bi(Viewi) = viva$!
,m
Real modelPlayers execute protocol&
Let (A1, A2) be strategies
Define REAL = (A1(View1), A2(View2))
Again, if Ai honest, then Ai(Viewi) = viBZ) tSecurity&
0A pair of strategies is admissible if at least one is honest
Protocol is secure if for all admissible PPT (A1, A2) in the real world, there exist admissible expected polytime (B1, B2) in ideal world such that REAL and IDEAL are comp. indistinguishable
Even with auxiliary inputs&
'AFBlackbox securityThe definition of security requires: " (malicious) Ai, $ (malicious) Bi, s.t. Bi satisfies the condition& .
Blackbox security imposes stronger requirement:$ (S1, S2), " (malicious) Ai, (malicious) Bi =SiAi satisfies the condition& x&6More formally& For malicious A1, define B1 as follows:
B1(x, z; r, r ) = S1A1(x, z; r)(x; r )
S1 not given auxiliary input z
Exp. running time of S1 is a fixed polynomial, independent of A1
But running time of B1 depends on A1
The above formulation avoids some technical problems& (dFZAd[Z
7 Theorem 1
No secure (blackbox) 4round protocol for flipping w(log k) coins
This rules out 4round protocols for other functionalities as well (e.g., XOR)
(Note: 3round protocols for O(log k) coins do exist [Bl82, GMW87])
Details: (next)COT4O,3333 Intuition
W.l.o.g., P2 sends the first message
No way to simulate for a malicious P1 who aborts very often
Sending different msg1 doesn t help
P1 starts over with new randomness [GK]
Sending different msg3 doesn t help
P1 anyway aborts very often "d$*$>(Proof details I0Let s() be the expected r.t. of S1
Define A1 as follows:
Use msg1 to define random string for an honest execution of the protocol (using O(s)wise independent hash function)
After msg3, compute coin c; abort unless first (3log s) bits of c are 0
Note: here we use c = w(log k)9dZ!
x>Proof details IIREAL is nonaborting with noticeable probability 1/s3
Thus, IDEAL must be nonaborting with roughly the same probability
Conditioned on good coin from TTP, S1 must force A1 not to abort with probability essentially 1fd6lProof details III Run S1 for at most 2s steps
Now, strict polytime
Conditioned on good coin from TTP, forces A1 not to abort with probability essentially 1/2fuE/Proof details IVDefine A2 as follows:
Feed good coin to S1; guess i, j
Send ith query of S1 to P1 as msg1, return msg2 to S1
Send jth query of S1 to P1 as msg2
Answer other queries of S1 internally, by either aborting or playing the role of A1
8,>3o Proof details VAnalysis:
Conditioned on correct guesses of i, j, honest player P1 outputs good coin with probability essentially 1/2
Probability of correct guess > 1/4s2
So probability that honest P1 outputs good coin is at least 1/8s2 > 1/s3
A2 noticeably biases the coin!
:[%!Implications
ZNo 4round (blackbox) protocol for general secure computation
Note: Could also derive from [GK]&
& but our techniques rule out 4round protocols for wider class of functions.?o?oSomewhat easier task[folklore]: kround with one player learning the output (k+1)round with both players learning the outputs
the output in the kth round includes encrypted and MAC ed output for other player.
SO: we need a 4round protocol where, say, player 1 gets the output.l85>D3333observation
It suffices to consider deterministic functionalities.
Rest of the talk: we show a 4round protocol tolerating malicious players where player 1 learns the output.
0d8oRest of the talk3round protocol for semihonest players
Background tools
Some of our new techniques
Our 4round protocol (if time permits)
Proof of security (if time permits)
Modifications needed for Dynamic Adv.
Conclusions.
"Recall: 12OT [EGL]VSender has (v0, v1);
Receiver has b,
12OT:
Receiver gets vb
Sender gets nothing^(
%
/Semihonest 12OT [EGL,GMW],S: generate td perm. (f, f1); send f
R: yb = f(zb), y1b rand; send (y0, y1)
S: send ui = h(f1(yi))vi, for i=0,1
R computes vb = h(zb)ub
Note: extends easily for strings in
semihonest setting>" d8" d833.Yao s garbled circuit DAlgorithms (Y1, Y2) s.t.:
Y1(y) outputs circuit C, inputwire labels {Zi,b},
[C represents F(.,y)]
Y2(C, Z1,x1, & , Zk,xk) outputs v
Correctness: v = F(x, y).o

$
33333round semihonest 2PCPlayer 2 sends Yao s C, f for OT
Player 1 sends OT pairs {(yi,0, yi,1)}
Player 2 sends {(ui,0, ui,1)} to Player 1.
Player 1 recovers v.t" " =33Malicious 2PC?Standard method [GMW87] increases roundcomplexity:
Coin tossing into the well to fix random tapes of players;
Players commit to their inputs;
ZK arguments of correctness after every round;
High round complexity of compilationD4%4%Malicious 2PC in 4 roundsOur goal: do everything in 4 rounds, (player 1 gets the output) forcing good behavior from both sides!
Intuition: do everything as early as possible but & things don t fit we need new tricks to cram it all..
Surprise: we must delay proofs to make it work.:d(+Reminder:3Round WI proofs [FS] ,P claims that graph G has a HC
PV: commit n cycle graphs C1..Cn
VP: random nbit string Q
PV: for each bit of Q, either
open entire matrix Ci OR
show perm of G onto Ci open nonedges of G in Ci.
!d_dMZd<OBSERVATION Graph G can be determined in the last round.
IF G is determined in the 1st round this is WI proof of knowledge
IF G is determined in the 3rd round this is only a WI proof, but it is still sound!!
#NEW PROPERTIES FOR 3ROUND WIPROOF$$,Next: [FS] 4round ZK<
Q can we get similar result for [FS] 4round ZK argument?
:<;1[FS] 4round ZK argument: 2 interleaved WIproofs22,[FS] 4round ZKargument2 interleaved WI proofs:
PV: gives y1,y2 s.t. f(a1)=y1,f(a2)=y2 and WI proof of this fact (3 rounds)
PV: WI proof of witness w that x is in L or w is one of the a s (starting on the 2nd round). Total of 4 rounds.
Proof of knowledge; also ZK.
dddd33 y 33New FS properties needed:,VObservation: In FS, prover needs to determine the statement in the second round.
Goal: to defer parts of statement to last (4th) round.
Previous ideas are not sufficient& #C,
"bTechnical lemma  we extend [FS] to FS so that:.2%(( (FS is a 4round Zeroknowledge argument where statements can be Postponed .
FS define conjunctive parts of statement in the second round (with knowledge extraction) and part of statement in the 4th round (without extraction but still sound!)
It is of independent interest (requires equivocal commitment, some other tools)
dGZNyP1[FS] 4round ZK argument: 2 interleaved WIproofs22,OUR PROTOCOL PROOFFLOWS,\Simulation on both sides? we need more tools& //,Malicious player 2 gains nothing by using nonrandom tape in Yao.
Player 1 cannot freely choose his random tape, but fullblown cointossing is not necessary (i.e., we don t need simulatability on both sides)
Player 2 has to commit Yao s garbled circuit in round 2, but the simulator need to open it arbitrary, so use equivocal comm.dNZB m33Equivocal commitments338(Informal): in real execution, sender committed to a single value; in simulation, can open arbitrarily
Construction: Equiv(b) = Com(b0), Com (b1)ZK argument that b0 = b1Open by opening either b0 or b1
Can fold ZK argument into larger statement already used in 4th round of FS
dg
>!!!<And now& the 4round protocol& ,!(only 4 slides, 1 msg per slide)*Round 1: P1(x)P2(y)0:P1 commits {(ri,0, ri,1)}; (random)
starts 3round WI PoK of either ri,0 or ri,1;
Starts FS 1 (statement TBA by P2 partly in round 2, partly in round 4)l0
;,Round 2: P1(x) P2(y)06
P2 Sends challenge for WI PoK
P2 Sends trapdoor perm {fi,b} for OT, and random values {r i,b};
P2 commits to inputwire labels for Yao
Equiv. commitment to Yao s garbled C(y);
FS 2 (proving correctness as part of the statement), part to be determined now, part in fourth round
Xd9
Z
c.Round 3: P1(x) P2(y) ,For each bit i of input x, set (for OT):
yi,xi = fi,xi(z);
yi,1xi = ri,1xir i,1xi;
WI PoK (final round 3), where the statement includes the fact that one of y s is correctly computed for each i.
FS (round 3)
*0*
.Round 4: P1(x) P2(y) 6Complete OT (i.e. P2 inverts f s and xor s with Yao s input wires), sends these to P1
FS final (4th) round, where P2 proves correctness of all its steps, including OT of this round.
P2 Decommits equivcommit of Yao s circuit, so that P1 can compute!
0cSIMULATION FOR CHEATING P2,/Simulating view of ADVP2 interacting with SIM1 SIMADVP20
SIM commits {(ri,0, ri,1)}; (random)
starts 3round WI PoK of either ri,0 or ri,1;
Starts FS 1 (statement TBA by P2 partly in round 2, partly in round 4)
Easy to simulate, we don t need to know x.d+d0
;+&Round 2: SIMADVP20Sends whatever it wants to SIM*Round 3: SIM ADVP2 ,For each bit i of input x, set (for OT):
yi,xi = ri,xir i,xi;
yi,1xi = ri,1xir i,1xi;
PoK (final round 3), is easy, since it s a true statement by the simulator.
FS (round 3) (play honestly)
>*d4Zjdd*k&Round 4: SIMADVP20Sends whatever it wants.
If all valid, we rewind, and extract y (using the fact that the msg commitment in the second round is a proof of knowledge, so we can extract)
Now, send y to the trusted party and we are done, and player 1 gets his output.
SIMULATION FOR CHEATING P1,5(simulating view of ADVP1 interacting with the SIM2)ADVP1 SIM0
Sends whatever it wantsADVP1 SIM0SIM send to P1 trapdoor perm {fi,b} for OT, and random values {r i,b}; as before
SIM commits to garbage (instead of inputwire labels for Yao)
SIM equiv. commitment to garbage (instead of Yao s garbled C(y); )
For FS 2 use ZK simulator (proving correctness as part of the statement), part to be determined now, part in fourth round
XQd
t*Round 3: ADVP1 SIM ,Adv sends whatever it wants
(ADVP1 SIM0
If all proofs in 3rd round are OK,rewinds and extracts half of r s from first round
After extraction, can get ADVP1 OT input values, this defines his input x.
Send x to trusted party, get the output. (cont on next slide),dADVP1 SIM0
8Now, simulate the Yao s circuit, and decomment equivocal commitment of Yao as needed, and prepare OT answers as needed.
Continue using ZK simulator for FS OverviewNo erasure of [BH].
Use adaptivelysecure encryption to encrypt each round (a la [CFGN96])
We avoid expensive keygeneration phase (using stronger assumptions:
Assume simulatable cryptosystem [DamgardNielsen 2000]
Maintain round complexity by not encrypting the first roundX[dZ[}Adaptivelysecure encryptionTo encrypt a single bit v:
Receiver generates {(pki,b)} but only knows secret key for one of each pair
Sender computes {(Ci,b)} where, in each pair, one ciphertext is random and one is an encryption of v
Receiver decrypts using keys he knows; takes majorityRECONCLUSIONSFOR BBsimulation, we completely closed 2party roundcomplexity: (both upper and lower bounds =5) for ANY 2party computation!
Gap for nonBBsimulation: either 4 or 5 rounds (we need at least 4 rounds even for nonBB), but 4 or 5 is still open& dx 0` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@0?" dn(@ 5 d " @ ` n?" dd@ @@``PR @ ` `p>>JB(
6܍ P
NClick to edit Master title
0hn
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
0 ``
X*
0,
`*/48
H
0h ? ̙33 Default Design P(
P
P
0g< P
<
X*
P
0,l< <
Z*
P
60q< `P <
X*
P
6(u< ` <
Z*H
P0h ? ̙3380___PPT10.2i00t(
tr
t S:p:
t
Z<:>?"
OJonathan Katz
U. Marylandn
t
Z<>?"
ORafail Ostrovsky
U.C.L.A.n H
t0h ? ̙33y___PPT10Y+D=' )=
@B +m
0$(
r
S`:P
:
r
S8::
H
0h ? ̙33y___PPT10Y+D=' )=
@B +m
0$(
r
S:P
:
r
S:`:
H
0h ? ̙33y___PPT10Y+D=' )=
@B +y
00D0(
Dx
D c$:P
:
x
D c$::
H
D0h ? ̙33y___PPT10Y+D=' )=
@B +y
0@H0(
Hx
H c$:P
:
x
H c$::
H
H0h ? ̙33y___PPT10Y+D=' )=
@B +y
0`P0(
Px
P c$:P
:
x
P c$4:P0:
H
P0h ? ̙33y___PPT10Y+D=' )=
@B +y
0X0(
Xx
X c$ĸ:P
:
x
X c$:P0:
H
X0h ? ̙33y___PPT10Y+D=' )=
@B +m
0$(
r
S0:P
:
r
S::
H
0h ? ̙33y___PPT10Y+D=' )=
@B +m
0$(
r
S̡:P
:
r
S::
H
0h ? ̙33y___PPT10Y+D=' )=
@B +m
0l$(
lr
l S:P
:
r
l S`::
H
l0h ? ̙33y___PPT10Y+D=' )=
@B +
00(
x
c$:P
:
x
c$::
H
0h ? ̙33
00(
x
c$:P
:
x
c$Ԇ::
H
0h ? ̙33
00(
x
c$d}:P
:
x
c$<~::
H
0h ? ̙33
00(
x
c$w:P
:
x
c$x::
H
0h ? ̙33
00(
x
c$j:P
:
x
c$`k::
H
0h ? ̙33
00(
x
c$a:P
:
x
c$b::
H
0h ? ̙33
00(
x
c$T:P
:
x
c$T::
H
0h ? ̙330w(
ZlO:>?"5
?Lower bound$H
0h ? ̙33y
00(
x
c$D:P
:
x
c$D::
H
0h ? ̙33y___PPT10Y+D=' )=
@B +
0 0(
x
c$;:P
:
x
c$::
H
0h ? ̙33
000(
x
c$0:P
:
x
c$1::
H
0h ? ̙33
0@0(
x
c$#:P
:
x
c$$::
H
0h ? ̙33
0P0(
x
c$:P
:
x
c$::
H
0h ? ̙33
0`0(
x
c$:P
:
x
c$::
H
0h ? ̙33
0p0(
x
c$9P
:
x
c$99
H
0h ? ̙33
00(
x
c$\ :P
:
x
c$
::
H
0h ? ̙330TL`p(
p
p
Z:>?"0
THM2: A 5round protocol for
secure twoparty computation
(for malicious adversary)
We construct a 5round
protocol where we force
good behavior on both sides
and can simulate
malicious Adv view from both sides&
@U$$33$H
p0h ? ̙33y___PPT10Y+D=' )=
@B +
00(
x
c$`9P
9
x
c$899
H
0h ? ̙33___PPT10i.ӄG+D=' )=
@B +}
0$(
r
SP
9
r
ST
H
0h ? ̙33___PPT10i.Ԅ`te+D=' )=
@B +}
0l$(
lr
l S9P
9
r
l S9 009
H
l0h ? ̙33___PPT10i.`I+D=' )=
@B +
0x:(
xr
x S9P
9
x S 99
"p`PpH
x0h ? ̙33y___PPT10Y+D=' )=
@B +
0:(
r
 SL9P
9
 SH9
"p`PpH
0h ? ̙33y___PPT10Y+D=' )=
@B +m
0p$(
r
St9P
9
r
S899
H
0h ? ̙33y___PPT10Y+D=' )=
@B +
0P:(
r
S,9P
9
S9
"p`PpH
0h ? ̙33y___PPT10Y+D=' )=
@B +m
0@$(
r
S9P
9
r
St99
H
0h ? ̙33y___PPT10Y+D=' )=
@B +y
0pT0(
Tx
T c$z9P
9
x
T c${99
H
T0h ? ̙33y___PPT10Y+D=' )=
@B +}
0P$(
r
SPi9P
9
r
S(j99
H
0h ? ̙33___PPT10i.ݰ+D=' )=
@B +
0`0(
x
c$c9P
9
x
c$c9 9
H
0h ? ̙33___PPT10i.ݰ+D=' )=
@B +c
0zr` *
(
x
c$08
8
p e
*#""rE
TP8>?"e
T33
@`
T8>?"@e
R
@`
T8>?"x@e
R
@`
T8>?"xe
P
@`
T$8>?"t
P
@`
T(8>?"@t
S
@`
TD9>?"xt@
Y ST1 & ST2
@`
T9>?"tx
_Round3:
ST2" @`
T(9>?"i t
T33
@`
T9>?"@i t
R
@`
T#9>?"xi @t
R
@`
T%9>?"i xt
Lround2 @`
T59>?"i
SPlayer2 @`
Tp.9>?"@i
T(
@`
TH99>?"x@i
R
@`
TQ9>?"xi
Player1
Round1
ST1< @`B
No?"B
H1?"i i B
H1?"ttB
H1?"B
No?"eeB
No?"eB
H1?"xxeB
H1?"@@eB
H1?"eB
No?"e
N>?#"`
2"
N>?#"`0 `b
!
N>?#"`
H
0h ? ̙33___PPT10i.p=+D=' )=
@B +}
00$(
r
SX8P
8
r
S088
H
0h ? ̙33___PPT10i.z++D=' )=
@B +
0#+h(
hx
h c$8P
8
dp
%h#""p
h
T$8>?"R
P
@`
h
T8>?"@R
R
@`
h
T4/8>?"xR
@
R
@`
h
T>8>?"R
x
Lround4 @`
h
TF8>?"]
R
P
@`
h
TP8>?"@]
R
S
@`
h
TX8>?"x]
@R
R
@`
h
TTa8>?"]
xR
Lround3 @`
h
Tc8>?"]
P
@`
h
T,r8>?"@]
R
@`
h
Ts8>?"x@]
R
@`
h
Th8>?"x]
Lround2 @`
h
Th8>?"
RProver @`
h
T8>?"@
T(
@`
h
T8>?"x@
R
@`
h
TЧ8>?"x
oVerifier
round1. @`B
h
No?"B
h
H1?"B
h
H1?"]
]
B
h
H1?"R
R
B
h
No?"B
h
No?"B
h
H1?"xxB
h
H1?"@@B
h
H1?"B
h
No?"
h
N>?#"`@
!h
N>?#"`G
"
"h
N>?#"``
&h
N>?#"`
G
"
*h
H>?#"` `
"
+h
H>?#"`@``H
h0h ? ̙33___PPT10i.p=+D=' )=
@B +}
0p$(
r
S 6P
6
r
S6 @6
H
0h ? ̙33___PPT10i.U+D=' )=
@B +}
0$(
r
S4
8P
8
r
S88
H
0h ? ̙33___PPT10i.фV+D=' )=
@B +}
0$(
r
S6P
6
r
S66
H
0h ? ̙33___PPT10i.+D=' )=
@B +/
0F>@##(
x
c$X]6P
6
v 0
##""p0
TD5>?"?
0
^Det. ST2$ @`4
T_6>?"
?
Proof: ST1& ST2
X @`
TXp6>?"?
R
@`
Tx6>?"?
Lround4 @`
Tz6>?"J
0?
P
@`
T6>?"
J
?
S
@`
T06>?"J
?
R
@`
T6>?"J
?
Lround3 @`
T6>?"0J
NDet. ST1 @`
Td6>?"
J
R
@`
T6>?"
J
R
@`
TH6>?"J
Lround2 @`
Tt6>?"0
RProver @`
Tx6>?"
T(
@`
T6>?"
R
@`
T6>?"
oVerifier
Round1. @`B
No?"0B
H1?"0B
H1?"J
0J
B
H1?"?
0?
B
No?"0B
No?"B
H1?"B
H1?"
B
H1?"B
No?"00
N>?#"`@
N>?#"`G
"
N>?#"``
!
N>?#"`
G
"
"
H>?#"` `
"
#
H>?#"`@``H
0h ? ̙33___PPT10i.p=+D=' )=
@B +
0&+tg(
tx
t c$85P
5
p
)t#""p
t
T5>?"p
ZFS : ST2 33 @`
t
T,5>?"@p
R
@`
t
T5>?"xp@
R
@`
t
T\5>?"px
Lround4 @`
t
T5>?"
p
P
@`
t
T5>?"@
p
S
@`
t
T\5>?"x
@p
R
@`
t
T5>?"
xp
_
Round3:
STWI @`
t
T6>?"
\FS : ST1
33 @`
t
TH5>?"@
R
@`
t
T,
6>?"x@
R
@`
t
T6>?"x
Lround2 @`
t
T((6>?"
SPlayer2 @`
t
T16>?"@
T(
@`
t
Tp96>?"x@
R
@`
t
TC6>?"x
nPlayer1
round1. @`B
t
No?"B
t
H1?"B
t
H1?"
B
t
H1?"ppB
t
No?"B
t
No?"B
t
H1?"xxB
t
H1?"@@B
t
H1?"B
t
No?"
t
N>?#"`p
B
t
N>?#"`p
2
"
"t
N>?#"`'
$t
N>?#"`
p
"
%t
N>?#"`
"
&t
N>?#"`'
't
N3f>?#"`0W b
*t
N3f>?#"`
R"
+t
N>?#"`
H
t0h ? ̙33___PPT10i.p=+D=' )=
@B +m
00$(
r
S5P
5
r
St55
H
0h ? ̙33y___PPT10Y+D=' )=
@B +m
0$(
r
S5P
5
r
Sܓ55
H
0h ? ̙33y___PPT10Y+D=' )=
@B +}0 $(
r
S`5>5
r
S `
5
H
0h ? ̙33___PPT10i.ۄ` +D=' )=
@B +
0F(
x
c$~5P
5
c$55
"p`PpH
0h ? ̙33y___PPT10Y+D=' )=
@B +
0F(
x
c$tl5P
5
c$q5
5
"p`PpH
0h ? ̙33y___PPT10Y+D=' )=
@B +y
00(
x
c$Z5P
5
x
c$]55
H
0h ? ̙33y___PPT10Y+D=' )=
@B +y
00(
x
c$O5P
5
x
c$
H
0h ? ̙33y___PPT10Y+D=' )=
@B +0@0(
x
c$L5>5
x
c$L5 `
5
H
0h ? ̙33___PPT10i.ۄ` +D=' )=
@B +
0PF(
x
c$055P
5
c$;55
"p`PpH
0h ? ̙33y___PPT10Y+D=' )=
@B +
0`F(
x
c$0/5P
5
c$5
"p`PpH
0h ? ̙33y___PPT10Y+D=' )=
@B +y
0p0(
x
c$5P
5
x
c$
55
H
0h ? ̙33y___PPT10Y+D=' )=
@B +y
00(
x
c$P
x
c$p
H
0h ? ̙33y___PPT10Y+D=' )=
@B +00(
x
c$>
x
c$` `
H
0h ? ̙33___PPT10i.ۄ` +D=' )=
@B +
0 F(
x
c$P
c$(
"p`PpH
0h ? ̙33y___PPT10Y+D=' )=
@B +
0$F(
$x
$ c$tP
$ c$L
"p`PpH
$0h ? ̙33y___PPT10Y+D=' )=
@B +y
0(0(
(x
( c$P
x
( c$H
H
(0h ? ̙33y___PPT10Y+D=' )=
@B +y
0,0(
,x
, c$<P
x
, c$
H
,0h ? ̙33y___PPT10Y+D=' )=
@B +y
000(
0x
0 c$P
x
0 c$
H
00h ? ̙33y___PPT10Y+D=' )=
@B +n04%(
4
4
Z$>?"=
UHandling adaptive adversaries(H
40h ? ̙33y___PPT10Y+D=' )=
@B +m
0$(
r
SԢP
r
S
H
0h ? ̙33y___PPT10Y+D=' )=
@B +m
0$(
r
S0P
r
S
H
0h ? ̙33y___PPT10Y+D=' )=
@B +}
08$(
8r
8 SPP
r
8 S(Pp
H
80h ? ̙33___PPT10i.߄@+D=' )=
@B +r` se S %@ r DIZiGx\9НQҢct ڼ[0] *p@g'sL=5%
]UME=5!zOh+'0 ` h
Rafi Ostrovsky1043Microsoft PowerPoint@u@@ pANGg !y$xx'@Times New Roman. 2
r1n."System :@Times New Roman. 2
r/48.@BComic Sans MS. 2
/Round..@BComic Sans MS. 2
/6n.@BComic Sans MS. 2
/:Optimal Secure .@BComic Sans MS. 2
<Two.@BComic Sans MS. 2
<+n.@BComic Sans MS. !2
</Party Computation.@BComic Sans MS. 2
V
Jonathan Katz.@BComic Sans MS. 2
`U. Marylandt.@BComic Sans MS. 2
VURafail Ostrovsky.@BComic Sans MS. 2
`dU.C.L.A..
Ostrovsky2party.՜.+,0h
Onscreen ShowCUCSRDITimes New RomanComic Sans MSSymbol
WingdingsDefault Design+RoundOptimal Secure TwoParty ComputationMotivationFor example…
This workThis work (1)This work (2)This work (3)Prior work (2PC)Round complexity of 2PC?Security definitionSetupIdeal modelIdeal modelReal modelSecurity…Blackbox securityMore formally… Slide 18
Theorem 1
IntuitionProof details IProof details IIProof details IIIProof details IVProof details V
Implications Slide 27Somewhat easier taskobservationRest of the talkRecall: 12OT [EGL]Semihonest 12OT [EGL,GMW]Yao’s “garbled circuit”3round semihonest 2PCMalicious 2PC?Malicious 2PC in 4 rounds Reminder:3Round WI proofs [FS]
OBSERVATION $NEW PROPERTIES FOR 3ROUND WIPROOFNext: [FS] 4round ZK2[FS] 4round ZK argument: 2 interleaved WIproofs[FS] 4round ZKargumentNew FS properties needed:4Technical lemma  we extend [FS] to FS’ so that:2[FS] 4round ZK argument: 2 interleaved WIproofsOUR PROTOCOL PROOFFLOWS1Simulation on both sides? we need more tools…Equivocal commitments#And now… the 4round protocol…Round 1: P1(x)P2(y)Round 2: P1(x) P2(y)Round 3: P1(x) P2(y) Round 4: P1(x) P2(y) SIMULATION FOR CHEATING P2 SIMADVP2Round 2: SIMADVP2Round 3: SIM ADVP2 Round 4: SIMADVP2SIMULATION FOR CHEATING P1ADVP1 SIMADVP1 SIMRound 3: ADVP1 SIM ADVP1 SIMADVP1 SIM Slide 65 OverviewAdaptivelysecure encryptionCONCLUSIONSFonts UsedDesign Template
Slide TitlesD&_a0Rafi OstrovskyRafi Ostrovsky
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~Root EntrydO)04N Current UserSummaryInformation(P PowerPoint Document(DocumentSummaryInformation8
!"#$%Oh+'0 ` h
Rafi Ostrovsky1043Microsoft PowerPoint@u@@ pANGg !y$xx'@Times New Roman. 2
r1n."System :@Times New Roman. 2
r/48.@BComic Sans MS. 2
/Round..@BComic Sans MS. 2
/6n.@BComic Sans MS. 2
/:Optimal Secure .@BComic Sans MS. 2
<Two.@BComic Sans MS. 2
<+n.@BComic Sans MS. !2
</Party Computation.@BComic Sans MS. 2
V
Jonathan Katz.@BComic Sans MS. 2
`U. Marylandt.@BComic Sans MS. 2
VURafail Ostrovsky.@BComic Sans MS. 2
`dU.C.L.A..
Ostrovsky2party