Rafail Ostrovsky Publications
(In Chronological Order)

For additional information, especially regarding journal publications, see DBLP.
You can also search my Publications by Topic or try Google Scholar.    
Color-coding: Security and cryptography Algorithms
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 Meassuring k-Wise Indepedence of Streaming Data, June 29, 2008; and
Vladimir Braverman, Rafail Ostrovsky AMS Without 4-Wise Independence on Product Domains, September 17, 2009.)
 
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]
Initially presened at DIMACS worksop, 1990. Extended abstract in the proceedings of Sequences '91, June 1991, Positano, Italy. Journal version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science}. Vol 13. (Jin-Yi Cai ed.) pp. 155-169, 1993.
 
   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)