Cryptography Reference
In-Depth Information
the latter contains the only 1-entries in
M
, all non-edges of
G
are mapped
to 0-entries of
M
. (In Case 2 the claim is trivial.) We remark that the prover's
actions can be implemented in polynomial time when given a Hamiltonian cycle
of
G
as auxiliary input. Specifically, all that the prover needs to do is to check
if
M
is useful and to find an isomorphism between two given
n
-vertex
cycles.
Next, suppose that
G
is non-Hamiltonian. By Fact 4.10.8, with probability at
least
(
n
−
3
/
2
)
the matrix
M
is useful. Fixing any useful matrix
M
, we show
that the verifier rejects
G
, no matter what the prover does. Clearly, if the prover
behaves as in Case 2, then the verifier rejects (since
M
is useful). Thus we focus
on the case in which the prover outputs a pair of matchings (
,
π
1
,π
2
) (as in Case 1).
Let
H
denote the (unique)
n
-by-
n
Hamiltonian sub-matrix of
M
, and consider
the following sub-cases:
π
1
(
V
)
×
π
2
(
V
) does not equal
H
. Because the prover must reveal all entries not in
the sub-matrix
1.
×
π
2
(
V
), it follows that it must reveal some row or column
of
H
. But such a row or column must contain a 1-entry, and so the verifier will
reject.
2.
Otherwise,
π
1
(
V
)
H
. Also, each non-edge of
G
must be mapped to a
0-entry of
H
(or else the verifier will reject). It follows that the pre-image of each
1-entry in
H
must be an edge in
G
, which implies that
G
has a Hamiltonian cycle
(in contradiction to our hypothesis).
π
1
(
V
)
×
π
2
(
V
)
=
We conclude that in case
G
is non-Hamiltonian, it is rejected with probability
(
n
−
3
/
2
).
Finally, we show that the prover is zero-knowledge. This is done by con-
structing a simulator that, on input a graph
G
, randomly selects an
n
3
-by-
n
3
matrix, denoted
M
, with distribution as in the common reference string (i.e.,
each entry being 1 with probability
n
−
5
). If
M
is not useful, then the simu-
lator outputs (
G
2
) (i.e., all bits are revealed, with values as in
M
, and no certificate is given). Otherwise, ignoring this (useful)
M
, the sim-
ulator uniformly selects a pair of 1-1 mappings (
π
1
,π
2
) such that
π
i
:
V
→
{
1
,...,
n
3
n
3
,
M
,
{
1
,...,
}
}
for
i
=
1
,
2. The simulator outputs (
G
,
0
n
6
−|
E
|
,
I
,
(
π
1
,π
2
)), where
def
={
1
,...,
n
3
2
\{
(
π
1
(
u
)
,π
2
(
v
)) : (
u
,v
)
∈
E
}
. The reader can easily verify that
the output distribution of the simulator is identical to the distribution seen by the
verifier.
I
}
Using Propositions 4.10.9 and 4.10.5 and Remark 4.10.6, we conclude the following:
Theorem 4.10.10:
Assuming the existence of one-way permutations,
25
each lan-
guage in
has a zero-knowledge non-interactive proof system. Furthermore,
assuming the existence of families of trapdoor permutations, each language in
NP
NP
has a zero-knowledge non-interactive proof system in which the prover can
25
As usual in this chapter, here and later, we mean constructs for which the hardness requirement also holds
with respect to non-uniform (polynomial-size) circuits.
