ࡱ> @=>?( / 0DArialgs(0(z[ 0 DTahomags(0(z[ 0 " DTimes New Roman(0(z[ 0 0DWingdingsRoman(0(z[ 0 @Dcmsy10gsRoman(0(z[ 0 "PDSymbolgsRoman(0(z[ 0  A .  @n?" dd@  @@`` 3         #$ %&' ()*,-./012 0AAP3@8w<^ ʚ;i8ʚ;g4LdLd@z[ 0ppp@ <4ddddl 0 <4!d!dl< 080___PPT10 ?  %/Lower Bounds for Non-Black-Box Zero Knowledge00=Boaz Barak (IAS*) Yehuda Lindell (IBM) Salil Vadhan (Harvard)b Interactive Proof Systems [GMR]$ $ Interactive Proof Systems [GMR]$ $ Interactive Proof Systems [GMR]$ $ Some Known Results A Natural Question The Public-Coin Case     !  $The Private-Coin Case %   &!  '"  " Other Results # Conclusions  Pfull8   R short8    T ` fzodf̙` Z\l[]kfEo` f3̙` hk]gj\fݿO` d^fPP̙f` N]1Ra3z` K` ~{3f` fff>?" dd@,?%Pd@ d %P@d`%P n?" dd@   @@``PR    @ ` `6p>> ځ,H(  ,F|T  , "/b  ,# " ,  D0e0e    B C>DETF\   ; 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||UtBstc=\;;d{}>C O9 . }  +,@S"w\v  ,  0e0e    B~C> DEF   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||!!A|:Gt[R[xQKSFT> "     OM ;~DU3CD@S"\  ,  t0e0e    BdC# DElFt   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||QHSqsuNp^^ Y # lj  2 s j X    ^d78@S"-xP  ,  0e0e    BC DEF   ; 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||##PR5i?-GEUFIv|o  q }?  g " 6  { !'q.i#1GH@S"yzAJ ,  0e0e    BCDE,F4   ; 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E|| ]WksT0@S"}*  ,  0e0e    BCC]DEF$   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||H (XC]@S"5x  ,  l0e0e    B C\ DEhFp   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||^qS|$>UvhX\ u*~rr@7  58@S" $ p  ,  0e0e    BwCEDEDFN   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||li>E wY#=l$(@`S"> +p   ,  40e0e    BC*DELFT   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||!tN:goOy*BY'(@S"   ,  <0e0e    B CDEPFX   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||  Q,b@H40x 0  T  S ),@S"b * ,  0e0e    B?CVDEF$   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||j9jz VA?@S"C0 ,  0e0e    BCDE$F.   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E|| @=mh@`S"Z xV , C 0e0e    B CDElFv d@  5% 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||`P@P@pp`P ` PP  pP` P` PP`p08<@`S"2` .Lb i ,# "it , 6Pq"^ jVt , 6Pq"AMSt , 6Pq"&2Nt , 6c"Tt , 6c"Yt , 6A+h"Xt , 6g"Vt , 6Y"Et , 6Y"iuHt , 6 ]"KWMt , 6_"+ 7Rt , 6^N"*t , 6R" t , 6R"-t  , 6T"0t !, 6e?"t ", 6e?"t #, 6/gD"wt $, 6H"Yet %, 6I"8"9IEt &, 6I"8"Y*t ', 6I"8"kt (, 6e?"|t ), 6_&"t *, 6_&""t +, 6D -" Rt ,, 6D -"l"xat -, 65n" H t ., 65n" 6 t /, 6M" # t 0, 6M"  t 1, 6"Y ' t 2, 6"L2 > t 3, 6">L X t 4, 6"(a mm t 5, 6"  t 6, 6T "  t 7, 6< "  t 8, 6< "u  t 9, 6" $ t :, 6"2 > t ;, 6"K W t <, 6ޑ"e q t =, 6z"  t >, 6K"  t ?, 6K"  t @, 6}"  t A, 6 " ' t B, 6p"0 < t C, 6p"H T t D, 6"c o t E, 6D"  t F, 6V"  t G, 6V"  t H, 6V"  t I, 6"MD P t J, 6C"ZU a t K, 6+"ik w t L, 6+"v|  t M, 6B" L t N, 6B"  a t O, 6B" p t P, 6", *  Q, BCDE,F6 @.^ ppO0@`"  t R, 6m" t S, 6"J V t T, 6Y"  t U, 6Y"  t V, 6Y"  t W, 6B" $ t X, 6["4Z @ t Y, 6["Ob [ t Z, 6  t a, 6J"59 A t b, 6"S6 _ t c, 6"r7 ~ t d, 6j"Q  t e, 6"L  t f, 6٧"H  t g, 6J"C  t h, 6̙" t i, 6|S"v  t j, 6&"$l 0 t k, 6+W"A^ M t l, 6" + t m, 6 "Z f t n, 6\"v t o, 6\" t p, 6!_" t q, 6r"# K/ t r, 66"r# ~t s, 66"{ m t t, 6r"# / t u, 6yb" t v, 6Ifo"o {t w, 6DmW"}t x, 68K"FROt y, 6k?" t z, 63"i,ut {, 6"" . t |, 6 "* 6 t }, 69"E t ~, 6("  t , 6[" t , 6o"+ 7 t , 6="0  t , 6~"  t , 6"3 % t , 60"{ " t , 6v" U t , 6o"r i~ t , 63" d t , 6Ü "f  t , 6"   , BCxDE4F> x *lr<f$Nlfl$$rx @`"R@   , BZCNDE4F> B$B$$N0H$$H6Z*6*B$ @`" m   , BeCYDE8FB6YAS0#YAe;SG S)0$-D)56Y @`"a[  , BSCNDE4F> $NS06$*606<$B0B$N @`"   , BZCHDE4F> ZB$H$B*$66<00< N*Z @`" &  , BZCTDE4F> *<*<H B*666HTZ*T*< @`"   , BC DEF& @`"  , BC0DEF&00*00@`" %+  , B$CBDEF&$$B$$@`"+Et , 6" : t , 6"a m ` , "BCDEF:""f;ojuxw=TT>7;*N h"l)o3u5{77/'~aM0$!YSOZk`"e hbf@           `" ` , "aBCDEF:""f;ojuxq/TT>7;*N h"l)o3u5{77/'~aM0$!YSOZk`"e hbf@           `"j # ,  h0e0e     ?B\CDEF d @ 5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||F\6 @`S" G2 ,  `r?2 @?"(   , 6 "`  T Click to edit Master title style! ! , 0ť "^`  X*  , 0ʥ "^   Z*  , 0Υ "^   Z* $ , 0ӥ "  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     Sr , Zd޽h @ ? Z\l[]kfEo80___PPT10. SE Compass=  0(  0F|T  0 "/b  0# " 0  D0e0e    B C>DETF\   ; 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||UtBstc=\;;d{}>C O9 . }  +,@S"w\v  0  0e0e    B~C> DEF   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||!!A|:Gt[R[xQKSFT> "     OM ;~DU3CD@S"\  0  t0e0e    BdC# DElFt   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||QHSqsuNp^^ Y # lj  2 s j X    ^d78@S"-xP  0  0e0e    BC DEF   ; 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||##PR5i?-GEUFIv|o  q }?  g " 6  { !'q.i#1GH@S"yzAJ 0  0e0e    BCDE,F4   ; 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E|| ]WksT0@S"}*  0  0e0e    BCC]DEF$   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||H (XC]@S"5x  0  l0e0e    B C\ DEhFp   ~@ 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||^qS|$>UvhX\ u*~rr@7  58@S" $ p  0  0e0e    BwCEDEDFN   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||li>E wY#=l$(@`S"> +p   0  40e0e    BC*DELFT   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||!tN:goOy*BY'(@S"   0  <0e0e    B CDEPFX   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||  Q,b@H40x 0  T  S ),@S"b * 0  0e0e    B?CVDEF$   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||j9jz VA?@S"C0 0  0e0e    BCDE$F.   tE 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E|| @=mh@`S"Z xV 0 C 0e0e    B CDElFv d@  5% 8c8c     ?1 d0u0@Ty2 NP'p<'p A)BCD|E||`P@P@pp`P ` PP  pP` P` PP`p08<@`S"2` .Lb i 0# "it 0 6Pq"^ jVt 0 6Pq"AMSt 0 6Pq"&2Nt 0 6c"Tt 0 6c"Yt 0 6A+h"Xt 0 6g"Vt 0 6Y"Et 0 6Y"iuHt 0 6 ]"KWMt 0 6_"+ 7Rt 0 6^N"*t 0 6R" t 0 6R"-t  0 6T"0t !0 6e?"t "0 6e?"t #0 6/gD"wt $0 6H"Yet %0 6I"8"9IEt &0 6I"8"Y*t '0 6I"8"kt (0 6e?"|t )0 6_&"t *0 6_&""t +0 6D -" Rt ,0 6D -"l"xat -0 65n" H t .0 65n" 6 t /0 6M" # t 00 6M"  t 10 6"Y ' t 20 6"L2 > t 30 6">L X t 40 6"(a mm t 50 6"  t 60 6T "  t 70 6< "  t 80 6< "u  t 90 6" $ t :0 6"2 > t ;0 6"K W t <0 6ޑ"e q t =0 6z"  t >0 6K"  t ?0 6K"  t @0 6}"  t A0 6 " ' t B0 6p"0 < t C0 6p"H T t D0 6"c o t E0 6D"  t F0 6V"  t G0 6V"  t H0 6V"  t I0 6"MD P t J0 6C"ZU a t K0 6+"ik w t L0 6+"v|  t M0 6B" L t N0 6B"  a t O0 6B" p t P0 6", *  Q0 BCDE,F6 @.^ ppO0@`"  t R0 6m" t S0 6"J V t T0 6Y"  t U0 6Y"  t V0 6Y"  t W0 6B" $ t X0 6["4Z @ t Y0 6["Ob [ t Z0 6  t a0 6J"59 A t b0 6"S6 _ t c0 6"r7 ~ t d0 6j"Q  t e0 6"L  t f0 6٧"H  t g0 6J"C  t h0 6̙" t i0 6|S"v  t j0 6&"$l 0 t k0 6+W"A^ M t l0 6" + t m0 6 "Z f t n0 6\"v t o0 6\" t p0 6!_" t q0 6r"# K/ t r0 66"r# ~t s0 66"{ m t t0 6r"# / t u0 6yb" t v0 6Ifo"o {t w0 6DmW"}t x0 68K"FROt y0 6k?" t z0 63"i,ut {0 6"" . t |0 6 "* 6 t }0 69"E t ~0 6("  t 0 6[" t 0 6o"+ 7 t 0 6="0  t 0 6~"  t 0 6"3 % t 0 60"{ " t 0 6v" U t 0 6o"r i~ t 0 63" d t 0 6Ü "f  t 0 6"   0 BCxDE4F> x *lr<f$Nlfl$$rx @`"R@   0 BZCNDE4F> B$B$$N0H$$H6Z*6*B$ @`" m   0 BeCYDE8FB6YAS0#YAe;SG S)0$-D)56Y @`"a[  0 BSCNDE4F> $NS06$*606<$B0B$N @`"   0 BZCHDE4F> ZB$H$B*$66<00< N*Z @`" &  0 BZCTDE4F> *<*<H B*666HTZ*T*< @`"   0 BC DEF& @`"  0 BC0DEF&00*00@`" %+  0 B$CBDEF&$$B$$@`"+Et 0 6" : t 0 6"a m ` 0 "BCDEF:""f;ojuxw=TT>7;*N h"l)o3u5{77/'~aM0$!YSOZk`"e hbf@           `" ` 0 "aBCDEF:""f;ojuxq/TT>7;*N h"l)o3u5{77/'~aM0$!YSOZk`"e hbf@           `"j # 0  h0e0e     ?B\CDEF d @ 5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||F\6 @`S" G2 0  `r?2 @?"(   0 < "Z  T Click to edit Master title style! ! 0 0, " `    W#Click to edit Master subtitle style$ $ 0 0 "``  \*  0 0  "`   ^*  0 0 "`   ^* r 0 Zd޽h @ ? Z\l[]kfEo80___PPT10. SE 0((  ~  s *0  x  c $0 `      0@ }'*Work done while in Weizmann Institute.( 2(   0 =Short 2H  0޽h ? 33___PPT10i.p}+D=' = @B +   0 ;(  x  c $L,     09` g NP 0 20t  0|QP E Completeness: If x2L , P can cause V to output  Accept w.p. 1 Soundness: If xL , no matter what P does, V will output  Reject w.h.p.  2 G      >81  0a9 0@ NV 0 20  0f @  Nx 0 2(^"  6PP d"  < d"  <    0j '  G Accept/Reject 2H  0޽h ? Z\l[]kfEo___PPT10i.}Pu+8+D=' = @B +^   um@ (  x  c $Hu,     0v` g NP 0 20  0{9 0@ NV 0 20  0 @  Nx 0 2(X"  0PP ^"  6 ^"  6    0 '  G Accept/Reject 2P  0q   An interactive proof system is zero-knowledge (ZK) if verifier cannot learn anything new after interacting with the prover. That is, no matter what V does, it will not learn anything that it couldn t have learned by itself (without any interaction with prover). 2Jq,tH  0޽h ? Z\l[]kfEo___PPT10i.}Pu+8+D=' = @B +  P0(  x  c $,     00` g NP 0 20  09 0@ NV 0 20  0 @  Nx 0 2(X"  0PP ^"  6 ^"  6    0̨ '  G Accept/Reject 2Z  0  >Formalized by showing that for every verifier there exists a simulator  a non-interactive alg whose output is indist from verifier s view in the interaction.l 2= E,\*  64g@n gS( , ) ~ 0 20$  6gP m ~DVerifier s strategy (Circuit / TM)# 2#  6LgP m JPublic input (X) 2  6IJgm XVerifier s view 2l ` 0   `0 ,$D 0  <DȲG4HIe33 "``   <   0β` 0d  0Two r.v. X,Y are indist if 8 poly circuit D | Pr[ D(X)=1 ]  Pr[ D(Y)=1 ] | < n-w(1)6V 2 G, ?H  0޽h ? Z\l[]kfEoyq___PPT10Q.}Pu+8+]KD%' = @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<*+H  _W`(  x  c $@,     0,p  =Under assumptions, 9 ZK proof for every language in NP. [GMW]\> 2G W  0@  ]In fact, 9 such proof that only uses a constant number of communication rounds. [FS,BCY,GKa]\^ 2 G -R   0D PA A proof system for a non-trivial language that is ZK w.r.t. verifiers that use a non-uniform strategy must have at least 3 rounds. [GO]Z 2Q 5N4  0,P  ^A ZK proof for a non-trivial* language must be interactive (i.e., have at least 2 rounds) [GO]Z_ 2/ H  0޽h ? Z\l[]kfEo___PPT10i.q}`+D=' = @B +h  wp (  x  c $,= ,  =  D  0= y` LIs there a 2-round proof system for NP that is ZK w.r.t. uniform verifiers?ZM 2  ' 3  0 = G 1We show that under assumptions, the answer is NO.:2 2.,  0= @  vThat is, we show that under reasonable assumptions, there is no 2-round ZK proof* system for a language not in co-NP. :w 2o  0|=  R* The result is for (statistically sound) proof systems with perfect completeness.S 2SH  0޽h ? Z\l[]kfEo___PPT10i.q}`+D=' = @B +       (  x  c $= ,0  =    0H#=  A BThm 1: Let E=Dtime(2O(n)). If NCC(E)=2W(n) then there is no 2-round ZK public-coins proof system for a non-trivial language.}  $zf  0|"`0`    0p/=  z ;P 2(  02= pz ;V 2(X"  0P   07=   a 2R {0,1}n 233G3O333^"  6`   0l>=  >b  23  0B=  . cA 2-round proof system is public-coins if the verifier sends its entire random tape as its message.8d >B  0(H= p  *Accept iff A(x,a,b)=1h,  0pO= 0P 9xH  0޽h ? Z\l[]kfEo___PPT10i.~+D=' = @B +  K(  f  08c"``J  0[=  Thm 1: If NCC(E)=2W(n) and L has a 2-round ZK public-coins proof then L2BPP.M GJf  0|"``    0e=    ;P 2(  0i=  p ;V 2(X"  0 `  0@m=   a 2R {0,1}n 233G3O333^"  6 p  0 u=  >b  23B  0o=   *Accept iff A(x,a,b)=1h,  0= p  ^tProof: Fix xL. Define a2{0,1}n as good if 8 b A(x,a,b)=0.;  3G, !   0=  9x  0X=  7  &<1. Pra2{0,1}n[ a is good ] >    0= p  N Note that:(  L  0=    2. Can test if a is good in non-deterministic time nc, where nc is running time of A.V  ,3  0= \P nUnder assumption, 9 poly-time G:{0,1}O(log n){0,1}n s.t. Pra=G(s)[ a is good ] > [KvM] T]C  >6H  0޽h ? Z\l[]kfEo___PPT10i.~+D=' = @B +q  (  f  0|"``   0=    ;P 2(  0=  P <V* 2(X"  0 `  0= 0  a=G(s)J 2333^"  6 p  0=  >b  23B  0=  *Accept iff A(x,a,b)=1h,  0=  9x  0H= @ Q xDefine verifier V* that sends a=G(s) for s 2R {0,1}O(log n)= GO    0>   zLet S be a simulator for V*. For every x2L, S should output a pair (a,b) that is indist from a real execution. Zr  G( S  0H= \   For every x, a=G(s), we define S(x,a) to be result of following poly-time process:T  - ,1  0> , xRun S(x) many times till output is of form (a,b). Output b.=#  6z ` 0   0,$D 0  <d> G4HIe33 "``   <   0#> ` 0)  <In particular, if x2L, then Pr(a,b)=S(x)[ A(x,a,b)=1 ] > 1  nw(1)hC 2G ,$H  0޽h ? Z\l[]kfEoyq___PPT10Q.~+ؠD%' = @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<*+0   G ?   (  LB  c $D    05> @@ To decide if x2 L: n G   0$@> YD<4___PPT9 Choose s2R{0,1}O( log n), let a=G(s). Note that a is good w.p.  EGO  G , 8X  0dS> pp "2. Compute b=S(a)x L  0P> Ip  $3. Output A(x,a,b)    0 \   For every x, a=G(s), we define S(x,a) to be result of following poly-time process:T  - ,1  0o> , xRun S(x) many times till output is of form (a,b). Output b.=#  6  0|> `` We get that L2BPP:n G H  0޽h ? Z\l[]kfEo___PPT10i.~+D=' = @B +X   o g  (  x  c $PK ,0  K  H  0QK \   Thm 2: If S2-CC(E)=2W(n) then there is no 2-round ZK proof system for a Lco-NP.R$Ff  0|"`0`   0> z ;P 2(  0_K pz ;V 2(X"  0P   0|-K   r a=a(r)J 2333^"  6`   0DiK   >b  23\  0lK pP  .Accept iff A(x,a,b;r)=1~,   0tK 0 P 9xH  0޽h ? Z\l[]kfEo___PPT10i.~+D=' = @B +   W(  B  0K  Q Thm 2: If S2-CC(E)=2W(n) and L has a 2-round ZK proof system then L2co-NPKGHf  0|"``    0XK P   ;P 2(  0K Pp  ;V 2(X"  0   08K 6 0 r a=a(r)J 2333^"  6   0K F@ >b  23\  0K P   .Accept iff A(x,a,b;r)=1~,   0K  9x  0dK   Proof: Fix xL. Define a=a(r) as good if 8 b 9r s.t. A(x,a,b;r)=0B  3GG > "   0K l   nUnder assumption, 9 poly-time G:{0,1}O(log n){0,1}n s.t. Pra=G(s)[ a is good ] > [KvM] T]C  >6H  0޽h ? Z\l[]kfEo___PPT10i.~+D=' = @B +    (    0K   KDefine V* as before to use r=G(s), and define S to be the simulator for V*.*LK,f  0|"``    0K P   ;P 2(  0K Pp  ;V 2(X"  0   0K 6 0 r a=a(r)J 2333^"  6   0K F@ >b  23\  0K P   .Accept iff A(x,a,b;r)=1~,   0K  9x(  0@K d  Again, for every x, a=G(s), we define S(x,a) to be result of following poly-time process:[ - ,1  0O  4  xRun S(x) many times till output is of form (a,b). Output b.=#  6:  0HO d Note that if x2L, and b=P(x,a) then 8r A(x,a,b,r)=1 Therefore w.h.p. this also holds for S(x,a)b GG&P H  0޽h ? Z\l[]kfEo___PPT10i.~+D=' = @B +    i(    0D$O p   To decide if x2 L: n G 2  0L,O ppD<4___PPT9 Choose s2R{0,1}O( log n), let r0=G(s) and a=a(r0). Note that a is good w.p. QGO  G,!#8X<  0PCO ppd &2. Compute b=S(x,a)x    0HKO pp HB3. Output A(x,a,b;r) where r=r0."     0P5O ` 1Consider the following attempted algorithm for L:H2/ P  0_O  3  If xL then w.p. 9r s.t. A(x,a,b;r)=0. However, it may be that A(x,a,b;r0)=1 !S GGP .  0wO _   RIf x2L then w.h.p. 8r A(x,a,S(x,a);r)=1.*G G,   0DO  P4 -KHowever, we can choose r in step 3 via non-det guess and get that L2co-AM!L !G+H  0޽h ? Z\l[]kfEo___PPT10i.~+D=' = @B +f    v (  x  c $O ,p  O    0O @p$ 0<4___PPT9 Y Under assumptions, there is no 2-round ZK proof system for NP w/ perfect completeness. <Z 2+)8X  0O 4,$ 0 \2. There is no constant-round public-coin proof system that is (even bounded) resettable ZK.l] 2 N 8X`  0HO  ,$ 0 R3. Under assumptions, there is no constant-round ZK strong proof of knowledge [G].HS 248X  0ĭO  00g ,$ 0 cTightness results:  28X  0ؽO p P,$ 0 d 1 & 3 use essentially tight assumptions. Furthermore, similar assumptions are required to rule out that w(log n)-wise parallel 3COL/HAM are ZK. There is an argument system for NP that is constant-round and bounded resettable ZK.V 2k4A H  0޽h ? Z\l[]kfEo( ___PPT10.}Pu+8+eD' = @B Dw' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+O  ++0+O  ++0+O  ++0+O  ++0+O  +L  \T(  x  c $,     0$ JStill several open questions regarding power of (non-BB) zero knowledge. K 2K]  0  ,$ 0 This work shows that there is a difference between arguments and proofs, and that sometimes one must use (uncommon) computational assumptions.  2  0 D ,$D 0 One of the most important open questions  prove the following under reasonable assumptions: ^ 2^[  0H ,$ 0 WConjecture: There is no constant-round public-coins zero-knowledge proof system for NP.TX 2 7H  0޽h ? Z\l[]kfEo___PPT10p.)+ qhD' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*^