Cryptography Reference
In-Depth Information
cution of the protocol. Furthermore, this procedure
also outputs an NP-witness for the yes-instance that
appears as the protocol's outcome.
For example,
L
may consist of all possible outcomes of a
pseudorandom generator that stretches its seed by a factor of
two, and the generation protocol may consist of the two par-
ties iteratively invoking a “coin tossing” protocol to obtain
a random string. Note that the outcome of a real execution
will be an almost uniformly distributed string, which is most
likely a no-instance of
L
, whereas it is easy to generate a
(random) transcript corresponding to any desired outcome
(provided that the parties use an adequate coin tossing
protocol).
(2) The parties execute a
witness indistinguishable
proof for
the NP-set
L
defined by the witness relation
R
=
((
α, α
)
,
(
β, β
)) : (
α, β
)
(
α
,β
)
R
}
{
. The sub-protocol
is such that the corresponding prover can be implemented
in probabilistic polynomial-time given any NP-witness for
(
α, α
)
∈
R
∨
∈
L
. The sub-protocol is invoked on common input
(
x, x
), where
x
is the outcome of Step 1, and the sub-prover
is invoked with the corresponding NP-witness as auxiliary
input (i.e., with (
w,
0), where
w
is the NP-witness for
x
(given
to the main prover)).
∈
The soundness of the above protocol follows by Property (a) of the
generation protocol (i.e., with high probability
x
L
,andso
x
L
follows by the soundness of the protocol used in Step 2). To demonstrate
the zero-knowledge property, we first generate a simulated transcript of
Step 1 (with outcome
x
∈
∈
∈
L
) along with an adequate NP-witness (i.e.,
w
such that (
x
,w
)
R
), and then emulate Step 2 by feeding the sub-
prover strategy with the NP-witness (0
,w
). Combining Property (b) of
the generation protocol and the witness indistinguishability property
of the protocol used in Step 2, the simulation is indistinguishable from
the real execution.
∈
