Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Joe Kilian:

TR01-050 | 24th June 2001
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

We show that any concurrent zero-knowledge protocol for a non-trivial
language (i.e., for a language outside $\BPP$), whose security is proven
via black-box simulation, must use at least $\tilde\Omega(\log n)$
rounds of interaction. This result achieves a substantial improvement
over previous lower bounds, and is the first bound to rule ... more >>>

TR95-038 | 2nd July 1995
Joe Kilian, Erez Petrank

An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions

We consider noninteractive zero-knowledge proofs in the shared random
string model proposed by Blum, Feldman and Micali \cite{bfm}. Until
recently there was a sizable polynomial gap between the most
efficient noninteractive proofs for {\sf NP} based on general
complexity assumptions \cite{fls} versus those based on specific
algebraic assumptions \cite{Da}. ... more >>>

ISSN 1433-8092 | Imprint