Rafail Ostrovsky Publications (In Chronological Order)

Rafail Ostrovsky Publications
(In Chronological Order)

For additional information, especially regarding journal publications, see DBLP or Google scholar.
You can also search my Publications by Topic.
Color-coding:

Security and cryptography

Algorithms

2013

2012

Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky, Ivan Visconti: Impossibility Results for Static Input Secure Computation.
[Abstract] [postscript] [pdf]
CRYPTO 2012: 424-442
Eli Ben-Sasson, Serge Fehr, Rafail Ostrovsky: Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority.
[Abstract] [postscript] [pdf]
CRYPTO 2012: 663-680
Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani: Unconditionally-Secure Robust Secret Sharing with Compact Shares.
[Abstract] [postscript] [pdf]
EUROCRYPT 2012: 195-208
Joshua Baron, Rafail Ostrovsky, Ivan Visconti: Nearly Simultaneously Resettabe Black-Box Zero Knowledge.
[Abstract] [postscript] [pdf]
ICALP 2012: 88-99
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky: Edge Fault Tolerance on Sparse Networks.
[Abstract] [postscript] [pdf]
ICALP 2012: 452-463
Ran Gelles, Rafail Ostrovsky, Kina Winoto: Multiparty Proximity Testing with Dishonest Majority from Equality Testing.
[Abstract] [postscript] [pdf]
ICALP 2012: 537-548
Brett Hemenway, Rafail Ostovsky: On Homomorphic Encryption and Chosen-Ciphertext Security.
[Abstract] [postscript] [pdf]
Public Key Crypotgraphy 2012: 52-65
Brett Hemenway, Steve Lu, Rafail Ostrovsky: Correlated Product Security from Any One-Way Function.
[Abstract] [postscript] [pdf]
Public Key Cryptography 2012: 558-575
Brett Hemenway, Rafail Ostovsky: Extended-DDH and Lossy Trapdoor Functions.
[Abstract] [postscript] [pdf]
Public Key Crypotgraphy 2012: 627-643
Joshua Baron, Karim El Defawy, Kirill Minkovich, Rafail Ostrovsky, Eric Tressler: 5PM: Secure Pattern Matching.
[Abstract] [postscript] [pdf]
SCN 2012: 222-240
Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky: On the (In)security of Hash-Based Oblivious RAM and a New Balancing Scheme.
[Abstract] [postscript] [pdf]
SODA 2012: 143-156
Yuval Ishai, Rafail Otrovsky, Hakan Seyalioglu: Identifying Cheaters without an Honest Majority.
[Abstract] [postscript] [pdf]
TCC 2011: 21-38
Sanjam Garg, Rafail Ostrovsky, Ivan Visconti, Akshay Wadia: Resettable Statistical Zero Knowledge.
[Abstract] [postscript] [pdf]
TCC 2012: 494-511
Chongwon Cho, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti: Simultaneously Resettable Arguments of Knowledge.
[Abstract] [postscript] [pdf]
TCC 2012: 530-547
Milan Bradonjic, Eddie Kohler, Rafail Ostrovsky: Near-optimal Radio Use for Wireless Network Synchronization.
[Abstract] [postscript] [pdf]
TCS 2012: 453:14-28

2011

Bret Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wooters: Public Key Locally Decodable Codes with Short Keys.
[Abstract] [postscript] [pdf]
APPROX-RANDOM 2011: 605-615
Brett Hemenway, Benoit Libert, Rafail Ostrovsky, Damien Vergnaud: Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security.
[Abstract] [postscript] [pdf]
ASIACRYPT 2011: 70-88
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schafner: Position-Based Quantum Cryptography: Impossibility and Constructions.
[Abstract] [postscript] [pdf]
CRYPTO 2011: 429--446
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, Jurg Wullschleger: Constant-Rate Oblivious Transfer from Noisy Channels.
[Abstract] [postscript] [pdf]
CRYPTO 2011: 667-684
Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky: Deterministic and Energy-Optimal Wireless Synchronization.
[Abstract] [postscript] [pdf]
DISC 2011: 237-251
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai: Efficient Non-interactive Secure Computation.
[Abstract] [postscript] [pdf]
EUROCRYPT 2011: 406-425
Juan A. Garay, Clint Givens, Rafail Ostovsky: Secure Message Transmission by Public Discussion: A Brief Survey.
[Abstract] [postscript] [pdf]
IWCC 2011: 126-141
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku: Streaming k-means on Well-Clusterable Data.
[Abstract] [postscript] [pdf]
SODA 2011: 26-40

2010

Vipul Goyal, Abhishek Jan, Rafail Ostrovsky: Passward-Authenticated Session-Key Generation on the Internet in Plain Model.
[Abstract] [postscript] [pdf]
CRYPTO 2010: 277-294
Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky: Equivalence of Uniform Key Agreement and Composition Insecurity.
[Abstract] [postscript] [pdf]
CRYPTO 2010: 447-464
Juan A. Garay, Clint Givens, Rafail Ostrovsky: Secure Message Transmission with Small Public Discusssion.
[Abstract] [postscript] [pdf]
EUROCRYPT 2010: 177-196
Nishanth Chandran, Rafail Ostrovsky, Willim E. Skeith III: Encryption with Efficient Amortized Updates.
[Abstract] [postscript] [pdf]
SCN 2010: 17-35
Paul Bunn, Rafail Ostrovsky: Asynchronous Throughput-Optimal Routing in Malicious Networks.
[Abstract] [postscript] [pdf]
ICALP 2010: 236-248
Nashanth Chandran, Jual A. Garay, Rafail Ostrovsky: Improved Fault Tolerance and Secure Computation on Sparse Networks.
[Abstract] [postscript] [pdf]
ICALP 2010: 249-260
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin: Privacy Amplification with Asymptotically Optimal Entropy Loss
[Abstract] [postscript] [pdf]
Preliminary version in STOC 2010.
Vladimir Braverman, Rafail Ostrovsky: Measuring Independence of Datasets.
[Abstract] [postscript] [pdf]
Preliminary version in STOC 2010.
Vladimir Braverman, Rafail Ostrovsky: Zero-One Frequency Laws.
[Abstract] [postscript] [pdf]
Preliminary version in STOC 2010.
Rafail Ostrovsky, Omkant Pandey, Ivan Visconti: Efficiency Preserving Transformations for Concurrent Non-Malleable Zero Knowledge
[Abstract] [postscript] [pdf]
Preliminary version in TCC 2010
Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, Amit Sahai: On Complete Primitives for Fairness
[Abstract] [postscript] [pdf]
Preliminary version in TCC 2010
Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, Rafail Ostrovsky: AMS Without 4-Wise Independence on Product Domains
[Abstract] [postscript] [pdf]
STACS-2010
(This paper is the result of a merge. For historical reasons, and for slightly different proofs, see:
Vladimir Braverman, Rafail Ostrovsky AMS Without 4-Wise Independence on Product Domains, September 17, 2009.); and
Vladimir Braverman, Rafail Ostrovsky Meassuring k-Wise Indepedence of Streaming Data, June 29, 2008

2009

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Extracting Corrolations
[Abstract] [postscript] [pdf]
Preliminary version in FOCS 2009
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky: Postion Based Cryptography.
[Abstract] [postscript] [pdf]
CRYPTO-2009. (In addition, you can get [ppt].)
Milan Bradonjic, Eddie Kohler, and Rafail Ostrovsky: Near-Optimal Radio Use For Wireless Network Synchronization
[Abstract] [postscript] [pdf]
ALGOSENSORS-2009. (In addition, you can get [talk slides].)
Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo: Optimal Sampling from Sliding Windows
[Abstract] [postscript] [pdf]
PODS-2009.
Yair Amir, Paul Bunn, Rafail Ostrovsky: Authenticated Adversarial Routing.
[Abstract] [postscript] [pdf]
TCC-2009. (In addition, you can get [ppt].)
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti: Simulation-Based Concurrent Non-Malleable Commitments and Decommitments.
[Abstract] [postscript] [pdf]
TCC-2009

2008

Dan Boneh, Shai Halevi, Michael Hamburg, Rafail Ostrovsky: Circular-Secure Encryption from Decision Diffie-Hellman.
[Abstract] [postscript] [pdf]
CRYPTO 2008: 108-125 (See an informal description of the result in CS 2008 Annual Report).
Brett Hemenway, Rafail Ostrovsky: Public-Key Locally-Decodable Codes.
[Abstract] [postscript] [pdf]
CRYPTO 2008: 126-143
Rafail Ostrovsky, William E. Skeith III: Communication Complexity in Algebraic Two-Party Protocols.
[Abstract] [postscript] [pdf]
CRYPTO 2008: 379-396
Steve Lu, Daniel Manchala, Rafail Ostrovsky: Visual Cryptography on Graphs.
[Abstract] [postscript] [pdf]
Preliminary version appeared in COCOON 2008: 225-234.
Given COCOON-08 Best Paper Award. and invited to the special issue of Journal of Combinatorial Optimization for COCOON'08.
Juan A. Garay, Rafail Ostrovsky: Almost-Everywhere Secure Computation.
[Abstract] [postscript] [pdf]
EUROCRYPT 2008: 307-323
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti: Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model.
[Abstract] [postscript] [pdf]
ICALP 2008: 548-559
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Cryptography with constant computational overhead.
[Abstract] [postscript] [pdf]
Preliminary version in STOC 2008: 433-442
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai: Improved algorithms for optimal embeddings.
[Abstract] [postscript] [pdf]
ACM Transactions on Algorithms 4(4): (2008)
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.
[Abstract] [postscript] [pdf]
SIAM J. Comput. 38(1): 97-139 (2008)

2007

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William E. Skeith III: Public Key Encryption That Allows PIR Queries.
[Abstract] [postscript] [pdf]
Preliminary version appeared in CRYPTO 2007: 50-67
Jens Groth, Rafail Ostrovsky: Cryptography in the Multi-string Model.
[Abstract] [postscript] [pdf]
Preliminary version appeared in CRYPTO 2007: 323-341
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai: Covert Multi-Party Computation.
[Abstract] [postscript] [pdf]
Preliminary version appeared in FOCS 2007: 238-248
Vladimir Braverman, Rafail Ostrovsky: Smooth Histograms for Sliding Windows.
[Abstract] [postscript] [pdf]
Preliminary version appeared in FOCS 2007: 283-293
Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky: Round Complexity of Authenticated Broadcast with a Dishonest Majority.
[Abstract] [postscript] [pdf]
Preliminary version appeared in FOCS 2007: 658-668
Rafail Ostrovsky, Omkant Pandey, Amit Sahai: Private Locally Decodable Codes.
[Abstract] [postscript] [pdf]
Preliminary version appeared in ICALP 2007: 387-398
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky: Efficient Arguments without Short PCPs.
[Abstract] [postscript] [pdf]
Preliminary version appeared in IEEE Conference on Computational Complexity 2007: 278-291 (ECCC-2007)
Rafail Ostrovsky, William Skeith: A Survey of Single-Database Private Information Retrieval: Techniques and Applications.
[Abstract] [postscript] [pdf]
Preliminary version appeared in Proceedings of the Public Key Cryptography 2007 conference, pp. 393-411. (PKC-2007). Full version appeared as a book chapter in "Homeland Security Technology Challenges From Sensing and Encrypting to Mining and Modeling", Franceschetti, Giorgio and Grossi, Marina (EDT), Artec-House publishers.
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Zero-Knowledge from Secure Multiparty Computation
[Abstract] [postscript] [pdf]
In Proceedings of the ACM 2007 Symposim on Theory of Computing (STOC-2007). Full version invited and accepted to SIAM Journal of Computing (SICOMP) special issue devoted to STOC-2007.
Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai: Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions.
[Abstract] [postscript] [pdf]
ASIACRYPT 2007: 444-459
Rafail Ostrovsky, Amit Sahai, Brent Waters: Attribute-based encryption with non-monotonic access structures.
[Abstract] [postscript] [pdf]
ACM Conference on Computer and Communications Security 2007: 195-203 (CCS-2007)
Paul Bunn, Rafail Ostrovsky: Secure two-party k-means clustering.
[Abstract] [postscript] [pdf]
ACM Conference on Computer and Communications Security 2007: 486-497 (CCS-2007)

2006

Rafail Ostrovsky, Yuval Rabani, Leonard Schulman, and Chaitanya Swamy: The Effectiveness of Lloyd-Type Methods for the k-Means Problem
[Abstract] [postscript] [pdf]
In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006).
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Cryptography from Anonymity
[Abstract] [postscript] [pdf]
In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006).
Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky: Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
[Abstract] [postscript] [pdf]
In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS 2006).
Jens Groth, Rafail Ostrovsky, Amit Sahai: Non-interactive Zaps and New Techniques for NIZK
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (CRYPTO-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, and Brent Waters: Sequential Aggregate Signatures and Multisignatures Without Random Oracles
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfect Non-Interactive Zero Knowledge for NP
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.

2005

Rafail Ostrovsky, Yuval Rabani, Leonard Schulman: Error-Correcting Codes for Automatic Control
[Abstract] [postscript] [pdf]
In Proceedings of 46th Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2005).
Rafail Ostrovsky, William Skeith.: Private Searching on Streaming Data
[Abstract] [postscript] [pdf]
Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) Springer-Verlag/IACR Lecture Notes in Computer Science. Full version appeared in Journal of Cryptology Volume 20:4, pp. 397-430, October 2007.
Rafail Ostrovsky, Yuval Rabani.: Low distortion embeddings for edit distance
[Abstract] [postscript] [pdf]
Preliminary version appeared in STOC '05. Full version in J. ACM 54(5): 2007.
Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith.: Secure Authentication Using Biometric Data
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2005) Springer-Verlag/IACR Lecture Notes in Computer Science.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky: Sufficient Conditions for Collision-Risistant Hashing
[Abstract] [postscript] [pdf].
In Proceedings of Second Theory of Cryptography Conference (TCC) Springer-Verlag Lecture Notes in Computer Science, 2005

2004

Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin: Indentity-Based Zero-Knowledge
[Abstract] [postscript] [pdf]. In addition, you can get [SCN-talk (powerpoint)].
In Proceedings of Security in Communication Networks: 4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004, Springer-Verlag Lecture Notes in Computer Science.
Jonathan Katz, Rafail Ostrovsky: Round-Optimal Secure Two-Party Computation
[Abstract] [postscript] [pdf].
In addition, can get [crypto talk (powerpoint)] or a [90min talk (powerpoint)].
In Proceedings of Advances in Cryptology, (CRYPTO-2004) Springer-Verlag/IACR Lecture Notes in Computer Science.
Rafail Ostrovsky, Charles Rackoff, Adam Smith: Efficient Consistency Proofs for Generalized Queries on a Committed Database
[Abstract] [postscript] [pdf] In addition, can get [ICALP powerpoint] talk.
In Proceedings ICALP-2004.
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Batch Codes and Their Applications
[Abstract] [postscript] [pdf] In addition, can get [powerpoint presentation].
In Proceedings of the ACM 2004 Symposim on Theory of Computing (STOC-2004).
Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Guiseppe Persiano: Public Key Encryption with Keyword Search
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2004) Springer-Verlag/IACR Lecture Notes in Computer Science.

2003

Jonathan Katz, Rafail Ostrovsky, Adam Smith: Round Efficiency of Multi-Party Computation with a Dishonest Majority
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2003) Springer-Verlag/IACR Lecture Notes in Computer Science.
William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen: Dynamic Routing on Networks with Fixed-Sized Buffers
[Abstract] [postscript] [pdf] [ SODA talk (pdf file)]
In Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA-2003)

2002

Jonathan Katz, Rafail Ostrovsky, Moti Yung: Forward Security in Password-Only Key Exchange Protocols
[Abstract] [postscript] [pdf]
In Proceedings of Security in Communication Networks 2002 conference (CSN-2002) Springer-Verlag Lecture Notes in Computer Science.
Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai: Universally composable two-party and multi-party secure computation.
[Abstract] [stoc version (postscript)] [stoc version (pdf file)] [full paper postscript] [full paper pdf]
In Proceedings of the ACM 2002 Symposim on Theory of Computing (STOC-2002), pp. 494-503.

2001

Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani.: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
[Abstract] [ preliminary (postscript)] [ full version (pdf file)]
Preliminary version in Proceedings of 42st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2001). Full version accepted to Journal of Mathematics of Operations Research.
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai: Robust Non-Interactive Zero Knowledge
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (CRYPTO-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky: Minimal Complete Primitives for Secure Multi-Party Computation
[Abstract] [postscript] [pdf]
Journal of Cryptology Springer-Verlag Volume 18, Number 1, January 2005 pp.37 - 61. Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
Jonathan Katz, Rafail Ostrovsky, Moti Yung: Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
For a non-technical discussion, see [New Scientist 2001] article regarding this work.
Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith: Efficient and Non-interactive Non-malleable Commitment
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
Jonathan Katz, Steven Myers, Rafail Ostrovsky: Cryptographic Counters and Applications to Electronic Voting.
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
Allan Borodin, Rafail Ostrovsky, Yuval Rabani.: Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds
[Abstract] [postscript] [pdf]
In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2001). Full versoin in Journal of Interconnection Networks, Vol. 5, No. 1, pp. 1-12.

2000

Rafail Ostrovsky, Yuval Rabani.: Polynomial Time Approximation Schemes for Geometric k-Clustering.
[Abstract] [postscript] [pdf] In addition, you can get a [powerpoint survey presentation].
In Proceedings of 41st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2000). Journal version in JACM 49(2): 139-156 (2002).
Eyal Kushilevitz, Rafail Ostrovsky: One-way Trapdoor Permutations Are Sufficient for Non-Trivial Single-Server Private Information Retrieval
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology (EUROCRYPT-2000) Springer-Verlag Lecture Notes in Computer Science Vol. 1807, pp. 104-121.
Giovanni Di Crescenzo, Tal Malkin, and Rafail Ostrovsky: Single Database Private Information Retrieval Implies Oblivious Transfer
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology (EUROCRYPT-2000) Springer-Verlag Lecture Notes in Computer Science Vol 1807, pp. 122-138.

1999

Giovanni Di Crescenzo and Rafail Ostrovsky: On Concurrent Zero-Knowledge with Pre-Processing
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology (CRYPT0-99), pp. 485-502, Springer-Verlag Lecture Notes in Computer Science, Vol 1666.
Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems
[Abstract] [postscript] [pdf]
Book Chapter In Discrete and Computational Geometry - The Goodman-Pollack Festschrift. Algorithms and Combinatorics Series 3143, Springer Verlag, Berlin, August 2003, pages 252-274. Preliminary version appeared in STOC '99.
Ran Canetti, Rafail Ostrovsky: Secure Computation with Honest-Looking Parties
[Abstract] [postscript] [pdf]
In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces
[Abstract] [postscript] [pdf]
In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
Journal version in Mahine Learning Journal Special Issue: Theoretical Advances in Data Clustering (Guest Editors: Nina Mishra and Rajeev Motwani) 56 (1-3): 153-167, 2004
Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan: Efficient Timed-release Public-key Encryption
[Abstract] [postscript] [pdf]
In Proceedings of EUROCRYPT-99 Springer Verlag.
Rafail Ostrovsky, Boaz Patt-Shamir: Optimal and Efficient Clock Synchronization Under Drifting Clocks
[Abstract] [postscript] [pdf]
In Proceedings of Eeighteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-99)

1998

William Aiello, Sachin Lodha, Rafail Ostrovsky: Fast Digital Identity Revocation
[Abstract] [postscript] [pdf]
In Proceedings of advances in cryptology, (CRYPTO-98) Springer-Verlag Lecture Notes in Computer Science.
Giovanni De-Crescenzo, Yuval Ishai, Rafail Ostrovsky: Universal Service-Providers for Database Private Information Retrieval
[Abstract] [postscript] [pdf]
In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98). Journal version appears in Journal of Cryptology 14(1): 37-74 (2001).
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen: Amortizing Randomness in Private Multiparty Computations
[Abstract] [postscript] [pdf]
In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98)
Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky: Non-Interactive and Non-Malleable Commitment
[Abstract] [postscript] [pdf]
In Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98)
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
[Abstract] [postscript] [pdf]
SIAM J. Comput. 30(2): 457-474 (2000). Preliminary version in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98)
William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen: Adaptive Packet Routing for Bursty Adversarial Traffic
[Abstract] [postscript] [pdf]
In Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98). Journal version appeared in JCSS 60(3): 482-509 (2000).
Richard J. Lipton, Rafail Ostrovsky: Micro-Payments via Efficient Coin-Flipping
[Abstract] [postscript] [pdf]
In Proceedings of Second Financial Cryptography Conference, (FINANCIAL CRYPTO-98) February 1998. Lecture Notes in Computer Science LNCS volume 1465

1997

Eyal Kushilevitz, Rafail Ostrovsky: Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval
[Abstract] [postscript] [pdf]
In Proceedings of Thirty-eigth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-97)
Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen: Randomness vs. Fault-Tolerance
[Abstract] [postscript] [pdf]
In Proceedings of Sixteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-97). Journal version in Journal of Cryptology 13(1): 107-142 (2000).
Shlomi Dolev, Rafail Ostrovsky: Efficient Anonymous Multicast and Reception
[Abstract] [postscript] [pdf]
Preliminary version in proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science. Journal version in ACM Trans. Inf. Syst. Secur. 3(2): 63-84 (2000)
Ari Juels, Michael Luby, Rafail Ostrovsky: Security of Blind Digital Signatures
[Abstract] [postscript] [pdf]
In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky: Deniable Encryption.
[Abstract] [postscript] [pdf]
In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
Rafail Ostrovsky, Victor Shoup: Private Information Storage
[Abstract] [postscript] [pdf]
In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)
Rafail Ostrovsky, Yuval Rabani: Universal O(congestion+dilation+log^{1+\epsilon} N) Local Control Packet Switching Algorithm
[Abstract] [postscript] [pdf]
In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)

1996

Eyal Kushilevitz, Nati Linial, Rafail Ostrovsky: The Linear-Array Conjecture in Communication Complexity is False.
[Abstract] [postscript] [pdf]
Preliminary version in Proceedings of The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96) Journal version in Combinatorica 19(2): 241-254 (1999)
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen: Characterizing Linear Size Circuits in Terms of Privacy.
[Abstract] [postscript] [pdf]
Invited paper to the Journal of Computer and System Sciences special issue for STOC 96. In Vol 58, JCSS 58(1): 129-136 (1999). Preliminary version appeared in the Proceedings of The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96).
Alain Mayer, Rafail Ostrovsky, Moti Yung: Self-Stabilizing Algorithms for Synchronous Unidirectional Rings.
[Abstract] [postscript] [pdf]
In Proceedings of Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-96) January 28-30, Atlanta, Georgia

1995

Rafail Ostrovsky, Danal Wilkarson: Faster Computation On Directed Networks of Automata
[Abstract] [postscript] [pdf]
In the Proceedings of Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-95)
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen: LOG-Space Polynomial End-to-End Communication
[Abstract] [postscript] [pdf]
In SIAM Journal of Computing Volume 27, 1998. SIAM J. Comput. 27(6): 1531-1549 (1998). Preliminary version appeared in the Proceedings of Twenty-seventh ACM Symposium on Theory of Computing STOC-95

1994

Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky: Reducibility and Completeness In Multi-Party Private Computations.
[Abstract] [postscript] [pdf]
Preliminary version appeared in Proceedings of Thirty-fifth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-94). Journal version in SIAM J. Comput. 29(4): 1189-1208 (2000)
Baruch Awerbuch, Rafail Ostrovsky: Memory-Efficient and Self-Stabilizing Network RESET.
[Abstract] [postscript] [pdf]
In Proceedings of Thirteens Annual ACM Symposium on Principles of Distributed Computing (PODC-94) UCLA, Los Angeles, California, August 14-17 1994.
Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani: Simple and Efficient Leader Election In The Full Information Model.
[Abstract] [postscript] [pdf]
In Proceedings of Twenty-sixth ACM Symposium on Theory of Computing (STOC-94)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank: Computational Complexity and Knowledge Complexity.
[Abstract] [postscript] [pdf]
Preliminary version appeared in the Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) Full version in SIAM Journal on Computing, 27(4):1116-1141, August 1998.
Noga Alon, Manuel Blum, Amos Fiat, Sampath K. Kannan, Moni Naor, Rafail Ostrovsky: Matching Nuts and Bolts.
[Abstract] [postscript] [pdf]
In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-94) January 23-25, 1994, Arlington, Virginia.

1993

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Interactive Hashing Simplifies Zero-Knowledge Protocol Design.
[Abstract] [postscript] [pdf]
In Proceedings of (EUROCRYPT-93) Springer Verlag.
Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir.: The Las-Vegas Processor Identity Problem
[Abstract] [postscript] [pdf]
In Proceedings of the Second Israel Symposium on Theory of Computing and Systems (ISTCS-93) Journal version appeared in J. Algorithms 37(2): 468-494 (2000).
Rafail Ostrovsky, Avi Wigderson: One-Way Functions are Essential for Non-Trivial Zero-Knowledge.
[Abstract] [postscript] [pdf]
In Proceedings of the second Israel Symposium on Theory of Computing and Systems} (ISTCS-93)

1992

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.: Secure Commitment Against Powerful Adversary: A Security Primitive based on Average Intractability.
[Abstract] [postscript] [pdf]
In Proceedings of 9th Symposium on Theoretical Aspects of Computer Science (STACS-92) (LNCS 577 Springer Verlag Ed. A. Finkel and M. Jantzen) pp. 439-448 February 13-15 1992, Paris, France.
Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung: Self-Stabilizing Symmetry Breaking in Constant-Space.
[Abstract] [postscript] [pdf]
In Proceedings of 24th annual ACM Symposium on Theory of Computing (STOC-92)
Shafi Goldwasser, Rafail Ostrovsky: Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent.
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology (CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science.
Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.: Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions.
[Abstract] [postscript] [pdf]
Preliminary version appeared in Proceedings of advances in cryptology (CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science. Final version appeared in J. of Cryptology, 1988.

1991

Rafail Ostrovsky: One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs.
[Abstract] [postscript] [pdf]
In Proceedings of 6th Annual Structure in Complexity Theory Conference (STRUCTURES-91) June 30 -- July 3, 1991, Chicago. pp. 51-59.
Rafail Ostrovsky, Moti Yung.: How to Withstand Mobile Virus Attacks.
[Abstract] [postscript] [pdf]
In Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC-91) August 1991, Montreal, Quebec, Canada, pp. 51-59.
Joan Feigenbaum, Rafail Ostrovsky: A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems.
[Abstract] [postscript] [pdf]
In Proceedings of the first international symposium in cryptology in Asia (ASIACRYPT'91) November 11-14, 1991, Fujsiyoshida, Yamanashi, Japan.

1990

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Fair Games Against an All-Powerful Adversary.
[Abstract] [postscript] [pdf]
Presented in DIMACS Complexity and Cryptography Workshop, Princeton, October 1990. Extended abstract in proceedings of Sequences II, June 1991, Positano, Italy, R.M. Capocelli, A. De-Santis and U. Vaccaro (Eds.), Springer-Verlag. Journal version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 13. (Jin-Yi Cai ed.) pp. 155-169, 1991.
Rafail Ostrovsky and Moti Yung.: On Necessary Conditions for Secure Distributed Computation.
[Abstract] [postscript] [pdf]
In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 2. 1990. Proceedings of a DIMACS workshop, October 4-6, 1989, pp. 229-234.
Rafail Ostrovsky: Software Protection and Simulation on Oblivious RAMs.
[Abstract] [postscript] [pdf]
Preliminary version appeared as a single-author paper in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90) pp. 514-523. Full version became my M.I.T. Ph.D. thesis in 1992. Journal version appeared in JACM, Vol. 43, No. 3, May 1996, pp.431-473 co-authored with Oded Goldreich [postscript], [pdf].
Mihir Bellare, Silvio Micali, Rafail Ostrovsky.: Perfect Zero-Knowledge in Constant Rounds.
[Abstract] [postscript] [pdf]
In Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90)
Mihir Bellare, Silvio Micali, and Rafail Ostrovsky: The (True) Complexity of Statistical Zero Knowledge.
[Abstract] [postscript] [pdf]
In Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90)

1989

Joe Kilian, Silvio Micali, Rafail Ostrovsky: Minimum Resource Zero-Knowledge Proofs.
[Abstract] [postscript] [pdf]
In Proceedings of 30th annual IEEE Symposium on the Foundations of Computer Science (FOCS-89)