ࡱ > n y YK /s 2q
m4mPNG
IHDR A f PLTEzr<1%YPBH\ tRNS ރY bKGDa cmPPJCmp0712 Om IDATX˗Hn܊)R5/mT IUVssz)JX _%!ߐo!V]UQ`B Q?ʲYd ~ѤjP-˱ p-m?b7 QheԩA-ߕ@Hu}ͨeDu] C }DM@ @&z w S~v V۶xG-/w|@ W^:e!b¥-7 @:CN 2 \Yth8T~XM?^]V y3 HG.^7;!F^y.d ߬ŭlWX?H@'JbgV~I/3K4f_B|p [{4JX$rdݮ50NSË.i'fY~% PL3aB#/Bj2+ J|'l,1cnjK 7$Ի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%R9ҋ_EY> E~I
=Nx}P 6%$j`J>}ZO! 0 >{=60Z UX$\Q3" އv'
&v4U;#R"u-S wA`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=K 2B~MD-< V- k
O*ANӎ
nxe%'L(^ (3DIpBUGN|RW~>6+(ĉoJ+^<\SKVUƠúÑ}\8 MLOˬF--S1HXVIIR*~bL tԍUYQ Ԉ9K ܣ/XY☛8vyvT5g$gޟToo7
@ u@T+ IENDB` c (
- . / 0 D A r i a l l a c D( 0 ( z[ 0 " D T i m e s N e w R o m a n ( 0 ( z[ 0 D W i n g d i n g s R o m a n ( 0 ( z[ 0 0 D A r i a l B l a c k m a n ( 0 ( z[ 0 "@ D T a h o m a l a c k m a n ( 0 ( z[ 0 "P D c m s y 1 0 l a c k m a n ( 0 ( z[ 0 "` D S y m b o l l a c k m a n ( 0 ( z[ 0 @ .
@ n ? " d d @ @@ `` _ FL 2L d r u m r o l l . w a v . W A V 1 0 1 1 0 K RIFFK WAVEfmt + + dataK ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||ggg`N9@DGK`kdn`gryy||unrdYRNNGKGGGNGGGNUYYkuyyuungkdYG@@@GNRRUR\dgy|nn`rNK@KRGDKGYDR\dgk||||r`y`YdKGD9KK``nnyyu||YUgrukYYRKNUGY`kgkdryggUUu`\RnU`\uu\y|u|y||ugrr|`\uggurunuuykrunuy|y||nnnrgrdrUYdr|r|ykyyy||||ykkuunn|kuugynrnr|||uu|yukukr|u||nd|r|y||yyr||||ynn|||uu|ygdgdRDYRY`ud\Rgy|ryyynykr|gr\RUnRUkdUR\YgY`un|rnddn`\RKKYR\NYYkyyyy||gUkgKUK ? @ A B C D ` f f f 33 ` 3KI 3 ff ` 33 f f ` / p ` 3 % * 3 | ` Jy 3f ff3 f ` 3 f f3 ̙ ` 3 3f f 33 ` D D yq 3f ` ̙ 3 n ` w 3 ff ` } ff > ? " d d @ , ? n K d @ P n A @ F ` d n ? " d d @ @@ `` P R " @ ` ` 2 p > >
+ *
(
6 X # " ` `
` *
T
6 x # " ` ` ` ` H @ _ _ _ P P T 9 " @
r * &
& F X
# " X
T d # " ` P
H " 0 C
< ¬ d # " ` U
H " 0 C
c $ \Ƭ " U Y
B D
s * ʬ " Y W
B D
s * ̬ " Y U
B D
s * xЬ "
B D
c $ Ӭ # " ` S V
H " 0 C
c $ 8 " Y
B D
s * ڬ " X
B D
< ݬ # " ` `
T Click to edit Master title style !
! $
0 ߬ " `p
R Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level !
S N
6 # " ` ^ ` ` H @ _ _ _ P P T 9 " @
l * $
H
0 h ? } ff 8 0 _ _ _ P P T 1 0 .
07
P i x e l y 0 e (
F
"
Z r d
# "
H " 0 C
s * v
" 9 ) e
H " 0 C
b e
# " e
c $ Xz " i e
H " 0 C
c $ } " 9 )
H " 0 C
c $ " 0
H " 0 C
c $ " ? e
H " 0 C
c $ h " )
H " 0 C
c $ " ? G
H " 0 C
c $ " o G
H " 0 C
c $ p " 9 G
H " 0 C
c $ Ȕ " i A
H " 0 C
c $ " A ?
H " 0 C
N
6 # " ` ` ` ` H @ _ _ _ P P T 9 " @
l * $
6 p # " ` `
` *
T
6 # " ` ` ` ` H @ _ _ _ P P T 9 " @
r * &
0 " P
T Click to edit Master title style !
!
0 "
P
W # Click to edit Master subtitle style $
$ H
0 h ? } ff 8 0 _ _ _ P P T 1 0 .
07
0 r j 0 (
0 `
^ *
8
0 Q ` H @ _ _ _ P P T 9 " @
p * "
d
c $ ?
0
0
R Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level !
S
6 t _
^ *
>
6 p _ Q ` H @ _ _ _ P P T 9 " @
p * "
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3 X @ x (
0 \
^ *
8
0 Q ` H @ _ _ _ P P T 9 " @
p * "
6 _
^ *
>
6 8 _ Q ` H @ _ _ _ P P T 9 " @
p * "
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3 0 L (
L r
L S
r
L S p `P
r
L
C J A 2 s m a l l t r e e _ t e x t _ b l u e t r a n s
`N H
L 0 h ? } ff _ _ _ P P T 1 0 i . t# + D= ' =
@B +
x (
H ( " ` P
0 p P`
L=L(R) 2 NP X ( 2 c c c c
0 , iP
p
[ P " ( 2 c 0
0 h iPp
[ V " ( 2 c 0
0 0
0
w2R(x) R ( 2 g g g
0 x" @
x (x2L) \ ( 2 g c c c
X
0 @
` "
s * " ` 0
X
0
0 , P , $
0
l 9 e f f i c i e n t S s . t . 8 e f f i c i e n t V * 8 x 2 L S ( V * , x ) < P , V * > ( x ) G ( 2 c c g 33 g 33 g c c c c g c g c c c c c g g & 4
0 < ` L , $
0
_ Everything an efficient verifier can learn after a ZK interaction can be learned by applying an efficient algorithm (i.e., simulator) to the public input. ( 2 g g I g g 33 g 332 g
0 D 0 , $
0
g Zero-Knowledge: ( 2 c
H
0 h ? } ff | _ _ _ P P T 1 0 \ . Ų + i| D ' =
@B D ' =
@B A ? %, ( < + O %, (
< + Dh ' = % ( D ' = % ( D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < *
% ( D ' = -g 6 B f a d e *< 3 < *
Db ' = % ( D
' = % ( D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < * D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < * D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < *
D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < *
% ( +P +0 +
+ +0 +
+ +0 + + +0 + + +0 + + +0 + +
[
(
H ] " ` P
0 ^ P`
L=L(R) 2 NP X ( 2 c c c c
0 i
P , $
0
& R 9 efficient E s.t. 8 efficient P*
8 x Pr[ E(P*,x)2 R(X)] Pr[(x)=1] S ( 2 c c g 33 g 33 g c c c c g c g c c g g g g g & @
0 + B# s t y l e . v i s i b i l i t y < *
% ( D ' = -g 6 B f a d e *< 3 < *
D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * + +0 + + +0 +
+ +0 + + -
D < P
T (
T r
T S 0
T
0 D p
M Everything an efficient verifier can learn after a ZK interaction can be learned by applying an efficient algorithm to the public input. ( 2 g g I g g 33 g 33 g
T
0 d
v Popular formal interpretation: ( 2 c
T
0 ) 9
* efficient = probabilistic polynomial-time J + ( 2 g g ! c *
M
T
0
0
3 efficient = probabilistic expected polynomial-time 4 ( 2 g 33 g c g c c 3
T
0 L ` 0
l 9 e f f i c i e n t S s . t . 8 e f f i c i e n t V * 8 x 2 L S ( V * , x ) < P , V * > ( x ) G ( 2 c c g 33 g 33 g c c c c g c g c c c c c g g & 4
R B
T
s * D | ` ` H
T 0 h ? } ff _ _ _ P P T 1 0 i . [ + D= ' =
@B +
5
-
` X (
X x
X c $
X
0 H W
v Popular formal interpretation: ( 2 c
X
0 @
* efficient = probabilistic polynomial-time J + ( 2 g g ! c *
M
X
0 y P
3 efficient = probabilistic expected polynomial-time 4 ( 2 g 33 g c g c c 3
X
0 0
~ n I f a n e f f i c i e n t p r o v e r c a n c o n v i n c e t h e h o n e s t v e r i f i e r t h a t x 2 L t h e n t h e r e e x i s t s a n e f f i c i e n t a l g o r i t h m ( k n o w l e d g e e x t r a c t o r ) t o e x t r a c t a w i t n e s s f o r x f r o m t h e p r o v e r s s t r a t e g y . ( 2 g g / g g g g 33 g 33X g 8
X
0 P P 0
& R 9 efficient E s.t. 8 efficient P*
8 x Pr[ E(P*,x)2 R(X)] Pr[(x)=1] S ( 2 c c g 33 g 33 g c c c c g c g c c g g g g g & @
R B
X
s * D | P
P
H
X 0 h ? } ff _ _ _ P P T 1 0 i . [ + D= ' =
@B + p # 1] j (
\ 0 O
.] # "" ^ 0 O
\
< ? " `
O
T E x p e c t e d E f f i c i e n t
P r o b l e m w / d e f [ F e i g e ] B + c ! c 8
@` H
\
< 2 ? " `
0 E x p e c t e d E f f i c i e n t
G a p B c c @`
\
< > ? " ` \ T L _ _ _ P P T 9 . & @
No Constant-round prot* D c c c *
@`
\
< @ ? " ` 0
r Cons c
@` .
\
< Q ? " `
O
9 constant-round protocols** @ c c c
@` +
\
< \ ? " `
9 constant-round protocols @ c c c
@`
\
< K ? " `
% Strict=Efficient Computation
No Gap & & c %
@`
\
< `o ? " `
0
r Pros c
@`
\
< x ? " `
O
v Expected c
@`
\
< ́ ? " `
t Strict c
@`
\
< h ? " `
u Strict c
@` *
\
< p ? " ` 0
Efficient Verifier/ Prover 6 g c
@`
\
< ? " `
O
v Expected c
@`
\
< X ? " `
v Expected c
@`
\
< ? " `
t Strict c
@`
}\
< ? " ` 0
\ T L _ _ _ P P T 9 . & @
Efficient Simulator/ Extractor Z
g 33
c c
c (
@`
p\
< ? " `
O
w Def 3 $ g
@`
n\
< ? " `
w Def 2 $ g
@`
l\
< h ? " `
w Def 1 $ g
@`
j\
< ? " ` 0
X c
@` ` B
.\
0 o
? 0 0 Z B
0\
s * 1
? Z B
1\
s * 1
?
` B
2\
0 o
? O
O
` B
3\
0 o
? 0 O
` B
6\
0 o
? 0 O
` B
k\
0 o
? 0 O
Z B
\
s * 1
? 0 O
Z B
\
s * 1
? 0 O
` B
/\
0 o
? ` B
\
0 o
?
0
O
@\
0 3P
Possible Defs for Zero-Knowledge ! ( 2 ! c &
`
1]
s * " ` p
H
\ 0 h ? } ff _ _ _ P P T 1 0 i . pQ + D= ' =
@B + 4 ( (| (
| 0 O
| # # "" ^ 0 O
|
< ? " `
O
T E x p e c t e d E f f i c i e n t
P r o b l e m w / d e f [ F e i g e ] B + c ! c 8
@` H
|
< ? " `
0 E x p e c t e d E f f i c i e n t
G a p B c c @`
|
< ? " ` \ T L _ _ _ P P T 9 . & @
No constant-round prot* D c c c *
@`
|
< 0 ? " ` 0
r Cons c
@` C
|
< , ? " `
O
! 9 constant-round prot**
No gap @ " c c c &
@` +
|
< x7 ? " `
9 constant-round protocols @ c c c
@`
|
< TA ? " `
% Strict=Efficient Computation
No gap & & c %
@`
|
< J ? " `
0
r Pros c
@`
|
< S ? " `
O
v Expected c
@`
|
< \ ? " `
t Strict c
@`
|
< f ? " `
u Strict c
@` *
|
< h ? " ` 0
Efficient Verifier/ Prover 6 g c
@`
|
< z ? " `
O
v Expected c
@`
|
< x ? " `
v Expected c
@`
|
< ? " `
t Strict c
@`
|
< ȏ ? " ` 0
\ T L _ _ _ P P T 9 . & @
Efficient Simulator/ Extractor Z
g 33
c c
c (
@`
|
< x ? " `
O
w Def 3 $ g
@`
|
< @ ? " `
w Def 2 $ g
@`
|
< ? " `
w Def 1 $ g
@`
|
< Ķ ? " ` 0
X c
@` ` B
|
0 o
? 0 0 Z B
|
s * 1
? Z B
|
s * 1
?
` B
|
0 o
? O
O
` B
|
0 o
? 0 O
` B
|
0 o
? 0 O
` B
|
0 o
? 0 O
Z B
|
s * 1
? 0 O
Z B
|
s * 1
? 0 O
` B
|
0 o
? ` B
!|
0 o
?
0
O
"|
0 @ 3P
& Possible Defs for Zero-Knowledge / POK ' ( 2 ' c &
`
#|
s * " ` N
`
$|
s * " ` V `
%|
s * " `
4
`
&|
s * " `
<
`
'|
s * " `
`
(|
s * " `
H
| 0 h ? } ff _ _ _ P P T 1 0 . pQ + Dl ' =
@B D' ' =
@B A ? %, ( < + O %, (
< + D ' = % ( D ' = % ( DY ' =4 @B B
B B % ( ) ) ) D ' = -g 6 B f a d e *< 3 < * #| D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * #| % ( D ' = % ( D ' = % ( DY ' =4 @B B
B B % ( ) ) ) D ' = -g 6 B f a d e *< 3 < * $| D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * $| % ( D ' = % ( D ' = % ( DY ' =4 @B B
B B % ( ) ) ) D ' = -g 6 B f a d e *< 3 < * '| D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * '| % ( D ' = % ( D ' = % ( DY ' =4 @B B
B B % ( ) ) ) D ' = -g 6 B f a d e *< 3 < * (| D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * (| % ( D ' = % ( D ' = % ( DY ' =4 @B B
B B % ( ) ) ) D ' = -g 6 B f a d e *< 3 < * %| D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * %| % ( D ' = % ( D ' = % ( DY ' =4 @B B
B B % ( ) ) ) D ' = -g 6 B f a d e *< 3 < * &| D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * &| % ( + - # ) Q (
0 O
# # "" ^ 0 O
< ? " `
O
T E x p e c t e d E f f i c i e n t
P r o b l e m w / d e f [ F e i g e ] B + c ! c 8
@` H
< ? " `
0 E x p e c t e d E f f i c i e n t
G a p B c c @`
< l ? " ` \ T L _ _ _ P P T 9 . & @
No constant-round prot* D c c c *
@`
< ? " ` 0
r Cons c
@` C
< ` ? " `
O
! 9 constant-round prot**
No gap @ " c c c &
@` +
< ? " `
9 constant-round protocols @ c c c
@`
< ? " `
% Strict=Efficient Computation
No gap & & c %
@`
< - ? " `
0
r Pros c
@`
< l/ ? " `
O
v Expected c
@`
< ? ? " `
t Strict c
@`
< hI ? " `
u Strict c
@` *
< K ? " ` 0
Efficient Verifier/ Prover 6 g c
@`
< (] ? " `
O
v Expected c
@`
< Tf ? " `
v Expected c
@`
< o ? " `
t Strict c
@`
< q ? " ` 0
\ T L _ _ _ P P T 9 . & @
Efficient Simulator/ Extractor Z
g 33
c c
c (
@`
< P} ? " `
O
w Def 3 $ g
@`
< T ? " `
w Def 2 $ g
@`
< ~ ? " `
w Def 1 $ g
@`
< ? " ` 0
X c
@` ` B
0 o
? 0 0 Z B
s * 1
? Z B
s * 1
?
` B
0 o
? O
O
` B
0 o
? 0 O
` B
0 o
? 0 O
` B
0 o
? 0 O
Z B
s * 1
? 0 O
Z B
s * 1
? 0 O
` B
0 o
? ` B
!
0 o
?
0
O
"
0 3P
Possible Defs for Zero-Knowledge ! ( 2 ! c &
,
)
0 < 0
( Summary: Def 1 is best if it can be met. l ) ( 2 g c g c c (
H
0 h ? } ff _ _ _ P P T 1 0 x . pQ + D
' =
@B D_
' =
@B A ? %, ( < + O %, (
< + D ' = % ( D> ' = % ( D0 ' =4 @B B B B % ( D ' = 0l 9 HB HB B B *< 3 < * D ' =4 @B B B B % ( ) ? ) ? DF ' = . 7 B B B B BG M 0 . 0 1 . 8 5 1 8 5 E - 6 L - 0 . 3 5 - 0 . 3 3 3 3 4 * 3 >* B
p p t _ x B
p p t _ y = 0 B B A A < * D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' =A @B B B B 0B % ( ) ? ) ? DN ' = . 7 B B B B BO M 0 . 0 0 4 1 6 - 0 . 0 4 4 4 5 L 0 . 2 7 9 1 6 - 0 . 5 4 4 4 5 * 3 >* B
p p t _ x B
p p t _ y = 0 B B A A < * ) D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < * ) D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * ) % ( D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < * " D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * " % ( + +0 + " + +0 + ) + +0 + ) + @ - = (
, @
, # "" ; J @ < $ @
0
< ? " ` @
v Expected c
@`
< ? " `
t Strict c
@`
< ? " `
u Strict c
@` *
< ? " `
Efficient Verifier/ Prover 6 g c
@`
< ? " ` @
v Expected c
@`
< T ? " `
v Expected c
@`
< ? " `
t Strict c
@`
< ? " ` \ T L _ _ _ P P T 9 . & @
Efficient Simulator/ Extractor Z
g 33
c c
c (
@`
< ? " ` @
w Def 3 $ g
@`
< ? " `
w Def 2 $ g
@`
< t* ? " `
w Def 1 $ g
@`
< |, ? " `
X c
@` ` B
0 o
? Z B
s * 1
? Z B
s * 1
? ` B
0 o
? @ @ ` B
0 o
? @ ` B
0 o
? @ ` B
0 o
? @ Z B
s * 1
? @ ` B
0 o
? a
#
0 6 , $
0
) Summary: Def 1 is best if it can be met. l * ( 2 g c g c c )
)
0 >
, $
0
3 q [B,BG]: For Zero-Knowledge Def 1 can be met by a constant-round prot. w/ a non-black-box simulator (assuming CRH) x r ( 2 ! c c ' c
g c c & @ -
*
0 \
` , $
0
] Our Results:
1. In both cases Def 1 can not be met in constant-rounds by a black-box simulator/extractor.
2. In case of POK Def 1 can be met by a constant-round prot. w/ a non-black-box extractor (assuming CRH&TDP) & ( 2
g c g c g c g ) c g c g ' c
g c c & 1
8X
-
6 Ԕ " ` ` 0 , $ D
0 H
0 h ? } ff ' ' _ _ _ P P T 1 0 ' . pQ + %] D& ' =
@B D% ' =
@B A ? %, ( < + O %, (
< + D; ' = % ( % ( D ' = % ( D+ ' =4 @B B
B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * , % ( D ' = -g 6 B f a d e *< 3 < * , D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * # % ( D ' = -g 6 B f a d e *< 3 < * # D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * ) % ( D ' = -g 6 B f a d e *< 3 < * ) D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * *
% ( D ' = -g 6 B f a d e *< 3 < * *
D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * *
k % ( D ' = -g 6 B f a d e *< 3 < * *
k D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * * k % ( D ' = -g 6 B f a d e *< 3 < * * k D# ' = % ( D
' = % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * , D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * , % ( D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < * # D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * # % ( D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < * ) D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * ) % ( D< ' =A @B B @ B B 0B % ( ) ? ) ? D ' = .K 7 B B B B B] M - 1 . 6 6 6 6 7 E - 6 - 7 . 4 0 7 4 1 E - 7 L 0 . 0 0 3 1 3 - 0 . 5 4 4 9 1 * 3 >* B
p p t _ x B
p p t _ y =@ 0 B B A A p B B : B
< * *
D< ' =A @B B @ B B 0B % ( ) ? ) ? D ' = .K 7 B B B B B] M 5 . 5 5 5 5 6 E - 7 - 2 . 2 2 2 2 2 E - 6 L - 0 . 0 0 1 7 4 - 0 . 5 2 9 1 6 * 3 >* B
p p t _ x B
p p t _ y =@ 0 B B A A p B B 9c B ww < * *
k D> ' =A @B B @ B B 0B % ( ) ? ) ? D ' = .M 7 B B B B B_ M - 3 . 0 5 5 5 6 E - 6 - 4 . 0 7 4 0 7 E - 6 L - 0 . 0 0 6 0 7 - 0 . 4 7 3 3 8 * 3 >* B
p p t _ x B
p p t _ y =@ 0 B B A A p B B L B (}r < * * k D ' = % ( D ' = % ( Dg ' =4 @B B 7 B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * - % ( D ' = + 4 8 ?f C B # p p t _ w * 0 . 7 0 B C B # p p t _ w B *Y 3 > B
p p t _ w < * - D ' = + 4 8 ?\ C B # p p t _ h B C B # p p t _ h B *Y 3 > B
p p t _ h < * - D ' = -g 6 B f a d e *< 3 < * - +P +0 + # + +0 + # + +0 + ) + +0 + ) + +0 + * + +0 + * +
)
!
d (
d r
d S 4x `
m
d
0 y t
W Motivation: Look at how known expected poly-time black-box simulators work (e.g. [FS]) ~ X ( 2 c c g c g c W
d
0
[ P " ( 2 c 0
d
0 l
[ V " ( 2 c 0
z 8 P
d P
h "
d
s * " ` P
d
0 - '
Z V1 ( 2 c
r 8 P P
`
d P
`
d
0 P P
`
d
0 t
Z P1 ( 2 c
F P
d 0
h "
d
s * " ` P
d
0 - '
Z V2 ( 2 c
F P P
`
d @P
P `
d
0 P P
`
d
0 $
Z P2 ( 2 c
H
d 0 h ? } ff _ _ _ P P T 1 0 i . )v + D= ' =
@B + ^=
0 % (
0 ̧ @ G
[ S " ( 2 c 0
0 $ @G
\ V* " ( 2 c 0
z P
P
, $ D
0 h "
s * " ` P
0 į - '
Z V1 ( 2 c
z P P
`
, $ D
0 `
0 P P
`
0 D
Z P1 ( 2 c
z P
` , $ D
0 h "
s * " ` P
0 ĸ - '
Z V2 ( 2 c
z P P
`
P
, $ D
0 `
0 P P
`
0 D
^ P 2 ( 2 c
0 ` @ , $
0
Z V2 ( 2 c
z P
` , $ D
0 h "
s * " ` P
0 - '
^ V 2 ( 2 c
z P P
`
, $ D
0 `
0 P P
`
0
^ P 1 ( 2 c
0 3P , $
0
X S u p p o s e t h a t V * o n l y s e n d s m e s s a g e v 2 w . p . e | - ( 2
c c c c c &
"
0 P
, $
0
\ U s i n g ( v 1 , v 2 ) a n d ( v 1 , v 2 ) c a n s i m u l a t e p r o o f ! x / ( 2 c c c c c l ` P
% ` P , $ D
0
#
< GY Hj " ` ` P
:
$
0 ,
o No clue how to continue ( 2 c
H
0 h ? # } ff ) ) _ _ _ P P T 1 0 ) . )v + D( ' =
@B D( ' =
@B A ? %, ( < + O %, (
< + D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * D ' = % ( D ' = % ( Dg ' =4 @B B 7 B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % % ( D ' = + 4 8 ?f C B # p p t _ w * 0 . 7 0 B C B # p p t _ w B *Y 3 > B
p p t _ w < * % D ' = + 4 8 ?\ C B # p p t _ h B C B # p p t _ h B *Y 3 > B
p p t _ h < * % D ' = -g 6 B f a d e *< 3 < * % D ' = % ( D ' = % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * % D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % % ( D ' = % ( D ' = % ( D@ ' =A @B B B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -o 6 B w i p e ( u p ) *< 3 < * D
' = % ( D ' = % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * " % ( D ' = -g 6 B f a d e *< 3 < * " D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * + +0 + + +0 + + +0 + " +
P n (
0 @ G
[ S " ( 2 c 0
0 D @G
\ V* " ( 2 c 0
z P
P
, $ D
0 h "
s * " ` P
0 l - '
Z V1 ( 2 c
z P P
`
, $ D
0 `
0 P P
`
0 d
Z P1 ( 2 c
z P
` , $ D
0 h "
s * " ` P
0
- M
C ? & ( 2 g
0 P
, $
0
& 6 w . p . 1 - e: O u t p u t ( v 1 , p 1 , ? ) ( 2 c c r
0 P 3P
X S u p p o s e t h a t V * o n l y s e n d s m e s s a g e v 2 w . p . e | - ( 2
c c c c c & F
0 ! p , $
0
- n2 work ( 2 g g o g H
0 h ? } ff _ _ _ P P T 1 0 . )v + D ' =
@B D ' =
@B A ? %, ( < + O %, (
< + D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < *
% ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < *
D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * +p +0 + + +0 + + S
` # 4 F (
r
0 5 P
X S u p p o s e t h a t V * o n l y s e n d s m e s s a g e v 2 w . p . e | - ( 2
c c c c c &
0 0> Pp
& 6 w . p . 1 - e: O u t p u t ( v 1 , p 1 , ? ) ( 2 c c
0 4H p
- n2 work ( 2 g g o g
0 P @ G
[ S " ( 2 c 0
0 S @G
\ V* " ( 2 c 0
z P
P
, $ D
0 h "
s * " ` P
0 | D4 ' =
@B D4 ' =
@B A ? %, ( < + O %, (
< + D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * D ' = % ( D ' = % ( D@ ' =A @B B B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -o 6 B w i p e ( u p ) *< 3 < * D
' = % ( D ' = % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * " % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * " D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * % D
' = % ( D ' = % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * % D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * % % ( D) ' =4 @B B
B B % ( D ' = -g 6 B f a d e *< 3 < * " D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * " % ( D ' = % ( D ' = % ( D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * 4 % ( D ' = -g 6 B f a d e *< 3 < * 4 D ' = % ( D ' = % ( D6 ' =A @B B
B B 0B % ( D ' = -g 6 B f a d e *< 3 < * 4 D ' = 1 : B h i d d e n *o 3 >+ B# s t y l e . v i s i b i l i t y < * 4 % ( D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * ( % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * ( D ' = % ( D ' = % ( D9 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -u 6 B w i p e ( r i g h t ) *< 3 < * D ' = % ( D ' = % ( D7 ' =4 @B B B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -s 6 B w i p e ( l e f t ) *< 3 < * D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * 1 % ( D ' = -g 6 B f a d e *< 3 < * 1 D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * 2 % ( D ' = -g 6 B f a d e *< 3 < * 2 D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * 3 % ( D ' = -g 6 B f a d e *< 3 < * 3 +P +0 + + +0 + 1 + +0 + 2 + +0 + 3 + +0 + 4 + +0 + 4 + T'
c [ p + + (
r
0 P
X S u p p o s e t h a t V * o n l y s e n d s m e s s a g e v 2 w . p . e | - ( 2
c c c c c &
0 0 Pp
& 6 w . p . 1 - e: O u t p u t ( v 1 , p 1 , ? ) ( 2 c c
0 4 p
- n2 work ( 2 g g o g
0 @ G
[ S " ( 2 c 0
0 @G
\ V* " ( 2 c 0
F P
P
h "
s * " ` P
0 - '
Z V1 ( 2 c
F P P
`
`
0 P P
`
0
Z P1 ( 2 c
F P
` h "
s * " ` P
0 - '
Z V2 ( 2 c
F P P
`
P
`
0 P P
`
0
d P 2 ( 2 c
0 @
Z V2 ( 2 c
F P P
`
`
0 P P
`
0 `
^ P 1 ( 2 c
q F P
` h "
s * " ` P
0 - M
C ? & ( 2 g F P P
`
`
0 P P
`
0 T
` P 1 ( 2 c
q F P
` h "
s * " ` P
0 - M
C ? & ( 2 g F P P
`
`
!
0 P P
`
"
0
d P 1 ( 2 c
F P
#
` h "
$
s * " ` P
%
0 t - '
d V 2 ( 2 c
n
&
0 h P@
X w . p . e: O u t p u t ( v 1 , p 1 , v 2 , p 2 ) - ( 2 c * n
'
0 |
- ( 1 / e) n 2 w o r k ( 2 g g g o g
(
0 * P
B P E x [ w o r k ] = ( 1 - e) n 2 + e ( 1 / e) n 2 O ( n 2 ) ) ( 2 g g o g g g o g g g o g " 0 l
+
, $ D
0
)
B 9 G H,t " `
:
*
0 T>
I f w e s t o p s i m u l a t o r a f t e r l e s s t h a n 1 / e s t e p s t h e n s i m u l a t i o n f a i l s !
N o t e t h a t e m a y b e a n y n o n - n e g l i g i b l e v a l u e ( e . g . , 1 / e > > n 2 ) B ( 2 % c g ( c ( c g g g g g o c k
H
0 h ? ) } ff _ _ _ P P T 1 0 q . )v + I* DE ' =
@B D ' =
@B A ? %, ( < + O %, (
< + D7 ' = % ( % ( D ' = % ( Dg ' =4 @B B 7 B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * + % ( D ' = + 4 8 ?f C B # p p t _ w * 0 . 7 0 B C B # p p t _ w B *Y 3 > B
p p t _ w < * + D ' = + 4 8 ?\ C B # p p t _ h B C B # p p t _ h B *Y 3 > B
p p t _ h < * + D ' = -g 6 B f a d e *< 3 < * + + E
i a
(
0 R P `
> J Impossibility of strict black-box simulation for constant-round protocols. K ( 2 c g c g g c g
c g J
A
0 `
_ Let be ZK proof for L with c verifier messages and strict t(n)-time black-box simulator S 8 ` ( 2 c c c c c c c c c g c c c g c c c & @
0 m H ` , $
0
, F L e t V * b e s . t . V * a b o r t s i n a n y r o u n d w . p . 1 - e w h e r e e i s c h o s e n s . t . 8 x 2 L
1 . P r [ < P , V * > ( x ) = 1 ] = ec > 1 / p ( n )
2 . P r [ S V * ( x ) s e e s m o r e t h a n c m e s s a g e s ] < < 1 / p ( n ) d ( 2 c g c g c g
J
_
8X l
0 , $ D
0
0 Dw
$ ( C h o o s e e= ( c ) ( 2 c g g 6 g g g g 6 c 0
0 0
l t(n) & ( 2 g
0 ԅ p
` -1 & ( 2 g
& l `
` , $ D
0
B p G H m " ` `
:
@ 0
0
6 0
@ ( c ) ec + 1 ( 2 g g g 6 g g g g 6 o
6 l J
$
l t(n) & ( 2 g
H
0 h ? } ff | _ _ _ P P T 1 0 \ . a + 8 D ' =
@B D ' =
@B A ? %, ( < + O %, (
< + D ' = % ( D ' = % ( D8 ' =A @B B
B B 0B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( D ' = % ( Dg ' =4 @B B 7 B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = + 4 8 ?f C B # p p t _ w * 0 . 7 0 B C B # p p t _ w B *Y 3 > B
p p t _ w < * D ' = + 4 8 ?\ C B # p p t _ h B C B # p p t _ h B *Y 3 > B
p p t _ h < * D ' = -g 6 B f a d e *< 3 < * D ' = % ( D ' = % ( D+ ' =4 @B B
B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < *
% ( D ' = -g 6 B f a d e *< 3 < *
+8 +0 + +
j (
0
^ Our Results:
1. In both cases Def 1 can not be met in constant-rounds by a black-box simulator/extractor.
2. In case of POK Def 1 can be met by a constant-round prot. w/ a non-black-box extractor (assuming CRH&TDP) & ( 2
g c g c g c g ) c g c g ' c
g c c & 1
8X l
6 Ԕ " ` 0 H
0 h ? } ff _ _ _ P P T 1 0 i . E^ + D= ' =
@B + b
y
q
(
N | ) ) ? " `
0 Y
- Obtaining POK with strict poly-time extractor Z . ( 2 c g g c -
0
m Trapdoor Permutations ( 2 c
N | ) ) ? " `
6
0 ( @
v
2 ZK membership proof* w/ strict simulation [B,BG] l 3 ( 2 c
g
c g c 2
N | ) ) ? " ` P
0
) constant-round Commit With Extract Scheme V * ( 2 c g c c
B ?
Y = ( 2 H
B @ ? @
Y + ( 2 H
J
0 C
F C o m m i t - W i t h - E x t r a c t : S e c u r e c o m m i t m e n t s c h e m e s . t . u s i n g s e n d e r s c o d e c a n e x t r a c t c o m m i t t e d v a l u e i n s t r i c t p o l y n o m i a l - t i m e .
C a n b e u s e d t o o b t a i n a Z K P O K f o r N P f ( 2 c R c c 5 c c . s H
0 h ? } ff _ _ _ P P T 1 0 i . H, + D= ' =
@B + $
; 3 (
0 h
C P@
c Conclusion: ( 2 c
0 8C P@P
h v Non-Black-Box techniques are both necessary and sufficient to obtain strict polynomial-time simulation and extraction. w ( 2 " c g g c
g c g g + c v
H
0 h ? } ff _ _ _ P P T 1 0 i . e\ + D= ' =
@B +
A
9
(
0 C
- Obtaining POK with strict poly-time extractor F . ( 2 c g c -
\
0 $C
* Proof Outline: Let L 2 NP, a ZKPOK will be + ( 2 c c c c c c c c *
0 \ `
[ P " ( 2 c 0
0 @/C
[ V " ( 2 c 0
d
< GC H PP P
0 0C @@
`
u y=Comm(w) "
( 2
c &
0 X8C
x2L F ( 2 c c c
0 \=C
w2W(x) F ( 2 c c c
d
< GD H6
*
0 BC
ZKP Comm-1(y) 2 W(x) l ( 2 c k c c c &
l 0 P
0 P
, $ D
0
B JC GaH; " ` 0 P
:
0 HNC
C o m m i t - W i t h - E x t r a c t
N e e d c o n s t a n t - r o u n d c o m m i t m e n t s c h e m e s . t . c a n e x t r a c t c o m m i t t e d v a l u e i n s t r i c t p o l y - t i m e u s i n g s e n d e r s c o d e . ( 2 c c g c g c g c g c & : F
H
0 h ? } ff y q _ _ _ P P T 1 0 Q . H, + U D% ' =
@B D ' =
@B A ? %, ( < + O %, (
< + D ' = % ( D ' = % ( Dg ' =4 @B B 7 B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = + 4 8 ?f C B # p p t _ w * 0 . 7 0 B C B # p p t _ w B *Y 3 > B
p p t _ w < * D ' = + 4 8 ?\ C B # p p t _ h B C B # p p t _ h B *Y 3 > B
p p t _ h < * D ' = -g 6 B f a d e *< 3 < * + Y
(
0 aC PPp
0 4 Proof Sketch: Assume is c-round ZK proof for L 5 ( 2
c c g c g c c c c c 4
0 mC P , $
0
1 Suppose S is strict t(n)-time black-box simulator 2 ( 2 c g c c c g c c &
v
0 ,{C , $
0
v Lemma: If V* is honest+abort verifier and 8 x2 L
Pr[ SV*(x) is accepting and S saw c responds ] > 1/p(n)
Then L2BPP " w ( 2 c c g c c c g g g g c g o g
g g g g g g g g c g g g & Z
d
0 vC
`g , $
0
W h y ? F o r x L v
( 2 c c g g
0 C P , $
0
: Pr[ SV*(x) is accepting and S saw c responds ] = negl(n) ; ( 2 g o g
g g g g g g g
g & 3
H
0 h ? } ff
_ _ _ P P T 1 0
. `Tه + (!C D ' =
@B D ' =
@B A ? %, ( < + O %, (
< + D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( D0 ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * + +0 + C + +0 + C + +0 + C + +0 + C + 9
(
`
0 DC ` p , $
0
( Fix V* s.t. in any round independently Z ) ( 2 c g " c &
f
0 ,C @` ` , $
0
l T h u s 8 x 2 L P r [ S V * ( x ) i s a c c e p t i n g p r o o f f o r x ] ec . 7 ( 2 c g g g g o g g g g g 6
0 XC ` , $
0
@ F C l e a r l y , 8 x 2 L P r [ < P , V * > = 1 ] = ec $ ( 2 c g g g g o #
l P P
0 ` p , $ D
0
6 C P P
* h B u t P r [ S V * ( x ) g e t s > c n o n - ? r e s p o n d s ] ( c ) ec + 1 5 ( 2 c c g o g g g g g
g g g g 6 g g 6 o 4
6 C
l t(n) & ( 2 g
z )
) , $ D
0 &
6 ,C )
x P r [ S V * ( x ) a c c e p t i n g a n d S s a w c r e s p o n d s ] ec - ( c ) ec + 1
= ( 2 g o g g g g g g g
g g g g 6 g g 6 o c c : #
6 ec = 1 / p ( n ) ' ( 2 c g g 6 g g 6 c g g g o &
0 @ D ,
t(n) -1 H ( 2 g o
s * " ` 0P , $ D
0 H
0 h ? } ff H" @" _ _ _ P P T 1 0 " . `Tه + D ' =
@B D ' =
@B A ? %, ( < + O %, (
< + D[
' = % ( D
' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D[ ' =4 @B B
B B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * B % ( D ' = -g 6 B f a d e *< 3 < * B D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( D ' = % ( D[ ' =4 @B B
B B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * DK ' = % ( D ' = % ( Dh ' =A @B B
B B 0B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D+ ' =4 @B B
B B % ( D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( D ' = % ( D[ ' =4 @B B
B B % ( ) ) ) D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * D ' = % ( DZ ' = % ( D ' =4 @B B
B B % ( E ' =' B ` B P B < * % ( / / %, ( < + D ' = 1 : B v i s i b l e *o 3 >+ B# s t y l e . v i s i b i l i t y < * % ( D ' = -g 6 B f a d e *< 3 < * + +0 + D + +0 + C + +0 + D + +0 + D + +0 + D +
2 *
(
N | ) ) ? " `
0 =D
- Obtaining POK with strict poly-time extractor Z . ( 2 c g g c -
0 FD ` _
c Thm: Suppose that 1. 9 Trapdoor Permutations 2. 9 constant-round ZK argument for NP w/ strict poly-time simulator Then, 9 constant-round ZK argument of knowledge w/ strict poly-time knowledge-extractor. L ( 2 c c c c c c c c g c c c g c g g c c
0 TD
m Trapdoor Permutations ( 2 c
N | ) ) ? " `
6
0 lXD @
v
2 ZK membership proof* w/ strict simulation [B,BG] l 3 ( 2 c
g
c g c 2
N | ) ) ? " ` P0 ;
0 _D \
- ZK proof* of knowledge w/ strict extraction . ( 2
c g c g c
g c
B LhD ?
Y = ( 2 H
B lD ? @
Y + ( 2 H
H
0 h ? } ff _ _ _ P P T 1 0 i . H, + D= ' =
@B +
0 P (
X
C
S
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3S$
0 ` (
X
C
S |Y
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3S$
0 p (
X
C
S
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3S$
0 (
X
C
S '
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3S$
0 (
X
C
S T
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3S$
0 (
X
C
S
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3S$
0 (
X
C
S
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3%
0 (
X
C
S
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3%
0 (
X
C
S ,t
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3%
0 (
X
C
S
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3%
0 (
X
C
S
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3%
0 (
X
C
S 0
0
H
0 h ? 33 8 0 _ _ _ P P T 1 0 . 3%
0 (
X
C
S @@ TB hD |F H J L N P R U ?
W D Oh +'0 U
p x
$ 0
< H P 4 Strict Polynomial-Time in Simulation and Extraction Boaz Barak n Pixel ar Boaz Barak n 130 Microsoft PowerPoint e i@ bEG` @ @ P##@ iP G S g ) ' """ ))) UUU MMM BBB 999 | PP 3 f 3 33 f3 3 3 3 f 3f ff f f f 3 f ̙ 3 f f 3 3 3 f 3 3 3 3 33 333 f33 33 33 33 f3 3f3 ff3 f3 f3 f3 3 33 f3 3 ̙3 3 3 33 f3 3 3 3 33 f3 3 3 3 f 3 f f f f f f 3f 33f f3f 3f 3f 3f ff 3ff fff ff ff f 3f ff f ̙f f f 3f f f f f 3f f f 3 33 f 3 f 3f f3 f f 3 3 f ̙ ̙ 3̙ ff ̙ ̙ ̙ 3 f̙ 3 f 3 33 f3 3 3 3 f 3f ff f f f 3 f ̙ 3 f 3 f 3 f 3 33 f3 3 3 3 f 3f ff f f f 3 f ̙ 3 f 3 f ff ff f ff f f ! ___ www 4 ' A x ( x K ʦ """ ))) UUU MMM BBB 999 | PP 3 f 3 33 3f 3 3 3 f f3 ff f f f 3 f 3 f ̙ f 3 3 3 3 f 3 3 3 33 333 33f 33 33 33 3f 3f3 3ff 3f 3f 3f 3 33 3f 3 3 3 3 33 3f 3̙ 3 3 33 3f 3 3 3 f f 3 f f f f f f3 f33 f3f f3 f3 f3 ff ff3 fff ff ff f f3 ff f f f f f3 f̙ f f f f3 f f 3 33 f 3 f f3 3f f f 3 3 f 3 ff ̙ 3 f 3 f 3 33 3f 3 3 3 f f3 ff f f f ̙ ̙3 ̙f ̙ ̙ ̙ 3 f ̙ 3 f 3 f 3 33 3f 3 3 3 f f3 ff f f f 3 f 3 f ̙ 3 f ff ff f ff f f ! ___ www ݼݼݼݼýݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݽݼݼݼ¼ݽݼݼݽݼݼݼݽüݼݽݼݼݼݼݼݼݼݼ⽼ݼݼݼݽݼݼݽݼݶݼܼ¼ýݻݼܼݼݼݼݼݼݽݼݼݼݶ⼶ݵݼ⼼ⵍϮݼݽݼݼݼݼݼݼݵݼݼݵ⼯ύݼݼݼݽݼݼݼݼݼݼݼݼݼݒݼܯϑݼݼݼݼݼݼݼݽ¼ݼݒϻݼܶόݼݼݼݼݽ¼⼻⼼ݼݶݽݼݼݼݼ½ݵݶ¼ݼϯݼݵϴݼݼݼݼݼݼݽݼݼג⼼Ϯ϶ݼݶܵܶݼݼݼݼݼݼݼϯݶϒݼݼݼݽݼݼݼݼݼݼݽϵܼݼݼݼݼݼ¼ݽ¼ݽûݼּݼݼݶּϒύϒüݼݼݼݽݼݼݽ½ⶵݼݼݶܻݼϮύϒύݼݵ⽼ݼݼݼݼݼݽݼݼݻݍϮϮύύϮϵݼݼݼݼݼݼݼݼݽݼݼݼݼݶݼݼݼݼ⽼ݼ⼼ݼݽݼݼݼݼݼݼݼݼݼ½ݽݼݼݼݼݼݼݼݼݽݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼüü ݼݼݼݼݼݽ ݼݽݼݼ½ݽݽ ݼ¼ݼݽݼ ݼݼü ݼݼݼݼ¼¼ݼݽ½ݼݽݼݼݼݼ¼ݼݼݼݼݼ½ݼݼݼݽݼݼݼݼݼݼݼݼݼݼݽݼݼݼݼݼݽݼݼݼݼݼݼݼݼݼݼݽݼݼݼݽݼݽݼ½ݽݼݼݼ_____________________________________________________________________________________ݼݼݼݵ______________________________________________________________________ݼݼݼ_______________________________________________________________________________________ݼݼݼݵ_______________________________________________________________ݼݼݼݼ________________________________________________________________________________________ݼݼݼݵ____________________________________________________________________________ݼݽݼݼ_________________________________________________________________________ݼݼݼݼ__________________________________________________________________________________ݼݼݼ_______________________________________________________________________ݼݼݼݵ_______________________________________________________________________________ݼݼݼݵ___________________________________________________________________________ݼݼݽݼݼݼݵ________________________________________________________________________ݼݼݼݼݼݼݼݵ______________________________________________________________________ݼݼݼݼݼݼݼ________________________________________________________________________ݼݽݼݼݼ______________________________________________ݼݼݼݼݵ__________________________________________________ݼݼݼݽݼݼݵ_____________________________________________________ݼݼݼݼݼݼݼ_________________________________________________ݼݼݼݼݼݼݼ______________________________________________ݼݼݼݼݼݼݼݵ_________________________________________________________________________ݼݼݼݼݼݼ___________________________________________________________ݼݼݼݼݼݵ________________________________________________________________________________ݼüݼݼݼݼݵ___________________________________________________________________ݽݼݼݼݼݼݵ__________________________________________________________________________ݼݼݽݼݼݼ________________________________________________________________________ݼݼݼݼݼ_________________________________________________ݼݼݼݼݼݼݵ_________________________________________________________ݼݼݼݼݼ__________________________________________________ݽݼݼݼݼݼ__________________________________________________________ݼݼݼݼݼݼ______________________________________________ݼݼݼݼݼݼݵ_______________________________________________________________ݽ⼽ݼݼݼݼݼݵ__________________________________________________________________ݼݽݼݼݼݼ_________________________________________________________________ݼݽݼ¼ݼݼݼݵ____________________________________________________________ݼݼݼ⽼ݼݼݼݵ_______________________________________________________________ݼݼݼݼݼݼݼݼݼ________________________________________________________ݼݼݼݼݼݼݼݼݼݼ________________________________________________________________ݼݼݼݼݼݼݼݵ________________________________________________________________ݼݼݼݼ½ݼݼݼݼ____________________________________________________ݼݼݼݼݼݼ¼ݼݼݼݼ_____________________________________________________________________ݼݽݼݼݼݼݼݼݼݵ____________________________________________________ݼݼݽݼݼݼݼݼ____________________________________________________________ݼݼݼݼݽݼݼݼݵ___________________________________________________________________ݼݼݼݼݼ¼ݼݼݼݼ____________________________________________________ݽݼݼݽݼݼݼݼݼݼݼýݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݼݽݼݼݼݼݼݼݼ¼ݽ⼼ݼݼݼݼݼݽݼݼݼݽüݼݼݼݽݼݼݼݼ⼼ݼݼݼݼݼݼ⽼ݼݼݼݼݼݼݼݽݼݼݼݼݼݼݼݼݼݽݼ⼼ݼݼݼݼݼݼݼݼݼݼݼݼݽݼݼݼݼݼݼݼݼݽݼݼݼݼݽ¼ݼݼݼݼ½ݼݼݼݽݼݼݼݼݼݼݼݽݼݼݼݼݼݼݼ¼ݽ¼ݽݼݼݼݽݼݼݽ½ݼݼݼݼݼݽݼݼݼݼݼݼݽݼݼݼݼ⽼ݼ⼼ݼݽݼݼݼݼݼݼݼݼݼ½ݽݼݼݼݼݼݼݼݼݽݼݼݼݼݼݼݼݼݼݼ ՜. +,D ՜. +,
K On-screen Show MTA ,h A
Arial Times New Roman
Wingdings Arial Black Tahoma cmsy10 Symbol Pixel 4 Strict Polynomial-Time in Simulation and Extraction Interactive Proofs/Arguments Interactive Proofs/Arguments Definition of Zero-Knowledge: ) Definition of Proofs of Knowledge (POK): Slide 6 Slide 7 Slide 8 Slide 9 7 Impossibility of strict poly-time black-box simulation Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Fonts Used Design Template
Slide Titles D 4 < Version " _X
Boaz Barak B o a z B a r a k
! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~
! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~ R o o t E n t r y dO ) P i c t u r e s C u r r e n t U s e r S u m m a r y I n f o r m a t i o n ( 0U P o w e r P o i n t D o c u m e n t ( ,X D o c u m e n t S u m m a r y I n f o r m a t i o n 8