Cryptography Reference
In-Depth Information
φ
←
ψ
−
2
ψ
1
is an isomorphism between
G
1
and
G
2
.In
3.
If both
ψ
j
's are correct, then
this case we output
φ
and halt.
4.
In case
ψ
j
is correct for a single
j
, and
i
<
n
, we let
T
←
(
T
,
j
) and proceed to the next
iteration (i.e.,
i
←
i
+
1). Otherwise, we halt, with no output.
It can be easily verified that if this extractor halts with no output in any iteration
i
<
n
,
then the verifier (in the real interaction) accepts with probability zero. Similarly, if
the extractor halts with no output in iteration
n
, then the verifier (in the real interac-
tion) accepts with probability at most 2
−
n
. Thus, whenever
p
((
G
1
,
G
2
)
2
−
n
, the
extractor succeeds in recovering an isomorphism between the two input graphs.
,
·
,
·
)
>
4.7.6.3. Strong (ZK) Proofs of Knowledge for
NNP
-Relations
NP
A similar argument can be applied to some zero-knowledge proof systems for
.
In particular, consider
n
sequential repetitions of the following basic (zero-knowledge)
proof system for the
Hamiltonian-cycle
(HC) problem. We consider directed graphs
(and the existence of directed Hamiltonian cycles).
Construction 4.7.14 (Basic Proof System for HC):
def
=|
Common input:
a directed graph G
=
(
V
,
E
)
, with n
V
|
.
Auxiliary input to prover:
a directed Hamiltonian cycle, C
⊂
E, in G.
Prover's first step (P1):
The prover selects a random permutation
of the vertices
V and commits to the entries of the adjacency matrix of the resulting permuted
graph. That is, it sends an n-by-n matrix of commitments such that the
(
π
π
(
i
)
,π
(
j
))
entry is a commitment to
1
if
(
i
,
j
)
∈
E and is a commitment to
0
otherwise.
Verifier's first step (V1):
The verifier uniformly selects
σ
∈{
0
,
1
}
and sends it to
the prover.
σ
=
Motivation:
0
means that the verifier asks to check that the matrix of commit-
ments is a legitimate one, whereas
1
means that the verifier asks to reveal a
Hamiltonian cycle in the permuted graph.
σ
=
Prover's second step (P2):
If
to the verifier along
with the revealing (i.e., pre-images) of all commitments. Otherwise, the prover
reveals to the verifier only the commitments to entries
(
σ
=
0
, then the prover sends
π
π
(
i
)
,π
(
j
))
, with
(
i
,
j
)
∈
C.
Verifier's second step (V2):
If
σ
=
0
, then the verifier checks that the revealed
graph is indeed isomorphic, via
, to G. Otherwise, the verifier simply checks
that all revealed values are
1
and that the corresponding entries form a simple
n-cycle. (Of course, in both cases, the verifier checks that the revealed values do fit
the commitments.) The verifier accepts if and only if the corresponding condition
holds.
π
We claim that the protocol resulting from sequentially repeating Construction 4.7.14
n
times is a (zero-knowledge) strong proof of knowledge of a Hamiltonian cycle; see
Exercises 20 and 30. Because a Hamiltonian cycle is
NP
-complete, we get such proof
systems for any language in
NP
. We mention that the known zero-knowledge strong
proofs of knowledge for
-complete languages are all costly in terms of the round-
complexity. Still, we have the following:
NP
