A Study of Perfect Zero-knowledge Proofs

Download or read book A Study of Perfect Zero-knowledge Proofs written by and published by . This book was released on 2008 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: Perfect zero-knowledge proofs enable one party (the prover) to prove an assertion to another party (the verifier) but without revealing anything but the truth of the assertion. The class of problems admitting such proofs is rich, including Graph Isomorphism, Quadratic Residuousity, and other problems that play a key role in cryptography and complexity theory. Due to their strong privacy guarantee, perfect zero-knowledge proofs are very difficult to study. Despite extensive research since the 1980s, especially in the area of statistical zero-knowledge proofs, many fundamental questions about them remain open, and it is not even clear how to address these questions. This thesis initiates a general investigation of perfect zero-knowledge proofs. Our main results are as follows. 1. We prove that all the known problems admitting perfect zero-knowledge PZK proofs can be characterized as non-interactive instance-dependent commitment schemes, and use this result to generalize and strengthen previous results, as well as to prove new results about PZK problems. 2. We give a new error shifting technique that allows us to overcome barriers in the study of PZK. Using this technique we present the first complete problem for the class of problems admitting non-interactive perfect zero-knowledge proofs (NIPZK), and the first hard problem for the class of problems admitting public-coin PZK proofs. 3. We make the first investigation into one of the most important questions in the field, namely, whether the number of rounds in PZK proofs can be collapsed to a constant. We give the first perfectly hiding commitment scheme, and prove that obtaining such a scheme that is also constant round is equivalent to collapsing the rounds in PZK proofs to a constant.