Cryptography Reference
In-Depth Information
Following is a sketch of the proof of this claim. We assume, to the contrary, that there
exists a polynomial-size circuit family
{
C
n
}
n
∈N
such that for infinitely many
n
's there
exist triples (
x
z
) for which
C
n
has a non-negligible distinguishing gap. We derive a
contradiction by incorporating the description of
C
n
together with the auxiliary input
z
into a longer auxiliary input, denoted
z
. This is done in such a way that both
V
∗
and
M
∗
have insufficient time to reach the description of
C
n
. For example, let
q
(
·
)be
a polynomial bounding the running times of both
V
∗
and
M
∗
. Assume, without loss of
generality, that
|
z
|≤
q
(
n
) (or else the rest of
z
, which is unreadable by both
V
∗
and
M
∗
,
can be ignored). Then we let
z
be the string that results by padding
z
with blanks to a
total length of
q
(
n
) and appending the description of the circuit
C
n
at its end (i.e.,
z
is a
prefix of
z
). Clearly,
M
∗
(
x
,
z
)
=
M
∗
(
x
,
z
) and
P
(
y
)
,
V
∗
(
z
)
(
x
)
=
P
(
y
)
,
V
∗
(
z
)
(
x
).
On the other hand, by using a universal circuit-evaluating algorithm, we get a proba-
bilistic polynomial-time algorithm
D
such that
D
(
x
,
z
,α
,
y
,
=
C
n
(
x
,
z
,α
), and contra-
diction (to the hypothesis that
M
∗
produces output that is probabilistic polynomial-
time-indistinguishable from the output of (
P
)
V
∗
)) follows.
We mention that Definition 4.3.2 itself has some non-uniform flavor, since it requires
indistinguishability for all but finitely many
x
's. In contrast, a fully uniform analogue of
the definition would require only that it be infeasible to find
x
's on which the simulation
would fail (with respect to some probabilistic polynomial-time distinguisher). That is,
a fully uniform definition of zero-knowledge requires only that it be infeasible to find
x
's on which a verifier can gain knowledge (and not that such instances do not exist at
all). See further discussion in Section 4.4.2.4.
,
Advanced Comment: Why Not Go for a Fully Non-Uniform Formulation?
An oversimplified version of Definition 4.3.10 allows the verifier to be modeled by a
(non-uniform) family of (polynomial-size) circuits, and allows the same for the sim-
ulator. The non-uniform circuits are supposed to account for auxiliary inputs, and so
these are typically omitted from such an oversimplified version. For example, one may
require the following:
For every polynomial-size circuit family
V
n
}
n
∈N
(representing a possible verifier strategy
machine)
there exists a polynomial-size circuit family
{
{
M
n
}
n
∈N
(representing a simulator)
such that the ensembles
{
P
,
V
|
x
|
(
x
)
}
x
∈
L
and
{
M
|
x
|
(
x
)
}
x
∈
L
are indistinguishable by
polynomial-size circuits
.
However, the impression that non-uniform circuits account for auxiliary inputs is wrong,
and in general we find such oversimplified versions unsatisfactory. First, these versions
do not guarantee an “effective” transformation of verifiers to simulators. Indeed, such a
transformation is not required in Definition 4.3.10 either, but there the objects (i.e., ma-
chines) are of fixed size, whereas here we deal with infinite objects (i.e., circuit families).
Thus, the level of “security” offered by the oversimplified definition is unsatisfactory.
Second, the oversimplified version does not guarantee a relation between the size of the
non-uniform part of the verifier and the corresponding part of the simulator, whereas in
Definition 4.3.10 the only non-uniform part is the auxiliary input, which remains un-
changed. Both issues arise when trying to prove a sequential-composition theorem for
a non-constant number of iterations of zero-knowledge proof systems. Finally, we note
215
