Cryptography Reference
In-Depth Information
•
In the
basic definition
, one considers proving a single asser-
tion of a-priori bounded length, where this length may be
smaller than the length of the reference string.
•
A natural extension, required in many applications, is the
ability to prove multiple assertions of varying length, where
the total length of these assertions may exceed the length of
the reference string (as long as the total length is polyno-
mial in the length of the reference string). This definition is
sometimes referred to as the
unbounded definition
,because
the total length of the assertions to be proved is not a-priori
bounded.
•
Other natural extensions refer to the preservation of secu-
rity (i.e., both soundness and zero-knowledge) when the
assertions to be proved are selected
adaptively
(based on
the reference string and possibly even based on previous
proofs).
•
Finally, we mention the notion of
simulation-soundness
,
which is related to
non-malleability
. This extension, which
mixes the zero-knowledge and soundness conditions, refers
to the soundness of proofs presented by an adversary after
it obtains proofs of assertions of its own choice (with respect
to the same reference string). This notion is important in
applications of non-interactive zero-knowledge proofs to the
construction of public-key encryption schemes secure against
chosen ciphertext attacks (see (67, Sec. 5.4.4.4)).
Constructing non-interactive zero-knowledge proofs seems more di
-
cult than constructing interactive zero-knowledge proofs. Still, based
on standard intractability assumptions (e.g., intractability of factor-
ing), it is known how to construct a non-interactive zero-knowledge
proof (even in the adaptive and non-malleable sense) for any NP-set
(cf. (56; 116)).
Witness Indistinguishability and the FLS-Technique.
The
notion of witness indistinguishability was suggested in (57) as a
meaningful relaxation of zero-knowledge. Loosely speaking, for any
