Rafail Ostrovsky - Publications

     Jonathan Katz, Rafail Ostrovsky, Adam Smith

Round Efficiency of Multi-Party Computation with a Dishonest Majority
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)] [ SODA talk (pdf file)]
In Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA-2003)
 

     Jonathan Katz, Rafail Ostrovsky, Moti Yung

Forward Security in Password-Only Key Exchange Protocols
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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 file)] [stoc version (pdf file)] [full paper (postscript file)] [full paper (pdf file)]
Appeared in Proceedings of the ACM 2002 Symposim on Theory of Computing (STOC-2002), pp. 494-503.
 

     Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani.

Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of 42st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2001).
 

     Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai

Robust Non-Interactive Zero Knowledge
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2001)
 

     Rafail Ostrovsky, Yuval Rabani.

Polynomial Time Approximation Schemes for Geometric k-Clustering.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of Advances in Cryptology (EUROCRYPT-2000) Springer-Verlag Lecture Notes in Computer Science Vol 1807, pp. 122-138.
 

     Giovanni Di Crescenzo and Rafail Ostrovsky

On Concurrent Zero-Knowledge with Pre-Processing
[Abstract] [paper (postscript filqe)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99) Journal version in SIAM J. Comput. 30(2): 457-474 (2000).
 

     Ran Canetti, Rafail Ostrovsky

Secure Computation with Honest-Looking Parties
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
 

     Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan

Efficient Timed-release Public-key Encryption
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of EUROCRYPT-99 Springer Verlag.
 

     Rafail Ostrovsky, Boaz Patt-Shamir

Optimal and Efficient Clock Synchronization Under Drifting Clocks
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of Eeighteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-99)
 

     William Aiello, Sachin Lodha, Rafail Ostrovsky

Fast Digital Identity Revocation
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98). Journal version appeared in JCSS 60(3): 482-509 (2000).
 

     Eyal Kushilevitz, Rafail Ostrovsky

Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of Thirty-eigth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-97)
 

     Richard J. Lipton, Rafail Ostrovsky

Micro-Payments via Efficient Coin-Flipping
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of Second Financial Cryptography Conference, (FINANCIAL CRYPTO-98) February 1998. Lecture Notes in Computer Science LNCS volume 1465
 

     Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

Randomness vs. Fault-Tolerance
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
 

     Ari Juels, Michael Luby, Rafail Ostrovsky

Security of Blind Digital Signatures
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
 

     Rafail Ostrovsky, Victor Shoup

Private Information Storage
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)
 

     Eyal Kushilevitz, Nati Linial, Rafail Ostrovsky

The Linear-Array Conjecture in Communication Complexity is False.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Preliminary version in Proceedings of The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96) Journal version accepted to COMBINATORICA.
 

     Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

Characterizing Linear Size Circuits in Terms of Privacy.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Invited paper to the Journal of Computer and System Sciences special issue for STOC 96. Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-96) January 28-30, Atlanta, Georgia
 

     Rafail Ostrovsky, Daniel Wilkerson

Faster Computation On Directed Networks of Automata
[Abstract] [paper (postscript file)] [paper (pdf file)]
Preliminary verion Appeared in the Proceedings of Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-95) Journal version accepted to Journal of Algorithms, to appear.
 

     Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

LOG-Space Polynomial End-to-End Communication
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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
 

     Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky

Reducibility and Completeness In Multi-Party Private Computations.
[Abstract] [paper (postscript file)] [paper (pdf file)]
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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-94) January 23-25, 1994, Arlington, Virginia.
 

     Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Interactive Hashing Simplifies Zero-Knowledge Protocol Design.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of (EUROCRYPT-93) Springer Verlag.
 

     Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir.

The Las-Vegas Processor Identity Problem
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of the second Israel Symposium on Theory of Computing and Systems} (ISTCS-93)
 

     Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.

Secure Commitment Against Powerful Adversary: A Security Primitive based on Average Intractability.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
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.
 

     Rafail Ostrovsky

Software Protection and Simulation on Oblivious RAMs.
[Abstract] [paper (postscript file)] [paper (pdf file)]
M.I.T. Ph.D. Thesis, 1992. Preliminary version appeared in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90) pp. 514-523. Journal version appeared in the Journal of the JACM, Vol. 43, No. 3, May 1996, pp.431-473. written jointly with Oded Goldreich.
 

     Joan Feigenbaum, Rafail Ostrovsky

A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of the first international symposium in cryptology in Asia (ASIACRYPT'91) November 11-14, 1991, Fujsiyoshida, Yamanashi, Japan.
 

     Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Fair Games Against an All-Powerful Adversary.
[Abstract] [paper (postscript file)] [paper (pdf file)]
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

One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC-91) August 1991, Montreal, Quebec, Canada, pp. 51-59.
 

     Rafail Ostrovsky and Moti Yung.

On Necessary Conditions for Secure Distributed Computation.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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.
 

     Mihir Bellare, Silvio Micali, Rafail Ostrovsky.

Perfect Zero-Knowledge in Constant Rounds.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared 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] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90)
 

     Joe Kilian, Silvio Micali, Rafail Ostrovsky

Minimum Resource Zero-Knowledge Proofs.
[Abstract] [paper (postscript file)] [paper (pdf file)]
Appeared in Proceedings of 30th annual IEEE Symposium on the Foundations of Computer Science (FOCS-89)
 

---

 

     The Lecture Notes of the 1994 graduate Cryptography Course
           I taught at U.C. Berkeley are available here in postscript or pdf

Revised - March 3rd, 2000