Alon Rosen

Abstract of PhD Thesis (Weizmann Inst., 2003)

Title: The Round-Complexity of Black-Box Concurrent Zero-Knowledge

Available: the thesis (in PSfile). (in PDF).

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:

The above two results complement each other and yield an (almost) full characterization of the round-complexity of black-box cZK protocols.

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.