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)


Salil Vadhan (#475)
Name Salil Vadhan
Personal Homepage
Topic of his/her doctorate. A Study of Statistical Zero-Knowledge Proofs
Category foundations
Keywords zero knowledge, complexity theory
Ph.D. Supervisor(s) Shafi Goldwasser
Year of completion 1999
Abstract Zero-knowledge interactive proofs, introduced by Goldwasser, Micali, and Rackoff, are fascinating constructs which enable one party (the "prover") to convince another party (the "verifier") of an assertion, with the property that the verifier learns nothing other than the fact that the assertion being proven is true. In addition to being powerful tools for constructing secure cryptographic protocols, zero-knowledge proofs yield rich classes of computational problems that are of both complexity-theoretic and cryptographic interest. This thesis is a detailed investigation of statistical zero-knowledge proofs, which are zero-knowledge proofs in which the condition that the verifier "learns nothing" is interpreted in a strong statistical sense. We begin by showing that the class SZK of problems possessing such proofs has two natural complete problems. These problems essentially amount to approximating the statistical difference or the difference in entropies between two "efficiently samplable" distributions. Thus, they give a new characterization of SZK which makes no reference to interaction or zero knowledge. They also simplify the study of statistical zero knowledge, as questions about the entire class SZK can be reduced to examining these two particular complete problems. Using these complete problems as tools, we proceed to answer a number of fundamental questions about zero-knowledge proofs, including:
  • Transforming any statistical zero-knowledge proof against an honest verifier (i.e., a verifier that follows the specified protocol) into one which is zero knowledge even against cheating verifiers that deviate arbitrarily from the specified protocol. This transformation applies to public-coin computational zero-knowledge proofs as well.

  • Constructing statistical zero-knowledge proofs for complex assertions built out of simpler assertions already shown to be in SZK. Via the complete problems, these closure properties translate to new methods for manipulating "efficiently samplable" distributions, which may be of independent interest.

  • Obtaining simpler proofs of most previously known results about statistical zero knowledge, such as: Okamoto's result that SZK is closed under complement; the Fortnow and Aiello--HÃ¥stad upper bounds on the complexity of SZK; and Okamoto's result that every statistical zero-knowledge proof can be transformed into a public-coin one.
Your Ph.D. thesis as fulltext 51_SalilVadhan_AStudyStatisticalZeroKnowledg.pdf
E-Mail Address salil (at)
Last Change 2011-04-20 08:14:13
To provide an update on this entry, please click .

Salil Vadhan's Students

Shien Jin Ong - Unconditional Relationships within Zero Knowledge (foundations)

Contact: phds (at)

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