Cryptography Reference
In-Depth Information
is isomorphic to
G
2
),
1
|
2
−
v
∗
(
x
,
r
,
H
)
if
ψ
=
π
◦
φ
V
2
|
!
Pr
[
ν
(
x
,
r
)
=
(
H
,ψ
)]
=
0
otherwise
2
−
v
∗
(
x
,
r
,
H
)
, we conclude
Observing that
H
=
ψ
(
G
v
∗
(
x
,
r
,
H
)
) if and only if
ψ
=
π
◦
φ
that
µ
(
x
,
r
) and
ν
(
x
,
r
) are identically distributed.
The claim follows.
This completes the proof of Part 3 of the proposition.
4.3.3. Zero-Knowledge with Respect to Auxiliary Inputs
The definitions of zero-knowledge presented earlier fall short of what is required in
practical applications, and consequently a minor modification should be used. We
recall that these definitions guarantee that whatever can be efficiently computed after
interaction with the prover on any
common input
can be efficiently computed
from the
input itself
. However, in typical applications (e.g., when an interactive proof is used
as a sub-protocol inside a larger protocol) the verifier interacting with the prover on
common input
x
may have some additional a priori information, encoded by a string
z
,
that may assist it in its attempts to “extract knowledge” from the prover. This danger
may become even more acute in the likely case in which
z
is related to
x
. (For example,
consider the protocol of Construction 4.3.8 and the case where the verifier has a priori
information concerning an isomorphism between the input graphs.) What is typically
required is that whatever can be efficiently computed from
x
and
z
after interaction
with the prover on any common input
x
can be efficiently computed from
x
and
z
(without any interaction with the prover). This requirement is formulated next using
the augmented notion of interactive proofs presented in Definition 4.2.10.
Definition 4.3.10 (Zero-Knowledge, Revisited):
Let
(
P
,
V
)
be an interactive
proof for a language L (as in Definition 4.2.10). Denote by P
L
(
x
)
the set of strings
y satisfying the completeness condition with respect to x
∈
L
(
i.e.,
Pr
[
P
(
y
)
,
2
3
}
∗
)
. We say that
(
P
V
)
is
zero-knowledge
with respect to auxiliary input
(or is
auxiliary-input zero-knowledge
)
if for
every probabilistic polynomial-time interactive machine V
∗
there exists a prob-
abilistic algorithm M
∗
, running in time polynomial in the length of its first in-
put, such that the following two ensembles are computationally indistinguishable
(when the distinguishing gap is considered as a function of
V
(
z
)
(
x
)
=
1]
≥
for every z
∈{
0
,
1
,
|
x
|
):
{
P
(
y
x
)
,
V
∗
(
z
)
(
x
)
}
x
∈
L
,
z
∈{
0
,
1
}
∗
for arbitrary y
x
∈
P
L
(
x
)
{
M
∗
(
x
,
z
)
}
x
∈
L
,
z
∈{
0
,
1
}
∗
Namely, for every probabilistic algorithm D with running time polynomial in the
length of the first input, for every polynomial p
(
·
)
, and for all sufficiently long
x
∈
L, all y
∈
P
L
(
x
)
, and z
∈{
0
,
1
}
∗
, it holds that
1
|
Pr
[
D
(
x
,
z
,
P
(
y
)
,
V
∗
(
z
)
(
x
))
=
1]
−
Pr
[
D
(
x
,
z
,
M
∗
(
x
,
z
))
=
1]
|
<
p
(
|
x
|
)
