Rafail Ostrovsky

Norman E. Friedman Chair in Knowledge Sciences
Distinguished Professor of Computer Science;
Distinguished Professor of Mathematics (by courtesy);
Director of Center for Information and Computation Security
at Henry Samueli School of Engineering and Applied Science;
UCLA, Los Angeles, CA 90095

CV
Short Bio
Teaching
Research Interests
Publications by Year
Publications by Topic
Selected Honors and Awards
Professional Activities
Recent Invited Talks
Students and Postdocs
Useful & Fun Links
Contact Information
Directions to my UCLA office

Rafail Ostrovsky holds Norman E. Friedman Chair in Knowledge Sciences at UCLA Samueli School of Engineering. He is a Distinguished Professor of Computer Science and a Distinguished Professor of Mathematics at UCLA. He is a Fellow of multiple organizations, including the American Association for the Advancement of Science (AAAS), the Association for Computing Machinery (ACM), the Institute of Electrical and Electronics Engineers (IEEE), and the International Association for Cryptologic Research (IACR); and a foreign member of Academia Europaea, with over 350 refereed publications and 15 issued USPTO patents. He served as chair of the IEEE Technical Committee on Mathematical Foundations of Computing from 2015 to 2018 and served as a Chair of IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2011 Program Committee (PC). He also served on over 40 other international conference PC's and is currently serving on the editorial boards of Journal of ACM, Algorithmica Journal, and Journal of Cryptology. He is the recipient of multiple awards and honors including 1993 Henry Taub Prize; the 2017 IEEE Computer Society Edward J. McCluskey Technical Achievement Award; the 2018 RSA Award for Excellence in Mathematics (also known as RSA Prize); and the 2022 W. Wallace McDowell Award, the highest award given by the IEEE Computer Society.

Teaching

Fall 2024:

Recent courses taught at UCLA:

CS183 Introduction to Cryptogaphy;
CS282A/M209A Foundatoions of Cryptography;
CS282B/M209B Cryptographic Protocols;
CS289A Current Topics in Computer Science Theory;
CS289A Seminar on Probabilistically Checkable Proofs;
CS289A Seminar on Byzantine Agreement;
CS180 Introduction to Algorithms and Complexity;

Interested in working with me, or becoming my postdoc or visiting? (Please read this BEFORE EMAILING ME).

Research Interests

I am interested in all aspects of theory of computation, especially in cryptography, network algorithms, and search and classification of large-scale, high-dimensional data. I find these topics fascinating to work on, not only due to their philosophical and theoretical centrality in computer science, but also due to their practical significance. Below, is a more detailed list of topics, with links to papers written on each topic. (You can also search Publications by Year or Google Scholar or DBLP.)

Publications by Topic

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

Cryptography:
Search and Analysis of Large-scale, High-Dimensional Data:
Distributed Control Theory, Network Algorithms and Combinatorial Algorithms:

Publications: Cryptography

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

Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky On the (In)security of Hash-Based Oblivious RAM and a New Balancing Scheme . SODA 2012: 143-156
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

Wutichai Chongchitmate, Rafail Ostrovsky, Ivan Visconti Resettably-Sound Resettable Zero Knowledge in Constant Rounds . TCC (2) 2017: 111-138
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds . TCC (1) 2017: 711-742
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti Four-Round Concurrent Non-Malleable Commitments from One-Way Functions . CRYPTO (2) 2017: 127-157
Rafail Ostrovsky, Alessandra Scafuro, Muthuramakrishnan Venkitasubramaniam Resettably Sound Zero-Knowledge Arguments from OWFs - The (Semi) Black-Box Way . TCC (1) 2015: 345-374
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti On Input Indistinguishable Proof Systems . ICALP (1) 2014: 895-906
Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti Black-box non-black-box zero knowledge . STOC 2014: 515-524
Claudio Orlandi, Rafail Ostrovsky, Vanishree Rao, Amit Sahai, Ivan Visconti Statistical Concurrent Non-malleable Zero Knowledge . TCC 2014: 167-191
Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, Muthuramakrishnan Venkitasubramaniam, Ivan Visconti 4-Round Resettably-Sound Zero Knowledge . TCC 2014: 192-216
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti Impossibility of black-Box simulation Against Leakage Attacks. CRYPTO (2) 2015: 130-149
Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti Constant-Round Concurrent Zero Knowledge in the Bounded Player Model . ASIACRYPT (1) 2013: 21-40
Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, Ivan Visconti Simultaneous Resettability from One-Way Function . FOCS 2013: 60-69
Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti Concurrent Zero Knowledge in the Bounded Player Model . TCC 2013: 60-79
Joshua Baron, Rafail Ostrovsky, Ivan Visconti Nearly Simultaneously Resettabe Black-Box Zero Knowledge. ICALP 2012: 88-99
Sanjam Garg, Rafail Ostrovsky, Ivan Visconti, Akshay Wadia Resettable Statistical Zero Knowledge . TCC 2012: 494-511
Chongwon Cho, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti Simultaneously Resettable Arguments of Knowledge . TCC 2012: 530-547
Rafail Ostrovsky, Omkant Pandey, Ivan Visconti Efficiency Preserving Transformations for Concurrent Non-Malleable Zero Knowledge . Preliminary version in TCC 2010: 535-552
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
Rafail Ostrovsky, Omkant Pandey, Ivan Visconti Efficiency Preserving Transformations for Concurrent Non-Malleable Zero Knowledge. TCC-2010
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, Position-Based Identification, Passwords and Digital Signatures

Vipul Goyal, Abhishek Jan, Rafail Ostrovsky Passward-Authenticated Session-Key Generation on the Internet in Plain Model . Preliminary version appeared in Crypto 2010: 277-294. Full version appeared in J. ACM 57(1): 3:1-3:39 (2009)
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner Postion Based Quantim Cryptography: Impossibility and Constructions. SIAM Journal on Computing, 2014
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin Privacy Amplification with Asymptotically Optimal Entropy Loss. STOC 2010.
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky Postion Based Cryptography. CRYPTO-2009. (In addition, you can get a [ppt].)
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

Brett Hemenway, Rafail Ostrovsky Efficient robust secret sharing from expander graphs. Cryptography and Communications . Cryptography and Communications 10(1): 79-99 (2018)
Yuval Ishai, Manika Mittal, Rafail Ostrovsky On the Message Complexity of Secure Multiparty Computation. PKC (1) 2018: 698-711
Shlomi Dolev, Karim Eldefrawy, Juan A. Garay, Muni Venkateswarlu Kumaramangalam, Rafail Ostrovsky, Moti Yung Brief Announcement: Secure Self-Stabilizing Computation . PODC 2017: 415-417
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti Round-Optimal Secure Two-Party Computation from Trapdoor Permutations . TCC (1) 2017: 678-710
Steve Lu, Rafail Ostrovsky Black-Box Parallel Garbled RAM. CRYPTO (2) 2017: 66-92.
Juan A. Garay, Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas The Price of Low Communication in Secure Multi-party Computation . CRYPTO (1) 2017: 420-446
Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, Daniel Wichs Adaptively Secure Garbled Circuits from One-Way Functions . CRYPTO (3) 2016: 149-178
Ivan Damgard, Jesper Buus Nielsen, Rafail Ostrovsky, Adi Rosen Unconditionally Secure Computation with Reduced Interaction EUROCRYPT (2) 2016: 420-447
Shlomi Dolev, Karim Eldefrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung Brief Announcement: Proactive Secret Sharing with a Dishonest Majority . PODC 2016: 401-403
Shlomi Dolev, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung Proactive Secret Sharing with a Dishonest Majority . SCN 2016: 529-548
Joshua Baron, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky Communication-Optimal Proactive Secret Sharing for Dynamic Groups . ACNS 2015: 23-41
Sanjam Garg, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Cryptography with One-Way Communication . CRYPTO (2) 2015: 191-208
Rafail Ostrovsky, Silas Richelson, Alessandra Scafuro Round-Optimal Black-Box Two-Party Computation . CRYPTCRYPTO (2) 2015: 339-358
Alwen, Rafail Ostrovsky, Hong-Sheng Zhou, Vassilis Zikas Incoercible Multi-party Computation and Universally Composable Receipt-Free Voting . CRYPTO (2) 2015: 763-780
Melissa Chase, Rafail Ostrovsky, Ivan Visconti Executable Proofs, Input-Size Hiding Secure Computation and a New Ideal World . EUROCRYPT (2) 2015: 532-560
Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas The Hidden Graph Model:Communication Locality and Optimal Resiliency with Adaptive Faults . ITCS 2015: 153-162
Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro Garbled RAM From One-Way Functions . STOC 2015: 449-458
Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas Secure Multi-Party Computation with Identifiable Abort . CRYPTO (2) 2014: 369-386
Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, Daniel Wichs Garbled RAM Revisited . EUROCRYPT 2014: 405-422
Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, Rafail Ostrovsky Achieving Privacy in Verifiable Computation with Multiple Servers - Without FHE and without Pre-processing . Public Key Cryptography 2014: 149-166
Chongwon Cho, Sanjam Garg, Rafail Ostrovsky Cross-Domain Secure Computation . Public Key Cryptography 2014: 650-668
Joshua Baron, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky How to withstand mobile virus attacks, revisited . PODC 2014: 293-302
Juan A. Garay, Clinton Givens, Rafail Ostrovsky, Pavel Raykov Fast and unconditionally secure anonymous channel . PODC 2014: 313-321
Joshua Lampkins, Rafail Ostrovsky Communication-Efficient MPC for General Adversary Structures . SCN 2014: 155-174
Steve Lu, Rafail Ostrovsky How to Garble RAM Programs . EUROCRYPT 2013: 719-734
Juan A. Garay, Clint Givens, Rafail Ostrovsky, Pavel Raykov Broadcast (and Round) Efficient Verifiable Secret Sharing . ICITS 2013: 200-219
Steve Lu, Rafail Ostrovsky Distributed Oblivious RAM for Secure Two-Party Computation . TCC 2013: 377-396
Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky, Ivan Visconti Impossibility Results for Static Input Secure Computation . CRYPTO 2012: 424-442
Eli Ben-Sasson, Serge Fehr, Rafail Ostrovsky Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority . CRYPTO 2012: 663-680
Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani Unconditionally-Secure Robust Secret Sharing with Compact Shares . EUROCRYPT 2012: 195-208
Yuval Ishai, Rafail Otrovsky, Hakan Seyalioglu Identifying Cheaters without an Honest Majority . TCC 2012: 21-38
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, Jurg Wullschleger Constant-Rate Oblivious Transfer from Noisy Channels . CRYPTO 2011: 667-684
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai Efficient Non-interactive Secure Computation . EUROCRYPT 2011: 406-425
Nishanth Chandran, Jual A. Garay, Rafail Ostrovsky Improved Fault Tolerance and Secure Computation on Sparse Networks . ICALP (2) 2010: 249-260
Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, Amit Sahai On Complete Primitives for Fairness. TCC-2010.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Extracting Corrolations. Preliminary version in FOCS 2009: 261-270
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.

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti Four-Round Concurrent Non-Malleable Commitments from One-Way Functions CRYPTO (2) 2017: 127-157
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti Concurrent Non-Malleable Commitments (and More) in 3 Rounds. CRYPTO (3) 2016: 270-299
Rafail Ostrovsky, Vanishree Rao, Alessandra Scafuro, Ivan Visconti Revisiting Lower and Upper Bounds for Selective Decommitments . TCC 2013: 559-578
Brett Hemenway, Steve Lu, Rafail Ostrovsky Correlated Product Security from Any One-Way Function . Public Key Cryptography 2012: 558-575
Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti Constructing Non-malleable Commitments: A Black-Box Approach . FOCS 2012: 51-60
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, 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.

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.

Wutichai Chongchitmate, Rafail Ostrovsky Circuit-Private Multi-key FHE . PKC (2) 2017: 241-270
Nirattaya Khamsemanan, Rafail Ostrovsky, William E. Skeith III On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols. SIAM J. Discrete Math. 30(1): 266-295 (2016)
Brett Hemenway, Rafail Ostrovsky, Silas Richelson, Alon Rosen Adaptive Security with Quasi-Optimal Rate . TCC (A1) 2016: 525-541
Brett Hemenway, Rafail Ostrovsky, Alon Rosen Non-committing Encryption from Φ hiding . TCC (1) 2015: 591-608
Rafail Ostrovsky, Anat Paskin-Cherniavsky, Beni Paskin-Cherniavsky Maliciously Circuit-Private FHE . CRYPTO (1) 2014: 536-553
Rafail Ostrovsky, Vanishree Rao, Ivan Visconti On Selective-Opening Attacks against Encryption Schemes . SCN 2014: 578-597
Brett Hemenway, Rafail Ostrovsky Building Lossy Trapdoor Functions from Lossy Encryption . ASIACRYPT (2) 2013: 241-260
Brett Hemenway, Rafail Ostovsky On Homomorphic Encryption and Chosen-Ciphertext Security . Public Key Crypotgraphy 2012: 52-65
Brett Hemenway, Rafail Ostovsky Extended-DDH and Lossy Trapdoor Functions . Public Key Crypotgraphy 2012: 627-643
Bret Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wooters Public Key Locally Decodable Codes with Short Keys . 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. ASIACRYPT 2011: 70-88.
Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky Equivalence of Uniform Key Agreement and Composition Insecurity . CRYPTO 2010: 447-464.
Nishanth Chandran, Rafail Ostrovsky, Willim E. Skeith III Public Encryption with Efficient Amortized Updates. SCN 2010: 17-35.
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

Yuval Ishai, Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky Private Large-Scale Databases with Distributed Searchable Symmetric Encryption . CT-RSA 2016: 90-107 .
Brett Hemenway, Steve Lu, Rafail Ostrovsky, William Welser IV High-Precision Secure Computation of Satellite Collision Probabilities . SCN 2016: 169-187.
Farhad Hormozdiari, Jong Wha J. Joo, Akshay Wadia, Feng Guan, Rafail Ostrovsky, Amit Sahai, Eleazar Eskin Privacy preserving protocol for detecting genetic relatives using rare variants . Bioinformatics 30(12): 204-211 (2014).
Abishek Kumarasubramanian, Rafail Ostrovsky, Omkant Pandey, Akshay Wadia Cryptography Using Captcha Puzzles . Public Key Cryptography 2013: 89-106 .
Ran Gelles, Rafail Ostrovsky, Kina Winoto Multiparty Proximity Testing with Dishonest Majority from Equality Testing . ICALP 2012: 537-548
Joshua Baron, Karim El Defawy, Kirill Minkovich, Rafail Ostrovsky, Eric Tressler 5PM: Secure Pattern Matching. Preliminary version appeared in SCN 2012 PP: 222-240. Full version appeared in Journal of Computer Security 21(5): 601-625 (2013)
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schafner Position-Based Quantum Cryptography: Impossibility and Constructions . Preliminary version appeared in Crypto 2011:429-446.Full version appeared in SIAM J. Comput. 43(1): 150-178 (2014) ).
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky Postion Based Cryptography. CRYPTO-2009. 391-407 (In addition, you can get [ppt] ).
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

Hardware-based Security

Saikrishna Badrinarayanan, Dakshita Khurana, Rafail Ostrovsky, Ivan Visconti Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs . EUROCRYPT (1) 2017: 382-411
Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti, Akshay Wadia Universally Composable Secure Computation with (Malicious) Physically Uncloneable Functions. EUROCRYPT 2013: 702-718

Systems Security

Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas Provably Secure Virus Detection: Using The Observer Effect Against Malware. ICALP 2016: 32:1-32:14

Publications: Search and Analysis of High-Dimensional Data

Algorithms for Streaming Data

David Felber, Rafail Ostrovsky A Randomized Online Quantile Summary in O((1/epsilon) \log(1/epsilon)) Words Theory of Computing 13(1): 1-17 (2017). Preliminary version in APPROX-RANDOM 2015: 775-785
David Felber, Rafail Ostrovsky Variablity in Data Streams PODS 2016
Vladimir Braverman, Rafail Ostrovsky, Gregory Vorsanger Weighted sampling without replacement from data streams . Inf. Process. Lett. 115(12): 923-926 (2015)
Vladimir Braverman, Rafail Ostrovsky, Alan Roytman Zero-One Laws for Sliding Windows and Universal Sketches . APPROX-RANDOM 2015: 573-590
Ran Gelles, Rafail Ostrovsky, Alan Roytman Efficient Error-Correcting Codes for Sliding Windows . SOFSEM 2014: 258-268
Vladimir Braverman, Rafail Ostrovsky Approximating Large Frequency Moments with Pick-and-Drop Sampling . APPROX-RANDOM 2013: 42-57
Vladimir Braverman, Rafail Ostrovsky Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams. APPROX-RANDOM 2013: 58-70
Vladimir Braverman, Ran Gelles, Rafail Ostrovsky How to Catch L 2-Heavy-Hitters on Sliding Windows . Preliminary version appeared in COCOON 2013 pp: 638-650. Full version appeared in Theor. Comput. Sci. 554: 82-94 (2014)
Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik How Hard Is Counting Triangles in the Streaming Model? . ICALP (1) 2013: 244-254
Matthew K. Franklin, Ren Gelles,Rafail Ostrovsky,Leonard J.Schulman Optimal Coding for Streaming Authentication and Interactive Communication . Preliminary version appeared in CRYPTO 2013 pp: 258-276. Full version appeared in IEEE Trans. Information Theory 61(1): 133-145 (2015)
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku Streaming k-means on Well-Clusterable Data. SODA 2011: 26-40
Vladimir Braverman, Rafail Ostrovsky Effective Computations on Sliding Windows . SIAM J. Comput. 39(6): 2113-2131 (2010)
Vladimir Braverman, Rafail Ostrovsky Measuring Independence of Datasets. STOC-2010.
Vladimir Braverman, Rafail Ostrovsky Zero-One Frequency Laws. STOC-2010.
Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, Rafail Ostrovsky AMS Without 4-Wise Independence on Product Domains.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.)
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.

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.

Publications: Distributed Control Theory, Network Algorithms and Combinatorial Algorithms

Admission Control and Network Routing Algorithms

Paul Bunn, Rafail Ostrovsky Secure End-to-End Communication with Optimal Throughput and Resilience against Malicious Adversary , DISC 2013: 403-417
Paul Bunn, Rafail Ostrovsky Asynchronous Throughput-Optimal Routing in Malicious Networks , ICALP 2010: 236-248
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)
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.

Distributed Algorithms with severely limited memory per processor

Rafail Ostrovsky, Mor Perry, Will Rosenbaum Space-Time Tradeoffs for Distributed Verification , SIROCCO 2017: 53-70
Mor Baruch, Rafail Ostrovsky, Will Rosenbaum Brief Announcement: Space-Time Tradeoffs for Distributed Verification , PODC 2016: 357-359
Milan Bradonjic, Eddie Kohler, and Rafail Ostrovsky Near-Optimal Radio Use For Wireless Network Synchronization , ALGOSENSORS-2009. 15-28 (In addition, you can get [talk slides].
Mor Baruch, Rafail Ostrovsky, Will Rosenbaum Brief Announcement: Space-Time Tradeoffs for Distributed Verification , PODC 2016: 357-359
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).
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

Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky Coding for Interactive Communication Correcting Insertions and Deletions , ICALP 2016: 61:1-61:14
Rafail Ostrovsky, Anat Paskin-Cherniavsky Locally Decodable Codes for Edit Distance , ICITS 2015: 236-249
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky Locally Updatable and Locally Decodable Codes , TCC 2014: 489-514
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky Edge Fault Tolerance on Sparse Networks , ICALP 2012: 452-463
Juan A. Garay, Clint Givens, Rafail Ostovsky Secure Message Transmission with Small Public Discussion , Preliminary version appeared in IWCC 2011:126-141 IEEE Trans. Full version appeared in Information Theory 60(4): 2373-2390 (2014)
Juan A. Garay, Clint Givens, Rafail Ostrovsky Secure Message Transmission with Small Public Discussion , Preliminary version appeared in Eurocrypt 2010:177-196. Full version appeared in IEEE Trans. Information Theory 60(4): 2373-2390 (2014)
Brett Hemenway, Rafail Ostrovsky Public-Key Locally-Decodable Codes. CRYPTO 2008: 126-143
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

Rafail Ostrovsky, Will Rosenbaum Fast Distributed Almost Stable Matchings . PODC 2015: 101-108
Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum A Stable Marriage Requires Communication . SODA 2015: 1003-1017
Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky Deterministic and Energy-Optimal Wireless Synchronization . Preliminary version appeared in DISC 2011:237-251. Full version appeared in TOSN 11(1): 13:1-13:25 (2014)
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

Rafail Ostrovsky, Yuval Rabani, Arman Yousefi Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration . SODA 2017: 154-169
Joshua Baron, Yuval Ishai, Rafail Ostrovsky On Linear-Size Pseudorandom Generators and Hardcore Functions . Preliminary version appeared in COCOON 2013 pp: 169-181. Full version appeared in Theor. Comput. Sci. 554: 50-63 (2014)
Brett Hemenway, Rafail Ostrovsky, Mary Wootters Local Correctability of Expander Codes . Preliminary version appeared in ICALP 2013 pp: 540-551. Full version appeared in Inf. Comput. 243: 178-190 (2015)
Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman Robust Pseudorandom Generators . ICALP (1) 2013: 576-588
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),

Short Bio

Rafail Ostrovsky is a Distinguished Professor of Computer Science and Distinguished Professor of Mathematics at UCLA. Prof. Ostrovsky joined UCLA in 2003 as a full tenured professor, coming from Bell Communications Research where he was a Senior Research Scientist. Prof. Ostrovsky graduated 28 Doctoral Students and hosted 7 Postdoctoral Fellows. He is currently advising three Ph.D. students. Prior to beginning his career at Bellcore, he was an NSF Mathematical Sciences Postdoctoral Research Fellow at UC Berkeley. Dr. Ostrovsky received his Ph.D. in computer science from MIT in 1992, (advisor: Silvio Micali, thesis: Software Protection and Simulation on Oblivious RAM), supported by IBM Graduate Fellowship. Prof. Ostrovsky is a Fellow of ACM; Fellow of IEEE; Fellow of IACR; and a foreign member of Academia Europaea. He has 15 U.S. patents issued and over 300 papers published in refereed journals and conferences. Dr. Ostrovsky has served as a Chair of the IEEE Technical Committee on Mathematical Foundations of Computing from 2015-2018 and has served on over 40 international conference Program Committees including serving as PC chair of FOCS 2011. He is a member of the Editorial Board of Journal of ACM; Editorial Board of Algorithmica; and the Editorial Board of Journal of Cryptology and is the recipient of multiple awards and honors including the 2017 IEEE Computer Society Technical Achievement Award and the 2018 RSA Excellence in the Field of Mathematics Award. At UCLA, Prof. Ostrovsky heads the Center of Information and Computation Security (CICS) a multi-disciplinary Research Center (http://www.cs.ucla.edu/security/) at Henry Samueli School of Engineering and Applied Science.

Selected Honors and Awards

Dr. Ostrovsky's awards include:

JP Morgan Chase Faculty Award, 2021 ;
Google Faculty Award, 2020;
JP Morgan Chase Faculty Award, 2020 ;
Elevated to the title of "Distinguished Rrofessor" at UCLA (by Chancellor Gene D. Block), 2020;
JP Morgan Chase Faculty Award, 2019;
Foreign Member of Academia Europaea, inducted in 2019;
2018 RSA Conference Excellence in the field of mathematics lifetime achievement award;
2017 IEEE Fellow;
2017 IEEE Computer Society Technical Achievement Award;
2014 Rosalinde and Arthur Gilbert Foundation Research Award;
2013 IACR Fellow,
2012 Pazy Memorial Research Award;
2008 Best Paper Award of International Conference on Computing and Combinatorics (COCOON-2008);
2006 and 2005 Xerox Corporate Innovation Faculty Awards;
2006 IBM Faculty Award;
2006 Xerox Corporation Distinguished Lecture Series;
2005 Teradata Faculty Research Award;
2005 Distinguished Cryptographer of the Year Lecture Series NTT Labs, Japan;
2004 OKAWA Foundation Research Award;
1999-2002: three SAIC Awards for the best published work of the year (1999, 2001, 2002) in computer science and mathematics;
1996 Bellcore Prize for excellence in research;
1993 Henry Taub Prize; and
multiple papers solicited to journal special issues dedicated to highest PC-ranked STOC/FOCS articles.

Some Current and Past Professional Activities

Current:

The National Academies of Sciences, Engineering, and Medicine, ad-hoc Committe on Future of Encryption August 2020 -- present
Steering Commmittee member IEEE FOCS Conference 2018--present.
Johns Hopkins University Computer Science Department External Advisory Board 2017--present.
Editorial Board member Journal of ACM 2014--present.
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.
Advisory Board Member UCLA Advisory Board On Privacy and Data Protection 2010--present.
Board Member Stealth Software Technologies, Inc. 2008--present.

Past:

Member of the Theory of Computing Committee: Ad hoc committee to combat harassment and discrimination in the Theory of Computing community April 2018--2019.
General Chair FOCS 2017
Chair of the IEEE Technical Committee on Mathematical Foundations of Computing 2015-2018.
General Chair FOCS 2016
General Chair FOCS 2015
Program Committee Chair FOCS 2011 (October 22-25, 2011 in Palm Springs, CA.)
Steering Committee member UC Privacy and Information Security Steering Committee,
(Appointed by University of California President, Mark G. Yudof, see Announcement.) 2010--2014.
Program Committee 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 NSF-FUNDED program dedicated to Cybersecurity. September - December, 2006. Over 200 participatns.
Co-organizer, IPAM Workshop Locally decodable codes, PIR, privacy-preserving data-mining, and encryption with special properties. October 25 - 28, 2006, IPAM.
Co-organizer, IPAM Workshop Foundations of secure multi-party computation and zero-knowledge and its applications. November 13 - 17, 2006, IPAM.
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 2019 , Darmstadt, Germany.
Program committee member Eurocrypt 2017 30 April to 4 of May, 2017, Paris,.
Program committee member PKC 2016 March 2016.
Program committee member FIFTEENTH IMA INTERNATIONAL CONFERENCE ON CRYPTOGRAPHY AND CODING December 2015.
Program committee member ITCS-2012 Boston, January 8-10, 2012.
Program committee member PODS-2011.
Program committee member ICALP-2011.
Program committee member EUROCRYPT-2011.
Program committee member CT-RSA 2011.
Program committee member TCC-2010: Seventh Theory of Cryptography Conference, 2010.
Program committee member EUROCRYPT-2009 Cologne, 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.

Recent Invited Talks (from September 2005)

Invited talk: "Stewardship of Private Data with Cryptography" Technological Advisory Council of the Federal Trade Commision (FCC), August 12, 2020.
Invited talk: "Keeping the Internet Safe" Board on Mathematical Sciences and Analytics (BMSA) within the National Academies of Sciences, Engineerng and Medicine, March 17, 2020
Invited talk: Distinguished Lecture Series, Cloud Security, Texas A&M University, Computer Science Department, October, 2018.
Invited Keynote Lecture: workshop on "Mathematics of Information-Theoretic Cryptography" Institute of Mathematical Sciences (IMS) of National University of Singapore and Nanyang Technological University, Singapore, September 19-30, 2016.
Invited Keynote Speaker Bay Area Crypto Day, "Adaptively secure garbled circuits from AES" Stanford, May 2nd, 2016.
Invited talk: Distinguished Lecturer of the Year, Georgia Institute of Technology, Computer Science Department, December, 2015.
Invited talk: Distinguished Lecturer of the Year, Johns Hopkins University Computer Science Department, November 13, 2014.
Invited talk: Big Thinker Lecture Series Yahoo Labs, Sunnyvale, Califor nia, March 19, 2014.
Invited talk: Novel Privacy-Enhancing Technologies UCLA Henry Samueli School of Enginnering and Applied Science, 2012 Technology Forum, March 13, 2012.
Invited talk: NIST Privacy Enhancing Crytpography Meeting By invitation only Workshop for Industry, Governmnet and Academia, November 8, 2011.
Invited talk: Success Stories and Challanges in Cybersecurity September 21, 2011, Insitute of Pure and Applied Mathematics, Los Angeles.
Invited Scholar: U.S. Air Force Third Annual National Security Scholars Conference. April 26, 2011.
(Invited by the Honorable Michael B. Donley, Secretary of the Air Force.)
Invited talk: Mathematics of Information-Theoretic Cryptography IPAM, UCLA, March 3, 2011.
Invited panelist: UCLA 2011 Technology Forum March 1, 2011.
Invited talk: Trends in Theoretical Cryptography (TTC 2011) January 10-12, 2011, Tsinghua University, Beijing, China.
Invited talk: MIT CSAIL Theory Colloquium December 7, 2010.
Invited talk: MIT Qunatum Information Processing (QIP) seminar, December 6, 2010.
Invited talk: Caltech Computing and Mathematical Sciences Lecture Series Novermber 17, 2010.
Invited talk: Aerosapce Corporation Information Assurance Technology Department, Computers and Software Division, Octover 7, 2010.
Invited talk: 2010 Lockheed-Martin Anti-Tamper Conference, August 26, 2010, Forth Worth, Texas.
Invited talk: Symantec Research Labs's Seminar - Security in the Cloud, Symantec 900 Corporate Pointe, Culver City, CA 90230, July 29, 2010.
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 course Bertinoro, 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.

Current and Former Students, Postdocs and Visitors

Current Ph.D. Students:

Akash Shah (CS)
Eli Jaffe (CS)
Kevin Garbe (CS)

Doctoral Students (listed by graduation year):

Saikrishna Badrinarayanan (CS Ph.D. 2020, now researcher at LinkedIn.)
Arman Yousefi (CS Ph.D. 2018, now researcher at Google)
Dakshita Khurana (CS Ph.D. 2018, now tenure track faculty at UIUC CS Depatment)
Prabhanjan Ananth (CS Ph.D. 2017, now assistant professor at USCB CS Departmnet))
Will Rosenbaum (MATH Ph.D. 2016, now tenure-track faculty at Amherst Colledge CS Departmnet)
Wutichai Chongchitmate (MATH Ph.D. 2016, (now tenure-track faculty at Mathematics Departmnet Chulalongkorn University, Thailand.)
David Felber (CS Ph.D. 2015, now researcher at Google.)
Alan Roytman (CS Ph.D. 2014, now postdoctoral researcher at Tel-Aviv University Computer Science)
Ran Gelles (CS Ph.D. 2014, now tenure-track faculty at Bar-Ilan University CS Departmnet.)
Silas Richelson (MATH Ph.D. 2014, now tenure-track faculty at UC Reiverside CS Departmnet.)
Akshay Wadia (CS Ph.D. 2014, now researcher at Silicon-Valley Startup)
Chongwon Cho (CS Ph.D. 2013, now researcher at Stealth Software Technologies, Inc.)
Sanjam Garg (CS Ph.D. 2012), now a assosiate professor at U.C. Berkely EECS.) (As my student, Sanjam won 2013 ACM Doctoral Dissertation Award)
Cheng-Keui Lee (CS Ph.D. 2012, now Security Researcher, LinkedIn)
Abhishek Jain (CS Ph.D., 2012, now assosiate professor at Johns Hopkins University CS Departmnet.)
Hakan Seyalioglu (Math Ph.D., 2012, now researcher at Google.)
Joshua Baron (Math Ph.D., 2012, now DARPA Program Manager.)
Clint Givens (Math Ph.D., 2012, now tenure track Math faculty at University of Science and Arts of Oklahoma)
Vladimir Braverman (C.S. Ph.D. 2011, C.S. tenured faculty at Johns Hopkins University.)
Nishanth Chandran (C.S. Ph.D. 2011, now a researcher at MSR India)
Omkant Pandey (CS Ph.D., 2010, nowa tenure track faculty at Stony Brook Computer Sccience Department.)
Brett Hemenway (Math Ph.D., 2010, now a tenure-track research faculty at U. Penn.)
Paul Bunn (Math Ph.D., 2010, researcher at Google.)
Ryan Moriarty (CS Ph.D., 2010, entrepreneur in Silicon Valley. Startups: apprats, flotate.)
Vipul Goyal (CS Ph.D., 2009, now a tenure-track associate professor at CMU.)
Steve Lu (Math Ph.D., 2009, researcher at Stealth Software Technologies, Inc.)
William Skeith (Math Ph.D., 2007; CS tenured associated professor at City College of NY).
Jonathan Katz (CS Ph.D. 2002, Full Professor of CS at U. of Marylandm, head of their cyber-security center.)

Hosted Postdoctoral Researchers:

Wutichai Chongchitmate (postdoctoral researcher 2016 -- 2017; now tenure-track faculty at Chulalongkorn University, Thailand.)
Silas Richelson (postdoc 2014 -- 2015; now assistant professor at UC Riverside Computer Science)
Anat Paskin (postdoc 2012 -- 2015; now a tenure-track faculty at Ariel University, Israel)
Vassilis Zikas (postdoc 2012 -- 2015; now associated professor at Perdue)
Alessandra Scafuro (postdoc 2012 -- 2015; now tenure-track faculty at North Carolina State University. )
Bhavana Kanukurthi (postodc 2011 -- 2014; now a tenured faculty at Indian Institute of Science (IISC), Bangalore, India)
Jens Groth (2005-2007): Now full professor at University College of London.

Visitors:

Prof. Vassilis Zikas (short term visits 2016 -- present)
Michele Ciampi (Decemmber 2015 -- December 2016)
Luisa Siniscalchi (December 2016 -- December 2016)
Dr. Juan Garay (short term visits 2010 -- ppresent)
Prof. Ivan Vinsconti (several short, medium and long term visits from 2009 -- present, including spending several sabbaticals))
Prof. Yuval Ishai (Several sabbaticals, short and long term visits 2009 -- present)
Prof. Giuseppe (a.k.a. Pino) Persiano (short term visit 2012-- present)
Prof. Yuval Rabani (short term visits 2009 -- present)
Prof. Eyal Kushulevitz (sabbatical, short term visits, 2011 -- present)
Dr. Serge Fehr (short term visit, 2011)
Prof. Alon Rosen (summer visit 2010)
Claudio Orlandi (6-month visit from Aaharus, 2010)

Useful and Fun Links

Useful:

Fun:

Contact Info

Professor Rafail Ostrovsky

University of California, Los Angeles

Department of Computer Science

Office 475, Engineering VI

Los Angeles CA 90095-1596

(310) 206-5283 (office)

(310) 825-7578 (department fax, include cover page)

Email: my first name (at) cs.ucla.edu
Please read this before emailing me.

Administrative assistant: Ms. Osanna Kazarian;
Phone: (310) 825-1322;
Email: osannak (at) cs.ucla.edu