Cryptography Reference
In-Depth Information
Zero-knowledge is a property of some prover strategies. More gen-
erally, we consider interactive machines that yield no knowledge while
interacting with an arbitrary feasible adversary on a common input
taken from a predetermined set (in our case the set of valid assertions).
Astrategy
A
is
zero-knowledge
on (inputs from) the set
S
if, for every
feasible strategy
B
∗
, there exists a feasible computation
C
∗
such that
the following two probability ensembles are computationally indistin-
guishable
2
:
}
x∈S
de
= the output of
B
∗
after interacting with
A
on common input
x
(
A, B
∗
)(
x
)
(1)
{
∈
S
;and
de
= the output of
C
∗
on input
x ∈ S
.
{C
∗
(
x
)
(2)
}
x∈S
We stress that the first ensemble represents an actual execution of
an interactive protocol, whereas the second ensemble represents the
computation of a stand-alone procedure (called the “simulator”), which
does not interact with anybody.
The above definition does
not
account for auxiliary information that
an adversary
B
∗
may have prior to entering the interaction. Account-
ing for such auxiliary information is essential for using zero-knowledge
proofs as subprotocols inside larger protocols (see (71; 76)). This is
taken care of by a stricter notion called
auxiliary-input zero-knowledge
.
Definition 4.1.
(zero-knowledge (81), revisited (76)):
Astrategy
A
is
auxiliary-input zero-knowledge
on inputs from
S
if, for every probabilistic
2
Here we refer to a natural extension of Definition 3.1: Rather than referring to ensembles
indexed by
N
, we refer to ensembles indexed by a set
S ⊆{
0
,
1
}
∗
. Typically, for an ensem-
ble
{Z
α
}
α∈S
, it holds that
Z
α
ranges over strings of length that is polynomially-related
to the length of
α
.Wesaythat
{X
α
}
α∈S
and
{Y
α
}
α∈S
are
computationally indistinguish-
able
if for every probabilistic polynomial-time algorithm
D
every polynomial
p
,andall
suciently long
α ∈ S
,
1
|
Pr[
D
(
α, X
α
)=1]
−
Pr[
D
(
α, Y
α
)=1]
|
<
p
(
|α|
)
where the probabilities are taken over the relevant distribution (i.e., either
X
α
or
Y
α
)and
over the internal coin tosses of algorithm
D
.
