Cryptography Reference
In-Depth Information
An interactive pair
(
P
,
V
)
such that V is a strong knowledge verifier for a re-
lation R, and P is a machine satisfying the non-triviality condition (with re-
spect to V and R), is called a
system for strong proofs of knowledge
for the
relation R.
µ
) as an upper
bound on the failure probability of the extractor (in the strong validity requirement)
is immaterial. Furthermore, for
Our choice of using
µ
(rather than a different negligible function
-relations, requiring the existence of an extractor
that succeeds with noticeable probability is equivalent to requiring the existence of an
extractor that fails with exponentially vanishing probability. (That is, in the case of
NP
NP
-relations, the failure probability can be decreased by successive applications of
the extractor.) This
strong validity
requirement is stronger than the validity (with error
µ
) requirement of Definition 4.7.2, in two ways:
1.
The extractor in Definition 4.7.13 runs in (strict) polynomial time, regardless of the
value of
p
(
x
,
y
,
r
), whereas the extractor in Definition 4.7.2 runs in expected time
poly(
n
)
)). Note, however, that the extractor in Definition 4.7.13 is
allowed to fail with probability at most
/
(
p
(
x
,
y
,
r
)
−
µ
(
|
x
|
µ
(
|
x
|
), whereas the extractor in Definition 4.7.2
can never fail.
2.
The strong validity requirement implies that
x
∈
L
R
is accepted by the verifier with
probability at most
), whereas this is not required in Definition 4.7.2. This soundness
condition is natural in the context of the current definition that, unlike Definition 4.7.2,
always allows for non-zero (but negligible) error probability.
µ
(
|
x
|
4.7.6.2. An Example: Strong (ZK) Proof of Knowledge of Isomorphism
Sequentially repeating the (zero-knowledge) proof systems for Graph Isomorphism
(i.e., Construction 4.3.8) sufficiently many times yields a strong proof of knowledge of
isomorphism. The key observation is that each application of the basic proof system
(i.e., Construction 4.3.8) results in one of two possible situations, depending on whether
the verifier asks to see an isomorphism to the first or second graph. If the prover answers
correctly in both cases, then we can retrieve an isomorphism between the input graphs
(by composing the isomorphisms provided in the two cases). If the prover fails in both
cases, then the verifier will reject regardless of what the prover does from that point on.
Specifically, the preceding discussion suggests the following construction of a strong
knowledge extractor (where we refer to repeating the basic proof systems
n
times and
set
µ
(
n
)
=
2
−
n
).
Strong Knowledge Extractor for Graph Isomorphism.
On input (
G
1
,
G
2
) and access
to the prover-strategy oracle
P
∗
, we proceed in
n
iterations, starting with
i
=
1. Initially,
T
(the transcript thus far) is empty.
1.
Obtain the intermediate graph
G
from the prover strategy (i.e.,
G
=
P
∗
(
T
)).
2.
Extract the prover's answers to both possible verifier moves. That is, for
j
=
1
,
2, let
P
∗
(
T
ψ
j
is
correct
if it is an isomorphism between
G
j
and
G
.
275
ψ
j
←
,
j
). We say that
