The concurrent setting for Zero-Knowledge protocols is very challenging as it requires protocols to remain secure even when
several parties execute the same protocol concurrently. Indeed, it has been proved that achieving concurrent security for
(black-box-simulation) zero-knowledge protocols in standard models requires a non-constant number of rounds, thus severely
limiting efficiency. As a result, a few models with additional setup or network assumptions have been introduced to present
constant-round concurrently-secure zero-knowledge protocols for all languages in
NP{\mathcal NP}.
In this paper we consider the bare public-key model, which is known to have very minimal setup assumptions, and we present
the first constant round and concurrently secure zero-knowledge argument for any languages in
NP{\mathcal NP}, under standard intractability assumptions. In fact, our protocol requires 4 rounds and is therefore round-optimal, is a
proof of knowledge, and is time-efficient, in the sense that it is based on a tranformation that does not require any expensive
NP{\mathcal NP} reduction from prover or verifier. One 5-round variant of our protocol can be based on the minimal assumption of the existence
of a one-way function.
Copyright Telcordia. The second author releases his portion of the copyright to Springer-Verlag. Part of the second author’s
work done while being a post-doctoral fellow at the Dép. d’Inf. of the Ecole Normale Supérieure in Paris, France; and part
supported by NoE ECRYPT under contract IST-2002-507932.