Zero-knowledge proof systems are interactive protocols that enable one party, called the prover, to convince another party, called the verifier, in the truth of a statement without revealing anything beyond the validity of the assertion being proved.
The original setting in which zero-knowledge proofs were investigated consisted of a single prover and verifier executing only one instance of the protocol at a time. A more realistic setting, especially in the era of the Internet, is one that allows the concurrent execution of zero-knowledge protocols.
The most common technique for proving the zero-knowledge property of a protocol is called black-box simulation. As it turns out, the usage of black-box simulation in the concurrent setting introduces many technical difficulties. The only known way to enable black-box simulation in the concurrent setting is to significantly increase the protocol's round-complexity (i.e., the number of messages exchanged in the protocol).
It has already been shown that for every language outside BPP there is no 4-round protocol whose concurrent zero-knowledge (cZK) property is proved via black-box simulation. In contrast, the most efficient cZK protocol that we know of uses poly-logarithmically many rounds, where the complexity is w.r.t a ``security'' parameter that is polynomially related to the number of concurrent executions. In this thesis we close the gap between these upper and lower bounds. Our main results are:
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, June 2003.
Available: the thesis (in PSfile).
Back to Oded Goldreich's homepage.