Cryptography Reference
In-Depth Information
this
i
,wehave
a
i
−
1
·
(
c
i
−
κ
)
=
a
i
−
a
i
−
1
·
κ
i
t
(
i
−
1)
δ
t
i
i
>
κ
+
−
κ
+
=
t
The claim follows, and so does the proposition.
What About Parallel Composition .
As usual (see Section 4.3.4), the effect of parallel
composition is more complex than the effect of sequential composition. Consequently,
a result analogous to Proposition 4.7.5 is not known to hold in general. Still, parallel
execution of some popular zero-knowledge proofs of knowledge can be shown to reduce
the knowledge error exponentially in the number of repetitions; see Exercise 27.
Getting Rid of Tiny Error.
For
-relations, whenever the knowledge error is smaller
than the probability of finding a solution by a random guess, one can set the knowledge
error to zero.
NP
Proposition 4.7.6:
Let R be an
NP
-relation, and let q
(
·
)
be a polynomial such
that
(
x
V
)
is a system for proofs of
knowledge for the relation R, with knowledge error
κ
(
n
)
def
,
y
)
∈
R implies
|
y
|≤
q
(
|
x
|
)
. Suppose that
(
P
,
=
2
−
q
(
n
)
. Then
(
P
,
V
)
is
a system for proofs of knowledge for the relation R (with zero knowledge error).
Proof Sketch:
Again, we use the formulation of Definition 4.7.3. Given a know-
ledge extractor
K
substantiating the hypothesis, we construct a new knowledge
extractor that first invokes
K
, and in case
K
fails, it uniformly selects a
q
(
)-bit-
long string and outputs it if and only if it is a valid solution for
x
. Let
p
(
x
,
y
,
r
)be
as in Definitions 4.7.2 and 4.7.3, and let
s
(
x
|
x
|
) denote
the success probability of
K
P
x
,
y
,
r
(
x
). Then the new knowledge extractor succeeds
with probability at least
,
y
,
r
)
≥
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
r
)
def
s
(
x
2
−
q
(
|
x
|
)
,
y
,
=
s
(
x
,
y
,
r
)
+
(1
−
s
(
x
,
y
,
r
))
·
The reader can easily verify that
s
(
x
,
y
,
r
)
≥
p
(
x
,
y
,
r
)
/
2 (by separately consid-
ering the cases
p
(
x
,
y
,
r
)
≥
2
·
κ
(
|
x
|
) and
p
(
x
,
y
,
r
)
≤
2
·
κ
(
|
x
|
)), and the propo-
sition follows.
4.7.3. Zero-Knowledge Proofs of Knowledge for
NNP
The zero-knowledge proof systems for Graph Isomorphism (i.e., Construction 4.3.8)
and for Graph 3-Coloring (i.e., Construction 4.4.7) are in fact proofs of knowledge (with
some knowledge error) for the corresponding languages. Specifically, Construction
4.3.8 is a proof of knowledge of an isomorphism with knowledge error
1
2
, whereas
