Cryptography Reference
In-Depth Information
4.7.2. Reducing the Knowledge Error
The knowledge error can be reduced by sequential repetitions of the proof system.
Specifically, the error drops exponentially with the number of repetitions.
Proposition 4.7.5:
Let R be a polynomially bounded relation, and let t
:
N → N
be a polynomially bounded function. Suppose that
(
P
,
V
)
is a system for proof of
knowledge for the relation R with knowledge error
κ
. Then the proof system that
results by repeating
(
P
)
times on common input x is a system
for proof of knowledge for the relation R with knowledge error
,
V
)
sequentially t
(
|
x
|
κ
(
n
)
def
(
n
)
t
(
n
)
.
=
κ
Proof Sketch:
Let (
P
,
V
) denote the protocol obtained by
t
sequential repeti-
V
), as in the proposition. To analyze the validity property of
V
,we
use the formulation of Definition 4.7.3. Given an extractor
K
1
for the basic sys-
tem, we construct an extractor
K
for the composed system (
P
,
V
) as follows. On
input
x
, machine
K
uniformly selects
i
∈{
1
,...,
t
(
|
x
|
)
}
, emulates the first
i
−
1
iterations of the basic proof system (
P
,
V
), and invokes
K
1
with oracle access to
the residual prover determined by the transcript of these
i
−
1 iterations. That is,
given oracle access to a prover strategy for the composed proof system, we first
use it to emulate the first
i
−
1 iterations in (
P
,
V
), resulting in a transcript
α
.
We then define a prover strategy for the basic proof system by considering the
way in which the composed-system prover behaves in the
i
th iteration given that
α
tions of (
P
,
is the transcript of the first
i
−
1 iterations. Using this (basic-system) prover
strategy as oracle, we invoke
K
1
in an attempt to extract a solution to
x
.
It is left to analyze the success probability of extractor
K
for fixed
x
∈
L
R
def
=
t
(
def
=
κ
def
=
p
(
x
,
y
,
r
)
t
.(We
shall omit this fixed (
x
,
y
,
r
) also from the following notations.) Our aim is to
show that
K
extracts a solution for
x
with probability at least
|
x
|
κ
|
x
|
δ
−
κ
and
y
and
r
as before. Let
t
),
(
), and
). Toward
this goal, let us denote by
a
i
−
1
the probability that the verifier accepts in each
of the first
i
δ/
poly(
|
x
|
−
1 iterations of the composed proof system. For every possible
transcript
α
of the first
i
−
1 iterations, we denote by
p
(
α
) the probability that
the verifier accepts in the
i
th iteration when
α
describes the transcript of the first
i
−
1 iterations. Note that if
K
tries to extract a solution after emulating
i
−
1
, then its success probability is at least
p
(
iterations resulting in transcript
α
α
)
−
κ
.
Let
c
i
be the expected value of
p
(
α
) when
α
is selected at random among all
(
i
−
1)-iteration transcripts in which the verifier accepts. Then
a
i
=
a
i
−
1
·
c
i
, and
the probability that
K
extracts a solution after emulating
i
−
1 iterations is at least
a
i
−
1
·
).
Claim:
Either
c
1
−
κ
≥
δ/
(
c
i
−
κ
t
or there exists an
i
≥
2 such that
a
i
−
1
·
(
c
i
−
κ
)
>
δ/
t
.
In both cases we have established an adequate lower bound on the success
probability of
K
; that is,
K
succeeds with probability at least
δ/
t
2
, where an extra
factor of
t
is to account for the probability that
K
will select a good
i
.
Proof:
Observe that if
a
1
=
c
1
<κ
+
(
δ/
t
), then there must exist an
i
≥
2 such
i
−
1
i
t
that
a
i
−
1
<κ
+
((
i
−
1)
δ/
t
) and
a
i
≥
κ
+
(
i
δ/
t
), since
a
t
=
κ
+
δ
. Using
