Min-Round Resettable Zero-Knowledge in the Public-Key Model

by Silvio Micali and Leonid Reyzin

In STOC 2000, Canetti, Goldreich, Goldwasser, and Micali put forward the strongest notion of zero-knowledge to date, resettable zero-knowledge (RZK) and implemented it in constant rounds in a new model, where the verifier simply has a public key registered before any interaction with the prover.

To achieve ultimate round efficiency, we advocate a slightly stronger model. Informally, we show that, as long as the honest verifier does not use a given public key more than a fixed-polynomial number of times, there exist 3-round (which we prove optimal) RZK protocols for all of NP.

This work appears in Advances in Cryptology -- Eurocrypt 2001, Birgit Pfitzmann, editor, volume 2045 of Lecture Notes in Computer Science, Springer-Verlag, 2001. © IACR.