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)


Shien Jin Ong (#477)
Name Shien Jin Ong
Institution Harvard University
Topic of his/her doctorate. Unconditional Relationships within Zero Knowledge
Category foundations
Keywords zero knowledge
Ph.D. Supervisor(s) Salil Vadhan
Year of completion 2007

Zero-knowledge protocols enable one party, called a prover, to "convince" another party, called a verifier, the validity of a mathematical statement such that the verifier "learns nothing" other than the fact that the proven statement is true. The different ways of formulating the terms "convince" and "learns nothing" gives rise to four classes of languages having zero-knowledge protocols, which are: statistical zero-knowledge proof systems, computational zero-knowledge proof systems, statistical zero-knowledge argument systems, and computational zero-knowledge argument systems.

We establish complexity-theoretic characterization of the classes of languages in NP having zero-knowledge argument systems. Using these characterizations, we show that for languages in NP:

  • Instance-dependent commitment schemes are necessary and sufficient for zero-knowledge protocols. Instance-dependent commitment schemes for a given language are commitment schemes that can depend on the instance of the language, and where the hiding and binding properties are required to hold only on the YES and NO instances of the language, respectively.
  • Computational zero knowledge and computational soundness (a property held by argument systems) are symmetric properties. Namely, we show that the class of languages in NP intersect co-NP having zero-knowledge arguments is closed under complement, and that a language in NP has a statistical zero-knowledge argument system if and only if its complement has a computational zero-knowledge proof system.
  • A method of transforming any zero-knowledge protocol that is secure only against an honest verifier that follows the prescribed protocol into one that is secure against malicious verifiers. In addition, our transformation gives us protocols with desirable properties like having public coins, being black-box simulatable, and having an efficient prover.

The novelty of our results above is that they are unconditional, meaning that they do not rely on any unproven complexity assumptions such as the existence of one-way functions. Moreover, in establishing our complexity-theoretic characterizations, we give the first construction of statistical zero-knowledge argument systems for NP based on any one-way function.

Last Change 2011-04-20 08:11:49
To provide an update on this entry, please click .

Contact: phds (at)

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