Lower Bounds For Concurrent Zero Knowledge* |
| |
Authors: | Joe Kilian Charles Rackoff Erez Petrank |
| |
Affiliation: | (1) NEC Laboratories America, 4 Independence Way, Princeton, NJ 08550, USA;(2) Dept. of Computer Science Technion—Israel Institute of Technology, Haifa 32000, Israel;(3) Dept. of Computer Science, University of Toronto, Toronto, Ontario, M5S 3G4, Canada |
| |
Abstract: | 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 these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.* An abridge version of this work has appeared in [24]. |
| |
Keywords: | 68Q17 68Q10 68Q85 |
本文献已被 SpringerLink 等数据库收录! |
|