International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Joe Kilian

Publications

Year
Venue
Title
2008
TCC
2008
ASIACRYPT
2005
EUROCRYPT
2005
EUROCRYPT
2003
CRYPTO
2001
ASIACRYPT
2001
EPRINT
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 out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in $\NP$.
2001
JOFC
2000
EPRINT
Concurrent Zero-Knowledge in Poly-logarithmic Rounds
Joe Kilian Erez Petrank
A proof is concurrent zero-knowledge if it remains zero-knowledge when run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment; Kilian, Petrank and Rackoff have shown that any {\bf 4} rounds zero-knowledge interactive proof (for a non-trivial language) is not concurrent zero-knowledge. On the other hand, Richardson and Kilian have shown that there exists a concurrent zero-knowledge argument for all languages in NP, but it requires a {\bf polynomial} number of rounds. In this paper, we present a concurrent zero-knowledge proof for all languages in NP with a drastically improved complexity: our proof requires only a poly-logarithmic, specifically, $\omega(\log^2 k)$ number of rounds. Thus, we narrow the huge gap between the known upper and lower bounds on the number of rounds required for a zero-knowledge proof that is robust for asynchronous composition.
1999
EUROCRYPT
1999
EUROCRYPT
1999
EUROCRYPT
1998
CRYPTO
1998
JOFC
1997
EPRINT
Identity Escrow
Joe Kilian Erez Petrank
We introduce the notion of escrowed identity, an application of key-escrow ideas to the problem of identification. In escrowed identity, one party, A, does not give his identity to another party B, but rather gives him information that would allow an authorized third party, E, to determine A's identity. However, B receives a guarantee that E can indeed determine A's identity. We give protocols for escrowed identity based on the El-Gamal (signature and encryption) schemes and on the RSA function. A useful feature of our protocol is that after setting up A to use the system, E is only involved when it is actually needed to determine A's identity.
1997
JOFC
1996
CRYPTO
1995
CRYPTO
1995
CRYPTO
1995
EUROCRYPT
1994
CRYPTO
1994
CRYPTO
1993
CRYPTO
1992
CRYPTO
1991
CRYPTO
1990
CRYPTO
1990
CRYPTO
1990
CRYPTO
1989
CRYPTO
1989
CRYPTO
1988
CRYPTO
1988
CRYPTO

Program Committees

Eurocrypt 2007
TCC 2005 (Program chair)
Eurocrypt 2004
TCC 2004
Crypto 2001 (Program chair)
Eurocrypt 2000
Crypto 1992