Lower Bounds for Non-Black-Box Zero Knowledge

Boaz Barak, Yehuda Lindell and Salil Vadhan


We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:

The complexity assumptions we use are not commonly used in cryptography. However, in all cases, we show that assumptions like ours are necessary for the above results.
Most previously known lower bounds, such as those of Goldreich and Krawczyk (SIAM J. Computing, 1996), were only for black-box zero knowledge. However, a result of Barak (FOCS 2001) shows that many (or even most) of these black-box lower bounds do not extend to the case of general zero knowledge.

Postscript, gzipped Postscript.

Back Home