Cryptography Reference
In-Depth Information
4.4.4
Two basic problems: composition and black-box
simulation
We conclude this section by considering two basic problems regarding
zero-knowledge, which actually arise also with respect to the security
of other cryptographic primitives.
Composition of protocols.
The first question refers to the
preser-
vation of security
(i.e., zero-knowledge in our case)
under various
types of composition operations
. These composition operations rep-
resent independent executions of a protocol that are attacked by an
adversary (which coordinates its actions in the various executions). The
preservation of security under such compositions (which involve only
executions of the same protocol) is a first step towards the study of the
security of the protocol when executed together with other protocols
(see further discussion in Section 7.4). Turning back to zero-knowledge,
we recall the main facts regarding sequential, parallel and concurrent
execution of (arbitrary and/or specific) zero-knowledge protocols:
Sequential composition
:
As stated above, zero-knowledge (with
respect to auxiliary inputs) is closed under sequential composi-
tion.
Parallel composition
:
In general, zero-knowledge is not closed under
parallel composition (71). Yet, some zero-knowledge proofs (for
NP) preserve their security when many copies are executed in
parallel. Furthermore, some of these protocol use a constant
number of rounds (cf. (66)).
Concurrent composition
:
One may view parallel composition as
concurrent composition in a model of strict synchronity. This
leads us to consider more general models of concurrent compo-
sition. We distinguish between a model of full asynchronicity
and a model naturally limited asynchronicity.
•
In the full asynchronous model, some zero-knowledge
proofs (for NP) preserve their security when many
copies are executed concurrently (cf. (111; 91; 107)), but
such a result is not known for constant-round protocols.
