Unconditional Relationships within Zero Knowledge

DSpace/Manakin Repository

Unconditional Relationships within Zero Knowledge

Citable link to this page


Title: Unconditional Relationships within Zero Knowledge
Author: Ong, Shien Jin
Citation: Ong, Shien Jin. 2007. Unconditional Relationships within Zero Knowledge. Doctoral dissertation, Harvard University.
Full Text & Related Files:
Abstract: 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.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:5128473
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search