Lower Bounds for Zero-knowledge on the Internet

Joe Kilian, Erez Petrank, Charles Rackoff

We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and…