Zero-Knowledge On The Internet

Zero-knowledge protocols allow one party to prove the validity of a mathematical statement to another party, without revealing any additional information. The use of zero-knowledge in internet applications has boomed recently; this is no surprise considering that internet privacy has become such an important issue in the last few years. The original zero-knowledge definition considers the setting where an adversarial verifier interacts only with one honest prover. In the age of the internet, however, a great number of sessions of the same protocol are executed concurrently. This led to the definition of concurrent zero-knowledge (cZK) by Dwork, Naor and Sahai (Journal of ACM, 2004). Concurrent zero-knowledge protocols are secure against adversarial verifiers who may launch a coordinated attack against multiple independent honest provers, concurrently. Much study has already been done on the subject of cZK, resulting in a wide range of constructions under different hardness assumptions, and in different models (e.g., the plain model or with setup assumptions). Moving beyond the original focus on constructions, this thesis works on improving our understanding of cZK in three areas: security, efficiency, and simplicity. In part 1 we simplify and extend the current techniques to construct cZK protocols with additional security properties such as "knowledge precision". In part 2 we present a very practical cZK protocol in the timing model. In part 3 we investigate the curious phenomenon that no known cZK protocol is public-coin