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.

∈