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.
Shien Jin Ong (#477)
Shien Jin Ong
Topic of his/her doctorate.
Unconditional Relationships within Zero Knowledge
Year of completion
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
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.