Rafail Ostrovsky

I am a professor of computer science and mathematics at UCLA. My research has been supported by NSF, Binational Science Foundation (BSF), OKAWA Foundation, John B. Garrick Foundation, UC MICRO, Intel, IBM, Lockheed-Martin, Teradata, and Xerox.

Teaching

Spring 2009: CS183: Intro to Cryptography.

Research

The papers below are also available in a chronological list or organized by topics. More information can be found at DBLP.
For additions in 2008-2009, look for the signs.

Private Information Retrieval, Privacy-preserving datamining, and Searching on Encrypted Data

• Brett Hemenway, Rafail Ostrovsky Public-Key Locally-Decodable Codes. CRYPTO 2008: 126-143
• Rafail Ostrovsky, William Skeith, Communication Complexity in Algebraic Two-Party Protocols. CRYPTO 2008: 379-396
• Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William Skeith, Public Key Encryption That Allows PIR Queries. Appeared in CRYPTO 2007: 50-67
• Survey: Rafail Ostrovsky, William Skeith A Survey of Single-Database Private Information Retrieval: Techniques and Applications. Preliminary version (PKC-2007). Full version appeared as a book chapter in "Homeland Security Technology Challenges From Sensing and Encrypting to Mining a nd Modeling" Franceschetti and Grossi, (EDT), Artec-House publishers.
• Rafail Ostrovsky, Omkant Pandey, Amit Sahai Private Locally Decodable Codes. ICALP 2007: 387-398
• Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS 2006). In addition, you can get a powerpoint presentation.
• Rafail Ostrovsky, William Skeith. Private Searching on Streaming Data, Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) Springer-Verlag/IACR Lecture Notes in Computer Science. Full version in Journal of Cryptography, 2007.
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky Sufficient Conditions for Collision-Resistant Hashing, In Proceedings of Second Theory of Cryptography Conference (TCC-2005)Springer-Verlag Lecture Notes in Computer Science, 2005.
• Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Batch Codes and Their Applications, In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC-2004).
• Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Guiseppe Persiano Public Key Encryption with Keyword Search, In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2004) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Eyal Kushilevitz, Rafail Ostrovsky One-way Trapdoor Permutations Are Sufficient for Non-Trivial Single-Server Private Information Retrieval , In Proceedings of Advances in Cryptology (EUROCRYPT-2000) Springer-Verlag Lecture Notes in Computer Science.
• Giovanni Di Crescenzo, Tal Malkin, and Rafail Ostrovsky Single Database Private Information Retrieval Implies Oblivious Transfer , In Proceedings of Advances in Cryptology (EUROCRYPT-2000) Springer-Verlag Lecture Notes in Computer Science.
• Giovanni De-Crescenzo, Yuval Ishai, Rafail Ostrovsky Universal Service-Providers for Database Private Information Retrieval , 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 Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval , In Proceedings of Thirty-eighth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-97).
• Rafail Ostrovsky, Victor Shoup Private Information Storage , In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97).
• Rafail Ostrovsky Software Protection and Simulation on Oblivious RAMs. , 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.

Zero Knowledge, Non-Interactive Zero-Knowledge, Knowledge Complexity

• Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model. ICALP 2008: 548-559
• Jens Groth, Rafail Ostrovsky Cryptography in the Multi-string Model. Preliminary version appeared in CRYPTO 2007: 323-341
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky Efficient Arguments without Short PCPs. Preliminary version appeared in IEEE Conference on Computational Complexity 2007 : 278-291 (ECCC-2007).
• Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Zero-Knowledge from Secure Multiparty Computation, In Proceedings of the ACM 2007 Symposium on Theory of Computing (STOC-2007). Full version invited and accepted to SIAM Journal of Computing (SICOMP) special issue devoted to STOC-2007.
• Jens Groth, Rafail Ostrovsky, Amit Sahai. Non-interactive Zaps and New Techniques for NIZK, In Proceedings of Advances in Cryptology, (CRYPTO-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Jens Groth, Rafail Ostrovsky, Amit Sahai. Perfect Non-Interactive Zero Knowledge for NP, In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions. ASIACRYPT 2007: 444-459
• Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin Identity-Based Zero-Knowledge, In Proceedings of Security in Communication Networks: 4th International Conference, SCN-2004 Springer-Verlag Lecture Notes in Computer Science.
• Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai Robust Non-Interactive Zero Knowledge, In Proceedings of Advances in Cryptology, (CRYPTO-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Giovanni Di Crescenzo and Rafail Ostrovsky On Concurrent Zero-Knowledge with Pre-Processing , In Proceedings of Advances in Cryptology (CRYPT0-99), Springer-Verlag Lecture Notes in Computer Science.
• Oded Goldreich, Rafail Ostrovsky, Erez Petrank Computational Complexity and Knowledge Complexity. , Preliminary version in the Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) Full version in SIAM Journal on Computing, 27(4):1116-1141, 1998.
• Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Interactive Hashing Simplifies Zero-Knowledge Protocol Design. , In Proceedings of (EUROCRYPT-93) Springer Verlag.
• Rafail Ostrovsky, Avi Wigderson One-Way Functions are Essential for Non-Trivial Zero-Knowledge. , In Proceedings of the second Israel Symposium on Theory of Computing and Systems} (ISTCS-93).
• Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung. Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions. , Preliminary version in Proceedings of advances in cryptology (CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science. Journal version in J. of Cryptology, 1988.
• Joan Feigenbaum, Rafail Ostrovsky A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems. , In Proceedings of the first international symposium in cryptology in Asia (ASIACRYPT'91).
• Rafail Ostrovsky One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs. , In Proceedings of 6th Annual Structure in Complexity Theory Conference (STRUCTURES-91) June 30 -- July 3, 1991, Chicago. pp. 51-59.
• Mihir Bellare, Silvio Micali, Rafail Ostrovsky. Perfect Zero-Knowledge in Constant Rounds. , 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. , In Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90).
• Joe Kilian, Silvio Micali, Rafail Ostrovsky Minimum Resource Zero-Knowledge Proofs. , In Proceedings of 30th annual IEEE Symposium on the Foundations of Computer Science (FOCS-89).

Biometric Identification, Passwords and Digital Signatures

• Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1): 97-139 (2008)
• Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, and Brent Waters Sequential Aggregate Signatures and Multisignatures Without Random Oracles , In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith. Secure Authentication Using Biometric Data, In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2005) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Jonathan Katz, Rafail Ostrovsky, Moti Yung Forward Security in Password-Only Key Exchange Protocols, In Proceedings of Security in Communication Networks 2002 conference (CSN-2002) Springer-Verlag Lecture Notes in Computer Science.
• Jonathan Katz, Rafail Ostrovsky, Moti Yung Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords , In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Ari Juels, Michael Luby, Rafail Ostrovsky Security of Blind Digital Signatures , In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
• Shafi Goldwasser, Rafail Ostrovsky Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent. , In Proceedings of Advances in Cryptology (CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science.

Secure Two-Party and Multi-Party Computation

• Yair Amir, Paul Bunn, Rafail Ostrovsky Authenticated Adversarial Routing. TCC-2009 In addition, you can get a powerpoint presentation.
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Cryptography with constant computational overhead. Preliminary version in STOC 2008: 433-442
• Juan A. Garay, Rafail Ostrovsky Almost-Everywhere Secure Computation. EUROCRYPT 2008: 307-323
• Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky Round Complexity of Authenticated Broadcast with a Dish onest Majority. Preliminary version appeared in FOCS 2007: 658-668
• Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai Covert Multi-Party Computation. Preliminary version appeared in FOCS 2007: 238-248
• Paul Bunn, Rafail Ostrovsky Secure two-party k-means clustering. ACM Conference on Computer and Communications Security 2007: 486-497 (CCS-2007)
• Jonathan Katz, Rafail Ostrovsky Round-Optimal Secure Two-Party Computation, In Proceedings of Advances in Cryptology, (CRYPTO-2004) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Jonathan Katz, Rafail Ostrovsky, Adam Smith Round Efficiency of Multi-Party Computation with a Dishonest Majority, In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2003) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai Universally composable two-party and multi-party secure computation., In Proceedings of the ACM 2002 Symposium on Theory of Computing (STOC-2002).
• Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky Minimal Complete Primitives for Secure Multi-Party Computation , 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.
• Ran Canetti, Rafail Ostrovsky Secure Computation with Honest-Looking Parties , In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
• Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen Amortizing Randomness in Private Multiparty Computations , In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98).
• Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen Randomness vs. Fault-Tolerance , 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).
• Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen Characterizing Linear Size Circuits in Terms of Privacy. , 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).
• Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky Reducibility and Completeness In Multi-Party Private Computations. , 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).
• Rafail Ostrovsky, Moti Yung. How to Withstand Mobile Virus Attacks. In Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC-91).
• Rafail Ostrovsky and Moti Yung. On Necessary Conditions for Secure Distributed Computation. , 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.

Non-Malleable Commitment Protocols, and Commitments with special properties.

• Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti Simulation-Based Concurrent Non-Malleable Commitments and Decommitments. TCC-2009
• Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith Efficient and Non-interactive Non-malleable Commitment , In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Rafail Ostrovsky, Charles Rackoff, Adam Smith Efficient Consistency Proofs for Generalized Queries on a Committed Database , In Proceedings ICALP-2004.
• Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky Non-Interactive and Non-Malleable Commitment , In Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98).
• Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung. Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions. , Preliminary version in Proceedings of advances in cryptology (CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science. Journal version in J. of Cryptology, 1988.
• Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung. Secure Commitment Against Powerful Adversary: A Security Primitive based on Average Intractability. , In Proceedings of 9th Symposium on Theoretical Aspects of Computer Science (STACS-92).
• Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Fair Games Against an All-Powerful Adversary. , Initially presented at DIMACS workshop, 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.

Hash Functions

• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Cryptography with constant computational overhead. Preliminary version in STOC 2008: 433-442
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky Sufficient Conditions for Collision-Resistant Hashing, In Proceedings of Second Theory of Cryptography Conference (TCC-2005)Springer-Verlag Lecture Notes in Computer Science, 2005.

Issues of Anonymity

• Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Cryptography from Anonymity, In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006).
• Shlomi Dolev, Rafail Ostrovsky Efficient Anonymous Multicast and Reception ,
  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)

Public-Key Encryption with Additional Properties, PKI and Identity revocation.

• Dan Boneh, Shai Halevi, Michael Hamburg, Rafail Ostrovsky Circular-Secure Encryption from Decision Diffie-Hellman. 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. CRYPTO 2008: 126-143
• Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William Skeith, Public Key Encryption That Allows PIR Queries. Preliminary version appeared in CRYPTO 2007: 50-67
• Rafail Ostrovsky, Amit Sahai, Brent Waters Attribute-based encryption with non-monotonic access st ructures. ACM Conference on Computer and Communications Security 2007: 195-203 (CCS-2007)
• William Aiello, Sachin Lodha, Rafail Ostrovsky Fast Digital Identity Revocation , In Proceedings of advances in cryptology, (CRYPTO-98) Springer-Verlag Lecture Notes in Computer Science.
• Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan Efficient Timed-release Public-key Encryption, In Proceedings of EUROCRYPT-99 Springer Verlag.
• Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky Deniable Encryption., In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.

Cryptographic Applications: Electronic Voting, Micropayments, Visual crypto

• Steve Lu, Daniel Manchala, Rafail Ostrovsky Visual Cryptography on Graphs. Preliminary version appeared in COCOON 2008: 225-234. (Best Paper Award).
• Jonathan Katz, Steven Myers, Rafail Ostrovsky Cryptographic Counters and Applications to Electronic Voting. , In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
• Richard J. Lipton, Rafail Ostrovsky Micro-Payments via Efficient Coin-Flipping , In Proceedings of Second Financial Cryptography Conference, (FINANCIAL CRYPTO-98) February 1998. Lecture Notes in Computer Science LNCS volume 1465
  
  

Dimension Reduction, Emeddings and Geometric search

• Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai Improved algorithms for optimal embeddings. ACM Transactions on Algorithms 4(4): (2008)
• Rafail Ostrovsky, Yuval Rabani. Low distortion embedding for edit distance, Preliminary version appeared in STOC '05. Full version JACM, 2008.
• Allan Borodin, Rafail Ostrovsky, Yuval Rabani Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems , 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.
• Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces , SIAM J. Comput. 30(2): 457-474 (2000). Preliminary version in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98)

Clustering Algorithms for high-dimensional data

• Rafail Ostrovsky, Yuval Rabani, Leonard Schulman, and Chaitanya Swamy The Effectiveness of Lloyd-Type Methods for the k-Means Problem. In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006).
• Paul Bunn, Rafail Ostrovsky Secure two-party k-means clustering. ACM Conference on Computer and Communications Security 2007: 486-497 (CCS-2007)
• Rafail Ostrovsky, Yuval Rabani. Polynomial Time Approximation Schemes for Geometric k-Clustering. , In Proceedings of 41st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2000). Journal version in JACM 49(2): 139-156 (2002).
• Allan Borodin, Rafail Ostrovsky, Yuval Rabani Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces , Preliminary version in proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99), Journal version in Machine Learning Journal Special Issue: Theoretical Advances in Data Clustering 56 (1-3): 153-167, 2004.

Algorithms for Streaming Data

• Vladimir Braverman, Rafail Ostrovsky, Calro Zaniolo Optimal Sampling from Sliding Windows. In PODS-2009.
• Vladimir Braverman, Rafail Ostrovsky Smooth Histograms for Sliding Windows. Preliminary version appeared in FOCS 2007: 283-293
• Rafail Ostrovsky, William Skeith. Private Searching on Streaming Data, Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) Springer-Verlag/IACR Lecture Notes in Computer Science. Full version in Journal of Cryptography, 2007.
  

Admission Control and Network Routing Algorithms

• Yair Amir, Paul Bunn, Rafail Ostrovsky Authenticated Adversarial Routing. TCC-2009 In addition, you can get a powerpoint presentation.
• William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen Dynamic Routing on Networks with Fixed-Sized Buffers, In Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA-2003).
• Allan Borodin, Rafail Ostrovsky, Yuval Rabani. Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds , In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2001). Journal version in Journal of Interconnection Networks, Vol. 5, No. 1, pp. 1-12.
• William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen Adaptive Packet Routing for Bursty Adversarial Traffic , In Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98). Journal version appeared in JCSS 60(3): 482-509 (2000).
• Rafail Ostrovsky, Yuval Rabani Universal O(congestion+dilation+log(N)) Local Control Packet Switching Algorithm , 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. , 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)

Distributed Algorithms with severely limited memory per processor

• Alain Mayer, Rafail Ostrovsky, Moti Yung Self-Stabilizing Algorithms for Synchronous Unidirectional Rings. , In Proceedings of Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-96) January 28-30, Atlanta, Georgia.
• Rafail Ostrovsky, Wilkersan Faster Computation On Directed Networks of Automata , 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 , 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.
• Baruch Awerbuch, Rafail Ostrovsky Memory-Efficient and Self-Stabilizing Network RESET. , In Proceedings of Thirteens Annual ACM Symposium on Principles of Distributed Computing (PODC-94),

Symmetry Breaking

• Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani Simple and Efficient Leader Election In The Full Information Model. , In Proceedings of Twenty-sixth ACM Symposium on Theory of Computing (STOC-94).
• Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir. The Las-Vegas Processor Identity Problem , 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).
• Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung Self-Stabilizing Symmetry Breaking in Constant-Space. , In Proceedings of 24th annual ACM Symposium on Theory of Computing (STOC-92).

Distributed Control Theory and Error-Correcting Codes

• Rafail Ostrovsky, Yuval Rabani, Leonard Schulman. Error-Correcting Codes for Automatic Control, In Proceedings of 46th Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2005).
• Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Batch Codes and Their Applications, In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC-2004).

Synchronization in distributed networks

• Milan Bradonjic, Eddie Kohler, and Rafail Ostrovsky Near-Optimal Radio Use For Wireless Network Synchronization ALGOSENSORS-2009.
• Rafail Ostrovsky, Boaz Patt-Shamir Optimal and Efficient Clock Synchronization Under Drifting Clocks , In Proceedings of Eighteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-99).

Combinatorial Algorithms

• Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani. Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. Preliminary version in (FOCS-2001). Journal version accepted to Journal of Mathematics of Operations Research.
• Noga Alon, Manuel Blum, Amos Fiat, Sampath K. Kannan, Moni Naor, Rafail Ostrovsky Matching Nuts and Bolts. , In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-94),

Research Interests

• Cryptography:
  • Private Information Retrieval, Privacy-preserving dataminging and searching on encrypted data;
  • Zero Knowledge, Non-Interactive Zero-Knowledge;
  • Secure Two-Party and Multi-Party Computation;
  • Public-Key Encryption with Additional Properties; PKI;
  • Biometric Authentication, Passwords, and Digital Signatures;
  • Hash Functions;
  • Anonymity;
  • Non-Malleable Commitment Protocols and Commitments with additional properties;
  • Cryptographic applications: Secure Voting; Visual crypto; Micropayments;
• Search and Analysis of Large-scale, High-Dimensional Data:
  • Algorithms for Streaming Data;
  • Metric embedding, and Nearest-Neighbor Proximity Problems for High-Dimensional Data;
  • Clustering Algorithms for High-Dimensional Data;
• Distributed Control Theory, Network Algorithms and Combinatorial Algorithms:
  • Admission Control and Network Routing Algorithms;
  • Distributed Control and Error-Correcting Codes;
  • Distributed Algorithms with severely limited memory per processor;
  • Synchronization in Distributed Networks;
  • Distributed symmetry breaking algorithms;
  • Combinatorial Algorithms.

Short Bio

Some Current and Past Professional Activities

• Program committee member TCC-2010: Seventh Theory of Cryptography Conference, 2010.
  
  
• Editorial Board member Journal of Cryptology 2006--present.
• Editorial Board member Algorithmica 2005--present.
• Editorial Board member International Journal of Information and Computer Security. 2004--present.
• Steering Committee member Conference on Security and Cryptography for Networks 2005--present.

• Program Chair, Sixth Conference on Security and Cryptography for Networks Amalfi, September 10-12, 2008. The proceedings of SCN 2008 appeared in LNCS 5229 and are available on-line. See also Italian press coverage.
• Program Chair, Institute of Pure and Applied Mathematics semester-long program dedicated to Cybersecurity. September - December, 2006.
• Co-chair, Dagshtul Workshop Anonymous Communication and its Applications October 9-14, 2005.
• Co-organizer, IPAM Workshop Multiscale Geometry and Analysis in High Dimensions October 19-23, 2004.
• Co-organizer, DIMACS Workshop Cryptographic Protocols in Complex Environments May 15-17, 2002.
  
  
• Program committee member EUROCRYPT-2009 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Eurocrypt 2009 will take place in Cologne from April 26-30, 2009.
• Program committee member Algosensors-2009 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks 2009.
• Program committee member FOCS-2008 49th Annual IEEE Symposium on Foundations of Computer Science.
• Program committee member PKC-2007: International Workshop on Practice and Theory in Public Key Cryptography, (Apr 17-19 2007, Beijing). China 2007
• Program committee member ACISP-2007 12th Australian Conference on Information Security and Privacy July 2-6, 2007, Townsville, Queensland, Australia.
• Program committee member ICALP-2006: 33rd International Colloquium on Automata, Languages and Programming, July 9-16, 2006, Venice, Italy
• Program committee member STOC-2006: Annual ACM Symposium on Theory of Computing, May 2006.
• Program committee member PKC 2006: International Workshop on Practice and Theory in Public Key Cryptography, April 24-26, New York City, USA.
• Program committee member INDOCRYPT-2005 December 10-12, 2005 Indian Institute of Science Bangalore, India, 2005.
• Program committee member EUROCRYPT-2005 Aarhus, May 22-26, 2005.
• Program committee member TCC-2005: Second Theory of Cryptography Conference, Feb 2005.
• Program committee member SCN-2004 Security in Communication Networks 2004 to be held on September 8-10 in Amalfi, Italy.
• Program committee member PODC-2004: 23rd Annual ACM Symposium on Principles of Distributed Computing, July 2004.
• Program committee member CRYPTO-2004: 24nd Annual IACR/IEEE Conference on Cryptologic Research, August 2004.
• Program committee member CRYPTO-2003: 23nd Annual IACR/IEEE Conference on Cryptologic Research, August 2003.
• Program committee member STOC-2003: Annual ACM Symposium on Theory of Computing, May 2003.
• Program committee member CRYPTO-2002: 22nd Annual IACR/IEEE Conference on Cryptologic Research, 2002.
• Program committee member RANDOM-2002: The 6th International Workshop on Randomization and Approximation Techniques in Computer Science, 2002.
• Program committee member SCN-2002: Third Workshop on Security in Communication Networks, September 2002, Amalfi, Italy.
• Program committee member STOC-2000: Annual ACM Symposium on Theory of Computing, 2000.
• Program committee member SODA-2000: Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, , January 1-9, 2000, San Francisco.
• Program committee member SCN-99: Second Workshop on Security in Communication Networks, September 1999, Italy.
• Program committee member CRYPTO-98: 18th Annual IACR/IEEE Conference on Cryptologic Research 1998.
• Program committee member ISTCS-97: 5th ISRAEL Symposium on Theory of Computing and Systems, 1997.

Invited Talks (from September 2005)

• Invited talk: 2009 Workshop on Cryptographic Protocols and Public-Key Cryptography May 24-29 2009, Bertinoro, Italy.
• Distinguished Lecturer Seminar Series, U.C. Inrvine Computer Science Deparmtment, May 15, 2009.
• Plenary invited speaker at International Conference on Cyber Security 2009 organized by FBI and Fordham university.
• Plenary keynote speaker at PKC-2007 International Workshop on Practice and Theory in Public Key Cryptography, China 2007.
• Invited talk: Sun Microsystems, 2007 Distinguished Lecture Series, January 2007, Palo Alto, CA, USA
• Invited tutorial: Series of IPAM lectures on Private Information Retrieval September 2006, Los Angeles, CA, USA.
• Two invited tutorials at Homeland Defense and Security Conference 18-21 Octover 2006, Sorrento, Italy.
• Invited talk: 2006 Xerox Corporation Distinguished Lecture Series Los Angeles, July 2006. USA
• Invited talk: Worksop on Data Sirveillance and Privacy Protection Workshop Harvard, June 2006.
• Invited talk: Workshop on classical & quantum information security Caltech, December 15-18, 2005.
• Invited talk: Interdepartmental Seminar on Algorithmics University of Rome "La Sapienza", Italy. November 21, 2005.
• Invited 1-week courseBertinoro, Italy September 4-9, 2005.
• Invited talk: 2005 Distinguished Cryptographer Lecture Series NTT Labs, Kanagawa, Japan, October 2005.
• Invited talk: Workshop on Cryptography and Information Security 2005 Tokyo, Japan, October 21, 2005.
• Invited talk: IEEE Information Theory Workshop on Theory and Practice in Information-Theoretic Security Awaji Island, Japan, October 16- 19, 2005.
• Invited talk: Dagshtul Workshop. Germany, October 9-14, 2005.
• Invited talk: Southern California Security and Cryptography Workshop September 24, 2005, Irvine, CA. USA
• Invited talk: Bertinoro Invited one-week course, International PhD School on Mathematical Aspects of Modern Cryptography, Bertinoro, Italy September 4-9, 2005.

Some Current and Former Ph.D. Students, Postdocs and Long Term Visitors

• Vladimir Braverman
• Paul Bunn
• Nishanth Chandran (also a violin player.)
• Vipul Goyal
• Brett Hemenway
• Abhishek Jain
• Steve Lu
• Omkant Pandey
  
  

• Jonathan Katz (CS Ph.D. 2002, now CS faculty at U. of Maryland.)
• William Skeith (Math Ph.D. 2007; now CS faculty at City College of NY).
• Ryan Moriarty (on leave)

• Jens Groth (2005-2007): Now tenure-ttrack faculty at University College of London.

• Yuval Ishai (2007-presnet): on Subbatical from Technion.

Useful and Fun Links

• UCLA schedule
• UCLA calendars
• UCLA yellow pages
• UCLA Campus maps
• Call for papers for Crypto conferences
• UCLA Number Theory
• My Math page
  
  
  
  

• My Favorite Poems
• Photos:
  • 2005, Positano
  • 2006, Hateratti
  • 2008, with Ivan Visconti

Contact Info