Cryptography Reference

In-Depth Information

NP-relation
R
, a proof (or argument) system for the corresponding

NP-set is called
witness indistinguishable
if no feasible verifier may dis-

tinguish the case in which the prover uses one NP-witness to
x
(i.e.,
w
1

such that (
x, w
1
)

∈ R
) from the case in which the prover is using a dif-

ferent NP-witness to the same input
x
(i.e.,
w
2
such that (
x, w
2
)

R
).

Clearly, any zero-knowledge protocol is witness indistinguishable, but

the converse does not necessarily hold. Furthermore, it seems that

witness indistinguishable protocols are easier to construct than zero-

knowledge ones. Another advantage of witness indistinguishable proto-

cols is that they are closed under arbitrary concurrent composition (57),

whereas in general zero-knowledge protocols are not closed even under

parallel composition (71). Witness indistinguishable protocols turned

out to be an
important tool in the construction of more complex proto-

cols
, as is demonstrated next.

Feige, Lapidot and Shamir (56) introduced a technique for con-

structing zero-knowledge proofs (and arguments) based on witness

indistinguishable proofs (resp., arguments). Following is a sketchy

description of a special case of their technique, often referred to as

the
FLS-technique
, which has been used in numerous works. On com-

mon input
x

∈

L
,where
L
is the NP-set defined by the witness relation

R
, the following two steps are performed:

∈

(1) The parties generate an instance
x
for an auxiliary NP-

set
L
,where
L
is defined by a witness relation
R
.The

generation protocol
in use must satisfy the following two

conditions:

(a) If the verifier follows its prescribed strategy then no

matter which strategy is used by the prover, with high

probability, the protocol's outcome is a no-instance

of
L
.

(b) Loosely speaking, there exists an ecient (non-

interactive) procedure for producing a (random)

transcript of the generation protocol such that the

corresponding protocol's outcome is a yes-instance of

L
and yet the produced transcript is computationally

indistinguishable from the transcript of a real exe-