Studies in Zero Knowledge

An interactive proof system allows a prover to convince a verifier, beyond any reasonable doubt, that a mathematical statement is true. The proof system is said to be zero-knowledge if the verifier learns nothing but the validity of the statement. This thesis studies the properties of zero-knowledge under two important attack models: man-in-middle attack and concurrent attack.;A zero-knowledge interactive proof system which ensures "independence" of executions under the man-in-middle attack is known as a non-malleable zero-knowledge proof system. We present a non-malleable zero-knowledge protocol of optimal round-complexity (four) for all languages in NP . In addition, this protocol has a black-box simulator. Our construction proceeds by constructing an important cryptographic primitive, called a non-interactive and non-malleable commitment scheme.;To achieve these results, we define and develop the notion of adaptive one-way functions. This notion is of independent interest. Various candidate constructions for adaptive one-way functions based on the hardness of specific number-theoretic assumptions are also presented. Our results in the man-in-middle model assume the existence of adaptive one-way functions.;An interactive proof system which remains zero-knowledge under the concurrent attack is known as concurrent zero-knowledge proof system. The simulation techniques of known concurrent zero-knowledge protocols lack an important measure of quality, namely precision. We present a concurrent zero-knowledge protocol for all languages in NP with a precise simulation technique.;The two attack models mentioned above are somewhat orthogonal to each other. This leads to a combined and stronger attack model: concurrent man-in-middle attack. A protocol that remains zero-knowledge under this attack is called concurrent non-malleable zero-knowledge. A general compiler for transforming a protocol with much weaker security (namely, honest-verifier zero-knowledge) into a protocol with strong security (i.e., concurrent non-malleable zero-knowledge) is also presented. This transformation is based on the (standard) decisional Diffie-Hellman (DDH) assumption.