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-
