History

Please fill in your query. A complete syntax description you will find on the General Help page.
Minimal assumptions and round complexity for concurrent zero-knowledge in the bare public-key model. (English)
Ngo, Hung Q. (ed.), Computing and combinatorics. 15th annual international conference, COCOON 2009, Niagara Falls, NY, USA, July 13‒15, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02881-6/pbk). Lecture Notes in Computer Science 5609, 127-137 (2009).
Summary: Under the (minimal) assumption of the existence of one-way functions, we show that every language in NP has (round-optimal) argument systems in the bare public key (BPK) model of [{\it R. Canetti}, {\it O. Goldreich}, {\it S. Goldwasser} and {\it S. Micali}, “Resettable zero-knowledge”, in: Proceedings of the 32nd annual ACM symposium on theory of computing, STOC ’00, 235‒244 (2000)], which are sound (i.e., a cheating prover cannot prove that $x\not\in L$) and (black-box) zero-knowledge (i.e., a cheating verifier does not obtain any additional information other than $x \in L)$ even in the presence of concurrent attacks (i.e., even if the cheating prover or verifier are allowed to arbitrarily interleave several executions of the same protocol). This improves over the previous best result [{\it G. Di Crescenzo} and {\it I. Visconti}, Lect. Notes Comput. Sci. 3580, 816‒827 (2005; Zbl 1084.94513)], which obtained such a protocol using a stronger assumption (the existence of one-way permutations) or a higher round complexity (5 messages), and is round-optimal among black-box zero-knowledge protocols. We also discuss various extensions and applications of our techniques with respect to protocols with different security and efficiency requirements.