The Weizmann Institute of Science Faculty of Mathematics and Computer Science Theory of Computation Research Seminar Erez Petrank Technion - Haifa will speak on Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds Seminar Room, Room 261, Ziskind Building on Sunday, July 1, 2001 at 11:00 Abstract: A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. Richardson and Kilian have shown that there exists a concurrent zero-knowledge proof for any language in NP, but with round complexity **polynomial** in the maximum number of concurrent proofs. In this talk, we present a concurrent zero-knowledge proof for all languages in NP with a poly-logarithmic round complexity: specifically, a bit more than $\log^2 k$ rounds given at most $k$ concurrent proofs. Finally, we show that a simple modification of our proof is a resettable zero-knowledge proof for NP, with the same number of rounds; previously known protocols required a polynomial number of rounds. Joint work with Joe Kilian. --------------------------------------------------------- >>Technion Mathematics Net 2 [TECHMATH2] (Editor: Eddy Mayer-Wolf)<< Announcement from: Miriam Abraham