Rafail Ostrovsky

Norman E. Friedmann 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 Biography
Teaching
Research Interests
Publications by Year
Publications by Topic
Selected Honors and Awards
Professional Activities
Invited Talks
Students and Postdocs
Useful & Fun Links
Contact Information
Directions to my UCLA office

Rafail Ostrovsky holds the Norman E. Friedmann Endowed Chair in Knowledge Sciences at the UCLA Samueli School of Engineering and is a Distinguished Professor of Computer Science and Mathematics at UCLA. He is a Fellow of the National Academy of Inventors (NAI 2024), the American Association for the Advancement of Science (AAAS 2021), the Association for Computing Machinery (ACM 2021), the Institute of Electrical and Electronics Engineers (IEEE 2017), and the International Association for Cryptologic Research (IACR 2013), and a foreign member of Academia Europaea (2019). He received the 2022 W. Wallace McDowell Award, the IEEE Computer Society’s highest technical achievement award. His honors also include the 2018 RSA Award for Excellence in Mathematics (also known as the RSA Prize), the 2017 IEEE Computer Society Edward J. McCluskey Technical Achievement Award, and the 1993 Henry Taub Prize. He chaired the IEEE Technical Committee on Mathematical Foundations of Computing from 2015 to 2018 and the FOCS 2011 Program Committee. He serves on the editorial boards of the Journal of the ACM and Algorithmica.

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

Teaching

Fall 2026:

Recent courses taught at UCLA:

CS183 Introduction to Cryptography;
CS282A/M209A Foundations 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;

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.
Papers published in 2025 and 2026 are marked .

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

Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication. ITC 2025: 6:1-6:23
Brett Hemenway Falk, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang GigaDORAM: Breaking the Billion Address Barrier. USENIX Security Symposium 2023: 3871-3888
Brett Hemenway, Daniel Noble, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead. TCC (1) 2023: 441-470
Wutichai Chongchitmate, Yuval Ishai, Steve Lu, Rafail Ostrovsky PSI from Ring-OLE. CCS 2022: 531-545
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky CNF-FSS and Its Applications. Public Key Cryptography (1) 2022: 283-314
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky 3-Party Distributed ORAM from Oblivious Set Membership. SCN 2022: 437-461
Surya Addanki, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky, Antigoni Polychroniadou Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares. SCN 2022: 516-539
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, Angelos Stavrou Streaming and Unbalanced PSI from Function Secret Sharing. SCN 2022: 564-587
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky Alibi: A Flaw in Cuckoo-Hashing Based Hierarchical ORAM Schemes and a Solution. EUROCRYPT (3) 2021: 338-369
Paul Bunn, Jonathan Katz, Eyal Kushilevitz, Rafail Ostrovsky Efficient 3-Party Distributed ORAM. SCN 2020: 215-232
Ariel Hamlin, Rafail Ostrovsky, Mor Weiss, Daniel Wichs Private Anonymous Data Access. EUROCRYPT (2) 2019: 244-273
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky Private Set Intersection with Linear Communication from General Assumptions. WPES@CCS 2019: 14-25
Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky DURASIFT: A Robust, Decentralized, Encrypted Database Supporting Private Searches with Complex Policy Controls. WPES@CCS 2019: 26-36
George Alter, Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky Computing Statistics from Private Data. Data Science Journal 17: 31 (2018)
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 E. Skeith III Communication Complexity in Algebraic Two-Party Protocols. CRYPTO 2008: 379-396
Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William E. Skeith III Public Key Encryption That Allows PIR Queries. Preliminary version appeared in CRYPTO 2007: 50-67
Rafail Ostrovsky, Omkant Pandey, Amit Sahai Private Locally Decodable Codes. Preliminary version appeared in ICALP 2007: 387-398
Rafail Ostrovsky, William Skeith A Survey of Single-Database Private Information Retrieval: Techniques and Applications. Preliminary version appeared in Proceedings of the Public Key Cryptography 2007 conference, pp. 393-411. (PKC-2007). Full version appeared as a book chapter in "Homeland Security Technology Challenges: From Sensing and Encrypting to Mining and Modeling", Franceschetti, Giorgio and Grossi, Marina (EDT), Artech House publishers.
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) 79-88.
Journal version: Journal of Computer Security 19(5): 895-934 (2011). [powerpoint presentation]
Rafail Ostrovsky, William Skeith Private Searching on Streaming Data. Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) 223-240 Springer-Verlag/IACR Lecture Notes in Computer Science. Full version appeared in Journal of Cryptology Volume 20:4, pp. 397-430, October 2007. [Journal]
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky Sufficient Conditions for Collision-Resistant Hashing.
In Proceedings of Second Theory of Cryptography Conference (TCC 2005) 445-456 Springer-Verlag Lecture Notes in Computer Science, 2005
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Batch Codes and Their Applications. In addition, can get [powerpoint presentation].
In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC-2004) 262-271.
Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano Public Key Encryption with Keyword Search. In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2004) 506-522 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 Vol. 1807, pp. 104-121.
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 Vol 1807, pp. 122-138.
Giovanni Di 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) 91-100. Journal version: Universal Service-Providers for Private Information Retrieval. 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) 364-373
Rafail Ostrovsky, Victor Shoup Private Information Storage. In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97) 294-303
Rafail Ostrovsky Software Protection and Simulation on Oblivious RAMs. Preliminary version appeared as a single-author paper in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90) pp. 514-523. Full version became my M.I.T. Ph.D. thesis in 1992. Journal version appeared in Journal of the ACM, Vol. 43, No. 3, May 1996, pp.431-473 co-authored with Oded Goldreich [Journal]

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

Yuval Ishai, Rafail Ostrovsky, Akash Shah Zero-Knowledge RAM: Doubly Efficient and Black-Box. EUROCRYPT (4) 2025: 363-395
Yuval Ishai, Eyal Kushilevitz, Varun Narayanan, Rafail Ostrovsky, Akash Shah Query-Reusable Proof Systems. EUROCRYPT (4) 2025: 333-362
Yuval Ishai, Rafail Ostrovsky, Akash Shah Succinct Arguments for RAM Programs via Projection Codes. CRYPTO (2) 2023: 159-192
Samuel Dittmer, Karim Eldefrawy, Stéphane Graham-Lengrand, Steve Lu, Rafail Ostrovsky, Vitor Pereira Boosting the Performance of High-Assurance Cryptography: Parallel Execution and Optimizing Memory Access in Formally-Verified Line-Point Zero-Knowledge. CCS 2023: 2098-2112
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One. CCS 2022: 829-841
Nicholas Franzese, Jonathan Katz, Steve Lu, Rafail Ostrovsky, Xiao Wang, Chenkai Weng Constant-Overhead Zero-Knowledge for RAM Programs. CCS 2021: 178-191
Samuel Dittmer, Yuval Ishai, Rafail Ostrovsky Line-Point Zero Knowledge and Its Applications. ITC 2021: 5:1-5:24
Ohad Barta, Yuval Ishai, Rafail Ostrovsky, David J. Wu On Succinct Arguments and Witness Encryption from Groups. CRYPTO (1) 2020: 776-806
Dakshita Khurana, Rafail Ostrovsky, Akshayaram Srinivasan Round Optimal Black-Box "Commit-and-Prove". TCC (1) 2018: 286-313
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, Giuseppe Persiano, Ivan Visconti Impossibility of Black-Box Simulation Against Leakage Attacks. CRYPTO (2) 2015: 130-149
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
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
Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth Succinct Non-interactive Arguments via Linear Interactive Proofs. TCC 2013: 315-333
Journal version: Journal of Cryptology 35(3), Article 15 (2022).
Joshua Baron, Rafail Ostrovsky, Ivan Visconti Nearly Simultaneously Resettable 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
Journal version: Journal of Cryptology 27(3): 506-543 (2014).
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 Ishai, 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) 21-30. Full version invited and accepted to SIAM Journal on Computing (SICOMP) special issue devoted to STOC-2007.
Published journal version: Zero-Knowledge Proofs from Secure Multiparty Computation, SIAM Journal on Computing 39(3): 1121-1152 (2009).
Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions. ASIACRYPT 2007: 444-459
Jens Groth, Rafail Ostrovsky, Amit Sahai Non-interactive Zaps and New Techniques for NIZK. In Proceedings of Advances in Cryptology, (CRYPTO-2006) 97-111 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) 339-358 Springer-Verlag/IACR Lecture Notes in Computer Science.
Journal version: New Techniques for Noninteractive Zero-Knowledge. Journal of the ACM 59(3), Article 11: 11:1-11:35 (2012). This journal version also incorporates Non-interactive Zaps and New Techniques for NIZK (CRYPTO 2006: 97-111).
Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin Identity-Based Zero-Knowledge. In addition, you can get [SCN-talk (powerpoint)].
In Proceedings of Security in Communication Networks: 4th International Conference, (SCN 2004) 180-192, Amalfi, Italy, September 8-10, 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) 566-598 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 (CRYPTO-99), pp. 485-502, Springer-Verlag Lecture Notes in Computer Science, Vol 1666.
Oded Goldreich, Rafail Ostrovsky, Erez Petrank Computational Complexity and Knowledge Complexity. Preliminary version appeared in the Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) 534-543 Full version in SIAM Journal on Computing, 27(4):1116-1141, August 1998.
Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Interactive Hashing Simplifies Zero-Knowledge Protocol Design. In Proceedings of (EUROCRYPT-93) 267-273 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) 3-17
Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions. Preliminary version appeared in Proceedings of advances in cryptology (CRYPTO-92) 196-214 Springer-Verlag Lecture Notes in Computer Science. Final journal version: Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation. Journal of Cryptology 11(2): 87-108 (1998).
Rafail Ostrovsky One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs. Structure in Complexity Theory Conference 1991: 133-138. In Proceedings of 6th Annual Structure in Complexity Theory Conference (STRUCTURES-91) June 30 -- July 3, 1991, Chicago. pp. 133-138
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) 352-359 November 11-14, 1991, Fujiyoshida, Yamanashi, Japan.
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

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner Position-Based Quantum Cryptography: Impossibility and Constructions. Preliminary version appeared in Crypto 2011: 429-446. Full version appeared in SIAM Journal on Computing 43(1): 150-178 (2014)
Plenary talk at QIP 2011. [Journal]
Vipul Goyal, Abhishek Jain, Rafail Ostrovsky Password-Authenticated Session-Key Generation on the Internet in the Plain Model. Preliminary version appeared in Crypto 2010: 277-294.
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin Privacy Amplification with Asymptotically Optimal Entropy Loss. Preliminary version appeared in STOC 2010. Full version appeared in Journal of the ACM 61(5), Article 29: 29:1-29:28 (2014)
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky Position-Based Cryptography. CRYPTO-2009. 391-407 (In addition, you can get [ppt].)
Journal version: SIAM Journal on Computing 43(4): 1291-1341 (2014).
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM Journal on Computing 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) 465-485 Springer-Verlag/IACR Lecture Notes in Computer Science.
Journal version: Sequential Aggregate Signatures, Multisignatures, and Verifiably Encrypted Signatures Without Random Oracles. Journal of Cryptology 26(2): 340-373 (2013).
Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith Secure Authentication Using Biometric Data. In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2005) 147-163 Springer-Verlag/IACR Lecture Notes in Computer Science.
Jonathan Katz, Rafail Ostrovsky, Moti Yung Forward Secrecy in Password-Only Key Exchange Protocols. In Proceedings of Security in Communication Networks 2002 conference (SCN-2002) 29-44 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) 475-494 Springer-Verlag/IACR Lecture Notes in Computer Science.
Journal version: Efficient and Secure Authenticated Key Exchange Using Weak Passwords. Journal of the ACM 57(1), Article 3: 3:1-3:39 (2009). This journal version also incorporates Forward Secrecy in Password-Only Key Exchange Protocols (SCN 2002: 29-44).
For a non-technical discussion, see [New Scientist 2001] article regarding this work.
Ari Juels, Michael Luby, Rafail Ostrovsky Security of Blind Digital Signatures. In Proceedings of advances in cryptology, (CRYPTO-97) 156-164 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) 228-245 Springer-Verlag Lecture Notes in Computer Science.

Secure Two-Party and Multi-Party Computation

Samuel Dittmer, Rafail Ostrovsky On Randomness Complexity of 1-Private Protocols. ICALP 2026: 79:1-79:23
Samuel Dittmer, Rohit Nema, Rafail Ostrovsky Linear Secret-Shared Shuffle with Malicious Security. CRYPTO (8) 2026: 296-328
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Hendrik Waldner Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions. EUROCRYPT (5) 2025: 331-359
Michele Ciampi, Ankit Kumar Misra, Rafail Ostrovsky, Akash Shah Black-Box Constant-Round Secure 2PC with Succinct Communication. EUROCRYPT (5) 2025: 360-389
Vipul Goyal, Junru Li, Rafail Ostrovsky, Yifan Song Towards Building Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing. CRYPTO (4) 2025: 70-104
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication. ITC 2025: 6:1-6:23
Mark Blunk, Paul Bunn, Samuel Dittmer, Steve Lu, Rafail Ostrovsky Linear-Time Secure Merge in O(loglog n) Rounds. ITC 2025: 7:1-7:23
Nishanth Chandran, Juan A. Garay, Ankit Kumar Misra, Rafail Ostrovsky, Vassilis Zikas Adaptive Security, Erasures, and Network Assumptions in Communication-Local MPC. TCC (4) 2024: 293-326
Vipul Goyal, Junru Li, Ankit Kumar Misra, Rafail Ostrovsky, Yifan Song, Chenkai Weng Dishonest Majority Constant-Round MPC with Linear Communication from DDH. ASIACRYPT (6) 2024: 167-199
Brett Hemenway Falk, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang GigaDORAM: Breaking the Billion Address Barrier. USENIX Security Symposium 2023: 3871-3888
Brett Hemenway, Daniel Noble, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead. TCC (1) 2023: 441-470
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Hendrik Waldner List Oblivious Transfer and Applications to Round-Optimal Black-Box Multiparty Coin Tossing. CRYPTO (1) 2023: 459-488
Vipul Goyal, Chen-Da Liu-Zhang, Rafail Ostrovsky Asymmetric Multi-Party Computation. ITC 2023: 6:1-6:25
Wutichai Chongchitmate, Yuval Ishai, Steve Lu, Rafail Ostrovsky PSI from Ring-OLE. CCS 2022: 531-545
Nishanth Chandran, Pouyan Forghani, Juan A. Garay, Rafail Ostrovsky, Rutvik Patel, Vassilis Zikas Universally Composable Almost-Everywhere Secure Computation. ITC 2022: 14:1-14:25
Journal version: Journal of Cryptology 39(1): 12 (2026)
Brett Hemenway Falk, Rohit Nema, Rafail Ostrovsky A Linear-Time 2-Party Secure Merge Protocol. CSCML 2022: 408-427
Journal version: Journal of Computer and System Sciences 137: 37-49 (2023); published as "Linear-time 2-party secure merge from additively homomorphic encryption"
Michele Ciampi, Rafail Ostrovsky, Hendrik Waldner, Vassilis Zikas Round-Optimal and Communication-Efficient Multiparty Computation. EUROCRYPT (1) 2022: 65-95
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky CNF-FSS and Its Applications. Public Key Cryptography (1) 2022: 283-314
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky 3-Party Distributed ORAM from Oblivious Set Membership. SCN 2022: 437-461
Surya Addanki, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky, Antigoni Polychroniadou Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares. SCN 2022: 516-539
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, Angelos Stavrou Streaming and Unbalanced PSI from Function Secret Sharing. SCN 2022: 564-587
Xiaoqi Duan, Vipul Goyal, Hanjun Li, Rafail Ostrovsky, Antigoni Polychroniadou, Yifan Song ACCO: Algebraic Computation with Comparison. CCSW 2021: 21-38
Brett Hemenway Falk, Rafail Ostrovsky Secure Merge with O(n log log n) Secure Operations. ITC 2021: 7:1-7:29
Vipul Goyal, Hanjun Li, Rafail Ostrovsky, Antigoni Polychroniadou, Yifan Song ATLAS: Efficient and Scalable MPC in the Honest Majority Setting. CRYPTO (2) 2021: 244-274
Arka Rai Choudhuri, Michele Ciampi, Vipul Goyal, Abhishek Jain, Rafail Ostrovsky Oblivious Transfer from Trapdoor Permutations in Minimal Rounds. TCC (2) 2021: 518-549
Juan A. Garay, Aggelos Kiayias, Rafail M. Ostrovsky, Giorgos Panagiotakos, Vassilis Zikas Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era. EUROCRYPT (2) 2020: 129-158
Karim Eldefrawy, Seoyeon Hwang, Rafail Ostrovsky, Moti Yung Communication-Efficient (Proactive) Secure Computation for Dynamic General Adversary Structures and Dynamic Groups. SCN 2020: 108-129
Paul Bunn, Jonathan Katz, Eyal Kushilevitz, Rafail Ostrovsky Efficient 3-Party Distributed ORAM. SCN 2020: 215-232
Samuel Dittmer, Rafail Ostrovsky Oblivious Tight Compaction In O(n) Time with Smaller Constant. SCN 2020: 253-274
Sanjam Garg, Mohammad Hajiabadi, Rafail Ostrovsky Efficient Range-Trapdoor Functions and Applications: Rate-1 OT and More. TCC (1) 2020: 88-116
Arka Rai Choudhuri, Michele Ciampi, Vipul Goyal, Abhishek Jain, Rafail Ostrovsky Round Optimal Secure Multiparty Computation from Minimal Assumptions. TCC (2) 2020: 291-319
Saikrishna Badrinarayanan, Abhishek Jain, Rafail Ostrovsky, Ivan Visconti UC-Secure Multiparty Computation from One-Way Functions Using Stateless Tokens. ASIACRYPT (2) 2019: 577-605
Nishanth Chandran, Wutichai Chongchitmate, Rafail Ostrovsky, Ivan Visconti Universally Composable Secure Computation with Corrupted Tokens. CRYPTO (3) 2019: 432-461
Melissa Chase, Yevgeniy Dodis, Yuval Ishai, Daniel Kraschewski, Tianren Liu, Rafail Ostrovsky, Vinod Vaikuntanathan Reusable Non-Interactive Secure Computation. CRYPTO (3) 2019: 462-488
Eyal Kushilevitz, Rafail Ostrovsky, Emmanuel Prouff, Adi Rosén, Adrian Thillard, Damien Vergnaud Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND. [Abstract]
TCC (2) 2019: 386-406
Journal version: SIAM Journal on Discrete Mathematics 35(1): 465-484 (2021)
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky Private Set Intersection with Linear Communication from General Assumptions. WPES@CCS 2019: 14-25
George Alter, Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky Computing Statistics from Private Data. Data Science Journal 17: 31 (2018)
Saikrishna Badrinarayanan, Abhishek Jain, Rafail Ostrovsky, Ivan Visconti Non-interactive Secure Computation from One-Way Functions. ASIACRYPT (3) 2018: 118-138
Karim Eldefrawy, Rafail Ostrovsky, Moti Yung Theoretical Foundations for Mobile Target Defense: Proactive Secret Sharing and Secure Multiparty Computation. From Database to Cyber Security 2018: 470-486
Karim Eldefrawy, Rafail Ostrovsky, Sunoo Park, Moti Yung Proactive Secure Multiparty Computation with a Dishonest Majority. SCN 2018: 200-215
Wutichai Chongchitmate, Rafail Ostrovsky Information-Theoretic Broadcast with Dishonest Majority for Long Messages. TCC (1) 2018: 370-388
Brett Hemenway, Rafail Ostrovsky Efficient robust secret sharing from expander graphs. Cryptography and Communications 10(1): 79-99 (2018)
Yuval Ishai, Manika Mittal, Rafail Ostrovsky On the Message Complexity of Secure Multiparty Computation. Public Key Cryptography (1) 2018: 698-711
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti Round-Optimal Secure Two-Party Computation from Trapdoor Permutations. TCC (1) 2017: 678-710
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
Juan A. Garay, Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas The Price of Low Communication in Secure Multi-party Computation. CRYPTO (1) 2017: 420-446
Shlomi Dolev, Karim Eldefrawy, Juan A. Garay, Muni Venkateswarlu Kumaramangalam, Rafail Ostrovsky, Moti Yung Brief Announcement: Secure Self-Stabilizing Computation. PODC 2017: 415-417
Saikrishna Badrinarayanan, Dakshita Khurana, Rafail Ostrovsky, Ivan Visconti Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs. EUROCRYPT (1) 2017: 382-411
Ivan Damgård, Jesper Buus Nielsen, Rafail Ostrovsky, Adi Rosén 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. CRYPTO (2) 2015: 339-358
Joël 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
Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas Secure Multi-Party Computation with Identifiable Abort. CRYPTO (2) 2014: 369-386
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
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 Ostrovsky, 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, Juan A. Garay, Rafail Ostrovsky Improved Fault Tolerance and Secure Computation on Sparse Networks. ICALP (2) 2010: 249-260
S. Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, Amit Sahai On Complete Primitives for Fairness. Preliminary version in TCC 2010: 91-108
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Extracting Correlations. Preliminary version in FOCS 2009: 261-270
Yair Amir, Paul Bunn, Rafail Ostrovsky Authenticated Adversarial Routing. (TCC-2009) 163-182 (In addition, you can get [ppt].)
Journal version: Journal of Cryptology 27(4): 636-771 (2014).
Juan A. Garay, Rafail Ostrovsky Almost-Everywhere Secure Computation. EUROCRYPT 2008: 307-323
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Cryptography with constant computational overhead. Preliminary version in STOC 2008: 433-442
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai Covert Multi-Party Computation. Preliminary version appeared in FOCS 2007: 238-248
Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky Round Complexity of Authenticated Broadcast with a Dishonest Majority. Preliminary version appeared in FOCS 2007: 658-668
Paul Bunn, Rafail Ostrovsky Secure two-party k-means clustering. ACM Conference on Computer and Communications Security 2007: 486-497 (CCS-2007)
Journal version: Oblivious Sampling with Applications to Two-Party k-Means Clustering. Journal of Cryptology 33(3): 1362-1403 (2020).
Jonathan Katz, Rafail Ostrovsky Round-Optimal Secure Two-Party Computation.
In addition, can get [crypto talk (powerpoint)] or a [90min talk (powerpoint)].
In Proceedings of Advances in Cryptology, (CRYPTO-2004) 335-354 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) 578-595 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), pp. 494-503.
Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky Minimal Complete Primitives for Secure Multi-Party Computation. Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2001) 80-100 Springer-Verlag/IACR Lecture Notes in Computer Science.
Journal version: Journal of Cryptology 18(1): 37-61 (2005).
Ran Canetti, Rafail Ostrovsky Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? In Proceedings of The 31st ACM Symposium on Theory of Computing (STOC-99) 255-264
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) 81-90
Journal version: SIAM Journal on Discrete Mathematics 16(4): 533-544 (2003).
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) 35-44 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) 541-550.
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) 478-489 Journal version: Reducibility and Completeness in Private Computations. SIAM Journal on Computing 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) August 1991, Montreal, Quebec, Canada, pp. 51-59.
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.

Garbling Schemes

David Heath, Nakul Khambhati, Rafail Ostrovsky, Turan Vural Authenticated Garbling with Tensor Gates. ACM CCS 2026 (accepted).
Cruz Barnum, David Heath, Vladimir Kolesnikov, Rafail Ostrovsky Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles. ITC 2026: 11:1-11:21
David Heath, Vladimir Kolesnikov, Varun Narayanan, Rafail Ostrovsky, Akash Shah Multiparty Garbling from OT with Linear Scaling and RAM Support. CRYPTO (4) 2025: 556-588
David Heath, Vladimir Kolesnikov, Rafail Ostrovsky Tri-State Circuits - A Circuit Model that Captures RAM. CRYPTO (4) 2023: 128-160
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky Authenticated Garbling from Simple Correlations. CRYPTO (4) 2022: 57-87
David Heath, Vladimir Kolesnikov, Rafail Ostrovsky EpiGRAM: Practical Garbled RAM. EUROCRYPT (1) 2022: 3-33
Abida Haque, David Heath, Vladimir Kolesnikov, Steve Lu, Rafail Ostrovsky, Akash Shah Garbled Circuits with Sublinear Evaluator. EUROCRYPT (1) 2022: 37-64
Laasya Bangalore, Rafail Ostrovsky, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam Adaptively Secure Computation for RAM Programs. EUROCRYPT (2) 2022: 187-216
Sanjam Garg, Mohammad Hajiabadi, Giulio Malavolta, Rafail Ostrovsky How to Build a Trapdoor Function from an Encryption Scheme. ASIACRYPT (3) 2021: 220-249
Michele Ciampi, Vipul Goyal, Rafail Ostrovsky Threshold Garbled Circuits and Ad Hoc Secure Computation. EUROCRYPT (3) 2021: 64-93
Sanjam Garg, Rafail Ostrovsky, Akshayaram Srinivasan Adaptive Garbled RAM from Laconic Oblivious Transfer. CRYPTO (3) 2018: 515-544
Steve Lu, Rafail Ostrovsky Black-Box Parallel Garbled RAM. CRYPTO (2) 2017: 66-92
Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, Daniel Wichs Adaptively Secure Garbled Circuits from One-Way Functions. CRYPTO (3) 2016: 149-178
Sanjam Garg, Steve Lu, Rafail Ostrovsky Black-Box Garbled RAM. FOCS 2015: 210-229
Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro Garbled RAM From One-Way Functions. STOC 2015: 449-458
Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, Daniel Wichs Garbled RAM Revisited. EUROCRYPT 2014: 405-422
Steve Lu, Rafail Ostrovsky How to Garble RAM Programs. EUROCRYPT 2013: 719-734

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

Dakshita Khurana, Rafail Ostrovsky, Akshayaram Srinivasan Round Optimal Black-Box "Commit-and-Prove". TCC (1) 2018: 286-313
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) 91-108
Rafail Ostrovsky, Charles Rackoff, Adam Smith Efficient Consistency Proofs for Generalized Queries on a Committed Database. In addition, can get [ICALP powerpoint] talk.
In Proceedings (ICALP-2004) 1041-1053.
Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith Efficient and Non-interactive Non-malleable Commitment. In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) 40-59 Springer-Verlag/IACR Lecture Notes in Computer Science.
Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky Non-Interactive and Non-Malleable Commitment. In Proceedings of The 30th ACM Symposium on Theory of Computing (STOC-98) 141-150
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) (LNCS 577 Springer Verlag Ed. A. Finkel and M. Jantzen) pp. 439-448 February 13-15, 1992, Paris, France.
Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions. Preliminary version appeared in Proceedings of advances in cryptology (CRYPTO-92) 196-214 Springer-Verlag Lecture Notes in Computer Science. Final journal version: Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation. Journal of Cryptology 11(2): 87-108 (1998).
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

Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, Rafail Ostrovsky Trapdoor Hash Functions and Their Applications. CRYPTO (3) 2019: 3-32
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) 445-456 Springer-Verlag Lecture Notes in Computer Science, 2005

Issues of Anonymity

Chongwon Cho, Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky Rabbit-Mix: Robust Algebraic Anonymous Broadcast from Additive Bases. USENIX Security Symposium 2024: 3151-3168
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky Anonymous Permutation Routing. TCC (3) 2023: 33-61
Ariel Hamlin, Rafail Ostrovsky, Mor Weiss, Daniel Wichs Private Anonymous Data Access. EUROCRYPT (2) 2019: 244-273
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Cryptography from Anonymity. In Proceedings of 47th Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006) 239-248.
Shlomi Dolev, Rafail Ostrovsky Efficient Anonymous Multicast and Reception. Preliminary version in proceedings of advances in cryptology, (CRYPTO-97) 395-409 Springer-Verlag Lecture Notes in Computer Science. Journal version: Xor-trees for efficient anonymous multicast and reception. ACM Transactions on Information and System Security 3(2): 63-84 (2000).

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

Sanjam Garg, Mohammad Hajiabadi, Giulio Malavolta, Rafail Ostrovsky How to Build a Trapdoor Function from an Encryption Scheme. ASIACRYPT (3) 2021: 220-249
Ohad Barta, Yuval Ishai, Rafail Ostrovsky, David J. Wu On Succinct Arguments and Witness Encryption from Groups. CRYPTO (1) 2020: 776-806
Sanjam Garg, Mohammad Hajiabadi, Rafail Ostrovsky Efficient Range-Trapdoor Functions and Applications: Rate-1 OT and More. TCC (1) 2020: 88-116
Wutichai Chongchitmate, Rafail Ostrovsky Circuit-Private Multi-key FHE. Public Key Cryptography (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 Journal on Discrete Mathematics 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 Ostrovsky On Homomorphic Encryption and Chosen-Ciphertext Security. Public Key Cryptography 2012: 52-65
Brett Hemenway, Rafail Ostrovsky Extended-DDH and Lossy Trapdoor Functions. Public Key Cryptography 2012: 627-643
Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters Public Key Locally Decodable Codes with Short Keys. APPROX-RANDOM 2011: 605-615
Brett Hemenway, Benoît 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, William 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 E. Skeith III 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 structures. ACM Conference on Computer and Communications Security 2007: 195-203 (CCS-2007)
Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan Efficient Timed-release Public-key Encryption. In Proceedings of EUROCRYPT-99 Springer Verlag.
William Aiello, Sachin Lodha, Rafail Ostrovsky Fast Digital Identity Revocation. In Proceedings of advances in cryptology, (CRYPTO-98) 137-152 Springer-Verlag Lecture Notes in Computer Science.
Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky Deniable Encryption. In Proceedings of advances in cryptology, (CRYPTO-97) 90-104 Springer-Verlag Lecture Notes in Computer Science.

Cryptographic Applications: Electronic Voting, Micropayments, Visual crypto

Michele Ciampi, Yun Lu, Rafail Ostrovsky, Vassilis Zikas Two-Tier Black-Box Blockchains and Application to Instant Layer-1 Payments. AFT 2025: 19:1-19:24
Michele Ciampi, Muhammad Ishaq, Malik Magdon-Ismail, Rafail Ostrovsky, Vassilis Zikas FairMM: A Fast and Frontrunning-Resistant Crypto Market-Maker. CSCML 2022: 428-446
Juan A. Garay, Aggelos Kiayias, Rafail M. Ostrovsky, Giorgos Panagiotakos, Vassilis Zikas Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era. EUROCRYPT (2) 2020: 129-158
Leonard Kleinrock, Rafail Ostrovsky, Vassilis Zikas Proof-of-Reputation Blockchain with Nakamoto Fallback. INDOCRYPT 2020: 16-38
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Cryptographic Sensing. CRYPTO (3) 2019: 583-604
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): i204-i211 (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 Defrawy, 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 Schaffner Position-Based Quantum Cryptography: Impossibility and Constructions. Preliminary version appeared in Crypto 2011: 429-446. Full version appeared in SIAM Journal on Computing 43(1): 150-178 (2014)
Plenary talk at QIP 2011. [Journal]
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky Position-Based Cryptography. CRYPTO-2009. 391-407 (In addition, you can get [ppt].)
Journal version: SIAM Journal on Computing 43(4): 1291-1341 (2014).
Steve Lu, Daniel Manchala, Rafail Ostrovsky Visual Cryptography on Graphs. Preliminary version appeared in COCOON 2008: 225-234.
Given COCOON-08 Best Paper Award. Full version appeared in Journal of Combinatorial Optimization 21(1): 47-66 (2011).
Jonathan Katz, Steven Myers, Rafail Ostrovsky Cryptographic Counters and Applications to Electronic Voting. In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) 78-92 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) 1-15 February 1998. Lecture Notes in Computer Science LNCS volume 1465

Hardware-based Security

Saikrishna Badrinarayanan, Abhishek Jain, Rafail Ostrovsky, Ivan Visconti UC-Secure Multiparty Computation from One-Way Functions Using Stateless Tokens. ASIACRYPT (2) 2019: 577-605
Nishanth Chandran, Wutichai Chongchitmate, Rafail Ostrovsky, Ivan Visconti Universally Composable Secure Computation with Corrupted Tokens. CRYPTO (3) 2019: 432-461
Quinn Grier, Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky ETERNAL: Encrypted Transmission With an Error-correcting, Real-time, Noise-resilient Apparatus on Lightweight Devices. MPS@CCS 2018: 61-70
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

Chongwon Cho, Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky Rabbit-Mix: Robust Algebraic Anonymous Broadcast from Additive Bases. USENIX Security Symposium 2024: 3151-3168
Samuel Dittmer, Karim Eldefrawy, Stéphane Graham-Lengrand, Steve Lu, Rafail Ostrovsky, Vitor Pereira Boosting the Performance of High-Assurance Cryptography: Parallel Execution and Optimizing Memory Access in Formally-Verified Line-Point Zero-Knowledge. CCS 2023: 2098-2112
Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky DURASIFT: A Robust, Decentralized, Encrypted Database Supporting Private Searches with Complex Policy Controls. WPES@CCS 2019: 26-36
Yun Lu, Konstantinos Mitropoulos, Rafail Ostrovsky, Avraham Weinstock, Vassilis Zikas Cryptographically Secure Detection of Injection Attacks. CCS 2018: 2240-2242
Karim Eldefrawy, Rafail Ostrovsky, Moti Yung Theoretical Foundations for Mobile Target Defense: Proactive Secret Sharing and Secure Multiparty Computation. From Database to Cyber Security 2018: 470-486
Quinn Grier, Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky ETERNAL: Encrypted Transmission With an Error-correcting, Real-time, Noise-resilient Apparatus on Lightweight Devices. MPS@CCS 2018: 61-70
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 Variability in Data Streams. PODS 2016: 251-260
Vladimir Braverman, Rafail Ostrovsky, Gregory Vorsanger Weighted sampling without replacement from data streams. Information Processing Letters 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
David Felber, Rafail Ostrovsky A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words. APPROX-RANDOM 2015: 775-785
Journal version: Theory of Computing 13, Article 14 (2017). [Journal PDF]
Ran Gelles, Rafail Ostrovsky, Alan Roytman Efficient Error-Correcting Codes for Sliding Windows. SOFSEM 2014: 258-268
Journal version: SIAM Journal on Discrete Mathematics 34(1): 904-937 (2020).
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 Theoretical Computer Science 554: 82-94 (2014)
Matthew K. Franklin, Ran 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 Transactions on Information Theory 61(1): 133-145 (2015)
Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik How Hard Is Counting Triangles in the Streaming Model? ICALP (1) 2013: 244-254
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 Measuring Independence of Datasets. Preliminary version in STOC 2010. 271-280
Vladimir Braverman, Rafail Ostrovsky Zero-One Frequency Laws. Preliminary version in STOC 2010. 281-290
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 AMS Without 4-Wise Independence on Product Domains, September 17, 2009.); and
Vladimir Braverman, Rafail Ostrovsky Measuring k-Wise Independence of Streaming Data, June 29, 2008. 119-130
Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo Optimal Sampling from Sliding Windows. (PODS-2009) 147-156
Journal version: Journal of Computer and System Sciences 78(1): 260-272 (2012).
Vladimir Braverman, Rafail Ostrovsky Smooth Histograms for Sliding Windows. Preliminary version appeared in FOCS 2007: 283-293
Journal version: Effective Computations on Sliding Windows. SIAM Journal on Computing 39(6): 2113-2131 (2010). [Journal]
Rafail Ostrovsky, William Skeith Private Searching on Streaming Data. Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) 223-240 Springer-Verlag/IACR Lecture Notes in Computer Science. Full version appeared in Journal of Cryptology Volume 20:4, pp. 397-430, October 2007.

Dimension Reduction, Embeddings and Geometric search

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai Improved algorithms for optimal embeddings. (updated author version)
ACM Transactions on Algorithms 4(4): 45:1-45:14 (2008)
Published journal version: [pdf]
Rafail Ostrovsky, Yuval Rabani Low distortion embeddings for edit distance. Preliminary version appeared in STOC '05. Full version in Journal of the ACM 54(5), Article 23 (2007).
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) 312-321.
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. Preliminary version in Proceedings of The 30th ACM Symposium on Theory of Computing (STOC-98) 614-623
Journal version: SIAM Journal on Computing 30(2): 457-474 (2000).

Clustering Algorithms for high-dimensional data

Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Rakesh Venkat A refined approximation for Euclidean k-means. Information Processing Letters 176: 106251 (2022)
Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani Min-Sum Clustering (With Outliers). APPROX-RANDOM 2021: 16:1-16:16
Paul Bunn, Rafail Ostrovsky Secure two-party k-means clustering. ACM Conference on Computer and Communications Security 2007: 486-497 (CCS-2007)
Journal version: Oblivious Sampling with Applications to Two-Party k-Means Clustering. Journal of Cryptology 33(3): 1362-1403 (2020).
Rafail Ostrovsky, Yuval Rabani, Leonard Schulman, and Chaitanya Swamy The Effectiveness of Lloyd-Type Methods for the k-Means Problem. In Proceedings of 47th Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006) 165-176.
Journal version: Journal of the ACM 59(6), Article 28 (2012).
Rafail Ostrovsky, Yuval Rabani Polynomial Time Approximation Schemes for Geometric k-Clustering. In addition, you can get a [powerpoint survey presentation].
In Proceedings of 41st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2000) 349-358. Journal version: Polynomial-time approximation schemes for geometric min-sum median clustering. Journal of the ACM 49(2): 139-156 (2002).
Allan Borodin, Rafail Ostrovsky, Yuval Rabani Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces. In Proceedings of The 31st ACM Symposium on Theory of Computing (STOC-99) 435-444
Journal version in Machine Learning Special Issue: Theoretical Advances in Data Clustering (Guest Editors: Nina Mishra and Rajeev Motwani) 56 (1-3): 153-167, 2004

Publications: Distributed Control Theory, Network Algorithms and Combinatorial Algorithms

Admission Control and Network Routing Algorithms

Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky Anonymous Permutation Routing. TCC (3) 2023: 33-61
Wutichai Chongchitmate, Rafail Ostrovsky Information-Theoretic Broadcast with Dishonest Majority for Long Messages. TCC (1) 2018: 370-388
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) 163-182 (In addition, you can get [ppt].)
Journal version: Journal of Cryptology 27(4): 636-771 (2014).
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) 771-780
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) 601-610. Full version in Journal of Interconnection Networks 5(1): 1-12 (2004).
William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen Adaptive Packet Routing for Bursty Adversarial Traffic. In Proceedings of The 30th ACM Symposium on Theory of Computing (STOC-98) 359-368. Journal version appeared in Journal of Computer and System Sciences 60(3): 482-509 (2000).
Rafail Ostrovsky, Yuval Rabani Universal O(congestion+dilation+log^{1+\epsilon} N) Local Control Packet Switching Algorithm. In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97) 644-653
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) 1-10 Journal version in Combinatorica 19(2): 241-254 (1999)
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen LOG-Space Polynomial End-to-End Communication. STOC 1995: 559-568
Journal version: SIAM Journal on Computing 27(6): 1531-1549 (1998).

Distributed Algorithms with severely limited memory per processor

Shaan Mathur, Rafail Ostrovsky A Combinatorial Characterization of Self-stabilizing Population Protocols. [Abstract]
SSS 2020: 167-182
Journal version: Information and Computation 285: 104829 (2022)
Shafi Goldwasser, Rafail Ostrovsky, Alessandra Scafuro, Adam Sealfon Population Stability: Regulating Size in the Presence of an Adversary. PODC 2018: 397-406
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].)
Journal version: Theoretical Computer Science 453: 14-28 (2012).
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) 564-573 January 28-30, Atlanta, Georgia
Rafail Ostrovsky, Danal Wilkarson Faster Computation On Directed Networks of Automata. In the Proceedings of Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-95) 38-46
Baruch Awerbuch, Rafail Ostrovsky Memory-Efficient and Self-Stabilizing Network RESET. In Proceedings of Thirteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-94) 254-263 UCLA, Los Angeles, California, August 14-17, 1994.

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) 234-242
Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir The Las-Vegas Processor Identity Problem (How and When to Be Unique). In Proceedings of the Second Israel Symposium on Theory of Computing and Systems (ISTCS-93) 150-159 Journal version appeared in Journal of 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) 667-678
Journal version: SIAM Journal on Computing 31(5): 1571-1595 (2002).

Distributed Control Theory and Error-Correcting Codes

Rafail Ostrovsky, Giuseppe Persiano, Daniele Venturi, Ivan Visconti Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions. CRYPTO (3) 2018: 608-639
Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky Coding for Interactive Communication Correcting Insertions and Deletions. ICALP 2016: 61:1-61:14
Journal version: IEEE Transactions on Information Theory 63(10): 6256-6270 (2017).
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
Journal version: Almost-Everywhere Secure Computation with Edge Corruptions. Journal of Cryptology 28(4): 745-768 (2015).
Juan A. Garay, Clint Givens, Rafail Ostrovsky Secure Message Transmission by Public Discussion: A Brief Survey. Appeared in IWCC 2011: 126-141.
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 Transactions on 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) 309-316.
Journal version: IEEE Transactions on Information Theory 55(7): 2931-2941 (2009).
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai Batch Codes and Their Applications. In addition, can get [powerpoint presentation].
In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC-2004) 262-271.

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
Journal version: Games and Economic Behavior 118: 626-647 (2019).
Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky Deterministic and Energy-Optimal Wireless Synchronization. Preliminary version appeared in DISC 2011: 237-251. Full version appeared in ACM Transactions on Sensor Networks 11(1), Article 13: 13:1-13:25 (2014)
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].)
Journal version: Theoretical Computer Science 453: 14-28 (2012).
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) 3-12

Combinatorial Algorithms

Mark Blunk, Paul Bunn, Samuel Dittmer, Steve Lu, Rafail Ostrovsky Linear-Time Secure Merge in O(loglog n) Rounds. ITC 2025: 7:1-7:23
Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov Budget and Profit Approximations for Spanning Tree Interdiction. APPROX/RANDOM 2025: 7:1-7:23
David Heath, Vladimir Kolesnikov, Rafail Ostrovsky Tri-State Circuits - A Circuit Model that Captures RAM. CRYPTO (4) 2023: 128-160
Brett Hemenway Falk, Rohit Nema, Rafail Ostrovsky A Linear-Time 2-Party Secure Merge Protocol. CSCML 2022: 408-427
Journal version: Journal of Computer and System Sciences 137: 37-49 (2023); published as "Linear-time 2-party secure merge from additively homomorphic encryption"
Brett Hemenway Falk, Rafail Ostrovsky Secure Merge with O(n log log n) Secure Operations. ITC 2021: 7:1-7:29
Samuel Dittmer, Rafail Ostrovsky Oblivious Tight Compaction In O(n) Time with Smaller Constant. SCN 2020: 253-274
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration. ICALP 2018: 93:1-93:11
Juan A. Garay, Rafail Ostrovsky Special Issue: Algorithmic Tools in Cryptography. Algorithmica 79(4): 985-986 (2017) (Editorial)
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 Theoretical Computer Science 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 Information and Computation 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 Proceedings of 42nd Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2001) 348-356. Full version accepted to Mathematics of Operations Research 31(4): 730-738 (2006).
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 1994: 690-696 January 23-25, 1994, Arlington, Virginia.

Quantum

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner Position-Based Quantum Cryptography: Impossibility and Constructions. Preliminary version appeared in Crypto 2011: 429-446. Full version appeared in SIAM Journal on Computing 43(1): 150-178 (2014)
Plenary talk at QIP 2011. [Journal]

Selected Honors and Awards

Dr. Ostrovsky's awards include:

Amazon Research Award (AWS Cryptography), 2025;
Fellow of the National Academy of Inventors, inducted in December 2024;
Pazy Memorial Research Award, 2023;
UCLA Faculty Undergraduate Mentor Award, 2023;
Amazon Faculty Research Award, 2023;
EUROCRYPT Conference Best Paper Award, 2022;
IEEE Computer Society W. Wallace McDowell Award, 2022;
Cisco Faculty Research Award, 2022;
Norman E. Friedmann Endowed Chair in Knowledge Sciences, 2022;
Fellow of the American Association for the Advancement of Science (AAAS), inducted in 2021;
Fellow of the Association for Computing Machinery (ACM), inducted in 2021;
JP Morgan Chase Faculty Award, 2021;
Google Faculty Award, 2020;
JP Morgan Chase Faculty Award, 2020;
Distinguished Professor, UCLA;
Foreign Member of Academia Europaea, inducted in 2019;
JP Morgan Chase Faculty Award, 2019;
RSA Award for Excellence in the Field of Mathematics, 2018;
IEEE Computer Society Edward J. McCluskey Technical Achievement Award, 2017;
Fellow of the Institute of Electrical and Electronics Engineers (IEEE), inducted in 2017;
Distinguished Lecturer of the Year, Georgia Institute of Technology, Computer Science Department, 2015;
Distinguished Lecturer of the Year, Johns Hopkins University, Computer Science Department, 2014;
Big Thinker Lecture Series, Yahoo Labs, Sunnyvale, California, 2014;
Rosalinde and Arthur Gilbert Foundation Research Award, 2014;
Fellow of the International Association for Cryptologic Research (IACR), inducted in 2013;
Pazy Memorial Research Award, 2012;
B. John Garrick Foundation Award, 2011;
Invitee to the Third Annual National Security Scholars Conference, 2011, by personal invitation of the Honorable Michael B. Donley, Secretary of the Air Force;
Paper selected for a plenary talk at Quantum Information Processing (QIP), 2011;
Plenary Invited Speaker, FBI Conference on Cybersecurity and Law Enforcement, 2009;
Best Paper Award, International Conference on Computing and Combinatorics (COCOON), 2008;
Plenary Invited Speaker, Public Key Cryptography international conference, 2007;
IBM Faculty Award, 2006;
Xerox Corporate Innovation Faculty Awards, 2006 and 2005;
Xerox Corporation Distinguished Lecture Series invited speaker, 2006;
Teradata Faculty Research Award, 2005;
Distinguished Cryptographer of the Year Lecture Series, NTT Labs, Kanagawa, Japan, 2005;
B. John Garrick Foundation Research Award, 2005;
OKAWA Foundation Research Award, 2004;
Three SAIC Awards for the best published work of the year, 1999, 2001, and 2002;
Bellcore Prize for excellence in research, 1996;
Henry H. Taub Prize for "One-Way Functions are Essential for Non-Trivial Zero-Knowledge," 1993;
NSF Mathematical Sciences Postdoctoral Research Fellowship, 1992–1995;
IBM Graduate Fellowship, 1990–1992;
SUNY at Buffalo Department of Mathematics Undergraduate Graduation Honors: With Highest Distinction, 1984;
Multiple papers solicited to journal special issues dedicated to highest PC-ranked STOC/FOCS articles.

Some Current and Past Professional Activities

Current:

Program committee member, CRYPTO 2027.
Program committee member, STOC 2027.
Program committee member, EUROCRYPT 2027.
Steering Committee member IEEE FOCS Conference 2019--present.
External Advisory Board member, Mōbby, 2019--present.
Johns Hopkins University Computer Science Department External Advisory Board 2017--present.
Editorial Board member Journal of ACM 2014--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 2004--present.
Board Member Stealth Software Technologies, Inc. 2008--present.

Past:

Editorial Board member Journal of Cryptology 2006--2025.
The National Academies of Sciences, Engineering, and Medicine, ad-hoc Committee on Future of Encryption 2020 -- 2022
Advisory Board Member UCLA Advisory Board On Privacy and Data Protection 2010--2020.
Member of the Theory of Computing Committee: Ad hoc committee to combat harassment and discrimination in the Theory of Computing community April 2017--October 2018.
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 Committee report.) 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 participants.
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, Dagstuhl 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, CRYPTO 2025.
Program committee member, FOCS 2024.
Program committee member, CRYPTO 2024.
Program committee member, Workshop on Privacy Enhancing Technologies for the Homeland Security Enterprise, 2022.
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.
Guest editor, SIAM Journal on Computing special issue dedicated to selected papers from FOCS 2011.
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: 24th Annual IACR/IEEE Conference on Cryptologic Research, August 2004.
Program committee member CRYPTO-2003: 23rd 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

Distinguished lecture: "Randomness Complexity of Privacy", SCP Colloquium, School of Cybersecurity and Privacy, Georgia Institute of Technology, September 24, 2026.
Strachey Lecture: "Advances in Garbled Circuits", University of Oxford, Great Britain, October 21, 2025. [announcement]
Invited keynote: "Anonymous Permutation Routing", Theory and Practice of Laconic Cryptography (TPLC), EUROCRYPT 2025 affiliated workshop, Madrid, Spain, May 4, 2025.
Invited talk: "The Multiple Faces of Deniability", NIST Special Topics on Privacy and Public Auditability (STPPA), Event 7, virtual, January 16, 2025. [slides]
Invited Keynote Speaker: "Survey of Advances in Zero Knowledge and Its Applications," Texas A&M Global Cyber Research Institute Summit, Texas A&M University, College Station, Texas, September 20, 2024.
Invited talk: "Privacy Enhancing Technologies: From Theory to Practice," University of California Cybersecurity Summit, UCLA, April 19, 2023. [program]
Invited talk: "Deriving Actionable Intelligence from Siloed Data," inaugural talk in the Department of Homeland Security seminar series "Challenges and Opportunities for Privacy Enhancing Technologies in the Homeland Security Enterprise," hosted by the Center for Accelerating Operational Efficiency, a Department of Homeland Security Center of Excellence, November 10, 2022.
Invited talk: Japan-U.S. Workshop on Privacy Enhancing Technologies and Artificial Intelligence, organized by the White House Office of Science and Technology Policy, June 23, 2022.
Invited talk: "Possible Uses of Multi-Party Computation at the Census Bureau", Summer at Census, hosted by the Center for Optimization & Data Science, U.S. Census Bureau, May 19, 2022.
Invited talk: "Linking Without Leaking: Private Set Intersection," Workshop on Privacy Enhancing Technologies for the Homeland Security Enterprise, June 21, 2022.
Invited talk: "Secure Computation on Datasets", NIST Special Topics on Privacy and Public Auditability (STPPA), Event 2, virtual (with Steve Lu), April 19, 2021. [slides] [video]
Invited talk: "Stewardship of Private Data with Cryptography" Technological Advisory Council of the Federal Communications Commission (FCC), August 12, 2020.
Invited talk: "Keeping the Internet Safe" Board on Mathematical Sciences and Analytics (BMSA) within the National Academies of Sciences, Engineering and Medicine, March 17, 2020
Talk: "A Survey of Blockchain Building Blocks and Techniques", TTI/Vanguard Conference on Blockchain and Other Networks, Washington, D.C., September 12-13, 2019.
Invited talk: "CyLab Distinguished Seminar", Carnegie Mellon University, Pittsburgh, Pennsylvania, February 18, 2019.
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.
Talk: "Delegation of Computation into the Cloud", Parts 1 and 2, UCI Cryptography Day, University of California, Irvine, April 19, 2016.
Invited talk: Distinguished Lecturer of the Year, Georgia Institute of Technology, Computer Science Department, December, 2015.
Invited talk: "Cloud Security: Threats, Challenges and Solutions", Distinguished Lecturer of the Year, Johns Hopkins University Computer Science Department, November 13, 2014.
Talk: "War on Terror vs. Individual Privacy", Mathematics of Politics workshop, IPAM, UCLA, April 22, 2014. [program and video]
Invited talk: Big Thinker Lecture Series Yahoo Labs, Sunnyvale, California, March 19, 2014.
Invited talk: "Private RAM Computation", with Daniel Wichs, Visions of Cryptography workshop, Weizmann Institute of Science, Rehovot, Israel, December 12, 2013.
Invited talk: Novel Privacy-Enhancing Technologies UCLA Henry Samueli School of Engineering and Applied Science, 2012 Technology Forum, March 13, 2012.
Invited talk: NIST Privacy Enhancing Cryptography Meeting By invitation only Workshop for Industry, Government and Academia, November 8, 2011.
Invited talk: Success Stories and Challenges in Cybersecurity September 21, 2011, Institute 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: "Improved Fault Tolerance and Secure Computation on Sparse Networks", Mathematics of Information-Theoretic Cryptography workshop, 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 Quantum Information Processing (QIP) seminar, December 6, 2010.
Invited talk: Caltech Computing and Mathematical Sciences Lecture Series November 17, 2010.
Invited talk: Aerospace Corporation Information Assurance Technology Department, Computers and Software Division, October 7, 2010.
Invited talk: 2010 Lockheed-Martin Anti-Tamper Conference, August 26, 2010, Fort 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. Irvine Computer Science Department, 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: TTI/Vanguard Conference on Identity & Trust, Dallas, Texas, February 2007.
Invited talk: Sun Microsystems, 2007 Distinguished Lecture Series, January 2007, Palo Alto, CA, USA
Talk: "Private Searching on Streaming Data", IPAM Workshop II: Locally Decodable Codes, Private Information Retrieval, Privacy-Preserving Data-Mining, and Public Key Encryption with Special Properties, UCLA, October 25, 2006. [slides] [audio]
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 October 2006, Sorrento, Italy.
Invited talk: 2006 Xerox Corporation Distinguished Lecture Series Los Angeles, July 2006. USA [Academia Europaea profile]
Invited talk: Workshop on Data Surveillance and Privacy Protection Workshop Harvard, June 2006.
Seminar: "Cryptography from Anonymity", CS201 Seminar, UCLA, January 10, 2006.
Invited talk: Workshop on classical & quantum information security Caltech, December 15-18, 2005.
Seminar: "How to Compile Searching Software So that It Is Impossible to Reverse-Engineer", CS201 Seminar, UCLA, December 6, 2005.
Invited talk: Interdepartmental Seminar on Algorithmics University of Rome "La Sapienza", Italy. November 21, 2005.
Invited talk: 2005 Distinguished Cryptographer Lecture Series NTT Labs, Kanagawa, Japan, October 2005. [Academia Europaea profile]
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: Dagstuhl 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.
Talk: "How to Search Privately on Streaming Data", DIMACS Workshop on Theft in E-Commerce: Content, Identity, and Service, Rutgers University, Piscataway, New Jersey, April 15, 2005.
Seminar: "Survey on Private Information Retrieval", Joint RISC/Intercity Seminar on the Mathematics of Cryptology, Lorentz Center, Leiden, Netherlands, January 21, 2005.
Talk: "Dimension-Reductions in the Hamming Cube and Its Applications", MGA Workshop II: Multiscale Geometry in Scientific Computing, IPAM, UCLA, October 23, 2004. [slides]
Seminar: "Content-Sensitive Fingerprinting and Dimension Reduction", Monitoring Message Streams seminar, DIMACS/Rutgers University, August 29, 2002.
Talk: "Content-Sensitive Fingerprinting and Its Applications", CCR/DIMACS Workshop on Mining Massive Data Sets and Streams: Mathematical Methods and Algorithms for Homeland Defense, Center for Communications Research, Princeton, New Jersey, June 20, 2002.
Seminar: "Dimension Reduction in the Hamming Cube and Its Applications", Discrete Math/Theory of Computing Seminar, Rutgers University, Piscataway, New Jersey, November 27, 2001.
Talk: "Non-Interactive and Non-Malleable Commitment and Zero-Knowledge", Workshop in Honour of Allan Borodin's 60th Birthday, Fields Institute, Toronto, Canada, June 23, 2001.
Seminar: "Dimension Reduction in the Hamming Cube and Its Applications", Theoretical Computer Science/Discrete Math Seminar, Institute for Advanced Study, Princeton, New Jersey, April 9, 2001.
Seminar: "Recent Results in Private Information Retrieval", Seminars in Theoretical Computer Science, Princeton University, April 21, 2000.
Talk: "Recent Results on Single Database Private Information Retrieval", DIMACS Workshop on Cryptography and Intractability, Rutgers University, Piscataway, New Jersey, March 20-22, 2000.
Seminar: "Single Database Private Information Retrieval: A Survey", Cryptography and Information Security (CIS) Seminar, MIT, Cambridge, Massachusetts, February 11, 2000.
Talk: "Private and Secure Database Storage and Retrieval", DIMACS Research and Education Institute (DREI), Cryptography and Network Security, Rutgers University, Piscataway, New Jersey, August 7, 1997.

Current and Former Students, Postdocs and Visitors

Current Ph.D. Students:

Doctoral Students (listed by graduation year):

Akash Shah (CS Ph.D. 2026, research scientist in the cryptography group at JPMorgan Chase)
Kevin Garbe (CS Ph.D. 2024, researcher at Google)
Eli Jaffe (CS Ph.D. 2023, faculty at Flintridge Preparatory School)
Saikrishna Badrinarayanan (CS Ph.D. 2020, researcher at LinkedIn)
Arman Yousefi (CS Ph.D. 2018, researcher at Google)
Dakshita Khurana (CS Ph.D. 2018, associate professor at UIUC and senior scientist at NTT Research)
Prabhanjan Ananth (CS Ph.D. 2017, associate professor at UC Santa Barbara)
Will Rosenbaum (Math Ph.D. 2016, lecturer at the University of Liverpool, Great Britain)
Wutichai Chongchitmate (Math Ph.D. 2016, tenured faculty at Chulalongkorn University, Thailand)
David Felber (CS Ph.D. 2015, researcher at Google)
Alan Roytman (CS Ph.D. 2014, researcher at Google)
Ran Gelles (CS Ph.D. 2014, professor at Bar-Ilan University)
Silas Richelson (Math Ph.D. 2014, associate professor at UC Riverside)
Akshay Wadia (CS Ph.D. 2014, researcher at Apple)
Chongwon Cho (CS Ph.D. 2013, researcher at Stealth Software Technologies, Inc.)
Sanjam Garg (CS Ph.D. 2012, associate professor at UC Berkeley) (As my student, Sanjam won the 2013 ACM Doctoral Dissertation Award)
Chen-Kuei Lee (CS Ph.D. 2012, privacy researcher at Meta)
Abhishek Jain (CS Ph.D. 2012, professor of CS at Johns Hopkins University and researcher at NTT)
Hakan Seyalioglu (Math Ph.D. 2012, Director of Technical Investigations at Edelson PC)
Joshua Baron (Math Ph.D. 2012, Deputy Chief Strategy Officer, USD(R&E), Department of Defense)
Clint Givens (Math Ph.D. 2012, mathematics faculty at the Oklahoma School of Science and Mathematics)
Vladimir Braverman (CS Ph.D. 2011, full professor at Johns Hopkins University)
Nishanth Chandran (CS Ph.D. 2011, senior principal researcher at Microsoft Research India)
Omkant Pandey (CS Ph.D. 2010, associate professor at Stony Brook University Computer Science Department)
Brett Hemenway Falk (Math Ph.D. 2010, research professor at the University of Pennsylvania)
Paul Bunn (Math Ph.D. 2010, senior researcher at Stealth Software Technologies, Inc.)
Ryan Moriarty (CS Ph.D. 2010, serial entrepreneur. Startups: lol, apprats, flotate)
Vipul Goyal (CS Ph.D. 2009, senior scientist at NTT Research and adjunct associate professor at CMU)
Steve Lu (Math Ph.D. 2009, CEO at Stealth Software Technologies, Inc.)
William Skeith (Math Ph.D. 2007, CS associate professor at City College of New York)
Jonathan Katz (CS Ph.D. 2002, senior researcher at Google)

Hosted Postdoctoral Researchers:

Varun Narayanan (postdoctoral researcher 2023 -- 2025; assistant professor at Chennai Mathematical Institute)
Wutichai Chongchitmate (postdoctoral researcher 2016 -- 2017; tenured faculty at Chulalongkorn University, Thailand)
Silas Richelson (postdoctoral researcher 2014 -- 2015; tenured faculty at UC Riverside)
Anat Paskin (postdoctoral researcher 2012 -- 2014; associate professor at Ariel University, Israel)
Alessandra Scafuro (postdoctoral researcher 2012 -- 2014; associate professor at North Carolina State University)
Vassilis Zikas (postdoctoral researcher 2012 -- 2014; associate professor at Georgia Tech)
Bhavana Kanukurthi (postdoctoral researcher 2011 -- 2014; professor at the Indian Institute of Science, India)
Jens Groth (postdoctoral researcher 2005 -- 2007; Chief Scientist at Nexus and honorary professor at University College London)

Visitors:

Prof. Vassilis Zikas (short term visits 2016 -- present)
Prof. Michele Ciampi (December 2015 -- December 2016)
Prof. Luisa Siniscalchi (December 2016 -- December 2016)
Prof. Juan Garay (short term visits 2010 -- present)
Prof. Ivan Visconti (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 Kushilevitz (sabbatical, short term visits, 2011 -- present)
Prof. Serge Fehr (short term visit, 2011)
Prof. Alon Rosen (summer visit 2010)
Prof. Claudio Orlandi (6-month visit from Aarhus, 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