ࡱ> FwId:w!;=JFIFCreated by AccuSoft Corp.C    $.' "+"(6(+/1343&8<82<.231 }!1AQa"q2#BR$3br %&'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz ?$x[OxbI+ Wn?AGZo-c'U{&@"E p*  2m۹[#dKV(G?UMGOzlO&?>*Ǩª3V)& k3]T.}획3s>Y60;$#5gOWHKx✣Kh)3ڊC+[:tڶ[Hl]:M]L2޹Z&-ZKxDqʹپk3; ֬xIEŽf7xL; RYIH&`G#- rOC_V+Vkͻ{LЧiƜs.}{R`jR>\Pp:Vׂ)4}r+l-ޟ{|Qyu4B}@۱Nݏɺci UvjQi#N틓թOWֵ.U1"=I[x~yeP08>=L_J(V`9b?\?G45K5->(Ȼb {hDe9 QaqH6Q"AS<ZXx\4jCKoRjm\1`K>t.['m^ ́TNI$tAm^+QeN+Ǩi@`ӷV+ٓqIT3eiυ4NCM ;>Haޚ2W֐$= ,yҮwnlu49#=5  sM_ 1i^$Wğ ܺAhPpu |*s|N? O OzJ Ƭq+b @"! vҾ9 $Ӳ*=q}$dC%qckNI$ *?Z-H',K:~V'TgPo*b7lGe ?CQI0bXQ `>g^r=:$u%sJ8x(4S|q_"XvOhtgi#06wH)鎂,]}O{$&?$e=jk󐧱x`x=d )}xJ+Rt1v҆ ?6cg,By3D,0Hf+NG{t aPmgba zHϡȗ׺]Jkϒ֙x-/s22Ǎ́}2jӯ9d9)0$cv Sxԃ[Cs9KnKn#9#h[zlN]uי x H] `ER𸶵ۼ(YhvokҌNUî|kƟlW Z D7rҫ1VRuO f0ǀ8HpXӁ>b޽wmwUHUFUm.&%O"!,3ӎPijZt؎4F v06# ¤29J 8$*~(EI(' l؞ÏJio&_7ی翦+迆>5~Kҏ7+ɭ尹!9<U佞Wvw$%ƛCP#|q@c9c$8Ar\M N''ښG|-` ?Q^5[xU*Ī1PI[ '< cF" /\όX/tˀc kı("Oh5_&\k?QIA$c" $Za`pGO$y#ң0} LtХ4QHҷ@)E >p&ArJG5)ЛV &7# R5{Le#Fa64R,{w1#w' %0$J*2y8:W Cҳڵ|G7Vkkezን>W:>P˜iG q(_?I4ᇄ ?Ʋm>n[G}`L{_ y?pq0xSS]Pt#4*śiiG.1?Nq4A0F?m?o t1Y_ttlЧ xxtѬȥGMSZe~+R%$XFT`ndamۏòbodPNG  IHDRHmoPLTEcI级q¶;A;n`S֥ZG3*)vftYzjd\TKQKCKIiHBA=uhd9=:כQRMRLBsXDžy鵛252.24}żjb|z5:4]V7>A\YT73/jI=k::4ĴcP̚|vk]˵cQKVaڧ\]Zwܐ}'##jG㧗Ջ_SLd[gx壋QNJIB5cKA7ABZKAe^cQIFABH=D30f<˻zKI>FRkPzvxk[nofmv169-'&/1-WI:42RD>`Ih]ȇu?@52..UYX,-/!ԉX񾓍>IJRUZoXLlamS{vaANNQ\YNXOIN=]Wa>--ʢߨ`_pM" '%(Q40fP)*,$ !Z]@HDZU@HA68@JB8WDDXGI߉ߔo۩N?4(((YS.'687NPVXF\guHG8[f`oajttomLHFNbtRNSS%bKGD cmPPJCmp0712HsIDAThC\NH;rtD^9&V#*⨩ mLЙM[Aژ(v q[QlOmdOg{}A@rs">'ǹo8&Ыk\:8EfhM[֏Zƍfw69-{fQ, R3(\3#/O \NL\vow> A)1z3oI<)Hqv Iv:8ySrb9n3(KD4RW|- Y0kq4c~$klcY٪ .Ĭ/^ ?~:իf3(g殟D7/¬Wf'?{~CL_/[ \Ϭ _~ok/*BM)3-hm#H֙~H[m%CL,ޥJɔZ'qiUW~0jft' m (}[ .Rd,(FQ(%=. 2i,@&ǿ(RjRlD` ҊG~ %HH<2(`m 2S]h7Zd'b2f0e6J9@z6DpQZRDfP 1ݤR0XJmmr+ n JBE-Ĝ%2U B O !V)e(sU ]]!p ŁLyyEE|RRS P[9(3bDN&,|%u cV~_ ;zF B]h7 %nU Z4tI4^FCFFjRP1>~XPܫ(N\ ZR#P1"|nfF5"#20 $0U(LKUFJALQR Qua*uI'bDPG\:T@X Ͻ0=PZf0h!]B]1tv @ʵJu: bs(Jweh %8AQe_['2X e2O4"qTr&nXt]àuuF Bp $i!ɴ4%\=0hY.i2^[`ŋ0BZX01 y>-@4vl|%ʨ}J_G} wt8A9)V\9Pi ':Iߞ=ol^W*PaT Hcw 0O;H)pc1Ma0E((_~V(RYJЋ0_6{4A)zmepō! N,;o^jwV2Ra|c*f A uwIF٧60aq1b4x-Yf7D!hCw]QvQ$/nh5/]f;v,1b~҂TͨXJY1 0S'u씔KaPtJ7ge(E2wVԕ)푺a%Fc@"bō̊$:^?HAkI]Z3=^sJH4H01bjQ B2FGqvEi UB'>(Tal]Cw1{=XY}+Z@ZPAQ:@{fZb )@GMNBݵ2SjkByl(r;%n?m8-@lтiK60PS21SFj24̭]vB1Zn!)kz6DJvD׊ VG@ݡ6%w n%@CPPPjm'p jhGXc{FRH4m{v]h( iŅ[|tI18~@F^PdmVĊ#^P)'z]'!BW']]ݪ%vpPPb\lDm^ ޠr]c;p5H/J7*#?@)^3U`WMzy26@[u O~n0B2S OTBw@3ޯdІ>^' Wdʞ~ p? (B!СbS#3G;vR1* ՚A[L -4ouԶĶdARzj5EAs8\*6 tQ'F)wOP 6A*JmM!tf;LNWs] ]+ U@ \VRh4*BT/YȻeۉ_)X">!ً&3R.SۅvP\0<#O-qks&o~ZPLdW(\nzo !Ţ_C^T姀AR(J `N`^>;B g'@2R*aS;6ߐ6¯-9vDr(Ze9llh2yt04>apŬ~BiyDQCj)m*IJF0Rh+y.@RaS YeVlq8Aw fҥt ].RDϦya]}2Mk.R*dFU4r+tjTͨ 'V0}6IlkH-φ J3നa4P@1m}VǺ?aN5H ':j$ X-bқ˕eNh4 C߱㽯3S?St]dڤ[޺u[UO_>=fB[{3R ښ9m5ޢ,Hu能Y{Db}&HKRg߁<s55E;wySV/9Yκ̫M-?T?kcyfav6f.=b؏{nǾ4ne?xtZnjVjj}|܈uEq7˽;A?}f^0;T~\~9`lR( = ng q^=tq(漛_Ɔ~JE:(99[û- *;;)=\ABmk0.ߑ/JZl:t*)'vF z3 ~)>ܞ@ a@_H^% TT<.lHjSJ ?jZ Ic7];u7! zt^KKsGOUu=5r5*G&[ɯ4Ͼ_kLJ&KݸʫO~`_ápt2๔=֋REFSRO=}hoMsD: !o^K(Ug?8q ^ *W_OߖyKg0$>i){_;p޴ Ԭ)Qo?x-w}}r񼔤'R~ڎN>Od~_dCfjjϟTಧf_zk>qG8KnOlH gql-R n8zy('vˮlMW933'3/y؇K9]|X5s/~/#rRui?D8TS^셹dJPJ-i7e2u0o9"U귾3׶|\ٓiy'm/K߻SZR_i(Q=5y9L ޝ&یg#Uk"(7gY6mk2fxHOX_BmoR& jr !h6e )/ժ9]3̂dB)^ >?;!8JR8GR^[[@ &aEm'gIQ-V+8`Wat.% V%ٴgLPl%>hwXː#khmN{G\clr}ΘfFfl[EqSA:f p&`;JBAɂ F}nlnBTbLZ]NǏxJe*b!#.сڣh^MY0ߔH2L/t؆h' =XQܑ&GQCiKHk SOU/.߹$*ԙBab J DY%u O-#@*9!UEvZ~sn}h_뒧:GtfU"6M.铿4GQ\v\?Z;lGa41p @(~ۥN$VN\NJhGXjuu9oOӿn8iQQAul|P]>jo0W~FQ]my۷IZ^juI &(u#e\}o{9^CǛ4Xǽ(t༠ɌςK>tt[vZfW69u1C'DF#3uˣ 9(d6r{>۰6w "Lac(t PijR-o:M¸,.('XV[F7Y9VRL'פxJI(00q5h$ze;+ewΚ*Udf.Rx+5-ah]eLظX.I^֚5_Ԁs^XتU;8RqӏR!RMKnz9[ y1IYky3:-.ޏQ08?p@9qb x}X(cNӃ. c6ԗԛ/>;ƇA~(׈qډ2M\:M<~:J)iuՄ`Pd!52y<&E BQZèuZcpsr򜯘h$:zF&l4?dcꪎF1AI/H}GpNjm|1؋0Ig}ϪR;e35'>(@Qvx) tqaY}~=ӑU48uc u> 4`~1јN4&q6h2qC΀V:,&ïPbl:[C9 ;+W hIrXe. 1RSA!QF!Z%Ųwea\ԕD:2jp*\ԸˠLsږ>sڏJҔzw> #@A5pRX#ꎜ֔hj'89=IT&E1g)qzaTrf<®^\E)q4#ۢT }ZUI Og~oG RHw#ꎵƊKtjBmx~AHnsp&Qi  i3a k2aq;muJET`a†,, mL_:zxDr:01R!s[B#etwCZ˶` ƏH5Q, \f烇2EgX/nYwV^ uZ9iQqX =PŸt2* 26*+M7mF)Sl&N J ms>W DGz0$ 5 l5wtxAAtbPL.*`%>w3IZ%H^FMׁllt!_ ~eQgI??)xE16^ yv8)hRH_߈)?1J3\/Jm!GuEno⮬A) %StЍH#F{ъ5TH>w:)(M?_0nuÆbiQefh1ԕ`~~ވEEMN_'+LI}ہSԵ^oSr_.8s;U~ƚCUk.|clȷ34!>DðƔQK5;gΊM\bW5]˖']Jp0& +m} |0Ubno5XS̀g6Ew/30k k-߸p1")8 FƥCP+S{)3)^GZQJ8=ܝNzr/KҠx3)<uƬܿ48)>R ruJI{!QzfU,&N*O NU['o0AcmZsat8 C,A~,J5s12_'m]\PaJ7{'kQZA~p@stB. n8C6@ peBvkJr{Kmz$$U G @p2O?b3dCjYY@VdX<AhjF%\:ȆdpDJ⊻ "w@!B^_O/gN ( -4uRۭG{X`J;n ܸEkM8È8O)J+ib]X9Rf=5[/,1 -xճMEpA&![oqc=d2+R7n60"8;!bQ: z}QkcƂz :$`Ǟ'C1w@g"G_h'9bwvLŪk;I s,Eh;.sS"MG\ ߯ր("cujSEqKw)oaY#E\!oڶu˒.?ؾҼ @wCa`!q =PbZYTQ> 5    ()//  2121**//  5 HH   ]2^1`!jor&stuvwy {*|} ?R$wId:w!;=b$amۏòbodlb$TVũ9b8fqL' 0AA@f3@8QR38ʚ;ʚ;g4?d?d@z[ 04ppp@ <4ddddl 0A  80___PPT10 ?  %Q1How to Go Beyond the Black-Box Simulation Barrier42  1 Boaz Barak Weizmann Institute H      Zero Knowledge Proofs [GMR] (  Def of Interactive Proofs   !Zero Knowledge Property   "Black-Box Simulation    The Main Result  #@Proof of Thm 2  High Level View!!(.      Proof of Thm 2.    tCommitment Schemes ( digital envelopes ) [Blum,Naor] Witness Indistinguishable (WI) proofs [FeiSha] Universal Arguments [Mic,Kil,BGol] Z+f f2ff:fb,   5  =    .Witness Indistinguishable (WI) Proofs [FeiSha](/ %$ .'    Universal Arguments [Mic,BGol]*  .    A First Attempt  A Second Attempt   Protocol UZK    Protocol UZK     More Results  Prot UZK can be modified to obtain ZK against non-uniform verifiers. Prot UZK has simulator with strict prob. poly-time: Impossible w/ black-box simulation [BL] Modified version of Prot UZK remains ZK under bounded-concurrent composition Impossible w/ black-box simulation [CKPR] Instantiating Prot UZK in crypto schemes (e.g. identification, voting) yields schemes with non-black-box proof of security. . ))M+[  %Black-Box Reductions in Crypto  &= ` ffff!` 33` 3fff` 3PPf` fff̙3f` 3f33` ff3fff` fff̙` ̙>?" dZ@,|?" dd@   " @ ` n?" dd@   @@``PT    @ ` `4p>> p9h911t9(  t3T  t " t  hBC"DEFJ.. e%/5BEMebebur7p_Uz?dM<H E"5 %% "$@               `" b b@ tC# n"l (I  t xBSCuDEFSuS @`"b t xBCbDEFbv1b @`"~@ t xBC1DEF1 @`"5p t 2BCDETF~UUaSHfup`R@@&^F pG` Mr_&x669D>2}uynpbaN@N@BJ 6%:| <@@                            `"Z  L b ) $  t# "    tB BCDEF00.%mR 9#-< HQXh  &-($!}tkc[!R$J)B.4=*P%g#~#&).bd@`"}  l  tB .BCDEF::mpv!4Li}unf\RH=1% !+5?IS[dlt{o_O. ~wmvx@`") /O d  tB &BCDEdFn^i s{2Not^<1& .?Op[Sa.^48@`"y[ t  tB 6BuCDElFvK$./B>TPfgtuxsklZcJY:N-C$: EOYbimqrK8<@`"9&   tB BCMDE4F>  ,< M5% @`"!? 6v Nb  tC# *J"O $ t NcFBC4DExF ,Hc}+E=lSj 4gWpKQD5?8,)+D2 ,>@@`" t cFB/CDE<FF7e-//-g)G$4"  $@`"= A, t cFBWC(DEHFRWMD :/%  !*4@!J(W&(@`"b b@ t# $"G t xBSCuDEFSuS @`"b t xBCbDEFbv1b @`"~@ t xBC1DEF1 @`"5b b@ t# bS"z t xBSCuDEFSuS @`"b t xBCbDEFbv1b @`"~@ t xBC1DEF1 @`"5\ b@ t "/o t xBSCuDEFSuS @`"b t xBCbDEFbv1b @`"~@ t xBC1DEF1 @`"5V t  BCDEFY+ "'*33:tXRoJ=%   (Fen(<Pik{ Bm#)4|9|@wDpI_L_LEZwH3 ~wrmold^T={(cW H=1%  X\@                                          `"W^Rd  t & BmCDEdFn% :N,`Gklmic]WQJB:5~5o8`;P8>0+48@`"L v $ !t  B6C(DEDFN  &.652!,&%(' $(@`" L3$ "t BvCDEDFN!&36HC^OwW^[vuhwRE/$(@`" | #t >BCDEpFzg}~oy\oDg)^Z]H FB&B3CAFNNQJQ:R%RPMLKLO Yg:<@`" $t B/CVDE,F6 %%;VRI!?*3/$.%@`"m/ %t BCDEF-- )eC2~ZGJl;0{MRf%}Z(e@kRAl8D7 =F \`@`"  &t fgBCDEF!!2K bw&3CVjpaTH=}4k+X!E/ DH@`"l 't NgB|CnDExFM|lxkkiYeDc-ab fnbYRL$H/G;GHJIGF8C&A?=;99;BM>@@`"gd (t &gBmCDEdFn% :N,`Gklmic]WQJB:5~5o8`;P8>0+48@`"> )t gB.C^DE4F> &> O^ XP E(9-,.* @`"*2$ *t gB6C(DEDFN  &.652!,&%(' $(@`"I +t BhCDEF&&  '):5S?lIMPLC6;WroE# )tR+'L}m4VO1`hdUX7'NP@`"vh ,t fgBTCDEFAAtr hU>! -tETe7 :| !D q*AOT[SI6 >ghiG c1p]UK"A=?GTyee{TE90(!1St@`"8T\ -t S H9  "A`} 9  X Click to edit Master title style!!  .t C 9  " ` 9  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S 4 /t C 9  "] `}` 9 H@___PPT9"@ v*.0   0t C T#9  "`  9  h* 0  . 1t C '9  "] `}` 9 H@___PPT9"@ p*,0 B t s *޽h ? fff̙80___PPT10.(02 Balloons2 Q 1100x1(  x<,T  x " b  3 x# i"j x fBTCDEFAAtr hU>! -tETe7 :| !D q*AOT[SI6 >ghiG c1p]UK"A=?GTyee{TE90(!1St@`"  x fBCDEF!!2K bw&3CVjpaTH=}4k+X!E/ DH@`"   x NB|CnDExFM|lxkkiYeDc-ab fnbYRL$H/G;GHJIGF8C&A?=;99;BM>@@`"7wLp d x &BmCDEdFn% :N,`Gklmic]WQJB:5~5o8`;P8>0+48@`", x B.C^DE4F> &> O^ XP E(9-,.* @`"lp $  x B6C(DEDFN  &.652!,&%(' $(@`"7-  x BCDEF**)%:5IFXZdqpx|~xm.\VC' 6] )'$!n#?):V9mUQ,,VX@`" ( 3d  xB &BCDEdFn^i s{2Not^<1& .?Op[Sa.^48@`"Y.   x BCDEF//{:[It&m~An,$:OgR)LP5j+ W3\^]{`d@`"   x NB!CDExF%EDn:4Pmm}=}j!OyR^#du<[&>@@`"2 ! t xB 6BuCDElFvK$./B>TPfgtuxsklZcJY:N-C$: EOYbimqrK8<@`"'   xB BCMDE4F>  ,< M5% @`" v \ x BTCDE`Fj_]^ 3zEAemz&uN4l!T24@`" b b@ x# 5"%  M x xBSCuDEFSuS @`"b x xBCbDEFbv1b @`"~@ x xBC1DEF1 @`"5b b@ x# z" f x xBSCuDEFSuS @`"b x xBCbDEFbv1b @`"~@ x xBC1DEF1 @`"5b b@ x# &"  x xBSCuDEFSuS @`"b x xBCbDEFbv1b @`"~@ x xBC1DEF1 @`"5b b@ xC# &".a& x xBSCuDEFSuS @`"b x xBCbDEFbv1b @`"~@  x xBC1DEF1 @`"5b b@ !xC# Y"N   "x xBSCuDEFSuS @`"b #x xBCbDEFbv1b @`"~@ $x xBC1DEF1 @`"5J %x B^CvDEXF`k%S"RFCov^SXCm-NSi-0@"x &x fBCDEF!!2K bw&3CVjpaTH=}4k+X!E/ DH@`"nf  'x NB|CnDExFM|lxkkiYeDc-ab fnbYRL$H/G;GHJIGF8C&A?=;99;BM>@@`"Z p (x B.C^DE4F> &> O^ XP E(9-,.* @`"(+  )x B|CyDE@FJ|q cQ)?6)BJK `q)y<ySoeXt5|"$@`"Cy *x BCDEF**)%:5IFXZdqpx|~xm.\VC' 6] )'$!n#?):V9mUQ,,VX@`"}  +x B$CDEF$ @`"8$4 ,x C ė8  "` `` 8 H@___PPT9"@ v*.0   -x C 8  "`  8  h* 0  . .x C H7  "] `}` 8 H@___PPT9"@ p*,0  /x B7 3 3fԔ8c?"x HH  8  X Click to edit Master title style!!  0x C 7  " @0 7  [#Click to edit Master subtitle style$$ B x s *޽h ? fff̙80___PPT10.(02 RK0  (  x  c $48 /x 8  x  c $7 0x0  8  T  C ,Aradionics @ H  0޽h ? 33___PPT10i.P7\+D=' = @B +K@ QK0 d R(  d d 6t9 "`  `,$D  0 `m2&  " d 6Q7 ̙"`  ,$D 0 hm2.  d 6W7 "`   ,$D   0 `m1&  x d c $tX7 -t   7   d C $A woman P,$@ 0| d C Aman ,$D  01 d 0[7 0,$ 0 )e.g. L = { x | x is a 3-colorable graph }<*( 2$)   d 0ta7 0 ,$ 0 vL 2 NP8( 2C   d 0f7 P0p,$ 0 ux 2 L8( 2C %  d 0\l7 P0J,$ 0 e.g. x is a 3-colorable graph<( 2 (  d 0r7 0,$ 0  w 2 Wit(x)8 ( 2C.   A  d 04x7 0,$ 0 e.g. w is a 3-coloring of xZ( 2   d 07 ` ,$  0 Prover (Alice) knows w<( 2fff #  d 07 0 ,$  0 Verifier (Bob) knows only x<( 2fff l pP  d0 p ,$D  0 d Bp7 G= Hb "`pP  @  d 67 @  \TL___PPT9.&@ Alice wants to convince Bob that x2 L. But, without him gaining any knowledge about w! Thus, she can not simply send w to Bob! We need a more complicated, interactive protocol.( 2 C   2( 1 H d 0޽h ?d 3ffffff,,___PPT10,.@A+ gAD5*' = @B D)' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-g6B fade*<3<*dD' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-g6B fade*<3<*dD' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* d%(D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* d%(D' =-g6B fade*<3<* dD' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* d%(D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-g6B fade*<3<*dD8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* d%(D' =-g6B fade*<3<* dD' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* d%(D' =-g6B fade*<3<* dD+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-g6B fade*<3<*dD' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*dD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*dD' =-g6B fade*<3<*dD>' =%(D' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-s6Bwipe(left)*<3<*dD' =%(DF' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-u6Bwipe(right)*<3<*dD' =%(DD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D' =-s6Bwipe(left)*<3<*dD' =%(D' =%(D)' =4@BB BB%(D' =-g6B fade*<3<*dD' =1:Bhidden*o3>+B#style.visibility<*d%(+h+0+d7  ++0+d7  ++0+d7  ++0+d7  ++0+d7  ++0+d7  ++0+ d7  ++0+ d7  ++0+ d7  ++0+ d7  ++0+ d7  +z QK0 ` X   (  ~  s *7 -t   7  L  C $A womanP H  C Aman    07 `  Prover (Alice) knows w<( 2fff    07 0 Verifier (Bob) knows only x<( 2fff u  0 7  @ ,$ 0 ACompleteness: Given w, Prover can convince the Verifier that x2LhB( 2 (CA   0C5  ,$ 0 Comp. Soundness: If xL, then, regardless of Prover s (efficient) strategy, the verifier will reject with very high prob.z( 2+  H    D   6 L5 "`P  `m2&  "  6HQ5 ̙"`  hm2.   6U5 "`P `m1&  H  0޽h ? 3ffffff___PPT10.@A+.D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*+p+0+5  ++0+5  +m QK0 )V(  ~  s *Pb5 -t   5  LB  c $Do  LB  c $Do $   0Pd5 `  ^Regardless of efficient strategy Verifier uses, he can not gain new knowledge on the witness ._( 2]f3^ ^   05 p \TL___PPT9.&@ Informal Definition of ZK:@( 2 `R  s *"`PL  C $A womanYsH  C Aman4   05 p@P Prover (Alice) knows w<( 2fff   0 5 pD P Verifier (Bob) knows only x<( 2fff   05 0 P ,$ 0 +/Formal Def: 8 efficient verifier V* 9 S* s.t. 0( 2 3GG.*     05 Y f ,$ 0 VV* s view in interaction w/ P(x,w) S*(x)P,( 2 .      0 5   ,$ 0 S~( 2   B$5 GH[ 6d ,$D 0 w!Computationally Indistinguishable" "f!   0)5   ,$ 0 S~( 2   B4.5 GHYj 6P ,$D 0 uStatistically Indistinguishable  f   025   ,$  0 1Usual way to show ZK: Show universal S s.t. 8 V* 2( 23G.'   N   0`<5   p ,$  0 $V* s view SV*(x)^( 2  l `p  )p` ,$D  0`" ( 0`p  ' 0D"5  %This is called Black-Box simulation. B&( 2  % H  0޽h ?/  3ffffffiYaY___PPT10AY.@A+.DS' = @B DXS' = @BA?%,( < +O%,( < +D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*Dd' =%(D ' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*Dt' =A@BB7BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D ' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D ' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*Dt' =A@BB7BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-g6B fade*<3<* D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*)%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*)D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*)D' =-g6B fade*<3<*)DR/' =%(D.' =%(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<*)D' =1:Bhidden*o3>+B#style.visibility<*)%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D2' =A@BB@BB0B%()?)?Dy' =.A7 BBBBBSM -0.00417 -0.00555 L -0.00417 -0.41666 *3>*B ppt_xB ppt_y=@0BBAApBBB(}R<*D$' =A@BB@BB0B%()?)?Dk' =.37 BBBBBEM 0.0 -2.96296E-6 L 0.0 -0.41088 *3>*B ppt_xB ppt_y=@0BBAApBBB(}R<*D$' =A@BB@BB0B%()?)?Dk' =.37 BBBBBEM 0.0 -1.48148E-6 L 0.0 -0.41551 *3>*B ppt_xB ppt_y=@0BBAApBBBT<*D@' =A@BB@BB0B%()?)?D' =.O7 BBBBBaM -3.33333E-6 4.81481E-6 L -3.33333E-6 -0.4088 *3>*B ppt_xB ppt_y=@0BBAApBBBMQ<* D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(+x+0+5  ++0+ 5  ++0+ 5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+5  ++0+ 5  ++0+ 5  ++0+ 5  + Q f ^   (    0l5  ,$ 0 (All previously known ZK protocols used black-box simulators [GMR,GMW,BCC,FS,GKa,RK,& ](X( 2>.?   Y  05 P p ,$ 0 CConjecture: If a protocol is ZK, then it has a black-box simulator.JD( 2 $  C z d    `|,$D 0`"  0d '  0P5 p COur main result: Conjecture is false. (Under standard assumptions) DD( 2C    05  -t   5     0H5 p +/Formal Def: 8 efficient verifier V* 9 S* s.t. 0( 2 3GG.*   X   05  VV* s view in interaction w/ P(x,w) S*(x)P,( 2 .       0d5 0 +Black-Box Simulation: Show alg S s.t. 8 V* ,( 23 GH        05  p* $V* s view SV*(x)^( 2  P  0|5   ,$ 0 6Implication: Black-box ZK limitations ) ZK limitationsN7( 2 G6 H  0޽h ? fff̙___PPT10.hI+cD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*++0+4  ++0+4  ++0+4  +F Q }(  r  S  4 -tA`  4  }  0p 4  aMain Thm: If CRH* exist then there exists a ZK argument that does not have a black-box simulator.jb( 2 9  .  Y "  0`4   R*CRH  Collision Resistent Hash functions*( 2*.    LB  c $D .  0 4 @@`,$ 0 *Proof: Combine the following two theorems:8+( 2$*   0(!4 0,$ 0 Thm 1 [GolKra89]: If LBPP then every constant-round Arthur-Merlin argument for L does not have a black-box simulator.x( 2    " t    0/4 j 0p ,$ 0 SThm 2: If CRH exist then every L2NP has a constant-round Arthur-Merlin ZK argument.T( 2C" P    0,:4  `,$ 0 wRemark: Protocol of Thm 2 has other useful properties impossible to obtain w/ black-box simulation. More details later.6x( 2p.  `    B@4 GHr  `,$D 0 n With negligible soundness error.!!     s *"`  ,$D 0l    ,$D  0   <E4    Rest of the talk: Proof of Thm 2*! f.   h  s *̙"`0PH  0޽h ?  fff̙q7i7___PPT10I7.s+? cD 4' = @B D3' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D$' =%(D' =%(Dt' =A@BB7BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-g6B fade*<3<* D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-g6B fade*<3<* D\' =%(D' =%(D' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*Ds' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D)' =4@BB BB%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D)' =4@BB BB%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D@' =A@BB@BB0B%()?)?D' =.O7 BBBBBaM 3.33333E-6 -4.07407E-6 L 3.33333E-6 -0.40671 *3>*B ppt_xB ppt_y=@0BBAApBBB[P<* D6' =A@BB BB0B%( D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(++0+4  ++0+4  ++0+4  ++0+4  ++0+4  ++0+4  ++0+4  ++0+ 4  ++0+ 4  ++0+ 4  ++0+ 4  ++0+ 4  ++0+ 4  ++0+ 4  + Q    l (  X"  0p` x  c $d4 -t`  4  {  0`f4 ` SThm 2: If CRH exist then every L2NP has a constant-round Arthur-Merlin ZK argument.T( 2C" P Hl 0  0 0 ,$D 0n   0|"`0 V   6hs4   RIntuition of Construction: To prove x2L , prove that either x2L or prover knows the verifier s program Such that verifier can t distinguish between 1st case & 2nd case.^( 2 fGfffffGfffff.  j   04  `p,$ 0 jProtocol will be Sound because honest verifier will use a program chosen at random (from some collection).4k( 2Uj e   0ȍ4 `,$ 0 OProtocol will be ZK because non-black-box simulator knows the verifier program