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
(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-
Search WWH ::

Custom Search