# Eyal Kushilevitz

According to our database

Collaborative distances:

^{1}, Eyal Kushilevitz authored at least 158 papers between 1988 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2019

Sub-logarithmic Distributed Oblivious RAM with Small Block Size.

Proceedings of the Public-Key Cryptography - PKC 2019, 2019

2018

Minimizing Locality of One-Way Functions via Semi-private Randomized Encodings.

J. Cryptology, 2018

Efficient 3-Party Distributed ORAM.

IACR Cryptology ePrint Archive, 2018

Best Possible Information-Theoretic MPC.

Proceedings of the Theory of Cryptography - 16th International Conference, 2018

The Complexity of Multiparty PSM Protocols and Related Models.

Proceedings of the Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29, 2018

2017

Low-Complexity Cryptographic Hash Functions.

IACR Cryptology ePrint Archive, 2017

Low-Complexity Cryptographic Hash Functions.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity.

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Low-Complexity Cryptographic Hash Functions .

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Ad Hoc PSM Protocols: Secure Computation Without Coordination.

Proceedings of the Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30, 2017

2016

Secure Multiparty Computation with General Interaction Patterns.

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Distribution Design.

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Private Large-Scale Databases with Distributed Searchable Symmetric Encryption.

Proceedings of the Topics in Cryptology - CT-RSA 2016 - The Cryptographers' Track at the RSA Conference 2016, San Francisco, CA, USA, February 29, 2016

Secure Protocol Transformations.

Proceedings of the Advances in Cryptology - CRYPTO 2016, 2016

2015

Encoding Functions with Constant Online Rate, or How to Compress Garbled Circuit Keys.

SIAM J. Comput., 2015

Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Secure Computation with Minimal Interaction, Revisited.

Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

Cryptography with One-Way Communication.

Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

2014

On the Cryptographic Complexity of the Worst Functions.

Proceedings of the Theory of Cryptography - 11th Theory of Cryptography Conference, 2014

Non-Interactive Secure Multiparty Computation.

Proceedings of the Advances in Cryptology - CRYPTO 2014, 2014

2013

Guest Editorial: In-Network Computation: Exploring the Fundamental Limits.

IEEE Journal on Selected Areas in Communications, 2013

On the Power of Correlated Randomness in Secure Computation.

Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Lossy Chains and Fractional Secret Sharing.

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Robust Pseudorandom Generators.

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Encoding Functions with Constant Online Rate or How to Compress Garbled Circuits Keys.

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

2012

Encoding Functions with Constant Online Rate or How to Compress Keys in Garbled Circuits.

IACR Cryptology ePrint Archive, 2012

On the (in)security of hash-based oblivious RAM and a new balancing scheme.

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

From randomizing polynomials to parallel algorithms.

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Share Conversion and Private Information Retrieval.

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

On Achieving the "Best of Both Worlds" in Secure Multiparty Computation.

SIAM J. Comput., 2011

Black-Box Constructions of Protocols for Secure Computation.

SIAM J. Comput., 2011

How to Garble Arithmetic Circuits.

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Efficient Non-interactive Secure Computation.

Proceedings of the Advances in Cryptology - EUROCRYPT 2011, 2011

Constant-Rate Oblivious Transfer from Noisy Channels.

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

2010

On Achieving the "Best of Both Worlds" in Secure Multiparty Computation.

IACR Cryptology ePrint Archive, 2010

Black-Box Constructions of Protocols for Secure Computation.

IACR Cryptology ePrint Archive, 2010

Communication Complexity: From Two-Party to Multiparty.

Proceedings of the Structural Information and Communication Complexity, 2010

Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?

Proceedings of the Innovations in Computer Science, 2010

Choosing, Agreeing, and Eliminating in Communication Complexity.

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

From Secrecy to Soundness: Efficient Verification via Secure Computation.

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Secure Multiparty Computation with Minimal Interaction.

Proceedings of the Advances in Cryptology, 2010

2009

Zero-Knowledge Proofs from Secure Multiparty Computation.

SIAM J. Comput., 2009

On the complexity of communication complexity.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Partition Arguments in Multiparty Communication Complexity.

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Extracting Correlations.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Learning Automata.

Proceedings of the Encyclopedia of Algorithms, 2008

Distribution-Free Connectivity Testing for Sparse Graphs.

Algorithmica, 2008

OT-Combiners via Secure Computation.

Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008

Cryptography with constant computational overhead.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Zero-knowledge from secure multiparty computation.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

How Many Oblivious Transfers Are Needed for Secure Multiparty Computation?

Proceedings of the Advances in Cryptology, 2007

Public Key Encryption That Allows PIR Queries.

Proceedings of the Advances in Cryptology, 2007

Cryptography with Constant Input Locality.

Proceedings of the Advances in Cryptology, 2007

Efficient Arguments without Short PCPs.

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Information-theoretically secure protocols and security under composition.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Black-box constructions for secure computation.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Cryptography from Anonymity.

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

On Combining Privacy with Guaranteed Output Delivery in Secure Multiparty Computation.

Proceedings of the Advances in Cryptology, 2006

On Pseudorandom Generators with Linear Stretch in NC

^{0}.
Proceedings of the Approximation, 2006

2005

General constructions for information-theoretic private information retrieval.

J. Comput. Syst. Sci., 2005

Sufficient Conditions for Collision-Resistant Hashing.

Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

Learning with attribute costs.

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Computationally Private Randomizing Polynomials and Their Applications.

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

A Lower Bound for Distribution-Free Monotonicity Testing.

Proceedings of the Approximation, 2005

2004

Batch codes and their applications.

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Testing Monotonicity over Graph Products.

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Cryptography in NC

^{0}.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

On the Hardness of Information-Theoretic Multiparty Computation.

Proceedings of the Advances in Cryptology, 2004

Distribution-Free Connectivity Testing.

Proceedings of the Approximation, 2004

2003

Private computation using a PEZ dispenser.

Theor. Comput. Sci., 2003

Dynamic routing on networks with fixed-size buffers.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Distribution-Free Property Testing.

Proceedings of the Approximation, 2003

Efficient Multi-party Computation over Rings.

Proceedings of the Advances in Cryptology, 2003

On the Limitations of Universally Composable Two-Party Computation without Set-up Assumptions.

Proceedings of the Advances in Cryptology, 2003

2002

Some Applications of Polynomials for the Design of Cryptographic Protocols.

Proceedings of the Security in Communication Networks, Third International Conference, 2002

Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials.

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

On 2-Round Secure Multiparty Computation.

Proceedings of the Advances in Cryptology, 2002

2001

Private approximation of NP-hard functions.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

The round complexity of verifiable secret sharing and secure multicast.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Fair e-Lotteries and e-Casinos.

Proceedings of the Topics in Cryptology, 2001

2000

Computing Functions of a Shared Secret.

SIAM J. Discrete Math., 2000

Reducibility and Completeness in Private Computations.

SIAM J. Comput., 2000

Randomness versus Fault-Tolerance.

J. Cryptology, 2000

Learning functions represented as multiplicity automata.

J. ACM, 2000

Learning unions of high-dimensional boxes over the reals.

Inf. Process. Lett., 2000

Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation.

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval.

Proceedings of the Advances in Cryptology, 2000

Exposure-Resilient Functions and All-or-Nothing Transforms.

Proceedings of the Advances in Cryptology, 2000

1999

Characterizing Linear Size Circuits in Terms of Pricacy.

J. Comput. Syst. Sci., 1999

Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract).

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

One-Way Functions Are Essential for Single-Server Private Information Retrieval.

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

PAC Learning with Nasty Noise.

Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

1998

A Randomness-Rounds Tradeoff in Private Computation.

SIAM J. Discrete Math., 1998

SIAM J. Comput., 1998

On Learning Read-k-Satisfy-j DNF.

SIAM J. Comput., 1998

Private Information Retrieval.

J. ACM, 1998

Randomness versus Fault-Tolerance.

IACR Cryptology ePrint Archive, 1998

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Protecting Data Privacy in Private Information Retrieval Schemes.

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Adaptive Packet Routing for Bursty Adversarial Traffic.

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Computation in Noisy Radio Networks.

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Amortizing Randomness in Private Multiparty Computations.

Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

Improved Cryptanalysis of RC5.

Proceedings of the Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31, 1998

From Differential Cryptanalysis to Ciphertext-Only Attacks.

Proceedings of the Advances in Cryptology, 1998

The Query Complexity of Finding Local Minima in the Lattice.

Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997

A Simple Algorithm for Learning O (log n)-Term DNF.

Inf. Process. Lett., 1997

Protecting Data Privacy in Private Information Retrieval Schemes.

IACR Cryptology ePrint Archive, 1997

Communication Complexity.

Advances in Computers, 1997

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes.

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Randomness vs. Fault-Tolerance.

Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, 1997

Private Simultaneous Messages Protocols with Applications.

Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval.

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Learning Boxes in High Dimension.

Proceedings of the Computational Learning Theory, Third European Conference, 1997

Communication complexity.

Cambridge University Press, ISBN: 978-0-521-56067-2, 1997

1996

Witness Sets for Families of Binary Vectors.

J. Comb. Theory, Ser. A, 1996

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

Electronic Colloquium on Computational Complexity (ECCC), 1996

Characterizing Linear Size Circuits in Terms of Privacy.

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

The Linear-Array Conjecture in Communication Complexity is False.

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Randomness in Private Computations.

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

On the Applications of Multiplicity Automata in Learning.

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

A Simple Algorithm for Learning O(log n)-Term DNF.

Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996

1995

Learning by Distances

Inf. Comput., March, 1995

On Lotteries with Unique Winners.

SIAM J. Discrete Math., 1995

Amortized Communication Complexity.

SIAM J. Comput., 1995

Private Computations over the Integers.

SIAM J. Comput., 1995

Log-space polynomial end-to-end communication.

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Log-Space Polynomial End-to-End Communication (Abstract).

Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

Private Information Retrieval.

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Online learning versus offline learning.

Proceedings of the Computational Learning Theory, Second European Conference, 1995

On Self-Directed Learning.

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

On the Structure of the Privacy Hierarchy.

J. Cryptology, 1994

Reducibility and Completeness in Multi-Party Private Computations

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

A Randomnesss-Rounds Tradeoff in Private Computation.

Proceedings of the Advances in Cryptology, 1994

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

On Ultrafilters and NP.

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Privacy, additional information and communication.

IEEE Trans. Information Theory, 1993

Learning Decision Trees Using the Fourier Spectrum.

SIAM J. Comput., 1993

A Perfect Zero-Knowledge Proof System for a Problem Equivalent to the Discrete Logarithm.

J. Cryptology, 1993

Secret Sharing Over Infinite Domains.

J. Cryptology, 1993

A Communication-Privacy Tradeoff for Modular Addition.

Inf. Process. Lett., 1993

Lower bounds for randomized mutual exclusion.

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

An Omega(D log(N/D)) Lower Bound for Broadcast in Radio Networks.

Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, 1993

On Learning Visual Concepts and DNF Formulae.

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992

Privacy and Communication Complexity.

SIAM J. Discrete Math., 1992

Randomized Mutual Exclusion Algorithms Revisited.

Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992

Fractional Covers and Communication Complexity.

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

A Zero-One Law for Boolean Privacy.

SIAM J. Discrete Math., 1991

Learning Decision Trees Using the Fourier Sprectrum (Extended Abstract)

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Amortized Communication Complexity (Preliminary Version)

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Private Computations Over the Integers (Extended Abstract)

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Learning by Distances.

Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

Privacy, Additional Information, and Communication.

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

A Zero-One Law for Boolean Privacy (extended abstract)

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Privacy and Communication Complexity

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Secret Sharing Over Infinite Domains (Extended Abstract).

Proceedings of the Advances in Cryptology, 1989

1988

A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm.

Proceedings of the Advances in Cryptology, 1988