Cryptography Reference
In-Depth Information
p
u
n
,v
n
(
G
n
)
= Pr
|
e
u
n
=
= Pr
/
Pr
[
e
u
n
=
[
X
e
v
n
]
[
X
]
e
v
n
]
M
∗
(
G
n
)
[
M
∗
(
G
n
)
p
u
n
,v
n
(
G
n
)
= Pr
[
X
|
= ⊥
]
= Pr
[
X
]
/
Pr
= ⊥
]
2
[
M
∗
(
G
n
)
Using
Pr
[
e
u
n
=
e
v
n
]
=
3
≈
Pr
= ⊥
], where
≈
denotes equality up to a neg-
p
u
n
,v
n
(
G
n
)
ligible (in
n
) quantity, it follows that
|
−
p
u
n
,v
n
(
G
n
)
|
is negligible (in
n
).
Using the conditions of case 2, and omitting
G
n
from the notation, it follows that
p
u
n
,v
n
−
q
u
n
,v
n
≤
p
u
n
,v
n
−
p
u
n
,v
n
+
p
u
n
,v
n
−
q
u
n
,v
n
<
2
3
·
p
(
n
)
2
Combining the foregoing, we get
[
A
n
(
C
(1
n
2
n
3
n
))
|
Pr
=
1]
−
Pr
[
A
n
(
C
(
T
3
n
))
=
1]
|
q
u
n
,v
n
·
Pr
1
A
ν
u
n
,v
n
=
1
−
A
µ
u
n
,v
n
=
p
u
n
,v
n
·
Pr
=
≥
q
u
n
,v
n
·
Pr
A
µ
u
n
,v
n
=
1
−
p
u
n
,v
n
−
q
u
n
,v
n
A
ν
u
n
,v
n
=
1
−
Pr
1
3
·
p
(
n
)
2
Hence, the circuit family
{
A
n
}
distinguishes commitments to
{
1
n
2
n
3
n
1
p
(
n
)
·
1
p
(
n
)
−
2
3
·
p
(
n
)
2
=
>
}
from com-
mitments to
{
T
3
n
}
. Combining an averaging argument with a hybrid argument, we
conclude that there exists a polynomial-size circuit family that distinguishes com-
mitments. This contradicts the non-uniform secrecy of the commitment scheme.
Having reached contradiction in both cases, Claim 4.4.8.2 follows.
Combining Claims 4.4.8.1 and 4.4.8.2 (and using Exercise 9), the zero-knowledge
property of
P
G
3
C
follows. This completes the proof of the proposition.
4.4.2.4. Concluding Remarks
Construction 4.4.7 has been presented using a unidirectional commitment scheme. A
fundamental property of such schemes is that their secrecy is preserved in case (poly-
nomially) many instances are invoked simultaneously. The proof of Proposition 4.4.8
indeed took advantage on this property. We remark that Construction 4.4.4 also pos-
sesses this simultaneous secrecy property (although it is not unidirectional), and hence
the proof of Proposition 4.4.8 can be carried out if the commitment scheme used is
the one of Construction 4.4.4 (see Exercise 15). We recall that this latter construc-
tion constitutes a commitment scheme if and only if such schemes exist at all (since
Construction 4.4.4 is based on any one-way function, and the existence of one-way
functions is implied by the existence of commitment schemes).
Proposition 4.4.8 assumes the existence of a
non-uniformly
secure commitment
scheme. The proof of the proposition makes essential use of the non-uniform security
by incorporating instances in which the zero-knowledge property fails into circuits that
contradict the security hypothesis. We stress that the sequence of “bad” instances is
not necessarily constructible by efficient (uniform) machines. In other words, the zero-
knowledge requirement has some non-uniform flavor. A
uniform analogue of zero-
knowledge
would require only that it be infeasible to find instances in which a verifier
gains knowledge (and not that such instances do not exist at all). Using a
uniformly
239
