ࡱ>  `!<]ƨ,"'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[NKQUfTetr s琐t]8_YtӺ:Y[,2 b~*!b VĹ""t\*Φ[SOՙ~&d8c\ :8nQ$X[UHpk•m.d>n9V>g>x07{=sAž@Z#K M~ڃ`^%6WB2g>7aEhSBȢn`Eerd8cӉ숉pZK{a nqVU^Kڒ;-hXw۾ \K((/%FIE~.}[D9+ֆ45e]Z B"-"">TilnTgȞ!.[RSg[ocjˢhugӶhcd`":8ۧDD]y,""! Zuz Ǚ]ji)鄂3P0oRWiaeI2kj}$e7d9.e-JJF;ehOVOxSe;B".j/6Ҹ+E,g.$slҘzMP{UnϹ٧c"!^ruZOYP\;֑E-Mgc7'@]^cU RSq >g**Hum\dؐǿ>]CSQ/ysJdn'b$(y 7WJ{ jxd\vtVd0Yqwqܓrm7m㷈DEEI,m g COWJfGZKQRRdJhUιRsZyw^dAط=w[bTYAبtZk| l'ǖFSdVC1!a-L""xu( / 0DArialra Romantt0 0DLucida Sansmantt0 0" DWingdingssmantt0 00Dcmsy10gssmantt0 0"@DTahomagssmantt0 0"PDComic Sans MSntt0 0B`DTimes New Romantt0 0pDVerdanaw Romantt0 0"DSymbolw Romantt0 0DMT Extra Romantt0 0G .  @n?" dd@  @@`` >'   lBCDH'+_ d.&Fe-(&#'1)4l /''' "R "!#I!     )&( +I)  ()&('                       qr ?       67&A%*'&# #%!*$$D ()7   (!&#$%()*+23456789:7;/X2$<]ƨ,"'kg;^R$'zj=5 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[ \]^_ `ab@<3f@TPw,Zʚ;s5ʚ;g4DdDdD 0ppp@ <4dddd@k 0t  <4BdBd@l 0t80___PPT10 ?  %OaStatistical Zero-Knowledge Arguments & Statistically Hiding Commitments from Any One-Way Functionbb Assumptions for CryptographyOne-way functions ) Pseudorandom generators [Hastad-Impagliazzo-Levin-Luby90]. Pseudorandom functions & private-key cryptography [Goldreich-Goldwasser-Micali84] Commitment schemes [Naor89]. Zero-knowledge proofs for NP [Goldreich-Micali-Wigderson86]. Digital signatures [Rompel90]. Almost all cryptographic tasks ) one-way functions. [Impagliazzo-Luby89, Ostrovsky-Wigderson93] Some tasks not  black-box reducible to one-way fns. Public-key encryption [Impagliazzo-Rudich89] Collision-resistant hashing [Simon98] T!4  ,5T Main ResultsGOne-Way Functions ) Statistical ZK Arguments for NP & Statistically Hiding Commitments Resolves an open problem posed by [Naor-Ostrovsky-Venkatesan-Yung92]. OWF implied by commitments & ZK for hard-on-avg problems [Impagliazzo-Luby89,Ostrovsky-Wigderson93]. Key to unconditional results about ZK Arguments [Ong-Vadhan07]. YZ0Z2E#"<*  xoutline0 Introduction Commitments & ZK Constructions from OWF with structure Construction from any OWF ZK  Instance-Dependent Commitments Open Problems< PXC1outline0 Introduction Commitments & ZK Constructions from OWF with structure Construction from any OWF ZK  Instance-Dependent Commitments Open ProblemsR PFG1;<Commitment Schemes=Commitment SchemesBCommitment Schemes ASecurity of CommitmentsBHiding Statistical Computational Binding Statistical ComputationalPCStatistical Security?BHiding Statistical Computational Binding Statistical Computationaln  DStatistical BindingBHiding Statistical Computational Binding Statistical Computationaln  EStatistical HidingBHiding Statistical Computational Binding Statistical Computationaln  FBenefit of Statistical Hiding|In most protocols that use commitments: Binding only required during protocol execution Depends on adversary s current capabilities Safe to be computational Hiding may matter long after execution Adversary may gain computational resources Hardness assumption may be broken Statistical hiding )  everlasting secrecy (0F'y(0('`CG=Example: Zero Knowledge for NP [Goldreich-Micali-Wigderson86]>  Hiding ) Zero Knowledge Verifier learns nothing other than x2L Binding ) Soundness Prover cannot convince verifier if xL*)'G$GG $,Vr8.Complexity of Statistically Hiding Commitments// b.Complexity of Statistically Hiding Commitments// s.Complexity of Statistically Hiding Commitments// JOverview of the construction outline0 Introduction Commitments & ZK Constructions from OWF with structure Construction from any OWF ZK  Instance-Dependent Commitments Open ProblemsR P!'G1Structured One-Way Functions f : {0,1}n! {0,1}n is one-way function if: Computable in poly-time. If x{0,1}n, no poly-time algorithm can find a preimage of f(x) w/nonneg. prob. Regular OWF: f-1(y) same size for all y2f({0,1}n). One-Way Permutation: f a permutation.:,j]  C C F  C >tfK0One-way permutations ) Stat. hiding commitments,1   LInteractive Hashing MInteractive Hashing N0One-way permutations ) Stat. hiding commitments,1   O4Regular one-way functions ) Stat. hiding commitments,5   P4Regular one-way functions ) Stat. hiding commitments,5   Q4Regular one-way functions ) Stat. hiding commitments,5   R4Regular one-way functions ) Stat. hiding commitments,5   S2Regular one-way functions (unknown preimage size)33 $TFCan the receiver trust sender s t*?$$U1-out-of-2 binding commitmentsiCommitment in 2 phases. Statistically hiding in both phases. Computational binding in at least one phase.zjZ& V2Regular one-way functions (unknown preimage size)33 $W2Regular one-way functions (unknown preimage size)33 $X2Regular one-way functions (unknown preimage size)33 $Y1-out-of-2 binding commitmentsiCommitment in 2 phases. Statistically hiding in both phases. Computational binding in at least one phase.zjZ& Z2Regular one-way functions (unknown preimage size)33 $[2Regular one-way functions (unknown preimage size)33 $outline0 Introduction Commitments & ZK Constructions from OWF with structure Construction from any OWF ZK  Instance-Dependent Commitments Open ProblemsR PIG1Overview of the construction ^2Regular one-way functions (unknown preimage size)33 $_(Regular one-way functions same protocol6)  `2Regular one-way functions (unknown preimage size)33 $aRegular one-way functions  bRegular one-way functions  1-out-of-2 binding commitmentsiCommitment in 2 phases. Statistically hiding in both phases. Computational binding in at least one phase.zjZ& c2Regular one-way functions (unknown preimage size)$3  $d2Regular one-way functions (unknown preimage size)33 $e?(1/n)-hiding 1-out-2 binding commitments from one-way functions8@.   f2Regular one-way functions (unknown preimage size)$3  $Overview of the construction 4(1/n)-hiding ) W(1)-hiding: A hAmplify in O(log n) stages Each time d-hiding a 2d-hiding Inspired by [Reingold05,Dinur06] Each Stage O(1) repetitions of protocol. Combine using interactive hashing [OVY,CCM,DHRS]. Lose O(1) bits in message length. Nonstandard measures of hiding & binding quality. Start & end with O(log n)-bit messages. A sZ  * @#Z,  DW(1)-hiding ) statistically hiding2# AAmplify in 1 more stage Each Stage poly(n) repetitions of protocol. Combine using interactive hashing. Gain poly(n) bits in message length. Standard measures of hiding & binding quality. End with poly(n)-bit messages.  jO  B  0      >&CSOverview of the construction Overview of the construction 1-out-of-2 binding commitmentsiCommitment in 2 phases. Statistically hiding in both phases. Computational binding in at least one phase.zjZ& To Standard Commitments@Idea: Receiver randomly chooses whether to use 1st or 2nd phase.PAZ+  To Standard CommitmentsIdea: Receiver randomly chooses whether to use 1st or 2nd phase. Problem: Sender may decide which phase to break after choice of phase. AZZHZ+  @To Standard CommitmentsFix: Have sender provide a  collision-resistant hash of m Determines m (computationally). Enough entropy left in m to extract a random secret. At most one value of m allows breaking Phase 2 binding. ) only need UOWHF h<ZZZ8COverview of the construction outline0 Introduction Commitments & ZK Constructions from OWF with structure Construction from any OWF ZK  Instance-Dependent Commitments Open ProblemsT PdC"Instance-Dependent CommitmentsThm [OV07]: For every L2 NP, L has ZK protocol iff L has i.d. commitments [IOS94]. Moreover, stat/comp ZK $ stat/comp hiding proof/argument $ stat/comp binding Previously partial results [D89,D93,O91,OW93,MV03,V04,NV06,KMS07] < GGG!GW6-Instance-Dependent CommitmentsThm [OV]: For every L2 NP, L has ZK protocol iff L has i.d. commitments. stat/comp ZK $ stat/comp hiding proof/argument $ stat/comp binding Proof overview ()): 9 characterizations of all 4 ZK classes in terms of SZKP and  i.d. OWFs [V04,OV07]. i.d. OWFs ) i.d. commitments [HILL90,N91,NOV06,HR07]. SZKP i.d. commitments by combining i.d. 1-out-of-2 binding commitments [NV06] i.d. UOWHFs [OV]ZZ<Z < GG G"GGGH  G#<+,( Open ProblemsSimplify the construction. Better (sub-polynomial) round complexity. Requires non-black-box construction, even for one-way permutations [HHRS07]. Complexity of other crypto primitives. Noninteractive zero knowledge for NP. Chosen-ciphertext secure encryption.TFN'KFN'K, ijklmno/ s:cv>?@Ituvwxyz{|}~   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>>L0 !0 (   r  63ff&#" `~  <; #" `\ ^ ; 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 +  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>>L0 !0(  0r 0 63ff&#" `~ 0 <D? #" ` ^} ? T Click to edit Master title style! !  0 6$? #" ` ` ? y9Click to edit Master text styles Second level Third level!   :H 0 0޽h ? 33<___PPT10u..H"+D=' = @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>>L0 (  r  63ff&#" `~H  0޽h ? 33<___PPT10u..H"+D=' = @B + full 0 P *(     0pB P   B X*   0B    B Z* d  c $ ?  B  0B  0 B RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6B _P  B X*   6%B _  B Z* H  0޽h ? 3380___PPT10.gp0(   0L0 '  @  (  x  c $D?0~}  ?   6D? "`p Salil Vadhan @ ``d    T̷? Ԕ?"6@`NNN?N A Minh Nguyen x    T? Ԕ?"6@`NNN?N C Shien Jin Ongx     `T?8c?"0@NNN?NP}p DHarvard UniversityF ? >P   P A@ 4  N|? Ԕ?"6@`NNN?N? > P  pIftach Haitnerx$  N? Ԕ?"6@`NNN?N?  >O  C Omer Reingoldx&   `?8c?"0@NNN?N P  ^Weizmann Institute H  0޽h ? 33___PPT10i.gES+D=' = @B +  0 L0 L(  ~  s *tSB0 ^}  B   c $];0P  B ": H  0޽h ? 33<___PPT10u..h IC+D=' = @B +  0L0 p(B(  (x ( c $LnB \ ^  B  ( c $\;  ` B  H ( 0޽h ? 33___PPT10i.hQ9+D=' = @B +  0L0 !t~(  t t  6`B "`\ ^  B  t  6P~; "` B H t 0޽h ? 33<___PPT10i.hK+D=' = @B +  0L0  #~(     6\B "`\ ^  B    6\; "` B H  0޽h ? 33<___PPT10i.hK+D=' = @B +  0L0   6 (  V F    Pm N     hT  c $X99?   BC DEHFRH a a a   & ' ' 5 |*&(@`   BjCDEFWjuW @`5X  BqCDEF'q' @`Mr   BwC_DEF"_ww^w__@`,   BqCDEFKqqK @`   BC3DEF33 @` c   BCDE4F>  ``   @`J3s<   #   BdCiDE4F> idd;;4d4do;o;ddii @`YBe<  #    <tB0Ff *" h  s *"`  <B "`\ ^ &Commitment SchemesH  0޽h ? fff̙___PPT10i.K0͹s+D=' = @B + /  0L0  -6(    0lB 7  , 2!  0Bs GwZ  , 2!NF  "  F T   c $X99? "   BhCDEHFR!5!nMMS.h.h5!5&(@` "]   BCDEF @`H     BYC DE4F>  Y Y @`! h    B[CDEHFRZ[[555G5G[[Z&(@` 6 <  # ,  <  #      B}C:DE,F6 }rr}}rr::}}@`    BC DEFD D @`  h   B[CDEF&PP<[<[@`2 p <  #     BCDEFZ @` z   BZCDEFZ @` @%  BZCDEFZZ; @` %  xB(C/DEF/(/ @`Hz ^   BCDEF(y @` m:  BCDEF~a @`<(  BlCXDEF5X?fl5X @`cEu  BCDEF".^]@`8  BkCCDEF"QC"Ok/QC@`Nr  0|Bw  9m 2#$ z      ,$@ 0N   !  hT " c $X99?  # BC DEHFRH a a a   & ' ' 5 |*&(@`  $ BjCDEFWjuW @`5X % BqCDEF'q' @`Mr & BwC_DEF"_ww^w__@`, ' BqCDEFKqqK @` ( BC3DEF33 @` c ) BCDE4F>  ``   @`J3s< * #  + BdCiDE4F> idd;;4d4do;o;ddii @`YBe< , #   - < cB0F *" h . s *"` /  jA A  key1"` ^S<$D 0 B 1 s B0e0e  3"0e`\ ^  B  2 0,B F COMMIT STAGE (2 c 3 TBԔ?"6@`NNN?N0  ;S(2, 4 TBԔ?"6@`NNN?N0  ;R(2,H  0޽h ? 33334 TIMING|13.3|2.|1.1d___PPT10D.S+<'D'  q= @B Dc' = @BA?%,( < +O%,( < +D|' =%(D$' =%(D' =A@BBBB0B%()?)?D' =.7 BBBBBM 0.02048 0.0037 C 0.04201 0.02058 0.15121 0.07283 0.15104 0.10567 C 0.15087 0.1385 0.04687 0.18035 0.01962 0.20023 *3>*B ppt_xB ppt_y=B0BB aaapBBP=B?=<*D9' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*/%(D' =%(D}' =%(D%' =4@BB?BB%()?)?Dy' =.A7 BBBBBSM 5.E-6 1.85185E-6 L 0.63421 1.85185E-6 *3>*B ppt_xB ppt_y=@0BBAApBBO>B<* +p+0+0 ++0+0 +'  0L0 qi,5(  z  "   1n,$D 0T  c $X99? "  BhCDEHFR!5!nMMS.h.h5!5&(@` "]  BCDEF @`H    BYC DE4F>  Y Y @`! h   B[CDEHFRZ[[555G5G[[Z&(@` 6 <  # ,  <   #       B}C:DE,F6 }rr}}rr::}}@`     BC DEFD D @`  h    B[CDEF&PP<[<[@`2 p <   #     BCDEFZ @` z   BZCDEFZ @` @%  BZCDEFZZ; @` %  xB(C/DEF/(/ @`Hz ^   BCDEF(y @` m:  BCDEF~a @`<(  BlCXDEF5X?fl5X @`cEu  BCDEF".^]@`8  BkCCDEF"QC"Ok/QC@`Nr ! 0; 8  ;m(2#$F   "  _"T # c $X99?  $ BC DEHFRH a a a   & ' ' 5 |*&(@`  % BjCDEFWjuW @`5X & BqCDEF'q' @`Mr ' BwC_DEF"_ww^w__@`, ( BqCDEFKqqK @` ) BC3DEF33 @` c * BCDE4F>  ``   @`J3s< + #  , BdCiDE4F> idd;;4d4do;o;ddii @`YBe< - #   . <0q0F *"   04q 7  , 2!  088q6 Gw  , 2!  XA   key15  q   04qԔ?"6@`NNN?N0  ;R(2, 2 s dBq0e0e  3"0e`\ ^  q  3 TPCqԔ?"6@`NNN?N0  ;S(2, 5 0HGq F REVEAL STAGE (2 cH  0޽h ? 33337, TIMING|2.1|2.5___PPT10.S+/ƞHD' = @B Dj' = @BA?%,( < +O%,( < +D' =%(D' =%(D+' =4@BB?BB%()?)?D' =.G7 BBBBBYM 1.11111E-6 7.40741E-7 L 0.60104 -0.00764 *3>*B ppt_xB ppt_y=@0BBAApBBݙ>B<*D' =%(Df' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*"%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(+6   0L0 5 -  (    N8c?"0@NNN?N   x  c $Pq \ ^  q B  NDo?"0@NNN?N  P   0LRq` p F COMMIT STAGE (2 c  Z Wq8c?"0@NNN?N P   @accept/ reject  T[qԔ?"6@`NNN?N0 P  ;S(2  T^qԔ?"6@`NNN?N ;R(26    `bq8c?"0@NNN?N` Z nm2{0,1}tJ C B   NDo?"0@NNN?N PB   NDo?"0@NNN?N PB   NDo?"0@NNN?N@ P@B   NDo?"0@NNN?NF PF   0jq` p  F REVEAL STAGE (2 c  Z8oq8c?"0@NNN?NV `lP  Y(m,K)H  0޽h ? 33<___PPT10i.`V+D=' = @B +V&  0L0 me@%(   % N8c?"0@NNN?N   r  S xq \ ^  q B  NDo?"0@NNN?N  P   0yq` p F COMMIT STAGE (2 c  Zh{q8c?"0@NNN?N P   @accept/ reject  TqԔ?"6@`NNN?N0 P  ;S(2  TqԔ?"6@`NNN?N ;R(26   `hq8c?"0@NNN?N` Z nm2{0,1}tJ C B  NDo?"0@NNN?N PB  NDo?"0@NNN?N PB  NDo?"0@NNN?N@ P@B  NDo?"0@NNN?NF PF   0Dq` p  F REVEAL STAGE (2 c  Zq8c?"0@NNN?NV `lP  Y(m,K)   HLq  "`  `<$ 0 q B !@ ND8c?"0@NNN?N,$D 0< "  f q8c))?"6@`NNN?Nh `,$@ 0 4|COMMIT(m) & COMMIT(m ) indistinguishable even to cheating R*p?  cc*      $*B #@ ND8c?"0@NNN?N? X? ,$D  0@ $  f\q8c))?"6@`NNN?N ,$@  0 8pEven cheating S* cannot reveal (m,K), (m ,K ) with mm f9   %>  H  0޽h ? 33<yq___PPT10Q.`V+AzD}' = @B D8' = @BA?%,( < +O%,( < +D' =%(%(DM' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* !%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* !)%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* )5%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* 5C%(D' =%(Du' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*"%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =%(Du' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*#%(++0+ 0 ++0+"0 ++0+$0 +  0L0   P (    N8c?"0@NNN?N   x  c $q \ ^  q B  NDo?"0@NNN?N  P   0@!(  x  c $} \ ^     c $     I* F 7 e   -4Z 2  6 1  20 2  6ș   20 2  6 )  20 2  6;   20 2   6; > v 20 2   6; v  20 ZB   s *DjJ X ZB  B s *DjJ ^ ZB   s *DjJ X ZB  s *DjJ  ZB  s *DjJ  ZB  s *DjJ  ZB B s *DjJ    < el L 910   < .  920   <t  } 930   <P r  940   <T #  950   <\7 0  960 F  x     fB B 6|? x   BjJG  g(1,4)F0 PF pxh   J B fB B 6|?h xh f  6o p  f  6o pX  f  6o p  f   6oB p  f ! 6o p  f " 6o pP  F 2   # Px2 $ 60›33"`-m e  4 0 f % 6o2  f & 6o2  2 ' 6ƛ"`m U  4 0 F  P  ( \ pfB ) 6|? P ` * 0A?`  F ` + 0A?@ F  , T4ʛԔ?"6@`NNN?N  ;P(2 - TΛԔ?"6@`NNN?N ;V(2F 6Np . ` xH ZB / s *DjJA%AeZB 0B s *DjJX+;ZB 1 s *DjJH%*ZB 2 s *DjJR*ZB 3 s *DjJRRZB 4 s *DjJR*ZB 5B s *DjJ;*^T 3K`  6# 6Np2 7 6՛"`;s 00 2 8 6ٛ"`pK 00 2 9 6ܛ"`#( [`  00 2 : 6("`K 00 2 ; 6"`3pk 00 2 < 6833"`#[( 00 B = HDԔ?"0@NNN?N  @ Zdo?"0@NNN?N` ` D,$D 0 jCorollary: One-Way Functions ) Statistical Zero Knowledge Arguments for NP [Brassard-Chaum-Crepeau88]lk G2H  0޽h ? 33<___PPT10.h0 +crDO' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*@%(+8+0+@0 +Y) : 0L0   .t(  tx t c $ \ ^   D t T8c?"6@`NNN?NP]",$@ 0 Nnumber-theoretic assumptions6 t T`8c?"6@`NNN?N],$@  0 @claw-free permB  t TD8c?"0@NNN?N9` 9,$@ 0B t TD8c?"0@NNN?N` ,$@ 0% t N 8c?"0@NNN?NP 7,$ 0 ;[BCC]B !t ND8c?"0@NNN?N0P,$@ 05 #t Z8c?"0@NNN?NF_-,$ 0 ? [GMR,BKK]  ^l  R  +t R ,$@  0B $t TD8c?"0@NNN?N   %t N<8c?"0@NNN?N   :[NY] 't T8c?"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 `! 8c?"6@ NNN?Nx,$  0 <[GK]B .t TH&̙8c?"6@`NNN?Nz `,$@ 0 Lstat. hiding commitmentsH t 0޽h ? 33<___PPT10.h+]B@D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(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%(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 +& c 0L0 !(  B  TD8c?"0@NNN?N@` P x  c $`F \ ^   B  ND8c?"0@NNN?N ,$@ 0B  ND8c?"0@NNN?N  ,$@ 0  TH8c?"6@`NNN?NP]" Nnumber-theoretic assumptions  ThJ8c?"6@`NNN?N] @claw-free perm4  T R8c?"6@`NNN?N ] ,$@ 0 > one-way perm  3  T$V8c?"6@`NNN?N ] ,$@ 0 = regular OWF  B   TD8c?"0@NNN?N9` 9B   TD8c?"0@NNN?N` B   TD8c?"0@NNN?N` P ,$D 0B  TD8c?"0@NNN?N` ` ,$D  0/  T%HZ8c?"0@NNN?N  ,$ 0 ? [HHKKMS 05] -  T_8c?"0@NNN?N ,$ 0 = [NOVY 92]   Nb8c?"0@NNN?NP 7 ;[BCC]B  ND8c?"0@NNN?N0P  Z h8c?"0@NNN?NF_- ? [GMR,BKK]  8F  R    R B  TD8c?"0@NNN?N    N(l8c?"0@NNN?N   :[NY]  Tp8c?"6@`NNN?N R  T"collision-resistant hash functions##  T t 8c?"6@ NNN?Nx <[GK]  Ty̙8c?"6@`NNN?Nz ` Lstat. hiding commitments