Cryptography Reference
In-Depth Information
existence of non-uniformly one-way functions (see Definition 2.2.6 in Section 2.2),
commitment schemes with non-uniform secrecy can be constructed, using the same
construction as in the uniform case. Thus, we have the following:
Theorem 4.4.6: Suppose there exist non-uniformly one-way functions (as in
Definition 2.2.6). Then there exists a bit-commitment scheme (as in Definition
4.4.1) for which the secrecy condition also holds with respect to polynomial-size
circuits.
4.4.2. Zero-Knowledge Proof of Graph Coloring
NP
Presenting a zero-knowledge proof system for one
-complete language implies
the existence of a zero-knowledge proof system for every language in
NP
. This intu-
itively appealing statement does require a proof, which we postpone to a later stage. In
the current section we present a zero-knowledge proof system for one
NP
-complete
language, specifically Graph 3-Colorability. This choice is indeed arbitrary.
The language Graph 3-Coloring , denoted G 3 C , consists of all simple (finite) graphs
(i.e., no parallel edges or self-loops) 13 that can be vertex-colored using three colors such
that no two adjacent vertices are given the same color. Formally, a graph G
=
( V
,
E )
is 3-colorable if there exists a mapping
φ
: V
→{
1
,
2
,
3
}
such that
φ
( u )
= φ
(
v
) for
every ( u
,v
)
E .
4.4.2.1. Motivating Discussion
The idea underlying the zero-knowledge proof system for G 3 C is to break the proof
of the claim that a graph is 3-colorable into polynomially many pieces arranged in
templates so that each template by itself will yield no knowledge and yet all the templates
put together will guarantee the validity of the main claim. Suppose that the prover
generates such pieces of information, places each of them in a separate sealed and non-
transparent envelope, and allows the verifier to open and inspect the pieces participating
in one of the templates. Then certainly the verifier gains no knowledge in the process,
yet its confidence in the validity of the claim (that the graph is 3-colorable) increases.
A concrete implementation of this abstract idea follows.
To prove that the graph G
=
( V
,
E ) is 3-colorable, the prover generates a random
3-coloring of the graph, denoted
(actually a random relabeling of a fixed coloring will
do). The color of each single vertex constitutes a piece of information concerning the 3-
coloring. The set of templates corresponds to the set of edges (i.e., each pair (
φ
)),
where ( u ,v ) E , constitutes a template to the claim that G is 3-colorable). Each single
template (being merely a random pair of distinct elements in { 1 , 2 , 3 } ) will yield no
knowledge. However, if all the templates are OK (i.e., each contains a pair of distinct
elements in { 1 , 2 , 3 } ), then the graph must be 3-colorable. Consequently, graphs that
φ
( u )
(
v
13 A simple finite graph is a pair ( V , E ), where V is a finite set and E is a set of 2-subsets of V ; that is,
E
. The elements of V are called vertices , and the elements of E are called edges . Although
each edge is an unordered pair of two elements in V , we use the ordered-pair notation ( u ,v ) E rather than the
notation { u ,v }∈ E .For e = ( u ,v ) E , we say that u and v are the endpoints of e and that u is adjacent to v .
⊆{
e
V :
|
e
|=
2
}
Search WWH ::




Custom Search