Cryptography Reference
In-Depth Information
Definition 4.3.1 (Perfect Zero-Knowledge): Let ( P , V ) be an interactive proof
system for some language L. We say that ( P , V ) is perfect zero-knowledge if for
every probabilistic polynomial-time interactive machine V there exists a prob-
abilistic polynomial-time algorithm M such that for every x L the following
two conditions hold:
1
2 , on input x , machine M outputs a special symbol
1. With probability at most
[ M ( x )
1
2 ).
2. Let m ( x ) be a random variable describing the distribution of M ( x ) con-
ditioned
denoted
(i.e.,
Pr
=⊥
]
M ( x )
[ m ( x )
[ M ( x )
M ( x )
on
= ⊥
(i.e.,
Pr
= α
]
= Pr
= α |
= ⊥
]
} ). Then the following random variables are identically
for every
α ∈{
0
,
1
distributed:
P , V ( x ) (i.e., the output of the interactive machine V after interacting with
the interactive machine P on common input x )
m ( x ) (i.e., the output of machine M on input x , conditioned on not being
)
Machine M is called a perfect simulator for the interaction of V with P.
Condition 1 can be replaced by a stronger condition requiring that M output the special
symbol (i.e., ) only with negligible probability. For example, one can require that (on
input x ) machine M will output
with probability bounded above by 2 p ( | x | ) , for any
·
polynomial p (
); see Exercise 6. Consequently, the statistical difference between the
random variables
); see Exercise 8.
Hence, whatever the verifier efficiently computes after interacting with the prover can
be efficiently computed (with only an extremely small error) by the simulator (and
hence by the verifier himself ).
P , V
( x ) and M ( x ) can be made negligible (in
| x |
4.3.1.2. Computational Zero-Knowledge
Following the spirit of Chapter 3, we observe that for practical purposes there is no need
to be able to “perfectly simulate” the output of V after it interacts with P . Instead,
it suffices to generate a probability distribution that is computationally indistinguish-
able from the output of V after it interacts with P . The relaxation is consistent with
our original requirement that “whatever can be efficiently computed after interacting
with P on input x
L can also be efficiently computed from x (without any interac-
tion),” the reason being that we consider computationally indistinguishable ensembles
as being the same. Before presenting the relaxed definition of general zero-knowledge,
we recall the definition of computationally indistinguishable ensembles (see Item 2 in
Definition 3.2.2). Here we consider ensembles indexed by strings from a language L .
We say that the ensembles
S x } x L are computationally indistinguishable
if for every probabilistic polynomial-time algorithm D , for every polynomial p ( · ), and
for all sufficiently long x L , it holds that
{
R x } x L and
{
1
p ( | x | )
| Pr
[ D ( x , R x )
=
1]
Pr
[ D ( x , S x )
=
1]
| <
Search WWH ::




Custom Search