Show simple item record

dc.contributor.advisorVadhan, Salil P.
dc.contributor.authorOng, Shien Jin
dc.date.accessioned2011-09-09T17:48:54Z
dc.date.issued2011-09-09
dc.date.submitted2007
dc.identifier.citationOng, Shien Jin. 2007. Unconditional Relationships within Zero Knowledge. Doctoral dissertation, Harvard University.en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:5128473
dc.description.abstractZero-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.en_US
dc.language.isoen_USen_US
dash.licenseLAA
dc.subjectcryptographyen_US
dc.subjectzero knowledgeen_US
dc.subjectone-way functionen_US
dc.subjectcommitment schemeen_US
dc.titleUnconditional Relationships within Zero Knowledgeen_US
dc.typeThesis or Dissertationen_US
dc.date.available2011-09-09T17:48:54Z
thesis.degree.date06/06/2007en_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorHarvard Universityen_US
thesis.degree.leveldoctoralen_US
thesis.degree.nameDoctor of Philosophyen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record