Cryptography Reference
In-Depth Information
Prover:
1.
Using a standard reduction of L
2
to L
1
, the prover reduces
(
x
}
+
2
,
p
)
∈{
0
,
1
q
(
)
. In addition, when given an
to y
∈{
0
,
1
}
NP
-witness u for x
∈
L, the prover
L
1
.
2.
The prover invokes P on common input y, auxiliary input
reduces
26
u to a witness, denoted
w
, for y
∈
w
, and common
reference string s, obtaining output
π
, which it outputs/sends.
Verifier:
1.
Reduces
(
x
p
)
to y using the same standard reduction of L
2
to L
1
.
2.
Invokes V on common input y, common reference string s, and prover's output
π
,
, and decides as V does.
Note that the reduction maps (
+
2
)-bit-long instances of
L
2
to instances of
L
1
having length
q
(
). Recall that by the hypothesis, the proof system (
P
,
V
) handles
L
1
instances of length
q
(
) by using a reference string of length
q
(
)
=
n
−
2
, which
exactly matches the length of
s
. Let
ε>
0 be a constant satisfying
n
ε
≤
(i.e., (2
+
q
(
))
ε
≤
). Then we have the following:
Proposition 4.10.13:
Let
(
P
V
)
be as before, and let G be a pseudorandom
generator. Furthermore, suppose that P is zero-knowledge and that when given an
NP
,
-witness as auxiliary input, it can be implemented in probabilistic polynomial
time. Then Construction 4.10.12 constitutes an unboundedly zero-knowledge non-
interactive proof system for L, with fundamental constant
ε
. Furthermore, the
prover can be implemented by a probabilistic polynomial-time machine that gets
an
NP
-witness as auxiliary input.
Proof Sketch:
The completeness and efficiency claims for the new prover fol-
low immediately from the hypotheses concerning (
P
V
). The soundness con-
dition follows by observing that the probability that
p
is in the range of
G
is at most 2
−
(and relying on the soundness of (
P
,
V
)). To prove the zero-
knowledge property, we construct a simulator as follows. The simulator uni-
formly selects
u
∈{
0
,
1
}
and
s
∈{
0
,
1
}
,
n
−
2
, sets
p
=
G
(
u
), and handles each
instance
x
}
in a sequence of
L
instances as follows: The simulator emu-
lates the prover's program (on input
x
), except that it uses
u
as the
∈{
0
,
1
NP
-witness
for (
x
,
p
)
∈
L
2
. Namely, the simulator reduces (
x
,
p
)
∈
L
2
to
y
∈
L
1
, along
-witness
u
to a witness
w
(for
y
). Next, the simula-
tor invokes
P
on common input
y
, auxiliary in
pu
t
NP
with reducing the
w
, and common reference
string
s
.
Th
us, when given a sequence of instances
x
=
(
x
1
,...,
x
t
), the simulator
outputs (
x
P
w
(
y
1
,
P
w
(
y
t
,
s
)), where
y
i
is the result of applying
the reduction to (
x
i
,
p
). Note that the efficiency of the simulator relies on the
efficient implementation of
P
(and on the efficiency of
G
). To prove that the
simulator's output is computationally indistinguishable from the verifier's view,
,
(
p
,
s
)
,
s
)
,...,
26
We again use the fact that the standard reductions are coupled with an adequate witness-reduction (see
Exercise 16).
