Cryptography Reference
In-Depth Information
3.
We denote by
(
x
)
the random variable representing the (local ) output
of B when interacting with machine A on common input x , when the random input
to each machine is uniformly and independently chosen, and A (resp., B) has
auxiliary input y (resp., z).
4.
A pair of interactive machines
(
P
A
(
y
)
,
B
(
z
)
V
)
is called an
interactive proof system for
a language
L if machine V is polynomial-time and the following two conditions
hold:
,
Completeness:
For every x
∈
L, there exists a string y such that for every
}
∗
,
z
∈{
0
,
1
2
3
Pr
[
P
(
y
)
,
V
(
z
)
(
x
)
=
1]
≥
Soundness:
For every x
∈
L, every interactive machine B, and every y
,
z
∈
}
∗
,
{
0
,
1
1
3
Pr
[
B
(
y
)
,
V
(
z
)
(
x
)
=
1]
≤
We stress that when saying that an interactive machine is polynomial-time, we mean
that its running time is polynomial in the length of the common input. Consequently, it
is not guaranteed that such a machine has enough time to read its entire auxiliary input.
Teaching Tip.
The augmented model of interactive proofs is first used in this topic in
Section 4.3.3, where the notion of zero-knowledge is extended to account for a priori in-
formation that the verifier may have. One may thus prefer to present Definition 4.2.10 af-
ter presenting the basic definitions of zero-knowledge, that is, postpone Definition 4.2.10
to Section 4.3.3. (However, conceptually speaking, Definition 4.2.10 does belong to
the current section.)
4.3. Zero-Knowledge Proofs: Definitions
In this section we introduce the notion of a zero-knowledge interactive proof system
and present a non-trivial example of such a system (specifically, to claims of the form
“the following two graphs are isomorphic”).
4.3.1. Perfect and Computational Zero-Knowledge
Loosely speaking, we say that an interactive proof system (
P
,
V
) for a language
L
is
zero-knowledge if whatever can be efficiently computed after interacting with
P
on
input
x
∈
L
can also be efficiently computed from
x
(without any interaction). We stress
that this holds with respect to any efficient way of interacting with
P
, not necessarily the
way defined by the verifier program
V
. Actually, zero-knowledge is a property of the
prescribed prover
P
. It captures
P
's robustness against attempts to gain knowledge by
interacting with it. A straightforward way of capturing the informal discussion follows.
