Cryptography Reference
In-Depth Information
secure commitment scheme, Construction 4.4.7 can be shown to be
uniformly
zero-
knowledge.
By itself, Construction 4.4.7 has little practical value, since it offers a very mod-
erate acceptance gap (between inputs from inside and outside of the language). Yet,
repeating the protocol, on common input
G
=
(
V
,
E
), for
k
·|
E
|
times (and letting the
verifier accept only if all iterations are acceptance) will yield an interactive proof for
G
3
C
with error probability bounded by
e
−
k
, where
e
≈
2
.
718 is the natural-logarithm
base. Namely, on common input
G
∈
G
3
C
, the verifier always accepts, whereas on
common input
G
∈
G
3
C
, the verifier accepts with probability bounded above by
e
−
k
(no matter what the prover does). We stress that by virtue of the sequential-composition
lemma (Lemma 4.3.11), if these iterations are performed sequentially, then the result-
ing (strong) interactive proof is zero-knowledge as well. Setting
k
to be any super-
logarithmic function of
|
G
|
(e.g.,
k
=|
G
|
), the error probability of the resulting in-
teractive proof is negligible. We remark that it is unlikely that the interactive proof
that results by performing these
k
·|
E
|
iterations in parallel is zero-knowledge; see
Section 4.5.4.
An important property of Construction 4.4.7 is that the prescribed prover (i.e.,
P
G
3
C
)
can be implemented in probabilistic polynomial time, provided that it is given as aux-
iliary input a 3-coloring of the common-input graph. As we shall see, this property is
essential for application of Construction 4.4.7 to the design of cryptographic protocols.
As mentioned earlier, the choice of
G
3
C
as a “bootstrapping”
-complete lan-
guage is totally arbitrary. It is quite easy to design analogous zero-knowledge proofs
for other popular
NP
-complete languages using the underlying ideas presented in
Section 4.4.2.1 (i.e., the
motivating discussion
).
NP
4.4.3. The General Result and Some Applications
The theoretical and practical importance of a zero-knowledge proof for Graph
3-Coloring (e.g., Construction 4.4.7) follows from the fact that it can be applied to
prove, in zero-knowledge, any statement having a short proof that can be efficiently
verified. More precisely, a zero-knowledge proof system for a specific
NP
-complete
language (e.g., Construction 4.4.7) can be used to present zero-knowledge proof sys-
tems for every language in
NP
.
Before presenting zero-knowledge proof systems for every language in
NP
, let us
NP
recall some conventions and facts concerning
. We first recall that every language
L
∈
NP
is
characterized
by a binary relation
R
satisfying the following properties:
•
There exists a polynomial
p
(
·
) such that for every (
x
,
y
)
∈
R
, it holds that
|
y
|≤
p
(
|
x
|
).
•
There exists a polynomial-time algorithm for deciding membership in
R
.
•
L
={
x
:
∃
w
s.t. (
x
,w
)
∈
R
}
.
(Such a
w
is called a witness for the membership of
x
∈
L
.)
Actually, each language in
NP
can be characterized by infinitely many such relations.
Yet for each
L
∈
NP
, we fix and consider one characterizing relation, denoted
R
L
.
NP
Because
G
3
C
is
-complete, we know that
L
is polynomial-time-reducible (i.e.,
240
