Cryptography Reference
In-Depth Information
In contrast, constant-round zero-knowledge proofs (for
NP) are known (cf. (53; 66)) in a model of limited asyn-
chronicity, where each party holds a local clock such
that the relative clock rates are bounded by an a-priori
known constant and the protocols may employ time-
driven operations (i.e., time-out incoming messages and
delay out-going messages).
The study of zero-knowledge in the concurrent setting provides a good
test case for the study of concurrent security of general protocols. In
particular, the results in (71; 40) point out inherent limitations of the
“standard proof methods” (used to establish zero-knowledge) when
applied to the concurrent setting, where (71) treats the synchronous
case and (40) uncovers much stronger limitations for the asynchronous
case. By “standard proof methods” we refer to the establishment of
zero-knowledge via a single simulator that obtains only oracle (or
“black-box”) access to the adversary procedure.
Black-box proofs of security. The second basic question regarding
zero-knowledge refers to the usage of the adversary's program within
the proof of security (i.e., demonstration of the zero-knowledge prop-
erty). For 15 years, all known proofs of security used the adversary's
program as a black-box (i.e., a universal simulator was presented using
the adversary's program as an oracle). Furthermore, it was believed
that there was no advantage in having access to the code of the adver-
sary's program (cf. (71)). Consequently it was conjectured that negative
results regarding black-box simulation represent an inherent limitation
of zero-knowledge. This belief has been refuted recently by Barak (8)
who constructed a zero-knowledge argument (for NP) that has impor-
tant properties that are impossible to achieve by black-box simulation
(unless
). For example, this zero-knowledge argument uses
a constant number of rounds and preserves its security when an a-priori
fixed (polynomial) number of copies are executed concurrently. 10
NP⊆BPP
10 This result falls short of achieving a fully concurrent zero-knowledge argument, because
the number of concurrent copies must be fixed before the protocol is presented. Specifi-
cally, the protocol uses messages that are longer than the allowed number of concurrent
 
Search WWH ::




Custom Search