International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Leonid Reyzin (#514)
Name Leonid Reyzin
Personal Homepage
Topic of his/her doctorate. Zero-Knowledge with Public Keys
Category foundations
Keywords soundness, resettable zero knowledge
Ph.D. Supervisor(s) Silvio Micali
Year of completion 2001

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.

Your Ph.D. thesis as fulltext 78_LeonidReyzin_ZeroKnowledgewithPublicKeys.pdf
Last Change 2011-08-03 10:17:57
To provide an update on this entry, please click .

Leonid Reyzin's Students

Scott Russell - Communication and Query Privacy: Intrusion-Resilient Secure Channels and Private Database Queries (cryptographic protocols)
Chun-Yuan Hsiao - Butterfly Effect in Cryptography: Consequences of Changes in Definitions (foundations)
Benjamin Fuller - Strong Key Derivation from Noisy Sources (foundations)

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR