Publications

D. Harnik, J. Kilian, M. Naor, O. Reingold and A. Rosen
On Robust Combiners for Oblivious Transfer and other Primitives
Proceedings, Advances in Cryptology: Eurocrypt '05 (2005)
[ps] [pdf]

B. Chazelle, J. Kilian, R. Rubinfeld and A. Tal
The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables
Proceedings, Symposium on Distributed Algorithms (SODA) 2004
[contact]

S. Micali, M. O. Rabin and J. Kilian
Zero-Knowledge Sets
Proceedings, 44th Annual IEEE Symposium on Foundations of Computer Science (2003)
[ps] [pdf]

Y. Ishai, J. Kilian, K. Nissim and E. Petrank
Extending Oblivious Transfers Efficiently
Proceedings, Advances in Cryptology: Crypto 2003.
[ps] [pdf]

T. Batu, F. Ergun, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld and R. Sami.
A sublinear algorithm for weakly approximating edit distance.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing. (2003)
[ps] [pdf]

L. Fortnow, J. Kilian, D. M. Pennock and M. P. Wellman
Betting Boolean-style: A Framework for Trading in Securities Based on Logical Formulas.
Proceedings, ACM Conference on Electronic Commerce. (2003)
[ps] [pdf]

M. M. J. Treacy and J. Kilian.
Designability of Graphitic Cones
Proceedings, Materials Research Society 2001 Spring Meeting (2001)
[pdf]

T. Cohen, J. Kilian and E. Petrank.
Responsive Round Complexity and Concurrent Zero-Knowledge
Proceedings, Advances in Cryptology: Asiacrypt '01 (2001)
[ps] [pdf]

J. Kilian and E. Petrank.
Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds
Proceedings, 33rd Annual ACM Symposium on the Theory of Computing (2001)
[ps] [pdf]

R. Canetti, J. Kilian, E. Petrank and A. Rosen.
Concurrent Zero-Knowledge Requires Omega(log n/loglog n) Rounds
Proceedings, 33rd Annual ACM Symposium on the Theory of Computing (2001)
[ps] [pdf]

J. Kilian.
More General Completeness Theorems for Secure Two-Party Computation
Proceedings, 32nd Annual ACM Symposium on the Theory of Computing (2000)
[ps] [pdf]

F. Ergun, J. Kilian and R. Kumar.
A Note on the Limits of Collusion-Resistant Watermarks
Proceedings, Advances in Cryptology: Eurocrypt '99 (1999)
[ps] [pdf]

I. Damgard, J. Kilian and L. Salvail.
On the (Im)possibility of basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions
Proceedings, Advances in Cryptology: Eurocrypt '99 (1999)
[ps] [pdf]

R. Richardson and J. Kilian.
Non-Synchronized Composition of Zero-Knowledge Proofs
Proceedings, Advances in Cryptology: Eurocrypt '99 (1999)
[ps] [pdf]

J. Kilian, E. Petrank and C. Rackoff.
Zero Knowledge on the Internet
Proceedings, 39th Annual IEEE Symposium on Foundations of Computer Science (1998)
[ps] [pdf]

Uri Feige and J. Kilian.
Heuristics for finding large independent sets, with applications to coloring semi-random graphs
Proceedings, 39th Annual IEEE Symposium on Foundations of Computer Science (1998)
[ps] [pdf]

J. Kilian and E. Petrank.
Identity Escrow
Proceedings, Advances in Cryptology: Crypto '98 (1998)
[ps] [pdf]

J. Kilian and Erez Petrank.
An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions
Journal of Cryptology, vol.~11, no.~1, pp.~1--27, Winter (1998)
[ps] [pdf]

J. Kilian, E. Petrank and G. Tardos.
Probabilistically checkable proofs with zero knowledge
Proceedings, 29th Annual ACM Symposium on the Theory of Computing (1997)
[ps] [pdf]

U. Feige and J. Kilian.
Making Games Short
Proceedings, 29th Annual ACM Symposium on Theory of Computing (1997)
[ps] [pdf]

U. Feige and J. Kilian.
On limited versus polynomial nondeterminism
CJTCS: Chicago Journal of Theoretical Computer Science, March 12 (1997)
[ps] [pdf]

J. Kilian and Phil Rogaway.
How to Protect DES Against Exhaustive Key Search
Proceedings, Advances in Cryptology: Crypto '96 (1996)
[ps] [pdf]

I. Cox, J. Kilian, F. T. Leighton and T. Shamoon.
A secure, robust watermark for multimedia.
Proceedings, IEEE International Conference on Image Processing, vol.3, pp.243-246 (1996)
See also, IEEE Transaction on Image Processing, vol.~6, no.~12 pp.~1673--1687, December (1997)
[not available] [not available]

U. Feige and J. Kilian.
Zero Knowledge and the Chromatic Number
Proceedings, Eleventh Annual IEEE Conference on Computational Complexity, pages 278--287, Philadelphia, Pennsylvania, 24--27 May (1996). IEEE Computer Society Press.
To appear, Journal of Computers and System Sciences
[ps] [pdf]

K. Sako and J. Kilian.
Receipt-free mix-type voting scheme --- A practical solution to the implementation of a voting booth.
Proceedings, Advances in Cryptology: EUROCRYPT '95, Lecture Notes in Computer Science, Springer-Verlag, volume 921, pages 393--403 (1995)
[ps] [pdf]

U. Feige and J. Kilian.
Impossibility Results for Recycling Random Bits in Two-Prover Proof Systems
Proceedings, 27th Annual ACM Symposium on Theory of Computing (1995)
[ps] [pdf]

J. Kilian and F. T. Leighton.
Fair cryptosystems, revisited: A rigorous approach to key-escrow
Proceedings, Advances in Cryptology: Crypto '95 (1995)
[ps] [pdf]

J. Kilian and M. Naor.
On the Complexity of Statistical Reasoning
Proceedings, ISTCS: 3rd Israeli Symposium on the Theory of Computing and Systems (1995)
[ps] [pdf]

J. Kilian.
Improved Efficient Arguments
Proceedings, Advances in Cryptology: Crypto '95 (1995)
[ps] [pdf]

M. Bellare, J. Kilian and P. Rogaway.
The Security of Cipher Block Chaining
Proceedings, Advances in Cryptology: Crypto '94 (1994)
[ps] [pdf]

K. Sako and J. Kilian.
Secure Voting Using Partially Compatible Homomorphisms
Proceedings, Advances in Cryptology: Crypto '94 (1994)
[ps] [pdf]

K. Lang, J. Kilian and B. Pearlmutter.
Playing the Matching-Shoulders Lob-Pass Game with Logarithmic Regret
Proceedings, Seventh ACM Conference on Computational Learning Theory, pages 159--164, New Brunswick, New Jersey, 12--15 July (1994) ACM Press
[ps] [pdf]

J. Kilian.
On the complexity of Bounded-Interaction and Noninteractive Zero-Knowledge Proofs
Proceedings, 35th Annual IEEE Symposium on the Foundations of Computer Science (1994)
[ps] [pdf]

U. Feige, J. Kilian and Moni Naor\\.
A Minimal Model for Secure Computation
Proceedings 26th Annual ACM Symposium on Theory of Computing (1994)
[ps] [pdf]

U. Feige and J. Kilian.
Two Prover Protocols -- Low Error at Affordable Rates
Proceedings 26th Annual ACM Symposium on Theory of Computing (1994)
[ps] [pdf]

Claude Crepeau and J. Kilian.
Discreet Solitary Games,
Advances in Cryptology: Proceedings, Crypto '93 (1993)
[ps] [pdf]

J. Kilian and H. T. Siegelmann.
On the power of sigmoid neural networks
Proceedings, Sixth ACM Conference on Computational Learning Theory (1993),
See also, Information and Computation, Vol. 128, No. 1, pp. 48-56, July 10 (1996)
[ps] [pdf]

J. Kilian.
A note on efficient zero-knowledge proofs and arguments
Proceedings, 24th Annual ACM Symposium on the Theory of Computing (1992)
[ps] [pdf]

J. Kilian and R. Rubinfeld
Interactive proofs with space bounded provers
Proceedings, Advances in Cryptology: Crypto '91 (1991)
[ps] [pdf]

J. Kilian.
A General Completeness Theorem for Two-Party Games,
Proceedings, 23rd Annual ACM Symposium on Theory of Computing (1991)
[ps] [pdf]

J. Kilian.
Achieving Zero-Knowledge Robustly,
Proceedings, Advances in Cryptology: Crypto '90 (1990)
[ps] [pdf]

J. Kilian.
Interactive proofs with provable security against passive adversaries,
Proceedings, Advances in Cryptology: Crypto '90 (1990)
[ps] [pdf]

D. Beaver, J. Feigenbaum, J. Kilian and P. Rogaway.
Cryptographic Applications of Locally Random Reductions,
Proceedings, Advances in Cryptology: Crypto '90 (1990)
See also Journal of Cryptology, 10(1):17--36, Winter (1997)
[ps] [pdf]

J. Kilian, S. Micali and R. Ostrovsky.
Minimum Resource Zero-knowledge Proofs,
Proceedings, 30th Annual IEEE Symposium on the Foundations of Computer Science (1989)
[ps] [pdf]

J. Kilian.
Zero-Knowledge with Log-Space Verifiers,
Proceedings, 29th Annual IEEE Symposium on the Foundations of Computer Science, (1988)
[ps] [pdf]

C. Crepeau and J. Kilian.
Achieving Oblivious transfer Using Weakened Security Assumptions,
Proceedings, 29th Annual IEEE Symposium on the Foundations of Computer Science, (1988)
[ps] [pdf]

M. Ben-Or, S. Goldwasser, J. Kilian and A. Wigderson.
Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions,
Proceedings, 20th Annual ACM Symposium on Theory of Computing, (1988)
[not available] [not available]

J. Kilian.
Founding Cryptography on Oblivious Transfer,
Proceedings, 20th Annual ACM Symposium on Theory of Computing (1988)
[ps] [pdf]

J. Kilian, S. Kipnis and C. Leiserson.
The Organization of Permutation Architectures with Bussed Interconnections,
Proceedings, 28th Annual IEEE Symposium on the Foundations of Computer Science (1987)
See also, IEEE Transactions on Computers Volume 39, pp. 1346--1358 (1990)
[not available]

M. Abadi, J. Feigenbaum and J. Kilian.
On Hiding Information from an Oracle,
Proceedings, 19th Annual ACM Symposium on Theory of Computing (1987)
See also, Journal of Computer System Science, Volume 39, pp. 21-50 (1989)
[not available]

S. Goldwasser and J. Kilian.
Almost all Primes Can be Quickly Certified,
Proceedings, 18th Annual ACM Symposium on Theory of Computing (1986)
[ps] [pdf]