ࡱ> ny YK/s2q m4mPNG  IHDRAfPLTEzr<1%YPBH\tRNSރYbKGDa cmPPJCmp0712OmIDATX˗Hn܊)R5/mTIUVssz)JX_%!ߐo!V]UQ`BQ?ʲYd~ѤjP-˱p-m?b7QheԩA-ߕ@Hu}ͨeDu] C }DM@ @&zw S~vV۶xG-/w|@W^:e!b¥-7 @:CN 2 \Yth8T~XM?^]Vy3HG.^7;!F^y.d ߬ŭlWX?H@'JbgV~I/3K4f_B|p[{4JX$rdݮ50NSË.i'fY΢~%PL3aB#/Bj2+J|'l,1cnjK7$ԻesKaԬMmz;q U09Q^(S/fj@*>!=3>3m⤎m*1U1 f;?4^e+fsLٚZc^<vlm7  {{goxˆɴK主ǂaj;W*WYE^Iȯ+jT'Qv$o嬭A@iP%R򍐕9ҋ_EY>E~I =Nx}P6%$j`J>}ZO! 0>{=60Z UX$\Q3" އv' &v4U;#R"u-SwA`j"a ,!,ܜ=D^\O闐Eʯ!F@eh5;2޶Ą¯0L2*C~= P\h_DDx`"忄<쳰3DRbXN낙Ҫ +1|@Iۿ`&?zduI۷ra'Mw8o{u+z 1|ںU{:9Y-ExDfUء{Ի@ܓP˟ YPGemq:ss괺bͶUpkċ'7LkK wP3Y9 1q=K2B~MD-<􋲪 V-k O*ANӎ nxe%'L(^(3DIpBUGN|RW~>6+(ĉoJ+^<\SKVUƠúÑ}\8MLOˬF--S1HXVIIR*~bL tԍUYQԈ9Kܣ/XY☛8vyvT5g$gޟToo7 @u@T+IENDB`( / 0DArialca b(0(z[ 0 "DGaramond b(0(z[ 0  DTimes New Roman(0(z[ 0 0DWingdingsRoman(0(z[ 0 @DHelveticaRoman(0(z[ 0 "PDcmsy10caRoman(0(z[ 0 "`DSymbolcaRoman(0(z[ 0 @0.  @n?" dd@  @@`` ( <P    () () 5 * + , -/ 0 12278,:;<oGKL1M0N,b$YK/s2q m4m  0AA@8%&38ʚ;ʚ;g4DdDd@z[ 0ppp@ <4ddddl 0a 80___PPT10 ?  %*Universal Arguments and Their Applications+ +A* Boaz Barak & Oded Goldreich AV       Interactive Proofs for NP8 C C C  $CS Proofs [M] : Informal Description% %C $   $CS Proofs [M] : Informal Description% %C $   CS Proofs: Formal Def C    CS Proofs: Formal Def C     Our Results: C     "Collision Resistant Hash Functions##C "    The Construction (following [K])(! C C   PCP Properties( C C        Proof of Knowledge PropertyC   /  ` 3333ff3` 3333f33ff3` "3333̙ff3` Kf3̙` &e̙3g3f` f333̙po7` ___f3̙;/f9` ff3Lm` ff3LmNLm` ___f33;/f9` ___f33;/f>?" dd@*?nAd@q<nAqFLK#M n?" dd@   @@``PR    M`2p>> x(    H? ?" `}  X Click to edit Master title style!!  @  HX? ?" `  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S  R  6@ #" `] `}` H@___PPT9"@ p*(       6 #" ``   f*      T  6 #" `] `}` H@___PPT9"@ r*&         C @ABCDE FjJ@3"0`B  s *DjJ"0 `0H  0޽h ? ___f33;/f___PPT10i.  +D=' = @B + Edge % e(    HHi? ?"@  X Click to edit Master title style!!    Hk? ?"   [#Click to edit Master subtitle style$$  R  6d #" `] `}` H@___PPT9"@ p*(       6Pr #" `]}   f*      T  6v #" `] `}` H@___PPT9"@ r*&         C @ABCDE F8c@3"@B  s *DjJ"  ,$ 0H  0޽h ? ___f33;/f___PPT10i.  +ityD=' = @B +% 0 f^(    0p        ^*  0  0@  Q `  H@___PPT9"@ h*"  d  c $ ?     0u   0   RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S   6 _     ^*  6  6A  _Q` H@___PPT9"@ h*"  H  0޽h ? 3380___PPT10.P巩&  (  x  c $p@  x  c $D   r  C JA2smalltree_text_bluetransR p  H  0޽h ? 33___PPT10i.ox+D=' = @B +7  % N F p  (  r"  S  @     0`P` 3[GMW] gave ZK proof w/ n2 complexity for 3-ColoringT40( 2CCKC3 "  0,P` tCorollary: ZK proof w/ t(n)4 complexity for any Ntime(t) language L. (Since L is t(n)2-time reducible to 3-Coloring)u0( 2 C CCKCC CCCCCCCKC.0  =   0P`  ]ICorollary: 8 NP language L 9 ZK proof for L w/ polynomial complexity. J0( 2 CCCC CCCCCCCCCI L  68c"` P`t  @What about a single universal proof system for all NP languages?`A0( 2C CCC C@   0XP`0 6Note: This is interesting even without the ZK property470( 2C2C6    00 P  Note order of quantifiers!60( 2G    0\`0 hn = input size"0( 2A H  0޽h ? 3fffff3̙3f̙___PPT10i.4+D=' = @B +*  % A 9   (  x"  c $      0P0 0 A CS proof system is a system for proving* membership in the (N)EXP-complete language U where 2 U iff M(x) outputs 1 within t steps ( t is binary number, M is non-deterministic machine)j0( 2CGLCCC CCCCCC CC CC CCCCCG Cb`      Q    0xZ 0`  ^Any NP language L is reducible to U by a O(n)-time reduction. (e.g., even if L 2 Ntime(n12) !)_0( 2CC CCCCCC CCCCKCC.)  2   0% 0\TL___PPT9.&@ M_Thus a CS proof system yields a single protocol for proving membership for all L2NP. (even NE)`0( 2OCCCCCCCCC(T   x  0T*@ `M  Verifier s complexity is fixed polynomial (e.g. n3) in |M|+|x|+|t|BC0( 21CKC.8    RB  s *DV  H  0޽h ? 3fffff3̙3f̙___PPT10i.4+D=' = @B +  %  O(  x"  c $T      0B0 0 A CS proof system is a system for proving* membership in the (N)EXP-complete language U where 2 U iff M(x) outputs 1 within t steps ( t is binary number, M is non-deterministic machine)j0( 2CGLCCC CCCCCC CC CC CCCCCG Cb`      Q   0xT P` vzOur Goal: Obtain a single (universal) argument for NP under a standard assumption (i.e., hardness for poly-size circuits).{0( 2 C CGCC CG C C CCz 8 P`   P`   00`P`  )Thm [K,M]: If there exists hash functions that are collision resistant for 2n-sized circuits then there exists a CS proof system.b0( 2 CBCK4CC" ~   0$hW +  Te"0( 2  H  0޽h ? 3fffff3̙3f̙___PPT10i.4+D=' = @B + % F >   (  x"  c $ @   6  0q 0  ZDef: <P,V> is a CS proof system for U if it satisfies: [complexity] V runs in probabilistic polynomial time [completeness] 8 <M,x,t> 2 U <P(w), V>(M,x,t)=1 where P(M,x,t) runs for tO(1) (possibly 2O(n)) steps [soundness] 8 2O(n)-sized P* and 8 <M,x,t> U Pr[ <P*,V>(M,x,t) = 1] = negl(n).0( 2 CCGCCC GCC(C GCC CCCCCCCGO CK C GCCCK CCCCCCCC CC          T        _  000P 9Note: Max running time of P < Allowed running time for P*:0( 2CCCCCCCC9 al `       ,$D 0   6(G "``    D0    0  ?Seems to inherently require subexponential hardness assumption.$@0( 2@C.   H  0޽h ?  3fffff3̙3f̙yq___PPT10Q.4+QD%' = @B D' = @BA?%,( < +O%,( < +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<* +! %  (  x"  c $ @   &  0h 0  ZDef: <P,V> is a CS proof system for U if it satisfies: [complexity] V runs in probabilistic polynomial time [completeness] 8 <M,x,t> 2 U <P(w), V>(M,x,t)=1 where P(M,x,t) runs for tO(1) (possibly 2O(n)) steps [soundness] 8 2O(n)-sized P* and 8 <M,x,t> U Pr[ <P*,V>(M,x,t) = 1] = negl(n).0( 2 CCGCCC GCC(C GCC CCCCCCCGO CK C GCCCK CCCCCCCC!C          T        _  000P 9Note: Max running time of P < Allowed running time for P*:0( 2CCCCCCCC9   0`@0,$ 0 tUniversal Argument*0( 2G   0P ` ,$ 0 opolynomial size(0( 2G B  s *D|`` `,$D  0B  s *D|   ,$D  0  0| $ 0TL___PPT9.&@ O[proof of knowledge] There is a polynomial-time weak knowledge extractor.xP0( 2CGCCC:G( : B  s *D|0,$D  0H  0޽h ? 3fffff3̙3f̙___PPT10.4+摀D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(left)*<3<* D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-s6Bwipe(left)*<3<* 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' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(left)*<3<*++0+ ++0+ ++0+  +T % kc(  r  S h  `}   v  0  ` jThm 1: If standard collision-resistant hash functions exist then there exists a universal argument system.fk0( 2CCGXCC" g   0 M `D  f Corollary 2: If standard collision resistent hash functions exist then there exists a ZK argument satisfying (as in [B]) - Non-black-box simulation - Constant-round - Arthur-Merlin (public coin) - Strict polynomial-time simulator - Bounded concurrent zero-knowledge  0( 2 CCGaCCCCCCCCCCCC#C.#      0`!  ` /Same conclusion as [B] under weaker hypothesis 600( 2.GC/ H  0޽h ? ___f3̙;/f9___PPT10i.Dpn'+D=' = @B +b % yq (  r  S H+  `}   W  01   Def: A family H = {Hn} of functions from {0,1}2n to {0,1}n is called collision resistent if for any poly-size A Prh2H[ A(h) = (x,y) s.t. h(x)=h(y) ] = negl(n)N0( 2C CCCCKCK CK CGCCCGOO*G  ;   !             H  0޽h ? ___f3̙;/f9___PPT10i.Kv+D=' = @B +5 % *+s(  `  s *"` Px  c $LG  `}   B  0H pp Thm [BFL]: NEXP=PCP[poly,poly]d0( 2 CC C CC<        # #" 60 ,$D 0  <O  ? g1  M  <|_  ? e0 M   <g  ?Z e0 M   <p  ?Z  e1 M   <x  ?   e0 M   <Ё  ?   e1 M   <(  ? f e1 M  <P  ?f* e0 M  <H  ?* e0 M  <$  ? e1 MfB  6o ?fB  6o ?fB  6o ?`B  01 ?`B  01 ?**`B  01 ?ff`B  01 ?  `B  01 ?  `B  01 ?  `B  01 ?ZZ`B  01 ?`B  01 ?fB  6o ?Rl 0 @  + 0 @ ,$D  0TB  c $D@ @@ TB  B c $D0  ZB ! s *D  ZB " s *Dp p ZB # s *D0 0 Q $ 0  ,$  0  Ppcp(M,x,t,w)j0( 2GO GO"   r % 6Z ,$@ 0 & 0 PP 0p,$ 0 zp D0( 2  l 0@   *@ 0 ,$D 0#  0     Vpcp(M,x,t)j 0( 2GOGO"   n ' 08c"`0@   ( 0Խ PPp,$ 0 40( 2CC&    ) 08 0,$ 0 4|p|=tO(1) (possibly 2O(n))0( 2CCK CKCK H  0޽h ? ___f3̙;/f9___PPT10.E`+<D' = @B Di' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D' =-g6B fade*<3<*(D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%%(D' =-g6B fade*<3<*%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' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<**%(D' =-g6B fade*<3<**D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*+%(D' =-s6Bwipe(down)*<3<*+D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =-g6B fade*<3<*$++0+$  ++0+&  ++0+(  ++0+)  +  %   1J (  ` 0 s *"` Pr  S  `}   0 . 0 PP [completeness] 9 P s.t. 8 <M,x,t> 2 U (and witness w) Pr[VP(M,x,t,w) (M,x,t)=1] =1 where P(M,x,t) runs in time tO(1) [soundness] If <M,x,t> U then 8 p Pr[ Vppcp(M,x,t)=1] < 2-n [non-adaptive verifier] Verifier s queries are non-adaptive [efficient reverse-sampling] Given i,q can sample random verifier tape conditioned on ith query being q. [proof of knowledge] 9 poly-time E s.t. If Vppcp(M,x,t) > 2-|x| then 9 witness w s.t. 8 i Pr[ Ep(<M,x,t>,i) = wi ] > 2/3v0( 2C GCCCCCC CCCCC CCCCG GCCCCKC GCCCCCCCGGOKGCG'CGCGCG0CGO CGCGCC CC CC CKCC CCCCCG GO Gx           %     k  0  3             H  0޽h ? ___f3̙;/f9___PPT10i.E`+D=' = @B +% 8D0DpqC(   " 0  0  uPua80( 2C K   # 04  uVua80( 2C K   p [ #" @ ,$@ 0 > <@  ?5 i1  M ? <|9  ?5 g0 M @ <S  ?^ g0 M A <l\  ?^ g1 M B <0e  ? g0 M C <n  ? g1 M D <w  ? g1 M E <L  ?F g0 M F <  ?F g0 M G <  ?p g1 MfB H 6o ?pfB I 6o ?pfB J 6o ?pp`B K 01 ?`B L 01 ?FF`B M 01 ?`B N 01 ?`B O 01 ?`B P 01 ?`B Q 01 ?^^`B R 01 ?`B S 01 ?55fB T 6o ?2 W 0 `,$ 0 h 2R Hh0( 2CCKCC  B Y@ c $D0,$@ 0l ` P ` P,$D 0h" \ s *"`` P ] 0    _h&0( 2C . W6 $ #" '6,$@ 0  <  ?W6 Z   MfB  6o ?WfB  6o ?6W6fB  6o ?WW6fB  6o ?6B @ c $D@,$@  0B @ c $D,$@  0B @ c $D0,$@ 0B  c $D,$D 0B  c $D,$D  0B  c $D,$@ 0B ! c $De,$@ 04 W6 1# #" 76,$@  0 2 <t  ?W6 Z   MfB 3 6o ?WfB 4 6o ?6W6fB 5 6o ?WW6fB 6 6o ?64 W6 ># #" '6,$D 0 ? <  ?W6 Z   MfB @ 6o ?WfB A 6o ?6W6fB B 6o ?WW6fB C 6o ?64 W6 K# #" 6,$@  0 L <  ?W6 Z   MfB M 6o ?WfB N 6o ?6W6fB O 6o ?WW6fB P 6o ?64 W6 X# #" Ip,$@ 0 Y <  ?W6 Z   MfB Z 6o ?WfB [ 6o ?6W6fB \ 6o ?WW6fB ] 6o ?64 W6 e# #" p,$D 0 f <`  ?W6 Z   MfB g 6o ?WfB h 6o ?6W6fB i 6o ?WW6fB j 6o ?6F   #" 0,$D 0  <  ? rroot  C MfB  6o ?fB  6o ?fB  6o ?fB  6o ?B @ c $D2,$@ 0B @ c $DPp,$@ 0B  c $D,p,$@ 0B  c $D2@,$@ 0  s *"`0  ,$@  0L  # #"  N,$D  0  <  ? rroot  C MfB  6o ?fB  6o ?fB  6o ?fB  6o ?l 0 P  0 0 ,$D 0h"  s *"`0 P   0     vrpcp80( 2CK l @ @,$D 0n  0B"`7@n  0B"`@Wn  0B"`0)n  0B"`)n  0B"`pn  0B"`0n  0B"`@gl i0 i0,$D 0`B  0D8cpPp  0@ i0c _q&0( 2C l 0 `  ` 0  ,$D  0h  s *"`0 ` *  0 `   path1,& ,pathkb0( 2CKCKK"    04 @ 0,$  0 Preliminary Observations: 1. Verifier complexity and communication is polynomial 2. Completeness follows from completeness of PCPb0( 2C4CC*CC    0\% @ ,$ 0 vXpathq,s is called a certificate that pq = s-0( 2GOC GCG (   00 Pp,$ 0 Vp$0( 2    02  0 40( 2CC&   H  0޽h ? ___f3̙;/f9+Q#Q___PPT10Q.J+gDO' = @B DO' = @BA?%,( < +O%,( < +D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*W%(D' =-g6B fade*<3<*WD' =%(D' =%(D9' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-u6Bwipe(right)*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*[%(D' =-g6B fade*<3<*[D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*DA' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =-g6B fade*<3<*$D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*Y%(D' =-g6B fade*<3<*YD+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*DA' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*1%(D' =-g6B fade*<3<*1D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D ' =%(D ' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*K%(D' =-g6B fade*<3<*KD+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =-g6B fade*<3<*!D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-g6B fade*<3<* D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*>%(D' =-g6B fade*<3<*>D ' =%(D ' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*X%(D' =-g6B fade*<3<*XD+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*e%(D' =-g6B fade*<3<*eD' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D&' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(left)*<3<*D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(left)*<3<*D' =%(D' =%(D9' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-u6Bwipe(right)*<3<*D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*D' =%(D' =%(D+' =4@BB BB%(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' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-s6Bwipe(left)*<3<*D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*++0+W  ++0+  ++0+  ++0+  +T]%  JJpz I(   ` |  s *"` P   08o  0  rP*80( 2C K     0y  uVua80( 2C K  j p  # #" @    <p  ?5 i1  M   <Ȁ  ?5 g0 M   <  ?^ g0 M   <  ?^ g1 M   <  ? g0 M   <  ? g1 M   <(  ? g1 M   <Է  ?F g0 M   <  ?F g0 M   <D  ?p g1 MfB   6o ?pfB   6o ?pfB   6o ?pp`B   01 ?`B   01 ?FF`B   01 ?`B   01 ?`B   01 ?`B   01 ?`B   01 ?^^`B   01 ?`B   01 ?55fB   6o ?   0D ` h 2R Hh0( 2CCKCC  LB  @ c $D0F ` P   ` Ph"   s *"`` P   0    _h&0( 2C j W6 ! # #" '6 "  <  ?W6 Z   MfB #  6o ?WfB $  6o ?6W6fB %  6o ?WW6fB &  6o ?6LB ' @ c $D@LB ( @ c $DLB ) @ c $D0LB *  c $DLB +  c $DLB ,  c $DLB -  c $Dej W6 . # #" 76 /  <  ?W6 Z   MfB 0  6o ?WfB 1  6o ?6W6fB 2  6o ?WW6fB 3  6o ?6j W6 4 # #" '6 5  <,  ?W6 Z   MfB 6  6o ?WfB 7  6o ?6W6fB 8  6o ?WW6fB 9  6o ?6j W6 : # #" 6 ;  <  ?W6 Z   MfB <  6o ?WfB =  6o ?6W6fB >  6o ?WW6fB ?  6o ?6j W6 @ # #" Ip A  <0  ?W6 Z   MfB B  6o ?WfB C  6o ?6W6fB D  6o ?WW6fB E  6o ?6j W6 F # #" p G  <  ?W6 Z   MfB H  6o ?WfB I  6o ?6W6fB J  6o ?WW6fB K  6o ?6j  L # #" 0 M  <%  ? rroot  C MfB N  6o ?fB O  6o ?fB P  6o ?fB Q  6o ?LB R @ c $D2LB S @ c $DPpLB T  c $D,pLB U  c $D2@` V  s *"`0  j  W # #"  N X  <1  ? rroot  C MfB Y  6o ?fB Z  6o ?fB [  6o ?fB \  6o ?z @ `  @,$D 0n a  0B"`7@n b  0B"`@Wn c  0B"`0)n d  0B"`)n e  0B"`pn f  0B"`0n g  0B"`@gF i0 h  i0`B i  0D8cpPp j  047 i0c _q&0( 2C v n  0\? @l  Soundness: If poly-size P* convinces Vua that <M,x,t> 2 U w.p. e then 9 pcp proof p* for <M,x,t> that convinces Vpcp w.p. e2  negl(n). 0( 2 CC CCC CCKCCCCCCCCCCCCCKC GCC%                   o  0<\ p0v,$ 0 fObservation: For any q, given two inconsistent paths pathq,0 and pathq,1 can obtain x,y s.t. h(x)=h(y)g0( 2 CC GCCCKCCCK CCC C|T         l  P y @,$D 0t r  63fB"`W t s  63fB"` w t t  63fB"` P t u  63fB"` < t v  63fB"`0 g t w  63fB"`P Pt x  63fB"``^ z  0Lk Pp Vp$0( 2  p {  0o   $ 0TL___PPT9.&@ bFix  typical choice of h. Assume w.l.o.g P* deterministic and so root is also fixed. We treat P* as a function that gets a random pcp-verifier tape and returns a list of paths.0( 2CCCCCCCC\C\"  , -  + l   ,$D 0 }  0 v  a4(0( 2E  ~  0 iP a3(0( 2E    0  a2(0( 2E    00  a1(0( 2E    0Ԋ  0 40( 2CC&   H   0޽h ? ___f3̙;/f9___PPT10.J+rKD' = @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<*o %(D' =-g6B fade*<3<*o D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*` %(D' =-g6B fade*<3<*` Dd' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*y %(D' =-g6B fade*<3<*y D' =%(D)' =4@BB1BB%()?)?D}' =.E7 BBBBBWM 3.33333E-6 1.11111E-6 L 0.03333 0.04444 *3>*B ppt_xB ppt_y=@0BBAApBB<Ba <<*y D' =%(D' =%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-g6B fade*<3<* +p+0+o   ++0+{   +R% &%60%(  0 0 0   0 ] rP*80( 2C K   0 0x ] uVua80( 2C K  @ }   0 #" 3] ,$D 0 }0 <  ?} ^  o0/1C M z0 <  ?}   m0C M w0 <  ?E}   e0C  M t0 <@  ? } E  m1C M 0 <H  ?}   o0  C M 0 <  ?} #  q0/1  C M 0 <  ?#} b  m0C M 0 <d  ?b}   m1C M  0 <(  ?}   m0C M  0 <  ?} '  o0/1C M  0 <$  ?' } g  m1C M  0 <  ?g }  e0C  M  0 <t  ? }  m0C M 0 <T(  ?^}   m1C MfB 0 6o ?} } fB 0 6o ?  fB 0 6o ?}  `B 0 01 ?^} ^ `B 0 01 ? } `B 0 01 ?g } g `B 0 01 ?' } ' `B 0 01 ?}  `B 0 01 ?}  `B 0 01 ?b} b `B 0 01 ?#} # `B 0 01 ?}  fB 0 6o ?}  ZB u0 s *1 ? } ZB x0 s *1 ?E} E ZB {0 s *1 ?}  ZB ~0 s *1 ?}   0 0t.  h 2R Hh0( 2CCKCC  F ` P 0 ` h" 0 s *"`` P  0 0$6    _h&0( 2C ` V0 s *"`0 0j  W0# #"  \ X0 <l:  ? rroot  C MfB Y0 6o ?fB Z0 6o ?fB [0 6o ?fB \0 6o ?> 0 0E P@,$ 0 hDefine: pq(s) = Pr[ P* sends pathq,s | q is asked ]50( 2CCGOGGOG@      Cl `   0 ` ,$D 0tr 0 68c"`  ' 0 08Q P   1 p_q(1) > p_q(0) 0 otherwiseR 0( 2G GG 8X 0 0[ ` '   p*q =r0( 2GOG  0 0c  P ,$ 0 dDefine&0( 2C  0 0h  @,$ 0 (JClaim: p* is a convincing pcp proof.&0( 2CGCCCC.    0 0o  0 40( 2