Rafail Ostrovsky

According to our database1, Rafail Ostrovsky authored at least 314 papers between 1986 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

IEEE Fellow

IEEE Fellow 2017, "For contributions to cryptography".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Efficient Error-Correcting Codes for Sliding Windows.
SIAM J. Discret. Math., 2020

Oblivious Sampling with Applications to Two-Party k-Means Clustering.
J. Cryptology, 2020

A PoR/PoS-Hybrid Blockchain: Proof of Reputation with Nakamoto Fallback.
IACR Cryptol. ePrint Arch., 2020

Secure merge with O(n log log n) secure operation.
IACR Cryptol. ePrint Arch., 2020

Communication-Efficient (Proactive) Secure Computation for Dynamic General Adversary Structures and Dynamic Groups.
IACR Cryptol. ePrint Arch., 2020

Oblivious tight compaction in O(n) time with smaller constant.
IACR Cryptol. ePrint Arch., 2020

Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era.
Proceedings of the Advances in Cryptology - EUROCRYPT 2020, 2020

2019
Cryptographic Sensing.
IACR Cryptol. ePrint Arch., 2019

Efficient Range-Trapdoor Functions and Applications: Rate-1 OT and More.
IACR Cryptol. ePrint Arch., 2019

Resource-Restricted Cryptography: Honest-Majority MPC from a CRS (and No Broadcast).
IACR Cryptol. ePrint Arch., 2019

Trapdoor Hash Functions and Their Applications.
IACR Cryptol. ePrint Arch., 2019

Four-Round Secure Multiparty Computation from General Assumptions.
IACR Cryptol. ePrint Arch., 2019

On Round Optimal Secure Multiparty Computation from Minimal Assumptions.
IACR Cryptol. ePrint Arch., 2019

A stable marriage requires communication.
Games Econ. Behav., 2019

DURASIFT: A Robust, Decentralized, Encrypted Database Supporting Private Searches with Complex Policy Controls.
Proceedings of the 18th ACM Workshop on Privacy in the Electronic Society, 2019

Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND.
Proceedings of the Theory of Cryptography - 17th International Conference, 2019

Universally Composable Secure Computation with Corrupted Tokens.
Proceedings of the Advances in Cryptology - CRYPTO 2019, 2019

UC-Secure Multiparty Computation from One-Way Functions Using Stateless Tokens.
Proceedings of the Advances in Cryptology - ASIACRYPT 2019, 2019

2018
Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions.
IACR Cryptol. ePrint Arch., 2018

Round Optimal Black-Box “Commit-and-Prove”.
IACR Cryptol. ePrint Arch., 2018

On the Message Complexity of Secure Multiparty Computation.
IACR Cryptol. ePrint Arch., 2018

Private Anonymous Data Access.
IACR Cryptol. ePrint Arch., 2018

Adaptive Garbled RAM from Laconic Oblivious Transfer.
IACR Cryptol. ePrint Arch., 2018

Private Set Intersection with Linear Communication from General Assumptions.
IACR Cryptol. ePrint Arch., 2018

Information-Theoretic Broadcast with Dishonest Majority for Long Messages.
IACR Cryptol. ePrint Arch., 2018

Reusable Non-Interactive Secure Computation.
IACR Cryptol. ePrint Arch., 2018

Efficient 3-Party Distributed ORAM.
IACR Cryptol. ePrint Arch., 2018

Non-Interactive Secure Computation from One-Way Functions.
IACR Cryptol. ePrint Arch., 2018

Efficient robust secret sharing from expander graphs.
Cryptogr. Commun., 2018

Proactive Secure Multiparty Computation with a Dishonest Majority.
Proceedings of the Security and Cryptography for Networks - 11th International Conference, 2018

Population Stability: Regulating Size in the Presence of an Adversary.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Cryptographically Secure Detection of Injection Attacks.
Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018

ETERNAL: Encrypted Transmission With an Error-correcting, Real-time, Noise-resilient Apparatus on Lightweight Devices.
Proceedings of the 2nd International Workshop on Multimedia Privacy and Security, 2018

Theoretical Foundations for Mobile Target Defense: Proactive Secret Sharing and Secure Multiparty Computation.
Proceedings of the From Database to Cyber Security, 2018

2017
A Randomized Online Quantile Summary in O((1/ε) log(1/ε)) Words.
Theory Comput., 2017

Coding for Interactive Communication Correcting Insertions and Deletions.
IEEE Trans. Inf. Theory, 2017

The Price of Low Communication in Secure Multi-Party Computation.
IACR Cryptol. ePrint Arch., 2017

Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds.
IACR Cryptol. ePrint Arch., 2017

Round-Optimal Secure Two-Party Computation from Trapdoor Permutations.
IACR Cryptol. ePrint Arch., 2017

Resettably-Sound Resettable Zero Knowledge in Constant Rounds.
IACR Cryptol. ePrint Arch., 2017

Circuit-Private Multi-Key FHE.
IACR Cryptol. ePrint Arch., 2017

Universally Composable Secure Two and Multi-party Computation in the Corruptible Tamper-Proof Hardware Token Model.
IACR Cryptol. ePrint Arch., 2017

Special Issue: Algorithmic Tools in Cryptography.
Algorithmica, 2017

Matrix Balancing in <i>L</i><sub>p</sub> Norms: Bounding the Convergence Rate of Osborne's Iteration.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Space-Time Tradeoffs for Distributed Verification.
Proceedings of the Structural Information and Communication Complexity, 2017

Brief Announcement: Secure Self-Stabilizing Computation.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs.
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

Four-Round Concurrent Non-Malleable Commitments from One-Way Functions.
Proceedings of the Advances in Cryptology - CRYPTO 2017, 2017

2016
On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols.
SIAM J. Discret. Math., 2016

High-precision Secure Computation of Satellite Collision Probabilities.
IACR Cryptol. ePrint Arch., 2016

On Round-Efficient Non-Malleable Protocols.
IACR Cryptol. ePrint Arch., 2016

Concurrent Non-Malleable Commitments (and More) in 3 Rounds.
IACR Cryptol. ePrint Arch., 2016

New Feasibility Results in Unconditional UC-Secure Computation with (Malicious) PUFs.
IACR Cryptol. ePrint Arch., 2016

Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration.
CoRR, 2016

Adaptive Security with Quasi-Optimal Rate.
Proceedings of the Theory of Cryptography - 13th International Conference, 2016

Proactive Secret Sharing with a Dishonest Majority.
Proceedings of the Security and Cryptography for Networks - 10th International Conference, 2016

Variability in Data Streams.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Brief Announcement: Space-Time Tradeoffs for Distributed Verification.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Provably Secure Virus Detection: Using The Observer Effect Against Malware.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Unconditionally Secure Computation with Reduced Interaction.
Proceedings of the Advances in Cryptology - EUROCRYPT 2016, 2016

2015
Almost-Everywhere Secure Computation with Edge Corruptions.
J. Cryptology, 2015

Weighted sampling without replacement from data streams.
Inf. Process. Lett., 2015

Local correctability of expander codes.
Inf. Comput., 2015

Round-Optimal Black-Box Two-Party Computation.
IACR Cryptol. ePrint Arch., 2015

Black-Box Parallel Garbled RAM.
IACR Cryptol. ePrint Arch., 2015

Provable Virus Detection: Using the Uncertainty Principle to Protect Against Malware.
IACR Cryptol. ePrint Arch., 2015

Private Large-Scale Databases with Distributed Searchable Symmetric Encryption.
IACR Cryptol. ePrint Arch., 2015

Secure Multi-Party Computation with Identifiable Abort.
IACR Cryptol. ePrint Arch., 2015

Non-committing encryption from Φ-hiding.
IACR Cryptol. ePrint Arch., 2015

Building Lossy Trapdoor Functions from Lossy Encryption.
IACR Cryptol. ePrint Arch., 2015

Adaptively Secure Garbled Circuits from One-Way Functions.
IACR Cryptol. ePrint Arch., 2015

Communication-Optimal Proactive Secret Sharing for Dynamic Groups.
IACR Cryptol. ePrint Arch., 2015

Black-Box Garbled RAM.
Electronic Colloquium on Computational Complexity (ECCC), 2015

A randomized online quantile summary in O(1/ɛ log 1/ɛ) words.
CoRR, 2015

Resettably Sound Zero-Knowledge Arguments from OWFs - The (Semi) Black-Box Way.
Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015

Fast Distributed Almost Stable Matchings.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Executable Proofs, Input-Size Hiding Secure Computation and a New Ideal World.
Proceedings of the Advances in Cryptology - EUROCRYPT 2015, 2015

Impossibility of Black-Box Simulation Against Leakage Attacks.
Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

Incoercible Multi-party Computation and Universally Composable Receipt-Free Voting.
Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words.
Proceedings of the Approximation, 2015

Zero-One Laws for Sliding Windows and Universal Sketches.
Proceedings of the Approximation, 2015

2014
Deterministic and Energy-Optimal Wireless Synchronization.
ACM Trans. Sens. Networks, 2014

Secure Message Transmission With Small Public Discussion.
IEEE Trans. Inf. Theory, 2014

How to catch L<sub>2</sub>-heavy-hitters on sliding windows.
Theor. Comput. Sci., 2014

On linear-size pseudorandom generators and hardcore functions.
Theor. Comput. Sci., 2014

Cryptography in the Multi-string Model.
J. Cryptology, 2014

Authenticated Adversarial Routing.
J. Cryptology, 2014

Privacy amplification with asymptotically optimal entropy loss.
J. ACM, 2014

Resettably Sound Zero-Knoweldge Arguments from OWFs - the (semi) Black-Box way.
IACR Cryptol. ePrint Arch., 2014

Impossibility Results for Leakage-Resilient Zero Knowledge and Multi-Party Computation.
IACR Cryptol. ePrint Arch., 2014

Locally Decodable Codes for edit distance.
IACR Cryptol. ePrint Arch., 2014

Statistical Concurrent Non-Malleable Zero Knowledge.
IACR Cryptol. ePrint Arch., 2014

Garbled RAM Revisited, Part II.
IACR Cryptol. ePrint Arch., 2014

Black-Box Non-Black-Box Zero Knowledge.
IACR Cryptol. ePrint Arch., 2014

Garbled RAM From One-Way Functions.
IACR Cryptol. ePrint Arch., 2014

Cryptography with One-Way Communication.
IACR Cryptol. ePrint Arch., 2014

Optimally Resilient and Adaptively Secure Multi-Party Computation with Low Communication Locality.
IACR Cryptol. ePrint Arch., 2014

Improved Approximation Algorithms for Earth-Mover Distance in Data Streams.
CoRR, 2014

It's Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems.
CoRR, 2014

Fast distributed almost stable marriages.
CoRR, 2014

Universal Streaming.
CoRR, 2014

Privacy preserving protocol for detecting genetic relatives using rare variants.
Bioinform., 2014

4-Round Resettably-Sound Zero Knowledge.
Proceedings of the Theory of Cryptography - 11th Theory of Cryptography Conference, 2014

On Selective-Opening Attacks against Encryption Schemes.
Proceedings of the Security and Cryptography for Networks - 9th International Conference, 2014

Fast and unconditionally secure anonymous channel.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Cross-Domain Secure Computation.
Proceedings of the Public-Key Cryptography - PKC 2014, 2014

Achieving Privacy in Verifiable Computation with Multiple Servers - Without FHE and without Pre-processing.
Proceedings of the Public-Key Cryptography - PKC 2014, 2014

On Input Indistinguishable Proof Systems.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Garbled RAM Revisited.
Proceedings of the Advances in Cryptology - EUROCRYPT 2014, 2014

2013
Sequential Aggregate Signatures, Multisignatures, and Verifiably Encrypted Signatures Without Random Oracles.
J. Cryptology, 2013

Maliciously Circuit-private FHE.
IACR Cryptol. ePrint Arch., 2013

Communication-Efficient MPC for General Adversary Structures.
IACR Cryptol. ePrint Arch., 2013

Locally Updatable and Locally Decodable Codes.
IACR Cryptol. ePrint Arch., 2013

How to Withstand Mobile Virus Attacks, Revisited.
IACR Cryptol. ePrint Arch., 2013

Robust Pseudorandom Generators.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Secure End-to-End Communication with Optimal Throughput in Unreliable Networks
CoRR, 2013

Secure End-to-End Communication with Optimal Throughput and Resilience against Malicious Adversary.
Proceedings of the Distributed Computing - 27th International Symposium, 2013

Distributed Oblivious RAM for Secure Two-Party Computation.
Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Concurrent Zero Knowledge in the Bounded Player Model.
Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Erratum: Succinct Non-interactive Arguments via Linear Interactive Proofs.
Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Broadcast (and Round) Efficient Verifiable Secret Sharing.
Proceedings of the Information Theoretic Security - 7th International Conference, 2013

How Hard Is Counting Triangles in the Streaming Model?
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Simultaneous Resettability from One-Way Functions.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

How to Catch <i>L</i> <sub>2</sub>-Heavy-Hitters on Sliding Windows.
Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

Constant-Round Concurrent Zero Knowledge in the Bounded Player Model.
Proceedings of the Advances in Cryptology - ASIACRYPT 2013, 2013

Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Approximating Large Frequency Moments with Pick-and-Drop Sampling.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
Near-optimal radio use for wireless network synchronization.
Theor. Comput. Sci., 2012

Optimal sampling from sliding windows.
J. Comput. Syst. Sci., 2012

The effectiveness of lloyd-type methods for the k-means problem.
J. ACM, 2012

New Techniques for Noninteractive Zero-Knowledge.
J. ACM, 2012

Universally Composable Secure Computation with (Malicious) Physically Uncloneable Functions.
IACR Cryptol. ePrint Arch., 2012

How to Garble RAM Programs.
IACR Cryptol. ePrint Arch., 2012

Cryptography Using CAPTCHA Puzzles.
IACR Cryptol. ePrint Arch., 2012

Concurrent Zero Knowledge in the Bounded Player Model.
IACR Cryptol. ePrint Arch., 2012

Multiparty Proximity Testing with Dishonest Majority from Equality Testing.
IACR Cryptol. ePrint Arch., 2012

Impossibility Results for Static Input Secure Computation.
IACR Cryptol. ePrint Arch., 2012

Broadcast-Efficient Secure Multiparty Computation.
IACR Cryptol. ePrint Arch., 2012

Succinct Non-Interactive Arguments via Linear Interactive Proofs.
IACR Cryptol. ePrint Arch., 2012

5PM: Secure Pattern Matching.
IACR Cryptol. ePrint Arch., 2012

Simultaneous Resettability from Collision Resistance.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Optimal Coding for Streaming Authentication and Interactive Communication.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Identifying Cheaters without an Honest Majority.
Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012

Simultaneously Resettable Arguments of Knowledge.
Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012

Extended-DDH and Lossy Trapdoor Functions.
Proceedings of the Public Key Cryptography - PKC 2012, 2012

On Homomorphic Encryption and Chosen-Ciphertext Security.
Proceedings of the Public Key Cryptography - PKC 2012, 2012

Correlated Product Security from Any One-Way Function.
Proceedings of the Public Key Cryptography - PKC 2012, 2012

Edge Fault Tolerance on Sparse Networks.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Nearly Simultaneously Resettable Black-Box Zero Knowledge.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Constructing Non-malleable Commitments: A Black-Box Approach.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Unconditionally-Secure Robust Secret Sharing with Compact Shares.
Proceedings of the Advances in Cryptology - EUROCRYPT 2012, 2012

2011
Visual cryptography on graphs.
J. Comb. Optim., 2011

Revisiting Lower and Upper Bounds for Selective Decommitments.
IACR Cryptol. ePrint Arch., 2011

Multi-Server Oblivious RAM.
IACR Cryptol. ePrint Arch., 2011

On the (In)security of Hash-based Oblivious RAM and a New Balancing Scheme.
IACR Cryptol. ePrint Arch., 2011

Resettable Statistical Zero Knowledge.
IACR Cryptol. ePrint Arch., 2011

Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority.
IACR Cryptol. ePrint Arch., 2011

Public Key Locally Decodable Codes with Short Keys.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Streaming k-means on Well-Clusterable Data.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Secure Message Transmission by Public Discussion: A Brief Survey.
Proceedings of the Coding and Cryptology - Third International Workshop, 2011

2010
Effective Computations on Sliding Windows.
SIAM J. Comput., 2010

Homomorphic Encryption Over Cyclic Groups Implies Chosen-Ciphertext Security.
IACR Cryptol. ePrint Arch., 2010

Correlated Product Security From Any One-Way Function and the New Notion of Decisional Correlated Product Security.
IACR Cryptol. ePrint Arch., 2010

Throughput-Optimal Routing in Unreliable Networks.
IACR Cryptol. ePrint Arch., 2010

Position-Based Quantum Cryptography: Impossibility and Constructions.
IACR Cryptol. ePrint Arch., 2010

Building Injective Trapdoor Functions From Oblivious Transfer.
Electronic Colloquium on Computational Complexity (ECCC), 2010

How to Catch L_2-Heavy-Hitters on Sliding Windows
CoRR, 2010

Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
CoRR, 2010

Recursive Sketching For Frequency Moments
CoRR, 2010

Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge.
Proceedings of the Theory of Cryptography, 7th Theory of Cryptography Conference, 2010

On Complete Primitives for Fairness.
Proceedings of the Theory of Cryptography, 7th Theory of Cryptography Conference, 2010

Zero-one frequency laws.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Measuring independence of datasets.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

AMS Without 4-Wise Independence on Product Domains.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Improved Fault Tolerance and Secure Computation on Sparse Networks.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Asynchronous Throughput-Optimal Routing in Malicious Networks.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Password-Authenticated Session-Key Generation on the Internet in the Plain Model.
Proceedings of the Advances in Cryptology, 2010

2009
Error-correcting codes for automatic control.
IEEE Trans. Inf. Theory, 2009

Zero-Knowledge Proofs from Secure Multiparty Computation.
SIAM J. Comput., 2009

Efficient and secure authenticated key exchange using weak passwords.
J. ACM, 2009

Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security.
IACR Cryptol. ePrint Arch., 2009

Position Based Cryptography.
IACR Cryptol. ePrint Arch., 2009

Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Equivalence of Uniform Key Agreement and Composition Insecurity.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Throughput in Asynchronous Networks
CoRR, 2009

Simulation-Based Concurrent Non-malleable Commitments and Decommitments.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

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

2008
Improved algorithms for optimal embeddings.
ACM Trans. Algorithms, 2008

Constant-Round Concurrent Non-Malleable Commitments and Decommitments.
IACR Cryptol. ePrint Arch., 2008

Public-Key Encryption with Efficient Amortized Updates.
IACR Cryptol. ePrint Arch., 2008

Optimal-Rate Coding Theorem For Adversarial Networks in the Public-Key Setting
CoRR, 2008

Measuring $k$-Wise Independence of Streaming Data
CoRR, 2008

Cryptography with constant computational overhead.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Communication Complexity in Algebraic Two-Party Protocols.
Proceedings of the Advances in Cryptology, 2008

Public-Key Locally-Decodable Codes.
Proceedings of the Advances in Cryptology, 2008

Circular-Secure Encryption from Decision Diffie-Hellman.
Proceedings of the Advances in Cryptology, 2008

2007
Private Searching on Streaming Data.
J. Cryptology, 2007

Low distortion embeddings for edit distance.
J. ACM, 2007

Attribute-Based Encryption with Non-Monotonic Access Structures.
IACR Cryptol. ePrint Arch., 2007

A Survey of Single Database PIR: Techniques and Applications.
IACR Cryptol. ePrint Arch., 2007

Private Locally Decodable Codes.
IACR Cryptol. ePrint Arch., 2007

Almost-everywhere Secure Computation.
IACR Cryptol. ePrint Arch., 2007

Secure Two-Party k-Means Clustering.
IACR Cryptol. ePrint Arch., 2007

Public Key Encryption that Allows PIR Queries.
IACR Cryptol. ePrint Arch., 2007

Algebraic Lower Bounds for Computing on Encrypted Data.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Succinct Sampling on Streams
CoRR, 2007

Zero-knowledge from secure multiparty computation.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A Survey of Single-Database Private Information Retrieval: Techniques and Applications.
Proceedings of the Public Key Cryptography, 2007

Round Complexity of Authenticated Broadcast with a Dishonest Majority.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Covert Multi-Party Computation.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Smooth Histograms for Sliding Windows.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Efficient Arguments without Short PCPs.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
Math. Oper. Res., 2006

Constant-Round Concurrent NMWI and its relation to NMZK.
IACR Cryptol. ePrint Arch., 2006

Sequential Aggregate Signatures and Multisignatures without Random Oracles.
IACR Cryptol. ePrint Arch., 2006

Cryptography from Anonymity.
IACR Cryptol. ePrint Arch., 2006

Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions.
IACR Cryptol. ePrint Arch., 2006

Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions.
IACR Cryptol. ePrint Arch., 2006

Concurrent Non-Malleable Witness Indistinguishability and its Applications.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Improved Algorithms for Optimal Embeddings.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Non-interactive Zaps and New Techniques for NIZK.
Proceedings of the Advances in Cryptology, 2006

2005
Minimal Complete Primitives for Secure Multi-Party Computation.
J. Cryptology, 2005

Perfect Non-Interactive Zero Knowledge for NP
Electronic Colloquium on Computational Complexity (ECCC), 2005

Sufficient Conditions for Collision-Resistant Hashing.
Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

Secure Remote Authentication Using Biometric Data.
Proceedings of the Advances in Cryptology, 2005

05411 Abstracts Collection -- Anonymous Communication and its Applications.
Proceedings of the Anonymous Communication and its Applications, 09.10. - 14.10.2005, 2005

2004
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
Mach. Learn., 2004

Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds.
J. Interconnect. Networks, 2004

Efficient Consistency Proofs for Generalized Queries on a Committed Database.
IACR Cryptol. ePrint Arch., 2004

Batch codes and their applications.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Identity-Based Zero Knowledge.
Proceedings of the Security in Communication Networks, 4th International Conference, 2004

Round-Optimal Secure Two-Party Computation.
Proceedings of the Advances in Cryptology, 2004

2003
Amortizing Randomness in Private Multiparty Computations.
SIAM J. Discret. Math., 2003

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.
IACR Cryptol. ePrint Arch., 2003

Public Key Encryption with keyword Search.
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

Round Efficiency of Multi-party Computation with a Dishonest Majority.
Proceedings of the Advances in Cryptology, 2003

2002
Self-Stabilizing Symmetry Breaking in Constant Space.
SIAM J. Comput., 2002

Polynomial-time approximation schemes for geometric min-sum median clustering.
J. ACM, 2002

Universally Composable Two-Party and Multi-Party Secure Computation.
IACR Cryptol. ePrint Arch., 2002

Forward Secrecy in Password-Only Key Exchange Protocols.
Proceedings of the Security in Communication Networks, Third International Conference, 2002

2001
Universal Service-Providers for Private Information Retrieval.
J. Cryptology, 2001

Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords.
IACR Cryptol. ePrint Arch., 2001

Efficient and Non-Interactive Non-Malleable Commitment.
IACR Cryptol. ePrint Arch., 2001

Cryptographic Counters and Applications to Electronic Voting.
Proceedings of the Advances in Cryptology, 2001

Robust Non-interactive Zero Knowledge.
Proceedings of the Advances in Cryptology, 2001

2000
Xor-trees for efficient anonymous multicast and reception.
ACM Trans. Inf. Syst. Secur., 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. Cryptology, 2000

Adaptive Packet Routing for Bursty Adversarial Traffic.
J. Comput. Syst. Sci., 2000

The Las-Vegas Processor Identity Problem (How and When to Be Unique).
J. Algorithms, 2000

Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Polynomial Time Approximation Schemes for Geometric k-Clustering.
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

Single Database Private Information Retrieval Implies Oblivious Transfer.
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

Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Optimal and Efficient Clock Synchronization Under Drifting Clocks.
Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, 1999

Conditional Oblivious Transfer and Timed-Release Encryption.
Proceedings of the Advances in Cryptology, 1999

On Concurrent Zero-Knowledge with Pre-processing.
Proceedings of the Advances in Cryptology, 1999

1998
Log-Space Polynomial End-to-End Communication.
SIAM J. Comput., 1998

Perfect Zero-Knowledge Arguments for <i>NP</i> Using Any One-Way Permutation.
J. Cryptology, 1998

Universal Service Providers for Database Private Information Retrieval.
IACR Cryptol. ePrint Arch., 1998

Non-Interactive and Non-Malleable Commitment.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Universal Service-Providers for Database Private Information Retrieval (Extended Abstract).
Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

Micropayments via Efficient Coin-Flipping.
Proceedings of the Financial Cryptography, 1998

Fast Digital Identity Revocation (Extended Abstract).
Proceedings of the Advances in Cryptology, 1998

1997
Private Information Storage (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Universal <i>O</i>(Congestion + Dilation + log<sup>1+epsilon</sup><i>N</i>) Local Control Packet Switching Algorithms.
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

Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Security of Blind Digital Signatures (Extended Abstract).
Proceedings of the Advances in Cryptology, 1997

Efficient Anonymous Multicast and Reception (Extended Abstract).
Proceedings of the Advances in Cryptology, 1997

1996
Software Protection and Simulation on Oblivious RAMs.
J. ACM, 1996

Private Information Storage.
IACR Cryptol. ePrint Arch., 1996

Deniable Encryption.
IACR Cryptol. ePrint Arch., 1996

Characterizing Linear Size Circuits in Terms of Privacy.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Self-Stabilizing Algorithms for Synchronous Unidirectional Rings.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995
Faster Computation On Directed Networks of Automata (Extended Abstract).
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

Log-Space Polynomial End-to-End Communication (Abstract).
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

1994
Computational Complexity and Knowledge Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1994

Simple and efficient leader election in the full information model.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Computational complexity and knowledge complexity (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Matching Nuts and Bolts.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Memory-Efficient and Self-Stabilizing Network {RESET} (Extended Abstract).
Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

Reducibility and Completeness in Multi-Party Private Computations
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Interactive Hashing Simplifies Zero-Knowledge Protocol Design.
Proceedings of the Advances in Cryptology, 1993

1992
Software protection and simulation on oblivious RAMs.
PhD thesis, 1992

Self-Stabilizing Symmetry Breaking in Constant-Space (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Secure Commitment Against A Powerful Adversary.
Proceedings of the STACS 92, 1992

Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions (Extended Abstract).
Proceedings of the Advances in Cryptology, 1992

Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract).
Proceedings of the Advances in Cryptology, 1992

1991
How to Withstand Mobile Virus Attacks (Extended Abstract).
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991

A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems.
Proceedings of the Advances in Cryptology, 1991

1990
Efficient Computation on Oblivious RAMs
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

The (True) Complexity of Statistical Zero Knowledge
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Perfect Zero-Knowledge in Constant Rounds
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Fair Games against an All-Powerful Adversary.
Proceedings of the Advances In Computational Complexity Theory, 1990

1989
Minimum Resource Zero-Knowledge Proofs (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

On Necessary Conditions for Secure Distributed Computation.
Proceedings of the Distributed Computing And Cryptography, 1989

An Efficient Software Protection Scheme.
Proceedings of the Advances in Cryptology, 1989

1986
HOLMES-I, a prolog-based reason maintenance system for collecting information from multiple experts.
Proceedings of the Uncertainty in Knowledge-Based Systems, 1986


  Loading...