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) iacr.org.
Salil Vadhan (#475)
Topic of his/her doctorate.
A Study of Statistical Zero-Knowledge Proofs
zero knowledge, complexity theory
Year of completion
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
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
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.
salil (at) seas.harvard.edu
Salil Vadhan's Students Shien Jin Ong
- Unconditional Relationships within Zero Knowledge (foundations)