Cryptography Reference
In-Depth Information
directed graphs (and the existence of directed Hamiltonian cycles). Next, we present
a basic zero-knowledge system in which Hamiltonian graphs are accepted with prob-
ability 1, whereas non-Hamiltonian graphs on
n
vertices are rejected with probability
(
n
−
3
/
2
). (This system builds on the one presented in Construction 4.7.14.)
Construction 4.10.7 (A Hidden-Bits System for HC):
def
=|
Common input:
A directed graph G
=
(
V
,
E
)
, with n
V
|
.
Common reference string:
Viewed as an n
3
-by-n
3
Boolean matrix M , with each
entry being
1
with probability n
−
5
.
This is implemented by breaking the common reference string into blocks of
length 5 log
2
n
and setting a matrix entry to 1 if and only if the corresponding
block is all 1's.
Definitions:
A
permutation matrix
is a matrix in which each row (
resp., column
)
contains a single entry of value
1
.A
Hamiltonian matrix
is a permutation matrix
that corresponds to a simple directed cycle going through all rows and columns.
(That is, the corresponding directed graph consists of a single Hamiltonian cycle.)
An
n
3
-by-
n
3
matrix
M
is called useful if it contains a generalized
n
-by-
n
Hamiltonian sub-matrix and all other
n
6
−
n
2
entries in
M
are 0. That is, a
useful
n
3
-by-
n
3
matrix contains exactly
n
1-entries that form a simple
n
-cycle,
{
(
φ
1
(
i
)
,φ
2
((
i
mod
n
)
+
1)) :
i
=
1
,...,
n
}
, where
φ
1
and
φ
2
are 1-1 mappings
of
n
3
{
1
,...,
n
}
to
{
1
,...,
}
.
Prover:
Let C be a Hamiltonian cycle in G, in case such exists. The prover examines
the matrix M and acts according to the following two cases:
Case 1:
M
is useful
. Let H denote its Hamiltonian n-by-n sub-matrix and C
H
the
corresponding Hamiltonian cycle in H .
The prover
reveals
all
(
n
6
n
2
)
entries in M that are not in H .
−
The prover
finds
a
1-1
mapping,
π
1
, of V to the rows of H and a
1-1
mapping,
π
2
, of V to the columns of H , so that the edges of C are mapped
to the
1
-entries of H .
(Directed pairs of vertices of
G
, being edges or not, are mapped in the natu-
ral
,
π
2
(
v
)). The mapping pair (
π
1
,π
2
) is required to be an “isomorphism”
of
C
to
C
H
.
24
Actually, we should specify one isomorphism among the
n
possible ones.)
manner;
that
is,
(
u
,v
)
is
mapped
to
the
matrix
entry
(
π
1
(
u
)
The prover
reveals
the (n
2
−|
E
|
) entries corresponding to non-edges
of G.
(The correspondence is by the preceding mappings. That is, entry (
π
1
(
u
)
,
π
2
(
v
)) is revealed if and only if (
u
,v
)
∈
V
×
V
\
E
.)
24
The minor technicality that prevents us from freely using the term “isomorphism” is that
H
is not a graph.
