2023
Additive Randomized Encodings and Their Applications.
IACR Cryptol. ePrint Arch., 2023
Hard Languages in $\mathsf{NP} \cap \mathsf{coNP}$ and NIZK Proofs from Unstructured Hardness.
IACR Cryptol. ePrint Arch., 2023
Perfect MPC over Layered Graphs.
IACR Cryptol. ePrint Arch., 2023
Cryptography from Planted Graphs: Security with Logarithmic-Size Messages.
IACR Cryptol. ePrint Arch., 2023
Hard Languages in $\text{NP}\cap\text{coNP}$ and NIZK Proofs from Unstructured Hardness.
Electron. Colloquium Comput. Complex., 2023
Succinct Computational Secret Sharing.
Electron. Colloquium Comput. Complex., 2023
Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Perfect MPC over Layered Graphs.
Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023
2022
Random-Index Oblivious RAM.
IACR Cryptol. ePrint Arch., 2022
Anonymous Permutation Routing.
IACR Cryptol. ePrint Arch., 2022
2021
Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND.
SIAM J. Discret. Math., 2021
Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning.
Proc. Priv. Enhancing Technol., 2021
CNF-FSS and its Applications.
IACR Cryptol. ePrint Arch., 2021
Secure Computation from One-Way Noisy Communication, or: Anti-correlation via Anti-concentration.
Proceedings of the Advances in Cryptology - CRYPTO 2021, 2021
2020
Cryptography from One-Way Communication: On Completeness of Finite Channels.
Proceedings of the Advances in Cryptology - ASIACRYPT 2020, 2020
2019
Sub-logarithmic Distributed Oblivious RAM with Small Block Size.
IACR Cryptol. ePrint Arch., 2019
IACR Cryptol. ePrint Arch., 2019
On Fully Secure MPC with Solitary Output.
IACR Cryptol. ePrint Arch., 2019
2018
Best Possible Information-Theoretic MPC.
IACR Cryptol. ePrint Arch., 2018
Efficient 3-Party Distributed ORAM.
IACR Cryptol. ePrint Arch., 2018
The Complexity of Multiparty PSM Protocols and Related Models.
IACR Cryptol. ePrint Arch., 2018
2017
Ad Hoc PSM Protocols: Secure Computation Without Coordination.
IACR Cryptol. ePrint Arch., 2017
Low-Complexity Cryptographic Hash Functions.
Electron. Colloquium Comput. Complex., 2017
Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity.
Proceedings of the 31st International Symposium on Distributed Computing, 2017
2016
Secure Protocol Transformations.
IACR Cryptol. ePrint Arch., 2016
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016
2015
Encoding Functions with Constant Online Rate, or How to Compress Garbled Circuit Keys.
SIAM J. Comput., 2015
Private Large-Scale Databases with Distributed Searchable Symmetric Encryption.
IACR Cryptol. ePrint Arch., 2015
Secure Multiparty Computation with General Interaction Patterns.
IACR Cryptol. ePrint Arch., 2015
Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings.
Electron. Colloquium Comput. Complex., 2015
Secure Computation with Minimal Interaction, Revisited.
Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015
2014
How to Garble Arithmetic Circuits.
SIAM J. Comput., 2014
Cryptography with One-Way Communication.
IACR Cryptol. ePrint Arch., 2014
Non-Interactive Secure Multiparty Computation.
IACR Cryptol. ePrint Arch., 2014
On the Power of Multiplexing in Number-on-the-Forehead Protocols.
CoRR, 2014
Choosing, Agreeing, and Eliminating in Communication Complexity.
Comput. Complex., 2014
On the Cryptographic Complexity of the Worst Functions.
Proceedings of the Theory of Cryptography - 11th Theory of Cryptography Conference, 2014
2013
Guest Editorial: In-Network Computation: Exploring the Fundamental Limits.
IEEE J. Sel. Areas Commun., 2013
Lossy Chains and Fractional Secret Sharing.
IACR Cryptol. ePrint Arch., 2013
Robust Pseudorandom Generators.
Electron. Colloquium Comput. Complex., 2013
On the Power of Correlated Randomness in Secure Computation.
Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 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 Cryptol. ePrint Arch., 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
Partition arguments in multiparty communication complexity.
Theor. Comput. Sci., 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
On the (In)security of Hash-based Oblivious RAM and a New Balancing Scheme.
IACR Cryptol. ePrint Arch., 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
Information-Theoretically Secure Protocols and Security under Composition.
SIAM J. Comput., 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
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
Cryptography with Constant Input Locality.
J. Cryptol., 2009
On the complexity of communication complexity.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 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
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008
Testing monotonicity over graph products.
Random Struct. Algorithms, 2008
On Pseudorandom Generators with Linear Stretch in NC<sup>0</sup>.
Comput. Complex., 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
Distribution-Free Property-Testing.
SIAM J. Comput., 2007
Public Key Encryption that Allows PIR Queries.
IACR Cryptol. ePrint Arch., 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
Efficient Arguments without Short PCPs.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007
2006
Cryptography in NC<sup>0</sup>.
SIAM J. Comput., 2006
On the Limitations of Universally Composable Two-Party Computation Without Set-Up Assumptions.
J. Cryptol., 2006
Cryptography from Anonymity.
IACR Cryptol. ePrint Arch., 2006
Computationally Private Randomizing Polynomials and Their Applications.
Comput. Complex., 2006
Black-box constructions for secure computation.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
On Combining Privacy with Guaranteed Output Delivery in Secure Multiparty Computation.
Proceedings of the Advances in Cryptology, 2006
2005
Computation in Noisy Radio Networks.
SIAM J. Discret. Math., 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
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
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
Amortizing Randomness in Private Multiparty Computations.
SIAM J. Discret. Math., 2003
Efficient Multi-Party Computation over Rings.
IACR Cryptol. ePrint Arch., 2003
Dynamic routing on networks with fixed-size buffers.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003
2002
PAC learning with nasty noise.
Theor. Comput. Sci., 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
The Query Complexity of Finding Local Minima in the Lattice.
Inf. Comput., 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. Discret. Math., 2000
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.
SIAM J. Comput., 2000
Reducibility and Completeness in Private Computations.
SIAM J. Comput., 2000
Randomness versus Fault-Tolerance.
J. Cryptol., 2000
Protecting Data Privacy in Private Information Retrieval Schemes.
J. Comput. Syst. Sci., 2000
Adaptive Packet Routing for Bursty Adversarial Traffic.
J. Comput. Syst. Sci., 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
The Linear-Array Conjecture in Communication Complexity Is False.
Comb., 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
1998
A Randomness-Rounds Tradeoff in Private Computation.
SIAM J. Discret. Math., 1998
Log-Space Polynomial End-to-End Communication.
SIAM J. Comput., 1998
Lower Bounds for Randomized Mutual Exclusion.
SIAM J. Comput., 1998
An Omega(<i>D</i> log (<i>N/D</i>)) Lower Bound for Broadcast in Radio Networks.
SIAM J. Comput., 1998
On Learning Read-k-Satisfy-j DNF.
SIAM J. Comput., 1998
Private Information Retrieval.
J. ACM, 1998
Learning Boxes in High Dimension.
Algorithmica, 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
1997
Randomness in Private Computations.
SIAM J. Discret. Math., 1997
Online Learning versus Offline Learning.
Mach. Learn., 1997
A Simple Algorithm for Learning O (log n)-Term DNF.
Inf. Process. Lett., 1997
Protecting Data Privacy in Private Information Retrieval Schemes.
IACR Cryptol. ePrint Arch., 1997
Communication Complexity.
Adv. Comput., 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
Communication complexity.
Cambridge University Press, ISBN: 978-0-521-56067-2, 1997
1996
On Learning Visual Concepts and DNF Formulae.
Mach. Learn., 1996
Witness Sets for Families of Binary Vectors.
J. Comb. Theory A, 1996
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes
Electron. Colloquium Comput. Complex., 1996
Characterizing Linear Size Circuits in Terms of Privacy.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996
On the Applications of Multiplicity Automata in Learning.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
1995
Inf. Comput., March, 1995
On Lotteries with Unique Winners.
SIAM J. Discret. Math., 1995
Fractional Covers and Communication Complexity.
SIAM J. Discret. 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 (Abstract).
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 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. Cryptol., 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
On Learning Read-<i>k</i>-Satisfy-<i>j</i> DNF.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994
1993
Privacy, additional information and communication.
IEEE Trans. Inf. 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. Cryptol., 1993
Secret Sharing Over Infinite Domains.
J. Cryptol., 1993
A Communication-Privacy Tradeoff for Modular Addition.
Inf. Process. Lett., 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
1992
Privacy and Communication Complexity.
SIAM J. Discret. Math., 1992
Randomized Mutual Exclusion Algorithms Revisited.
Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992
1991
A Zero-One Law for Boolean Privacy.
SIAM J. Discret. 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
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
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