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)