###
Zero-Knowledge with Public Keys

a Ph.D. Thesis by Leonid Reyzin

Thesis supervisor: Silvio Micali

__Note__: most (but not all) of results in this thesis are contained in
Silvio Micali's and mine papers on Min-Round Resettable Zero-Knowledge in the
Public-Key Model and Soundness in the
Public-Key Model.

**Abstract**
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.
This work explores their new *public-key model* for zero-knowledge
protocols.

First, it shows that the soundness notion
in this model has not been sufficiently understood and is, in fact,
more subtle and complex than in the classical model.
It identifies four *meaningful* notions of soundness, and proves
that they are *distinct*. Thus, protocol designers should understand
the needs of the application in order to avoid designing protocols whose
soundness is too weak (thus resulting in insecure protocols)
or too strong (thus resulting in protocols that are less efficient than
necessary).

Second, having precisely defined the model, this work proceeds to
demonstrate that stronger notions of soundness require more rounds to
implement. Specifically, it provides upper and lower bounds on the
numbers of rounds needed to implement the various soundness notions.

Finally, to achieve both ultimate round efficiency and strong
soundness, this work puts forward a slightly stronger model. Informally, 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 (provably
optimal) RZK protocols for all of NP that possess strong soundness.
This is particularly surprising, because such 3-round protocols provably
do not exist in the public-key model without such an upper bound.