ࡱ> `!<]ƨ,"'kg;^V-f\+QPx}wxU9 (/&w  @-R H:R$ XM "%>wzΜ={ٳZZė.xHk俽a>Q'|5]ʧ绩\̒|?$/">_HRRő|Q=ӡzȊ{լWw5r;ώ;pfgYZϻWzٽ_3>u+@{Ff́3pQ~֢Z*pJ+j Ժ ChmHЖ*|f5(5V 6j@-Fh<&#@U}3PQSү*"g.>qˡ\6n1^Z୒U2Z`ڣ.TD }K{Ki( ؞{&p#Tva3V1X0I8JM 4FݑzkqqY9vFjIQaWNfۤmʶN*jyߖKE[(m9RƢ͐6U)jRFI~.ymzKV&d`Iom$5HkZ]iyC-'sZPj>Vߓc[h٥dfEVh&Y)DctEDCB% +2n:;C^INKrCܑ R@BrR)&򕔓RAVIeY"dԔ9RWfK&2IZXi#2\:KW>Mq qNq,˕ Z(ǥRrIm)*+/i4yI.)I0#0Pwe#1XW+Q=\wY9)T'WPXacx%yeXY-XeդՒVO:ZCfM֎QFZWmd"3X!'2JM6SZ,(~$PW˟Ćؕ&Y|z^REI$oFf. )ޑ zW*TGM+-=F4 j>`ޤNT>ҿ'oT})o=b[+f>-c1J3T=uvPtW;ۅw8\i)LSMLFwj쳍$YZAFdFvF~AIGm̘HhSiKszЂq~Zh[bv{`evU>/,u0PYe"5ir0;1L4 9.vVϺ]j-f"rKv{zhw\y?\7\g4Gzf!e},8Ms\a~٠؍3o`N r/8q2{:cSyg pvқyØ4Dڠ9A:YYɓR ȏ<ȁ,8MA6x%C9oc&weܒQQ$/Ȏd&S:@Ke&PV2r< J^]>d/Ar7dN'e2qr;ݔ]J<JFx=:Q0)4#*+1ꨃ 4A eE>BO0D"1SE3i;B_џ<d"/ gDzG5-'DU\Mg~*.E>Ѿ /l%d+|2ⶉn+Rv'?DJ 4y]&v⺴[Ҋʢ oE;*tb T;]x+Z6&FGf%Qj>{smH]НznlpmeڌEiM0GkUcl+אKlТmvwmfpv@ 47QacIzXpAOO9^׽z[wqv]7럺ְ$/T\Rdwl=Y9MSj/*xQ P9gujKTώ0oTM/_z^km}nw/=U}v6sqS zxrYErsf?hNK)-gIeGe"s_ӫFm3rV3ZZ_s69y,Gdhɝ \C- t8u87i=UCskGV"#6WqǑ+c'O.9r!2q<##Rs1DT~Za%~!)51*CP쑞TݩSW6}XE-dkJ]ӈ9졎͖6m"X)iSSr&92 \}y?&WŻ]^c<#*>&:> J&Z^#j^$zH=C4M"&% n&/g9-aCŞTKF# C1}صD%CGD'hW6HY3-vDԲϤ%?E^9[/=$ordu)-1$7\@αPHSbMD3R͌䅹WkAG9W漚\WO㵉Ӗ;*NdXu!ʻ0H :tR8Z̟u@7b ڎ]s?8$#eF7i~N;9]-,l*|*ή8l"81ai! % 1'5fv`dwMPQ؁{.da{:;r*-N=[} /q0{GN{ ?mb/7z kdH!#;|=2_ɸ' }oqbNw2YfB}.DCIj겨@ZQМsy:pm'JDAۛ /Qd $16(10NЋ:sK4}7ǿ-M6jOsOO'O~X%ZqUhiZpmźjG/u>ڛ%}j½hJ\$!'2={@'rKG='gMet]?J޷>=Iy>ƻ}wa2̇(,g!_>F$IM{R.[^zJ!wX;?ϧWk$tȀLTY3y}AL1FR5ԦJ(Ry4e7hL=UIGM ?Q}v>GOaU\kF<+n.+(9ɼF1S=>#g7gJT9Hoa+OշV.Z56Vuڮp]n`+FXirc1Jiߣ9>qV-"]j [e\upw8&!&Rs]2hƮ֌`3vdM0ʢ";}e@]4=C06$mHؐLNtD59XiA[pgq ;^-dE~B:B(_؀]8p w} 5oPeQ Ah`t7>A`h` c5ȟYO3:_sh4fa:&aD#)/PQ_Bk≯c)qWT+,a _aWH[* jad`^ 1- ƗF(> BcԵBBdE#(:+AT-+M4-i$GIOuGvac׮fێݴ{$~q$d{x <V8L)nNLTutǻx]ĽVX]f:lrt"ptoC9g.q}uõiriND$FtB0}Qks9v-6p;i#10rȵe~[];栝q ˮ`.}yLWUԁ}#@t4hQ/X˰\=dc)PϺz}W]dnzMrp1BP=\}B` ݇HK)c&&OOHF %+YbP¬ nurC7:(F Yg8o$3@BVn3Nr|9\z_v/K|,NevZeu,r= KYQ5PВk"FWtG/smB044}lpVˍ$ k\6v)ڂmzпkklif_bS#]I                     qrs t?yz{|         ,2$<]ƨ,"'kg;^ 0e0e    A A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| "0e@     @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab0 <3f@TPw,Zʚ;s5ʚ;g4,d,d -a0ppp@ <4dddd8))0l3 <4BdBd8K*0l80___PPT10 ?  %#EStatistical Zero-Knowledge Arguments for NP from Any One-Way FunctionFF Assumptions for CryptographyOne-way functions ) Pseudorandom generators [Hastad-Impagliazzo-Levin-Luby]. Pseudorandom functions & private-key cryptography [Goldreich-Goldwasser-Micali] Commitment schemes [Naor]. Zero-knowledge proofs for NP [Goldreich-Micali-Wigderson]. Digital signatures [Rompel]. Almost all cryptographic tasks ) one-way functions. [Impagliazzo-Luby, Ostrovsky-Wigderson] Some tasks not  black-box reducible to one-way fns. Public-key encryption [Impagliazzo-Rudich] Collision-resistant hashing [Simon] P4(5Pt-KE!8c' Main ResultOne-Way Functions ) Statistical Zero-Knowledge Arguments for NP Resolves an open problem posed by [Naor-Ostrovsky-Venkatesan-Yung92]. OWF is essentially the minimal complexity assumption for ZK [Ostrovsky-Wigderson].nA 2.#">Notions of Zero KnowledgeZero Knowledge statistical computational Soundness statistical (proofs) computational (arguments) [Brassard-Chaum-Crepeau] Completenessr H  / 'Notions of Zero KnowledgezZero Knowledge statistical computational Soundness statistical (proofs) computational (arguments) [Brassard-Chaum-Crepeau]v H  (Notions of Zero KnowledgezZero Knowledge statistical computational Soundness statistical (proofs) computational (arguments) [Brassard-Chaum-Crepeau]v H  )Notions of Zero KnowledgezZero Knowledge statistical computational Soundness statistical (proofs) computational (arguments) [Brassard-Chaum-Crepeau]v H  7Zero Knowledge for NP |Commitment SchemesPolynomial time algorithm Com(b; K) s.t. Hiding For random K, Com(0; K) Com(1; K) Binding Com(b; K) cannot be opened to b , where b b.*f* ,0Zero Knowledge for NP: Graph 3-Coloring Protocol11  0Zero Knowledge for NP: Graph 3-Coloring Protocol11   0Zero Knowledge for NP: Graph 3-Coloring Protocol11  8Zero Knowledge for NP 9Zero Knowledge for NP r8"Complexity of SZK Arguments for NP## b"Complexity of SZK arguments for NP## s"Complexity of SZK arguments for NP## u:"Complexity of SZK Arguments for NP## 1-out-of-2 binding commitmentsiCommitment in 2 phases. Statistically hiding in both phases. Computational binding in at least one phase.zjZ& 81-out-of-2 binding commitments suffice for SZK arguments99 iCommitment in 2 phases. Statistically hiding in both phases. Computational binding in at least one phase.zjZ& 81-out-of-2 binding commitments suffice for SZK arguments99 iCommitment in 2 phases. Statistically hiding in both phases. Computational binding in at least one phase.zjZ& :Zero Knowledge for NP 23Overview of our construction from one-way functions44 3OWF ) (1/n)-hiding&A.Starting Point: OWF w/  approximable preimage size ) stat. hiding commitments [HHK+05] Idea: sender  guess preimage size ) hiding w.p. 1/n Problem: sender sends overestimate. Solution: use second phase to  prove estimate correct [NV06] Main tool: interactive hashing [OVY]"%&Cc ccccccc cc0cc%cP A44(1/n)-hiding ) W(1)-hiding: A Amplify in O(log n) stages Each time d-hiding a 2d-hiding Inspired by [Reingold05,Dinur06] Each Stage O(1) repetitions of basic protocol Combine using interactive hashing [OVY] Analyze with nonstandard measures.A n * n 5 Future WorkStandard statistically hiding commitments from OWF. Useful for verifier commitments. Many applications beyond ZK. Better (sub-polynomial) round complexity Open even for one-way permutations [NOVY]. Simplify the construction.j4?),4?),/ # s:w<cv~"#*+,  0` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>&- {p_/̴` <` 33<` 33<` 33<>?" dd@$?dd2@ %  %" @% ` n?" dd@   @@``PR    @ ` ` p>>^N0 !0 (   r  63ff&#" `~  <8 #" `\ ^  T Click to edit Master title style! !   6 #" ` `  y9Click to edit Master text styles Second level Third level!   :H  0޽h ? 33<___PPT10u..H"+D=' b= @B +  Narrow  0` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>&- {p_/̴` <` 33<` 33<` 33<>?" dd@$?dd2@ %  %" @% ` n?" dd@   @@``PR    @ ` ` p>>^N0 !0(  0r 0 63ff&#" `~ 0 <e #" ` ^} e T Click to edit Master title style! !  0 6xe #" ` ` e y9Click to edit Master text styles Second level Third level!   :H 0 0޽h ? 33<___PPT10u..H"+D=' b= @B + Wide 0` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>&- {p_/̴` <` 33<` 33<` 33<>?" dd@$?dd2@ %  %" @% ` n?" dd@   @@``PR    @ ` ` p>>^N0 (  r  63ff&#" `~H  0޽h ? 33<___PPT10u..H"+D=' b= @B + full0 P *(     0Pie P   e X*   0@oe    e Z* d  c $ ?  e  0re  0 e RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6ye _P  e X*   6H|e _  e Z* H  0޽h ? 3380___PPT10.gp0 0^N0 @ 0(  x  c $e0~}  e   6e "`P  Salil Vadhan @ ``d h8 ? >P   @?     Te Ԕ?"6@`NNN?N? > P  A Minh Nguyen x     TD/e Ԕ?"6@`NNN?N?  >O  C Shien Jin Ongx     `3e8c?"0@NNN?N }  DHarvard UniversityH  0޽h ? 33___PPT10i.gES+D=' b= @B + 0 ^N0 L(  ~  s *e0 ^}  e   c $Xe0P  e ": H  0޽h ? 33<___PPT10u..h IC+D=' b= @B + 0^N0 p(B(  (x ( c $he \ ^  e  ( c $@e  ` e  H ( 0޽h ? 33___PPT10i.hQ9+D=' b= @B + 0^N0 0  6(  ~  s *$e \ ^  e   s *$e  `<$0 e   <b <0 Ooldwasser-Micali-Rackoff]B @ TD8c?"0@NNN?NG &  # lb8c))?"6@`NNN?N _ LVerifier learns nothing B  @ TD8c?"0@NNN?N@ ]   # le8c))?"6@`NNN?N @|  5Prover cannot convince Verifier of false statements 660H  0޽h ? 33___PPT10.h`rf++De' b= @B D ' = @BA?%,( < +O%,( < +D' =%(%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)3%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*{%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*3H%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*H{%(+8+0+0 +  0^N0 0 (  ~  s * \ ^   ~  s *|  `    < <0 Ooldwasser-Micali-Rackoff]B @ ND8c?"0@NNN?NG     f4 8c))?"6@`NNN?N _ LVerifier learns nothing B @ ND8c?"0@NNN?N@ W   f8c))?"6@`NNN?N @|  5Prover cannot convince Verifier of false statements 660   T8c?"0@NNN?N : VThm [Fortnow,Aiello-Hastad]: Only languages in AM co-AM have statistical ZK proofs.VW0n2C#$=H  0޽h ? 33___PPT10i.h`rf+D=' b= @B +I  0^N0 H@p $(  $~ $ s *D \ ^   ~ $ s *E  `   $ <F <0 Ooldwasser-Micali-Rackoff]B $@ ND8c?"0@NNN?NG   $  fL8c))?"6@`NNN?N _ LVerifier learns nothing B $@ ND8c?"0@NNN?N@ W $  fP8c))?"6@`NNN?N @|  5Prover cannot convince Verifier of false statements 660  $ TV8c?"0@NNN?N : "Thm [1980 s]: one-way functions ) all of NP has computational ZK proofs.VL0n2 C*IH $ 0޽h ? 33___PPT10i.h`rf+D=' b= @B +|  0^N0 1) ,(  ,~ , s *` \ ^   ~ , s *\9  `   , < ? <0 Ooldwasser-Micali-Rackoff]B ,@ ND8c?"0@NNN?NG   ,  f|8c))?"6@`NNN?N _ LVerifier learns nothing B ,@ ND8c?"0@NNN?N@ W ,  fP8c))?"6@`NNN?N @|  5Prover cannot convince Verifier of false statements 660  , T،8c?"0@NNN?N :,$0 KThm [today]: one-way functions ) all of NP has statistical ZK arguments.VL0n2C+IH , 0޽h ? 33___PPT10.h`rf+ DO' b= @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* ,%(+8+0+ ,0 + 0^N0    |& (  |x | c $P \ ^    |  `@8c?"0@NNN?Nl!  IOne-Way Functions | N1?"0@NNN?N@@0  |  `8c?"0@NNN?NPC@  JCommitment Schemes  |  `8c?"0@NNN?N A ZK for NP  8 |  `T8c?"0@NNN?N0 q  p[Goldreich- Micali- Wigderson]  h |  ``8c?"0@NNN?N0   *[Hastad- Impagliazzo- Levin-Luby], [Naor]++>    | N1?"0@NNN?N@@0 $  |  `8c?"0@NNN?N@1x \$computational zero-knowledge proofs%%  | N1?"0@NNN?N@@0 ,$D0H | 0޽h ? 33<___PPT10n.y+QDB' b= @B D' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* |%(+i  ~0 ^N0 h `   (    HHԔ?"6@`NNN?Npp   B x  c $ \ ^     c $  p    I  TԔ?"6@`NNN?N0 P  ;S(2  TMbԔ?"6@`NNN?N ;R(2B  ND|?"0@NNN?N l   NLԔ?"0@NNN?Np v  HCommit: c = Com(b;K)   N\Ԕ?"0@NNN?N   A Reveal: (b,K)B   ND|?"0@NNN?ND lD    Z8c?"0@NNN?N6n 0  T K {0,1}*.    Z\8c?"0@NNN?N = Sb2{0,1}0CH  0޽h ? 33<___PPT10i.h0 +D=' b= @B +A 0^N0 ((pBkh |((  hr h S H \ ^    h < O[Goldreich- Micali-Wigderson] 8 7 e  >h7 2 h 6 1  D0  2 h 6   D0  2 h 6 )  D0  2 h 6   D0  2  h 6 > v D0  2  h 6t v  D0  ZB  h s *DjJ X ZB  hB s *DjJ ^ ZB  h s *DjJ X ZB h s *DjJ  ZB h s *DjJ  ZB h s *DjJ  ZB hB s *DjJ   h <| el L 910  h <  .  920  h < $  } 930  h <' r  940  h <H,T #  950  h <.7 0  960  h T2Ԕ?"6@`NNN?N8@`X ;P(2 h T6Ԕ?"6@`NNN?N8X ;V(2G h <C"` ,$0 11. Randomly permute coloring & commit to colors..20 1bB2z h B F  ,$0 ]2. Pick random edge. ,0 l  x  Bh x ,$D0lB hB <|? x  h H$LjJG  g(1,4)F0 vl pxh  Ahx ,$@0fB hB 6|?h xh f  h 6o p  f !h 6o pX  f "h 6o p  f #h 6oB p  f $h 6o p  f %h 6o pP  Tl 6Np ?h ,$D0`B 'h 0DjJA%Ae`B (hB 0DjJX+;`B )h 0DjJH%*`B *h 0DjJR*`B +h 0DjJRR`B ,h 0DjJR*`B -hB 0DjJ;*^T 3K`  .h# 6Np2 /h 6W"`;s B0  2 0h 6Z"`pK B0  2 1h 6^"`#( [`  B0  2 2h 6a"`K B0  2 3h 6de"`3pk B0  2 4h 6h33"`#[( B0  4 6h <dl Z ,$ 0  4. Accept if colors different. J!0 l 2   @h P > ,$D 02 5h 6l33"`-m e  F 0  f 7h 6o2  f 8h 6o2  2 9h 6t"`m U  F 0  # :h <"`p * ,$0 u3. Send keys for endpoints. 0 bB2zl  P  Ch" P6 ,$D0fB ;h 6|? P ` +B#style.visibility<*Ah%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*?h%(D' =%(Du' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Bh%(D' =%(Du' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*:h%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Ch%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*@h%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*6h%(D' =%(D(' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*kh%(D' =-s6Bwipe(left)*<3<*khD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Dh%(++0+h0 ++0+h0 ++0+6h0 ++0+:h0 ++0+Dh0 +L( 0^N0 K'C'BBp&(  px p c $՗ \ ^    p < ח P[Goldreich- Micali-Wigderson] F 7 e  p 7 2 p 6ݗ 1  D0  2 p 6   D0  2 p 6Lߗ )  D0  2 p 6   D0  2  p 6 > v D0  2  p 6ؗ v  D0  ZB  p s *DjJ X ZB  pB s *DjJ ^ ZB  p s *DjJ X ZB p s *DjJ  ZB p s *DjJ  ZB p s *DjJ  ZB pB s *DjJ   p < el L 910  p < .  920  p <  } 930  p <l r  940  p <DT #  950  p < 7 0  960  p T Ԕ?"6@`NNN?N8@`X ;P(2 p TԔ?"6@`NNN?N8X ;V(2 p <t"`v  21. Randomly permute coloring & commit to colors. .30 1bB2z p <    ]2. Pick random edge. ,0 F  x  p  x fB pB 6|? x  p B 'jJG  g(1,4)F0 PF pxh  p x fB  pB 6|?h xh f !p 6o p  f "p 6o pX  f #p 6o p  f $p 6oB p  f %p 6o p  f &p 6o pP  F 6Np 'p  ZB (p s *DjJA%AeZB )pB s *DjJX+;ZB *p s *DjJH%*ZB +p s *DjJR*ZB ,p s *DjJRRZB -p s *DjJR*ZB .pB s *DjJ;*^T 3K`  /p# 6Np2 0p 62"`;s B0  2 1p 6 5"`pK B0  2 2p 68"`#( [`  B0  2 3p 6T="`K B0  2 4p 6@"`3pk B0  2 5p 6D33"`#[( B0   6p <G Z   4. Accept if colors different. J!0 F 2   7p  P > 2 8p 6W33"`-m e  F 0  f 9p 6o2  f :p 6o2  2 ;p 6["`m U  F 0   p 6|? P ` ?p 0A?`  F ` @p 0A?@ F  Ap B gԔ?"0@NNN?N hSoundness: Graph not 3-colorable ) V rejects w.p. 1/(# edges) because commitment bindingi  .B Bp HD|?"0@NNN?NppH p 0޽h ? 33<___PPT10i.h]+D=' b= @B +:( 0^N0 9'1'BCt&(  tx t c $(s \ ^    t <v P[Goldreich- Micali-Wigderson] F 7 e  t 7 2 t 64| 1  D0  2 t 6^b   D0  2 t 6耠 )  D0  2 t 6P   D0  2  t 6 > v D0  2  t 6 v  D0  ZB  t s *DjJ X ZB  tB s *DjJ ^ ZB  t s *DjJ X ZB t s *DjJ  ZB t s *DjJ  ZB t s *DjJ  ZB tB s *DjJ   t < el L 910  t <$ .  920  t <Ԓ  } 930  t <@ r  940  t <0T #  950  t <7 0  960  t TঠԔ?"6@`NNN?N8@`X ;P(2 t TठԔ?"6@`NNN?N8X ;V(2 t <ж"`v  21. Randomly permute coloring & commit to colors. .30 1bB2z t <   ]2. Pick random edge. ,0 F  x  t  x fB tB 6|? x  t BjJG  g(1,4)F0 PF pxh  t x fB  tB 6|?h xh f !t 6o p  f "t 6o pX  f #t 6o p  f $t 6oB p  f %t 6o p  f &t 6o pP  F 6Np 't  ZB (t s *DjJA%AeZB )tB s *DjJX+;ZB *t s *DjJH%*ZB +t s *DjJR*ZB ,t s *DjJRRZB -t s *DjJR*ZB .tB s *DjJ;*^T 3K`  /t# 6Np2 0t 6ʠ"`;s B0  2 1t 6Π"`pK B0  2 2t 6(Ѡ"`#( [`  B0  2 3t 6lϠ"`K B0  2 4t 6נ"`3pk B0  2 5t 6۠33"`#[( B0   6t <\ Z   4. Accept if colors different. J!0 F 2   7t  P > 2 8t 633"`-m e  F 0  f 9t 6o2  f :t 6o2  2 ;t 6"`m U  F 0   t 6|? P ` ?t 0A?`  F ` @t 0A?@ F  At BԔ?"0@NNN?N zZero knowledge: Graph 3-colorable ) Verifier learns nothing because commitment hidingL{Q  B Bt HD|?"0@NNN?NppH t 0޽h ? 33<___PPT10i.h]+D=' b= @B +  0^N0    hk (  hr h S Pb \ ^  b  h  ``8c?"0@NNN?Nl!  IOne-Way Functions h N1?"0@NNN?N@@0  h  `Pd8c?"0@NNN?NPC@  JCommitment Schemes  h  `h8c?"0@NNN?N A ZK for NP  8  h  `@l8c?"0@NNN?N0 q  p[Goldreich- Micali- Wigderson]  h  h  `p8c?"0@NNN?N0   *[Hastad- Impagliazzo- Levin-Luby], [Naor]++>    h N1?"0@NNN?N@@0 $  h  `w8c?"0@NNN?N@1x \$computational zero-knowledge proofs%%-  h  `x8c?"0@NNN?Np_* e-computationally hiding, statistically binding..H h 0޽h ? 33<___PPT10i.y+D=' b= @B + 0^N0    l9 (  lx l c $ \ ^    l  `إ8c?"0@NNN?Nl!  IOne-Way Functions l N1?"0@NNN?N@@0  l  `謡8c?"0@NNN?NPC@  JCommitment Schemes  l  `h8c?"0@NNN?N A ZK for NP  F l  `Ĵ8c?"0@NNN?N0 8q  ~[Brassard- Chaum- Crepeau],   l N1?"0@NNN?N@@0 %  l  `8c?"0@NNN?N@1x ]%statistical zero-knowledge arguments&&-  l  `8c?"0@NNN?Np]0* e-statistically hiding, computationally binding..  l N1?"0@NNN?N@@0 ,$@07  l  `<ȡ8c?"0@NNN?N,$0 ;???H l 0޽h ? 33<g____PPT10?.y+rD' b= @B D' = @BA?%,( < +O%,( < +D' =%(Du' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* l%(+8+0+ l0 +1 :0^N0 vn -t(  tx t c $  \ ^   D t T8c?"6@`NNN?NP]",$@0 Nnumber-theoretic assumptions6 t T< 8c?"6@`NNN?N],$@ 0 @claw-free perm7  t T\8c?"6@`NNN?N,$@0 A SZK argumentsB  t TD8c?"0@NNN?N9` 9,$@0B t TD8c?"0@NNN?N99,$@0B t TD8c?"0@NNN?N` ,$@ 0P t T̙8c?"6@`NNN?N z,$@0 Z&stat. hiding comp. binding commitments''% t N8c?"0@NNN?NP 7,$0 ;[BCC]% t ND8c?"0@NNN?NY@,$0 ;[BCC]B !t ND8c?"0@NNN?N0P,$@ 05 #t Z$#8c?"0@NNN?NF_-,$ 0 ? [GMR,BKK]  ^l  R  +t R ,$@0B $t TD8c?"0@NNN?N   %t N|'8c?"0@NNN?N   :[NY] 't T*8c?"6@`NNN?N R  T"collision-resistant hash functions##B (t ZD8c?"0@NNN?N@` P ,$@0: )t Z")/8c?"0@NNN?NI`O 0 ,$0 D[GMR, Damgard]2 -t T |4 8c?"6@ NNN?Nx,$ 0 <[GK]H t 0޽h ? 33< ___PPT10.h+1D' b= @B Dz' = @BA?%,( < +O%,( < +D ' =%(De ' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* t%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* t%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =%(D3' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*#t%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*!t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*-t%(DY' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*+t%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(t%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)t%(++0+t0 ++0+t0 ++0+ t0 ++0+t0 ++0+t0 ++0+t0 ++0+#t0 ++0+)t0 ++0+-t0 +) c0^N0  (  B  TD8c?"0@NNN?N@` P x  c $X \ ^   B  ND8c?"0@NNN?N ,$@0B  ND8c?"0@NNN?N  ,$@0  T[8c?"6@`NNN?NP]" Nnumber-theoretic assumptions  T_8c?"6@`NNN?N] @claw-free perm4  Tc8c?"6@`NNN?N ] ,$@0 > one-way perm  3  T0h8c?"6@`NNN?N ] ,$@0 = regular OWF     Tl8c?"6@`NNN?N A SZK argumentsB   TD8c?"0@NNN?N9` 9B   TD8c?"0@NNN?N99B   TD8c?"0@NNN?N` B   TD8c?"0@NNN?N` P ,$D0B  TD8c?"0@NNN?N` ` ,$D 0  T0r̙8c?"6@`NNN?N z Z&stat. hiding comp. binding commitments''K  T%w8c?"0@NNN?Ni  P ,$0 [ [HHK+ 05]6  -  T`}8c?"0@NNN?N ,$0 = [NOVY 92]   N8c?"0@NNN?NP 7 ;[BCC]  N8c?"0@NNN?NY@ ;[BCC]B  ND8c?"0@NNN?N0P  Z8c?"0@NNN?NF_- ? [GMR,BKK]  8F  R    R B  TD8c?"0@NNN?N    N8c?"0@NNN?N   :[NY]  Te8c?"6@`NNN?N R  T"collision-resistant hash functions##  T 4 8c?"6@ NNN?Nx <[GK]H  0޽h ? 33<NF___PPT10&.h+0nD' b= @B D' = @BA?%,( < +O%,( < +D' =%(%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+0 ++0+0 ++0+0 ++0+0 +8 v0^N0 7/`"(  x  c $` \ ^   B  ND8c?"0@NNN?N B  ND8c?"0@NNN?N  B @ ND8c?"0@NNN?N @  T8c?"6@`NNN?NP]" Nnumber-theoretic assumptions  Tܰ8c?"6@`NNN?N] @claw-free perm  T|8c?"6@`NNN?N ]  > one-way perm     T8c?"6@`NNN?N ]  = regular OWF     T8c?"6@`NNN?Np] Bone-way function   T¥8c?"6@`NNN?N A SZK argumentsB   TD8c?"0@NNN?N9` 9B  TD8c?"0@NNN?N99B  TD8c?"0@NNN?N` B  TD8c?"0@NNN?N` P B  TD8c?"0@NNN?N` `   Tȥ̙8c?"6@`NNN?N z Z&stat. hiding comp. binding commitments''  T% Υ8c?"0@NNN?Ni  P  [ [HHK+ 05]6    THӥ8c?"0@NNN?N  = [NOVY 92]   Nץ8c?"0@NNN?NP 7 ;[BCC]  Nxۥ8c?"0@NNN?NY@ ;[BCC]B  ND8c?"0@NNN?N0PB  TD8c?"0@NNN?N` B  TD8c?"0@NNN?N   Nߥ8c?"0@NNN?N  :[NY]B @ TD8c?"0@NNN?Np  @  THڥ8c?"6@`NNN?