Rafail Ostrovsky is a Distinguished Professor of Computer Science and Distinguished Professor of Mathematics at UCLA; Fellow of IEEE; Fellow of IACR; and a foreign member of Academia Europaea, with over 300 refereed publications and 14 issued USPTO patents. He served as chair of the IEEE Technical Committee on Mathematical Foundations of Computing from 2015 to 2018 and served as a Chair of FOCS 2011 Program Committee (PC). He also served on over 40 other international conference PC's and is currently serving as associate editor of Journal of ACM, Algorithmica Journal, and Journal of Cryptology. He is the recipient of multiple awards and honors including 1993 Henry Taub Prize; the
2017 IEEE Computer Society Technical Achievement Award and
the 2018 RSA Conference Excellence in the Field of Mathematics Award.
 Winter 2020:
 Recent courses taught at UCLA:
 CS282A/M209A Foundatoions of Cryptography;
 CS282B/M209B Cryptographic Protocols;
 CS289A Current Topics in Computer Science Theory;
 CS289A Seminar on Probabilistically Checkable Proofs;
 CS 289A Seminar on Byzantine Agreement;
 CS180 Introduction to Algorithms and Complexity;
Interested in working with me, or becoming my postdoc or visiting?
(Please read this BEFORE EMAILING ME).
I am interested in all aspects of theory of computation,
especially in cryptography, network algorithms,
and search and classification of largescale, highdimensional 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.)

The papers below are also available in a chronological list or organized by topics.
More information can be found at
DBLP.
For additions in 20172018, look for the signs.
 Cryptography:
 Search and Analysis of Largescale, HighDimensional Data:
 Distributed Control Theory, Network Algorithms and Combinatorial Algorithms:
Publications: Cryptography

Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky
On the (In)security of HashBased Oblivious RAM and a New Balancing Scheme .
SODA 2012: 143156

Brett Hemenway, Rafail Ostrovsky PublicKey LocallyDecodable Codes. CRYPTO 2008: 126143

Rafail Ostrovsky, William Skeith,
Communication Complexity in Algebraic TwoParty Protocols.
CRYPTO 2008: 379396

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William Skeith,
Public Key Encryption That Allows PIR Queries.
Appeared in CRYPTO 2007: 5067
 Survey:
Rafail Ostrovsky, William Skeith
A Survey of SingleDatabase Private Information Retrieval: Techniques and Applications.
Preliminary version (PKC2007). Full version appeared as a book chapter in
"Homeland Security Technology Challenges From Sensing and Encrypting to Mining a
nd Modeling" Franceschetti and Grossi, (EDT), ArtecHouse publishers.

Rafail Ostrovsky, Omkant Pandey, Amit Sahai
Private Locally Decodable Codes.
ICALP 2007: 387398
 Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky
Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS 2006).
In addition, you can get a powerpoint presentation.
 Rafail Ostrovsky, William Skeith.
Private Searching on Streaming Data, Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO2005) SpringerVerlag/IACR Lecture Notes in Computer Science.
Full version in Journal of Cryptography, 2007.
 Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Sufficient Conditions for CollisionResistant Hashing,
In Proceedings of Second Theory of Cryptography Conference (TCC2005)SpringerVerlag Lecture Notes in Computer Science, 2005.
 Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Batch Codes and Their Applications,
In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC2004).
 Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Guiseppe Persiano
Public Key Encryption with Keyword Search,
In Proceedings of Advances in Eurocrypt, (EUROCRYPT2004)
SpringerVerlag/IACR Lecture Notes in Computer Science.

Eyal Kushilevitz, Rafail Ostrovsky
Oneway Trapdoor Permutations Are Sufficient for
NonTrivial SingleServer Private Information Retrieval
,
In Proceedings
of Advances in Cryptology (EUROCRYPT2000)
SpringerVerlag
Lecture Notes in Computer Science.

Giovanni Di Crescenzo, Tal Malkin, and Rafail Ostrovsky
Single Database Private Information Retrieval
Implies Oblivious Transfer
,
In Proceedings
of Advances in Cryptology (EUROCRYPT2000)
SpringerVerlag
Lecture Notes in Computer Science.

Giovanni DeCrescenzo,
Yuval Ishai, Rafail Ostrovsky
Universal ServiceProviders for
Database Private Information Retrieval
,
In
Proceedings of Seventeenth Annual ACM Symposium on
Principles of Distributed Computing (PODC98). Journal
version appears in Journal of Cryptology 14(1): 3774 (2001).

Eyal Kushilevitz, Rafail Ostrovsky
Replication Is Not Needed: Single Database,
ComputationallyPrivate Information Retrieval
,
In
Proceedings of Thirtyeighth Annual
IEEE Symposium on
the Foundations of Computer Science (FOCS97).

Rafail Ostrovsky, Victor Shoup
Private Information Storage
,
In Proceedings of
The TwentyNinth ACM Symposium on Theory of Computing (STOC97).

Rafail Ostrovsky
Software Protection and Simulation on Oblivious RAMs.
,
M.I.T. Ph.D. Thesis, 1992. Preliminary version appeared in
Proceedings of 22nd annual ACM Symposium on Theory of
Computing (STOC90) pp. 514523.
Journal version appeared in the Journal of the JACM,
Vol. 43, No. 3, May 1996, pp.431473.
written jointly with Oded Goldreich.

Wutichai Chongchitmate, Rafail Ostrovsky, Ivan Visconti
ResettablySound Resettable Zero Knowledge in Constant Rounds .
TCC (2) 2017: 111138

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti
DelayedInput NonMalleable Zero Knowledge and MultiParty Coin Tossing in Four Rounds .
TCC (1) 2017: 711742

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti
FourRound Concurrent NonMalleable Commitments from OneWay Functions .
CRYPTO (2) 2017: 127157

Rafail Ostrovsky, Alessandra Scafuro, Muthuramakrishnan Venkitasubramaniam
Resettably Sound ZeroKnowledge Arguments from OWFs  The (Semi) BlackBox Way .
TCC (1) 2015: 345374

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
On Input Indistinguishable Proof Systems .
ICALP (1) 2014: 895906

Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti
Blackbox nonblackbox zero knowledge .
STOC 2014: 515524

Claudio Orlandi, Rafail Ostrovsky, Vanishree Rao, Amit Sahai, Ivan Visconti
Statistical Concurrent Nonmalleable Zero Knowledge .
TCC 2014: 167191

KaiMin Chung, Rafail Ostrovsky, Rafael Pass, Muthuramakrishnan Venkitasubramaniam, Ivan Visconti
4Round ResettablySound Zero Knowledge .
TCC 2014: 192216

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
Impossibility of blackBox simulation Against Leakage Attacks.
CRYPTO (2) 2015: 130149

Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti
ConstantRound Concurrent Zero Knowledge in the Bounded Player Model .
ASIACRYPT (1) 2013: 2140

KaiMin Chung, Rafail Ostrovsky, Rafael Pass, Ivan Visconti
Simultaneous Resettability from OneWay Function .
FOCS 2013: 6069

Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti
Concurrent Zero Knowledge in the Bounded Player Model .
TCC 2013: 6079

Joshua Baron, Rafail Ostrovsky, Ivan Visconti
Nearly Simultaneously Resettabe BlackBox Zero Knowledge.
ICALP 2012: 8899

Sanjam Garg, Rafail Ostrovsky, Ivan Visconti, Akshay Wadia
Resettable Statistical Zero Knowledge .
TCC 2012: 494511

Chongwon Cho, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti
Simultaneously Resettable Arguments of Knowledge .
TCC 2012: 530547

Rafail Ostrovsky, Omkant Pandey, Ivan Visconti
Efficiency Preserving Transformations for Concurrent NonMalleable Zero Knowledge .
Preliminary version in TCC 2010: 535552

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
ConstantRound Concurrent Nonmalleable Zero Knowledge in the Bare PublicKey Model.
ICALP 2008: 548559

Jens Groth, Rafail Ostrovsky
Cryptography in the Multistring Model.
Preliminary version appeared in CRYPTO 2007: 323341

Rafail Ostrovsky, Omkant Pandey, Ivan Visconti
Efficiency Preserving Transformations for Concurrent NonMalleable Zero Knowledge. TCC2010

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
ConstantRound Concurrent Nonmalleable Zero Knowledge in the Bare PublicKey Model.
ICALP 2008: 548559

Jens Groth, Rafail Ostrovsky
Cryptography in the Multistring Model.
Preliminary version appeared in CRYPTO 2007: 323341

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Efficient Arguments without Short PCPs.
Preliminary version appeared in IEEE Conference on Computational Complexity 2007
: 278291 (ECCC2007).

Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
ZeroKnowledge from Secure Multiparty Computation,
In Proceedings of the ACM 2007 Symposium on Theory of Computing (STOC2007).
Full version
invited and accepted to SIAM Journal of Computing (SICOMP)
special issue devoted to STOC2007.
 Jens Groth, Rafail Ostrovsky, Amit Sahai.
Noninteractive Zaps and New Techniques for NIZK,
In Proceedings of Advances in Cryptology, (CRYPTO2006) SpringerVerlag/IACR Lecture Notes in Computer Science.
 Jens Groth, Rafail Ostrovsky, Amit Sahai.
Perfect NonInteractive Zero Knowledge for NP,
In Proceedings of Advances in Eurocrypt, (EUROCRYPT2006) SpringerVerlag/IACR Lecture Notes in Computer Science.

Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai
Concurrent Statistical ZeroKnowledge Arguments for NP
from One Way Functions.
ASIACRYPT 2007: 444459
 Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin
IdentityBased ZeroKnowledge,
In Proceedings of Security in Communication Networks: 4th International Conference, SCN2004
SpringerVerlag Lecture Notes in Computer Science.
 Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai
Robust NonInteractive Zero Knowledge,
In Proceedings of Advances in Cryptology, (CRYPTO2001)
SpringerVerlag/IACR Lecture Notes in Computer Science.

Giovanni Di Crescenzo and Rafail Ostrovsky
On Concurrent ZeroKnowledge with PreProcessing
,
In Proceedings
of Advances in Cryptology (CRYPT099),
SpringerVerlag
Lecture Notes in Computer Science.

Oded Goldreich, Rafail Ostrovsky, Erez Petrank
Computational Complexity and Knowledge Complexity.
,
Preliminary
version in
the
Twentysixth ACM Symposium on Theory of Computing (STOC94)
Full version in SIAM Journal on Computing, 27(4):11161141, 1998.

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung
Interactive Hashing
Simplifies ZeroKnowledge Protocol Design.
,
In Proceedings of (EUROCRYPT93) Springer Verlag.

Rafail Ostrovsky, Avi Wigderson
OneWay Functions are Essential for NonTrivial ZeroKnowledge.
,
In Proceedings
of the second Israel Symposium on Theory of Computing and Systems}
(ISTCS93).

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.
Perfect ZeroKnowledge Arguments for NP Can Be Based on General Complexity Assumptions. , Preliminary version in Proceedings of advances in cryptology (CRYPTO92) SpringerVerlag Lecture Notes in Computer Science. Journal version in J. of Cryptology, 1988.

Joan Feigenbaum, Rafail Ostrovsky
A Note On OneProver, InstanceHiding
ZeroKnowledge Proof Systems.
,
In Proceedings of the first international symposium in cryptology
in Asia (ASIACRYPT'91).

Rafail Ostrovsky
Oneway Functions, Hard on Average Problems and
Statistical Zeroknowledge Proofs.
,
In
Proceedings of 6th Annual Structure in Complexity
Theory Conference (STRUCTURES91)
June 30  July 3, 1991, Chicago.
pp. 5159.

Mihir Bellare, Silvio Micali, Rafail Ostrovsky.
Perfect ZeroKnowledge in Constant Rounds.
,
In
Proceedings of 22nd annual ACM Symposium on
Theory of Computing (STOC90).

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 (STOC90).

Joe Kilian, Silvio Micali, Rafail Ostrovsky
Minimum Resource ZeroKnowledge Proofs.
,
In Proceedings of 30th annual
IEEE Symposium on
the Foundations of Computer Science (FOCS89).

Vipul Goyal, Abhishek Jan, Rafail Ostrovsky
PasswardAuthenticated SessionKey Generation on the Internet in Plain Model .
Preliminary version appeared in Crypto 2010: 277294. Full version appeared in J. ACM 57(1): 3:13:39 (2009)

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Postion Based Quantim Cryptography: Impossibility and Constructions.
SIAM Journal on Computing, 2014

Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Privacy Amplification with Asymptotically Optimal Entropy Loss. STOC 2010.

Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
Postion Based Cryptography.
CRYPTO2009. (In addition, you can get a [ppt].)

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.
SIAM J. Comput. 38(1): 97139 (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, (EUROCRYPT2006)
SpringerVerlag/IACR Lecture Notes in Computer Science.
 Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith.
Secure Authentication Using Biometric Data,
In Proceedings of Advances in Eurocrypt, (EUROCRYPT2005) SpringerVerlag/IACR Lecture Notes in Computer Science.
 Jonathan Katz, Rafail Ostrovsky, Moti Yung
Forward Security in PasswordOnly Key Exchange Protocols,
In Proceedings of Security in Communication Networks 2002 conference (CSN2002)
SpringerVerlag Lecture Notes in Computer Science.

Jonathan Katz, Rafail Ostrovsky, Moti Yung
Efficient PasswordAuthenticated Key Exchange Using HumanMemorable Passwords
,
In Proceedings of Advances in Cryptology, (EUROCRYPT2001)
SpringerVerlag/IACR Lecture Notes in Computer Science.

Ari Juels, Michael Luby, Rafail Ostrovsky
Security of Blind Digital Signatures
,
In Proceedings of advances in cryptology, (CRYPTO97)
SpringerVerlag Lecture Notes in Computer Science.

Shafi Goldwasser, Rafail Ostrovsky
Invariant Signatures and NonInteractive ZeroKnowledge
Proofs are Equivalent.
,
In Proceedings
of Advances in Cryptology (CRYPTO92)
SpringerVerlag
Lecture Notes in Computer Science.

Brett Hemenway, Rafail Ostrovsky
Efficient robust secret sharing from expander graphs. Cryptography and Communications .
Cryptography and Communications 10(1): 7999 (2018)

Yuval Ishai, Manika Mittal, Rafail Ostrovsky
On the Message Complexity of Secure Multiparty Computation.
PKC (1) 2018: 698711

Shlomi Dolev, Karim Eldefrawy, Juan A. Garay, Muni Venkateswarlu Kumaramangalam, Rafail Ostrovsky, Moti Yung
Brief Announcement: Secure SelfStabilizing Computation .
PODC 2017: 415417

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti
RoundOptimal Secure TwoParty Computation from Trapdoor Permutations .
TCC (1) 2017: 678710

Steve Lu, Rafail Ostrovsky
BlackBox Parallel Garbled RAM.
CRYPTO (2) 2017: 6692.

Juan A. Garay, Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas
The Price of Low Communication in Secure Multiparty Computation .
CRYPTO (1) 2017: 420446

Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, Daniel Wichs
Adaptively Secure Garbled Circuits from OneWay Functions .
CRYPTO (3) 2016: 149178

Ivan Damgard, Jesper Buus Nielsen, Rafail Ostrovsky, Adi Rosen
Unconditionally Secure Computation with Reduced Interaction
EUROCRYPT (2) 2016: 420447

Shlomi Dolev, Karim Eldefrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung
Brief Announcement: Proactive Secret Sharing with a Dishonest Majority
.
PODC 2016: 401403

Shlomi Dolev, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung
Proactive Secret Sharing with a Dishonest Majority
.
SCN 2016: 529548

Joshua Baron, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky
CommunicationOptimal Proactive Secret Sharing for Dynamic Groups
.
ACNS 2015: 2341

Sanjam Garg, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Cryptography with OneWay Communication
.
CRYPTO (2) 2015: 191208

Rafail Ostrovsky, Silas Richelson, Alessandra Scafuro
RoundOptimal BlackBox TwoParty Computation
.
CRYPTCRYPTO (2) 2015: 339358

Alwen, Rafail Ostrovsky, HongSheng Zhou, Vassilis Zikas
Incoercible Multiparty Computation and Universally Composable ReceiptFree Voting
.
CRYPTO (2) 2015: 763780

Melissa Chase, Rafail Ostrovsky, Ivan Visconti
Executable Proofs, InputSize Hiding Secure Computation and a New Ideal World
.
EUROCRYPT (2) 2015: 532560

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: 153162

Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro
Garbled RAM From OneWay Functions
.
STOC 2015: 449458

Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas
Secure MultiParty Computation with Identifiable Abort
.
CRYPTO (2) 2014: 369386

Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, Daniel Wichs
Garbled RAM Revisited
.
EUROCRYPT 2014: 405422

Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, Rafail Ostrovsky
Achieving Privacy in Verifiable Computation with Multiple Servers  Without FHE and without Preprocessing
.
Public Key Cryptography 2014: 149166

Chongwon Cho, Sanjam Garg, Rafail Ostrovsky
CrossDomain Secure Computation
.
Public Key Cryptography 2014: 650668

Joshua Baron, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky
How to withstand mobile virus attacks, revisited
.
PODC 2014: 293302

Juan A. Garay, Clinton Givens, Rafail Ostrovsky, Pavel Raykov
Fast and unconditionally secure anonymous channel
.
PODC 2014: 313321

Joshua Lampkins, Rafail Ostrovsky
CommunicationEfficient MPC for General Adversary Structures
.
SCN 2014: 155174

Steve Lu, Rafail Ostrovsky
How to Garble RAM Programs
.
EUROCRYPT 2013: 719734

Juan A. Garay, Clint Givens, Rafail Ostrovsky, Pavel Raykov
Broadcast (and Round) Efficient Verifiable Secret Sharing
.
ICITS 2013: 200219

Steve Lu, Rafail Ostrovsky
Distributed Oblivious RAM for Secure TwoParty Computation
.
TCC 2013: 377396

Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky, Ivan Visconti
Impossibility Results for Static Input Secure Computation
.
CRYPTO 2012: 424442

Eli BenSasson, Serge Fehr, Rafail Ostrovsky
NearLinear UnconditionallySecure Multiparty Computation with a Dishonest Minority
.
CRYPTO 2012: 663680

Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani
UnconditionallySecure Robust Secret Sharing with Compact Shares
.
EUROCRYPT 2012: 195208

Yuval Ishai, Rafail Otrovsky, Hakan Seyalioglu
Identifying Cheaters without an Honest Majority
.
TCC 2012: 2138

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, Jurg Wullschleger
ConstantRate Oblivious Transfer from Noisy Channels
.
CRYPTO 2011: 667684

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai
Efficient Noninteractive Secure Computation
.
EUROCRYPT 2011: 406425

Nishanth Chandran, Jual A. Garay, Rafail Ostrovsky
Improved Fault Tolerance and Secure Computation on Sparse Networks
.
ICALP (2) 2010: 249260

Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, Amit Sahai
On Complete Primitives for Fairness.
TCC2010.

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Extracting Corrolations.
Preliminary version in FOCS 2009: 261270

Yair Amir, Paul Bunn, Rafail Ostrovsky Authenticated Adversarial Routing. TCC2009
In addition, you can get a powerpoint presentation.

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Cryptography with constant computational overhead.
Preliminary version in STOC 2008: 433442

Juan A. Garay, Rafail Ostrovsky
AlmostEverywhere Secure Computation.
EUROCRYPT 2008: 307323

Juan A. Garay, Jonathan Katz, ChiuYuen Koo, Rafail Ostrovsky
Round Complexity of Authenticated Broadcast with a Dish
onest Majority.
Preliminary version appeared in FOCS 2007: 658668

Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai
Covert MultiParty Computation.
Preliminary version appeared in FOCS 2007: 238248

Paul Bunn, Rafail Ostrovsky
Secure twoparty kmeans clustering.
ACM Conference on Computer and Communications Security 2007: 486497 (CCS2007)
 Jonathan Katz, Rafail Ostrovsky
RoundOptimal Secure TwoParty Computation,
In Proceedings of Advances in Cryptology, (CRYPTO2004) SpringerVerlag/IACR Lecture Notes in Computer Science.
 Jonathan Katz, Rafail Ostrovsky, Adam Smith
Round Efficiency of MultiParty Computation with a Dishonest Majority,
In Proceedings of Advances in Eurocrypt, (EUROCRYPT2003)
SpringerVerlag/IACR Lecture Notes in Computer Science.
 Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai Universally composable twoparty and
multiparty secure computation., In Proceedings of the ACM 2002
Symposium on Theory of Computing (STOC2002).

Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky
Minimal Complete Primitives for Secure MultiParty Computation
,
Journal of Cryptology
SpringerVerlag
Volume 18, Number 1, January 2005
pp.37  61.
Preliminary version in
Proceedings of Advances in Cryptology, (CRYPTO2001)
SpringerVerlag/IACR Lecture Notes in Computer Science.

Ran Canetti, Rafail Ostrovsky
Secure Computation with HonestLooking Parties
,
In Proceedings of
The 31'st ACM Symposium on Theory of Computing (STOC99)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Amortizing Randomness in Private Multiparty Computations
,
In
Proceedings of Seventeenth Annual ACM Symposium on
Principles of Distributed Computing (PODC98).

Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Randomness vs. FaultTolerance
,
In
Proceedings of Sixteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC97).
Journal version in Journal of Cryptology 13(1): 107142 (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): 129136 (1999).
Preliminary version appeared in the
Proceedings of
The TwentyEighth ACM Symposium on Theory of Computing (STOC96).

Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky
Reducibility and Completeness In MultiParty Private Computations.
,
Preliminary version appeared in
Proceedings of Thirtyfifth Annual
IEEE Symposium on
the Foundations of Computer Science (FOCS94).
Journal version in SIAM J. Comput. 29(4): 11891208 (2000).
 Rafail Ostrovsky, Moti Yung.
How to Withstand Mobile Virus Attacks.
In Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC91).

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 46, 1989, pp. 229234.

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti
FourRound Concurrent NonMalleable Commitments from OneWay Functions
CRYPTO (2) 2017: 127157

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti
Concurrent NonMalleable Commitments (and More) in 3 Rounds.
CRYPTO (3) 2016: 270299

Rafail Ostrovsky, Vanishree Rao, Alessandra Scafuro, Ivan Visconti
Revisiting Lower and Upper Bounds for Selective Decommitments .
TCC 2013: 559578

Brett Hemenway, Steve Lu, Rafail Ostrovsky
Correlated Product Security from Any OneWay Function .
Public Key Cryptography 2012: 558575

Vipul Goyal, ChenKuei Lee, Rafail Ostrovsky, Ivan Visconti
Constructing Nonmalleable Commitments: A BlackBox Approach .
FOCS 2012: 5160

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti SimulationBased Concurrent NonMalleable Commitments and Decommitments. TCC2009

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith
Efficient and Noninteractive Nonmalleable Commitment
,
In Proceedings of Advances in Cryptology, (EUROCRYPT2001)
SpringerVerlag/IACR Lecture Notes in Computer Science.
 Rafail Ostrovsky, Charles Rackoff, Adam Smith
Efficient Consistency Proofs for Generalized Queries on a Committed Database ,
In Proceedings ICALP2004.

Giovanni Di Crescenzo,
Yuval Ishai, Rafail Ostrovsky
NonInteractive and NonMalleable Commitment
,
In Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC98).

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.
Perfect ZeroKnowledge Arguments for NP Can Be Based on General Complexity Assumptions. , Preliminary version in Proceedings of advances in cryptology (CRYPTO92) SpringerVerlag Lecture Notes in Computer Science. Journal version in J. of Cryptology, 1988.

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.
Secure Commitment Against Powerful Adversary:
A Security Primitive based on Average Intractability.
,
In Proceedings of 9th
Symposium on Theoretical Aspects of Computer
Science (STACS92).
 Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Fair Games Against an AllPowerful
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. DeSantis and U. Vaccaro (Eds.), SpringerVerlag.
Journal version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 13. (JinYi Cai ed.) pp. 155169, 1991.

Wutichai Chongchitmate, Rafail Ostrovsky
CircuitPrivate Multikey FHE .
PKC (2) 2017: 241270

Nirattaya Khamsemanan, Rafail Ostrovsky, William E. Skeith III
On the Blackbox Use of Somewhat Homomorphic Encryption in NonInteractive TwoParty Protocols.
SIAM J. Discrete Math. 30(1): 266295 (2016)

Brett Hemenway, Rafail Ostrovsky, Silas Richelson, Alon Rosen
Adaptive Security with QuasiOptimal Rate .
TCC (A1) 2016: 525541

Brett Hemenway, Rafail Ostrovsky, Alon Rosen
Noncommitting Encryption from Φ hiding .
TCC (1) 2015: 591608

Rafail Ostrovsky, Anat PaskinCherniavsky, Beni PaskinCherniavsky
Maliciously CircuitPrivate FHE .
CRYPTO (1) 2014: 536553

Rafail Ostrovsky, Vanishree Rao, Ivan Visconti
On SelectiveOpening Attacks against Encryption Schemes .
SCN 2014: 578597

Brett Hemenway, Rafail Ostrovsky
Building Lossy Trapdoor Functions from Lossy Encryption .
ASIACRYPT (2) 2013: 241260

Brett Hemenway, Rafail Ostovsky
On Homomorphic Encryption and ChosenCiphertext Security .
Public Key Crypotgraphy 2012: 5265

Brett Hemenway, Rafail Ostovsky
ExtendedDDH and Lossy Trapdoor Functions .
Public Key Crypotgraphy 2012: 627643

Bret Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wooters
Public Key Locally Decodable Codes with Short Keys .
APPROXRANDOM 2011: 605615

Brett Hemenway, Benoit Libert, Rafail Ostrovsky, Damien Vergnaud
Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security.
ASIACRYPT 2011: 7088.

Chongwon Cho, ChenKuei Lee, Rafail Ostrovsky
Equivalence of Uniform Key Agreement and Composition Insecurity .
CRYPTO 2010: 447464.

Nishanth Chandran, Rafail Ostrovsky, Willim E. Skeith III
Public Encryption with Efficient Amortized Updates.
SCN 2010: 1735.

Dan Boneh, Shai Halevi, Michael Hamburg, Rafail Ostrovsky
CircularSecure Encryption from Decision DiffieHellman.
CRYPTO 2008: 108125 (See an informal description of the result in
CS 2008 Annual Report).

Brett Hemenway, Rafail Ostrovsky
PublicKey LocallyDecodable Codes.
CRYPTO 2008: 126143

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William Skeith,
Public Key Encryption That Allows PIR Queries.
Preliminary version appeared in CRYPTO 2007: 5067

Rafail Ostrovsky, Amit Sahai, Brent Waters
Attributebased encryption with nonmonotonic access st
ructures.
ACM Conference on Computer and Communications Security 2007: 195203 (CCS2007)
 William Aiello, Sachin Lodha, Rafail Ostrovsky
Fast Digital Identity Revocation
,
In Proceedings
of advances in cryptology, (CRYPTO98)
SpringerVerlag Lecture Notes in Computer Science.
 Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan
Efficient Timedrelease Publickey Encryption,
In Proceedings of EUROCRYPT99 Springer Verlag.
 Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky
Deniable Encryption.,
In Proceedings of advances in cryptology, (CRYPTO97) SpringerVerlag Lecture Notes in Computer Science.

Yuval Ishai, Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky
Private LargeScale Databases with Distributed Searchable Symmetric Encryption .
CTRSA 2016: 90107 .

Brett Hemenway, Steve Lu, Rafail Ostrovsky, William Welser IV
HighPrecision Secure Computation of Satellite Collision Probabilities .
SCN 2016: 169187.

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): 204211 (2014).

Abishek Kumarasubramanian, Rafail Ostrovsky, Omkant Pandey, Akshay Wadia
Cryptography Using Captcha Puzzles .
Public Key Cryptography 2013: 89106 .

Ran Gelles, Rafail Ostrovsky, Kina Winoto
Multiparty Proximity Testing with Dishonest Majority from Equality Testing .
ICALP 2012: 537548

Joshua Baron, Karim El Defawy, Kirill Minkovich, Rafail Ostrovsky, Eric Tressler
5PM: Secure Pattern Matching.
Preliminary version appeared in SCN 2012 PP: 222240. Full version appeared in Journal of Computer Security 21(5): 601625 (2013)

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schafner
PositionBased Quantum Cryptography: Impossibility and Constructions .
Preliminary version appeared in Crypto 2011:429446.Full version appeared in SIAM J. Comput. 43(1): 150178 (2014) ).

Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
Postion Based Cryptography.
CRYPTO2009. 391407 (In addition, you can get [ppt] ).

Steve Lu, Daniel Manchala, Rafail Ostrovsky
Visual Cryptography on Graphs.
Preliminary version appeared in COCOON 2008: 225234.
(Best Paper Award).

Jonathan Katz, Steven Myers, Rafail Ostrovsky
Cryptographic Counters and Applications to Electronic Voting.
,
In Proceedings of Advances in Cryptology, (EUROCRYPT2001)
SpringerVerlag/IACR Lecture Notes in Computer Science.

Richard J. Lipton, Rafail Ostrovsky
MicroPayments via Efficient CoinFlipping
,
In Proceedings of Second
Financial Cryptography Conference,
(FINANCIAL CRYPTO98)
February 1998. Lecture Notes in Computer Science
LNCS volume 1465
Publications: Search and Analysis of HighDimensional Data

David Felber, Rafail Ostrovsky
A Randomized Online Quantile Summary in O((1/epsilon) \log(1/epsilon)) Words
Theory of Computing 13(1): 117 (2017). Preliminary version in APPROXRANDOM 2015: 775785
 David Felber, Rafail Ostrovsky
Variablity in Data Streams PODS 2016

Vladimir Braverman, Rafail Ostrovsky, Gregory Vorsanger
Weighted sampling without replacement from data streams .
Inf. Process. Lett. 115(12): 923926 (2015)

Vladimir Braverman, Rafail Ostrovsky, Alan Roytman
ZeroOne Laws for Sliding Windows and Universal Sketches .
APPROXRANDOM 2015: 573590

Ran Gelles, Rafail Ostrovsky, Alan Roytman
Efficient ErrorCorrecting Codes for Sliding Windows .
SOFSEM 2014: 258268

Vladimir Braverman, Rafail Ostrovsky
Approximating Large Frequency Moments with PickandDrop Sampling .
APPROXRANDOM 2013: 4257

Vladimir Braverman, Rafail Ostrovsky
Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for FrequencyBased Vectors on Streams.
APPROXRANDOM 2013: 5870

Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
How to Catch L 2HeavyHitters on Sliding Windows .
Preliminary version appeared in COCOON 2013 pp: 638650. Full version appeared in Theor. Comput. Sci. 554: 8294 (2014)

Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik
How Hard Is Counting Triangles in the Streaming Model? .
ICALP (1) 2013: 244254

Matthew K. Franklin, Ren Gelles,Rafail Ostrovsky,Leonard J.Schulman
Optimal Coding for Streaming Authentication and Interactive Communication .
Preliminary version appeared in CRYPTO 2013 pp: 258276. Full version appeared in IEEE Trans. Information Theory 61(1): 133145 (2015)

Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku
Streaming kmeans on WellClusterable Data.
SODA 2011: 2640

Vladimir Braverman, Rafail Ostrovsky
Effective Computations on Sliding Windows .
SIAM J. Comput. 39(6): 21132131 (2010)

Vladimir Braverman, Rafail Ostrovsky
Measuring Independence of Datasets.
STOC2010.

Vladimir Braverman, Rafail Ostrovsky
ZeroOne Frequency Laws.
STOC2010.

Vladimir Braverman, KaiMin Chung, Zhenming Liu, Michael Mitzenmacher, Rafail Ostrovsky
AMS Without 4Wise Independence on Product Domains.STACS2010.
(This paper is the result of a merge. For historical reasons, and for slightly
different proofs, see:
Vladimir Braverman, Rafail Ostrovsky
Meassuring kWise Indepedence of Streaming Data, June 29, 2008; and
Vladimir Braverman, Rafail Ostrovsky
AMS Without 4Wise Independence on Product Domains, September 17, 2009.)

Vladimir Braverman, Rafail Ostrovsky, Calro Zaniolo
Optimal Sampling from Sliding Windows.
In PODS2009.

Vladimir Braverman, Rafail Ostrovsky
Smooth Histograms for Sliding Windows.
Preliminary version appeared in FOCS 2007: 283293
 Rafail Ostrovsky, William Skeith.
Private Searching on Streaming Data, Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO2005) SpringerVerlag/IACR Lecture Notes in Computer Science.
Full version in Journal of Cryptography, 2007.

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad
Ali Safari, Amit Sahai
Improved algorithms for optimal embeddings.
ACM Transactions on Algorithms 4(4): (2008)
 Rafail Ostrovsky, Yuval Rabani.
Low distortion embedding for edit distance,
Preliminary version appeared in STOC '05. Full version JACM, 2008.

Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Lower Bounds for High Dimensional Nearest Neighbor Search
and Related Problems
,
Book Chapter In Discrete and Computational Geometry 
The GoodmanPollack Festschrift. Algorithms and Combinatorics Series 3143,
Springer Verlag, Berlin, August 2003, pages 252274.
Preliminary version appeared in STOC '99.

Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani
Efficient Search for Approximate Nearest Neighbor in High
Dimensional Spaces
,
SIAM J. Comput. 30(2): 457474 (2000). Preliminary version in
Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC98)

Rafail Ostrovsky, Yuval Rabani, Leonard
Schulman, and Chaitanya Swamy The
Effectiveness of LloydType Methods for the kMeans Problem. In
Proceedings of 47st Annual IEEE Symposium on the Foundations of
Computer Science (FOCS2006).
 Paul Bunn, Rafail Ostrovsky
Secure twoparty kmeans clustering.
ACM Conference on Computer and Communications Security 2007: 486497 (CCS2007)

Rafail Ostrovsky,
Yuval Rabani.
Polynomial Time Approximation Schemes for Geometric kClustering.
,
In Proceedings of 41st Annual IEEE Symposium on the
Foundations of Computer Science (FOCS2000).
Journal version in JACM 49(2): 139156 (2002).

Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms For Clustering Problems
in High Dimensional Spaces
,
Preliminary version in
proceedings of
The 31'st ACM Symposium on Theory of Computing (STOC99),
Journal version in Machine Learning Journal
Special Issue: Theoretical Advances in Data Clustering
56 (13): 153167, 2004.
Publications: Distributed Control Theory, Network Algorithms and Combinatorial Algorithms

Paul Bunn, Rafail Ostrovsky
Secure EndtoEnd Communication with Optimal Throughput and Resilience against Malicious Adversary
,
DISC 2013: 403417

Paul Bunn, Rafail Ostrovsky
Asynchronous ThroughputOptimal Routing in Malicious Networks
,
ICALP 2010: 236248

Yair Amir, Paul Bunn, Rafail Ostrovsky Authenticated Adversarial Routing. TCC2009
In addition, you can get a powerpoint presentation.
 William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen
Dynamic Routing on Networks with FixedSized Buffers,
In Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA2003).

Allan Borodin,
Rafail Ostrovsky,
Yuval Rabani.
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds
,
In Proceedings of the
Twelfth Annual
ACMSIAM Symposium on Discrete
Algorithms (SODA2001).
Journal version in
Journal of Interconnection Networks, Vol. 5, No. 1, pp. 112.

William Aiello,
Eyal Kushilevitz, Rafail Ostrovsky,
Adi Rosen
Adaptive Packet Routing for Bursty Adversarial Traffic
,
In
Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC98).
Journal version appeared in JCSS 60(3): 482509 (2000).

Rafail Ostrovsky, Yuval Rabani
Universal O(congestion+dilation+log(N))
Local Control Packet Switching Algorithm
,
In Proceedings of
The TwentyNinth ACM Symposium on Theory of Computing (STOC97).

Eyal Kushilevitz, Nati Linial, Rafail Ostrovsky
The LinearArray Conjecture in Communication Complexity is False.
,
Preliminary version in
Proceedings of
The TwentyEighth ACM Symposium on Theory of Computing (STOC96)
Journal version in Combinatorica 19(2): 241254 (1999)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
LOGSpace
Polynomial EndtoEnd Communication
,
In SIAM Journal of Computing Volume 27, 1998. SIAM J. Comput. 27(6): 15311549 (1998).
Preliminary version appeared in the Proceedings of
Twentyseventh ACM Symposium on Theory of Computing STOC95.

Rafail Ostrovsky, Mor Perry, Will Rosenbaum
SpaceTime Tradeoffs for Distributed Verification ,
SIROCCO 2017: 5370

Mor Baruch, Rafail Ostrovsky, Will Rosenbaum
Brief Announcement: SpaceTime Tradeoffs for Distributed Verification ,
PODC 2016: 357359

Milan Bradonjic, Eddie Kohler, and Rafail Ostrovsky
NearOptimal Radio Use For Wireless Network Synchronization ,
ALGOSENSORS2009. 1528 (In addition, you can get [talk slides].

Mor Baruch, Rafail Ostrovsky, Will Rosenbaum
Brief Announcement: SpaceTime Tradeoffs for Distributed Verification ,
PODC 2016: 357359

Alain Mayer, Rafail Ostrovsky, Moti Yung
SelfStabilizing Algorithms for Synchronous Unidirectional Rings.
,
In Proceedings of
Seventh Annual ACMSIAM Symposium on Discrete Algorithms
(SODA96)
January 2830,
Atlanta, Georgia.

Rafail Ostrovsky, Wilkersan
Faster Computation On Directed Networks of Automata
,
In the
Proceedings of Fourteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC95).

Baruch Awerbuch, Rafail Ostrovsky
MemoryEfficient and SelfStabilizing Network RESET.
,
In
Proceedings of Thirteens Annual ACM Symposium on
Principles of Distributed Computing
(PODC94).

Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani
Simple and Efficient Leader Election
In The Full Information Model.
,
In Proceedings of
Twentysixth ACM Symposium on Theory of Computing (STOC94).

Shay Kutten, Rafail Ostrovsky, Boaz PattShamir.
The LasVegas Processor Identity Problem
,
In Proceedings of the Second
Israel Symposium on Theory of Computing and Systems (ISTCS93)
Journal version appeared in
J. Algorithms 37(2): 468494 (2000).

Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung
SelfStabilizing Symmetry Breaking in ConstantSpace.
,
In
Proceedings of 24th annual ACM Symposium on
Theory of Computing (STOC92).

Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
Coding for Interactive Communication Correcting Insertions and Deletions ,
ICALP 2016: 61:161:14

Rafail Ostrovsky, Anat PaskinCherniavsky
Locally Decodable Codes for Edit Distance ,
ICITS 2015: 236249

Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky
Locally Updatable and Locally Decodable Codes ,
TCC 2014: 489514

Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Edge Fault Tolerance on Sparse Networks ,
ICALP 2012: 452463

Juan A. Garay, Clint Givens, Rafail Ostovsky
Secure Message Transmission with Small Public Discussion
,
Preliminary version appeared in IWCC 2011:126141 IEEE Trans. Full version appeared in Information Theory 60(4): 23732390 (2014)

Juan A. Garay, Clint Givens, Rafail Ostrovsky
Secure Message Transmission with Small Public Discussion
,
Preliminary version appeared in Eurocrypt 2010:177196. Full version appeared in IEEE Trans. Information Theory 60(4): 23732390 (2014)

Brett Hemenway, Rafail Ostrovsky PublicKey LocallyDecodable Codes. CRYPTO 2008: 126143
 Rafail Ostrovsky, Yuval Rabani, Leonard Schulman.
ErrorCorrecting Codes for Automatic Control,
In Proceedings of 46th Annual IEEE Symposium on the Foundations of Computer Science (FOCS2005).
 Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Batch Codes and Their Applications,
In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC2004).

Rafail Ostrovsky, Will Rosenbaum
Fast Distributed Almost Stable Matchings .
PODC 2015: 101108

Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum
A Stable Marriage Requires Communication .
SODA 2015: 10031017

Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky
Deterministic and EnergyOptimal Wireless Synchronization .
Preliminary version appeared in DISC 2011:237251. Full version appeared in TOSN 11(1): 13:113:25 (2014)

Milan Bradonjic, Eddie Kohler, and Rafail Ostrovsky
NearOptimal Radio Use For Wireless Network Synchronization.
ALGOSENSORS2009.

Rafail Ostrovsky, Boaz PattShamir
Optimal and Efficient Clock Synchronization Under Drifting Clocks
,
In
Proceedings of Eighteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC99).

Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration .
SODA 2017: 154169

Joshua Baron, Yuval Ishai, Rafail Ostrovsky
On LinearSize Pseudorandom Generators and Hardcore Functions .
Preliminary version appeared in COCOON 2013 pp: 169181. Full version appeared in Theor. Comput. Sci. 554: 5063 (2014)

Brett Hemenway, Rafail Ostrovsky, Mary Wootters
Local Correctability of Expander Codes .
Preliminary version appeared in ICALP 2013 pp: 540551. Full version appeared in Inf. Comput. 243: 178190 (2015)

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman
Robust Pseudorandom Generators .
ICALP (1) 2013: 576588
 Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani. Approximation Algorithms for the Job Interval
Selection Problem and Related Scheduling Problems. Preliminary
version in (FOCS2001). Journal version accepted to Journal of
Mathematics of Operations Research.
 Noga Alon, Manuel Blum, Amos Fiat, Sampath K. Kannan, Moni
Naor, Rafail Ostrovsky Matching Nuts and
Bolts. , In Proceedings of the Fifth Annual ACMSIAM Symposium
on Discrete Algorithms (SODA94),
Rafail Ostrovsky is a Distinguished Professor of
Computer Science and Distinguished Professor of Mathematics at UCLA.
Prof. Ostrovsky joined UCLA in 2003 as a full tenured professor,
coming from Bell Communications Research
where he was a Senior Research Scientist.
Prior to beginning his career at Bellcore,
he was an NSF Mathematical Sciences Postdoctoral Research Fellow
at UC Berkeley.
Dr. Ostrovsky received his
Ph.D. in computer science from
MIT in 1992,
(advisor: Silvio Micali, thesis:
Software Protection and Simulation on Oblivious RAM), supported by IBM Graduate Fellowship.
Prof. Ostrovsky is a Fellow of IEEE; Fellow of IACR;
and a foreign member of Academia Europaea.
He has 14 U.S. patents issued
and over 300 papers
published in refereed journals
and conferences.
Dr. Ostrovsky has served as a Chair of the IEEE Technical Committee on Mathematical Foundations of Computing from 20152018 and has served on
over 40 international conference Program Committees
including serving as PC chair of FOCS 2011.
He is a member of the Editorial Board of
Journal of ACM;
Editorial Board of
Algorithmica;
and the Editorial Board of
Journal of Cryptology and is the recipient of multiple awards and honors including the 2017 IEEE Computer Society Technical Achievement Award and
the 2018 RSA Conference Excellence in the Field of Mathematics
lifetime achievement
Award.
At UCLA, Prof. Ostrovsky heads the
Center of Information and Computation Security (CICS)
a multidisciplinary
Research Center
(http://www.cs.ucla.edu/security/)
at Henry Samueli School of Engineering and Applied Science.
Dr. Ostrovsky's awards include:
 Elevated to the title of "Distinguished Rrofessor" at UCLA by Chancellor Gene D. Block in 2020;
 Foreign Member of Academia Europaea, inducted in 2019;
 2018 RSA Conference Excellence in the field of mathematics lifetime achievement award;
 2017 IEEE Fellow;
 2017 IEEE Computer Society Technical Achievement Award;
 2014 Rosalinde and Arthur Gilbert Foundation Research Award;
 2013 IACR Fellow,
 2012 Pazy Memorial Research Award;
 2008 Best Paper Award of International Conference on Computing and Combinatorics (COCOON2008);
 2006 and 2005 Xerox Corporate Innovation Faculty Awards;
 2006 IBM Faculty Award;
 2006 Xerox Corporation Distinguished Lecture Series;
 2005 Distinguished Cryptographer of the Year Lecture Series NTT Labs, Japan;
 2004 OKAWA Foundation Research Award;
 19992002: three SAIC Awards for the best published work of the year (1999, 2001, 2002) in computer science and mathematics;
 1996 Bellcore Prize for excellence in research;
 1993 Henry Taub Prize; and
 multiple papers solicited to journal special issues dedicated to highest PCranked STOC/FOCS articles.
Current:Past:
 General Chair FOCS 2017
 Chair of the IEEE Technical Committee on Mathematical Foundations of Computing 20152018.
 General Chair FOCS 2016
 General Chair FOCS 2015
 Program Committee Chair
FOCS 2011 (October 2225, 2011 in Palm Springs, CA.)
 Steering Committee member UC Privacy and Information Security Steering Committee,
(Appointed by University of California President, Mark G. Yudof, see Announcement.) 20102014.
 Program Committee Chair, Sixth Conference on Security and Cryptography for Networks Amalfi, September 1012, 2008.
The proceedings of SCN 2008 appeared in LNCS 5229 and are available online.
(See also Italian press coverage.)
 Program Chair, Institute of Pure and Applied Mathematics
semesterlong NSFFUNDED program dedicated to
Cybersecurity. September  December, 2006. Over 200 participatns.
 Coorganizer, IPAM Workshop
Locally decodable codes, PIR, privacypreserving datamining, and encryption with special properties.
October 25  28, 2006, IPAM.
 Coorganizer, IPAM Workshop
Foundations of secure multiparty computation and zeroknowledge and its applications. November 13  17, 2006, IPAM.
 Cochair, Dagshtul Workshop Anonymous
Communication and its Applications October 914, 2005.

Coorganizer, IPAM Workshop
Multiscale Geometry and Analysis in High Dimensions October
1923, 2004.
 Coorganizer, DIMACS Workshop Cryptographic Protocols in Complex Environments
May 1517, 2002.
 Program committee member Eurocrypt 2017 30 April to 4 of May, 2017, Paris,.
 Program committee member PKC 2016 March 2016.
 Program committee member FIFTEENTH IMA INTERNATIONAL CONFERENCE ON CRYPTOGRAPHY AND CODING December 2015.
 Program committee member ITCS2012 Boston, January 810, 2012.
 Program committee member PODS2011.
 Program committee member ICALP2011.
 Program committee member EUROCRYPT2011.
 Program committee member CTRSA 2011.
 Program committee member TCC2010: Seventh Theory of Cryptography Conference, 2010.
 Program committee member EUROCRYPT2009 Cologne, April 2630, 2009.
 Program committee member Algosensors2009 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks 2009.
 Program committee member FOCS2008 49th Annual IEEE Symposium on Foundations of Computer Science.
 Program committee member PKC2007: International Workshop on Practice and
Theory in Public Key Cryptography, (Apr 1719 2007, Beijing). China 2007
 Program committee member
ACISP2007
12th Australian Conference on Information Security and Privacy
July
26, 2007, Townsville, Queensland, Australia.
 Program committee member
ICALP2006: 33rd International Colloquium on Automata,
Languages and Programming, July 916, 2006, Venice, Italy
 Program committee member
STOC2006: 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 2426, New York City, USA.
 Program committee member INDOCRYPT2005 December 1012, 2005 Indian
Institute of Science Bangalore, India, 2005.
 Program committee
member
EUROCRYPT2005 Aarhus, May 2226, 2005.
 Program committee member TCC2005: Second Theory of Cryptography Conference, Feb 2005.
 Program committee member SCN2004 Security in Communication Networks 2004 to
be held on September 810 in Amalfi, Italy.
 Program committee
member PODC2004: 23rd Annual ACM Symposium on
Principles of Distributed Computing, July 2004.
 Program
committee member
CRYPTO2004: 24nd Annual IACR/IEEE Conference on Cryptologic
Research, August 2004.
 Program committee member
CRYPTO2003: 23nd Annual IACR/IEEE Conference on Cryptologic
Research, August 2003.
 Program committee member
STOC2003: Annual ACM Symposium on Theory of Computing, May
2003.
 Program committee member
CRYPTO2002: 22nd Annual IACR/IEEE Conference on Cryptologic
Research, 2002.
 Program committee member
RANDOM2002: The 6th International Workshop on
Randomization and Approximation Techniques in Computer Science,
2002.
 Program committee member SCN2002:
Third Workshop on Security in Communication Networks, September
2002, Amalfi, Italy.
 Program committee member STOC2000: Annual ACM Symposium on Theory of
Computing, 2000.
 Program committee member SODA2000: Eleventh Annual ACMSIAM
Symposium on Discrete Algorithms, , January 19, 2000, San
Francisco.
 Program committee member
SCN99: Second Workshop on Security in Communication Networks,
September 1999, Italy.
 Program committee member CRYPTO98: 18th Annual IACR/IEEE Conference on
Cryptologic Research 1998.
 Program committee member ISTCS97: 5th ISRAEL Symposium on Theory of
Computing and Systems, 1997.
 Invited talk: Distinguished Lecture Series,
Cloud Security,
Texas A&M University, Computer Science Department,
October, 2018.
 Invited Keynote Lecture: workshop on "Mathematics of InformationTheoretic Cryptography" Institute of Mathematical Sciences (IMS) of National University of Singapore and Nanyang Technological University, Singapore, September 1930, 2016.
 Invited Keynote Speaker Bay Area Crypto Day,
"Adaptively secure garbled circuits from AES"
Stanford, May 2nd, 2016.
 Invited talk: Distinguished Lecturer of the Year, Georgia Institute of Technology, Computer Science Department, December, 2015.
 Invited talk: Distinguished Lecturer of the Year, Johns Hopkins University Computer Science Department, November 13, 2014.
 Invited talk: Big Thinker Lecture Series Yahoo Labs, Sunnyvale, Califor nia, March 19, 2014.
 Invited talk:
Novel PrivacyEnhancing Technologies
UCLA Henry Samueli School of Enginnering and Applied Science, 2012 Technology Forum,
March 13, 2012.
 Invited talk: NIST Privacy Enhancing Crytpography Meeting By invitation only Workshop for Industry, Governmnet and Academia, November 8, 2011.
 Invited talk: Success Stories and Challanges in Cybersecurity September 21, 2011, Insitute of Pure and Applied Mathematics, Los Angeles.
 Invited Scholar: U.S. Air Force Third Annual National Security Scholars Conference. April 26, 2011.
(Invited by the Honorable Michael B. Donley, Secretary of the Air Force.)
 Invited talk: Mathematics of InformationTheoretic Cryptography IPAM, UCLA, March 3, 2011.
 Invited panelist: UCLA 2011 Technology Forum March 1, 2011.
 Invited talk: Trends in Theoretical Cryptography (TTC 2011) January 1012, 2011, Tsinghua University, Beijing, China.
 Invited talk: MIT CSAIL Theory Colloquium December 7, 2010.
 Invited talk: MIT Qunatum Information Processing (QIP) seminar, December 6, 2010.
 Invited talk: Caltech Computing and Mathematical Sciences Lecture Series Novermber 17, 2010.
 Invited talk: Aerosapce Corporation Information Assurance Technology Department, Computers and Software Division, Octover 7, 2010.
 Invited talk: 2010 LockheedMartin AntiTamper Conference, August 26, 2010, Forth Worth, Texas.
 Invited talk: Symantec Research Labs's Seminar  Security in the Cloud,
Symantec 900 Corporate Pointe, Culver City, CA 90230,
July 29, 2010.
 Invited talk: 2009 Workshop on Cryptographic Protocols and PublicKey Cryptography May 2429 2009, Bertinoro, Italy.
 Distinguished Lecturer Seminar Series, U.C. Inrvine Computer Science Deparmtment, May 15, 2009.
 Plenary invited speaker at
International Conference on Cyber Security 2009 organized by FBI and Fordham university.
 Plenary keynote speaker at PKC2007
International Workshop on Practice and Theory in Public Key Cryptography, China 2007.
 Invited talk: Sun Microsystems, 2007 Distinguished Lecture Series, January 2007, Palo Alto, CA, USA
 Invited tutorial: Series of IPAM lectures on Private Information Retrieval September 2006, Los Angeles, CA, USA.
 Two invited tutorials at Homeland Defense and Security Conference 1821 Octover 2006, Sorrento, Italy.

Invited talk: 2006 Xerox Corporation Distinguished Lecture Series Los Angeles, July 2006. USA

Invited talk: Worksop on Data Sirveillance and Privacy Protection Workshop Harvard, June 2006.

Invited talk:
Workshop on classical & quantum information security Caltech, December 1518, 2005.

Invited talk: Interdepartmental Seminar on Algorithmics University of Rome "La Sapienza", Italy. November 21, 2005.
 Invited 1week course Bertinoro, Italy September 49, 2005.

Invited talk: 2005 Distinguished Cryptographer Lecture Series NTT Labs, Kanagawa, Japan, October 2005.

Invited talk:
Workshop on Cryptography and Information Security 2005 Tokyo, Japan, October 21, 2005.

Invited talk:
IEEE Information Theory Workshop on Theory and Practice in InformationTheoretic Security Awaji Island, Japan, October 16 19, 2005.

Invited talk: Dagshtul Workshop. Germany, October 914, 2005.

Invited talk:
Southern California Security and Cryptography
Workshop September 24, 2005, Irvine, CA. USA

Invited talk: Bertinoro
Invited oneweek course, International PhD School
on Mathematical Aspects of Modern Cryptography, Bertinoro, Italy
September 49, 2005.
Current Ph.D. Students:
 Saikrishna Badrinarayanan (CS)
 Asuthosh Kumar (CS)
 Eli Jaffe (CS)
My Ph.D. Students (listed by graduation year):
 Arman Yousefi (CS Ph.D. 2018, now researcher at Google)
 Dakshita Khurana (CS Ph.D. 2018, now tenure track faculty at UIUC)
 Prabhanjan Ananth (CS Ph.D. 2017, now postdoctoral researcher at MIT))
 Will Rosenbaum (MATH Ph.D. 2016, now postdoctoral researcher at University of Copenhagen)
 Wutichai Chongchitmate (MATH Ph.D. 2016, now postdoctoral researcher at UCLA)
 David Felber (CS Ph.D. 2015, now researcher at Google.)
 Alan Roytman (CS Ph.D. 2014, now postdoctoral researcher at TelAviv University Computer Science)
 Ran Gelles (CS Ph.D. 2014, now tenuretrack faculty at BarIlan University)
 Silas Richelson (MATH Ph.D. 2014, now tenuretrack faculty at UC Reiverside)
 Akshay Wadia (CS Ph.D. 2014, now researcher at SiliconValley Startup)
 Chongwon Cho (CS Ph.D. 2013, now researcher at HRL)
 Sanjam Garg (CS Ph.D. 2012), now a tenuretrack faculty of CS at U.C. Berkely.)
(As my student, Sanjam won 2013 ACM Doctoral Dissertation Award)
 ChengKeui Lee (CS Ph.D. 2012, now Security Researcher, LinkedIn)
 Abhishek Jain (CS Ph.D., 2012, now tenuretrack faculty at Johns Hopkins University.)
 Hakan Seyalioglu (Math Ph.D., 2012, now researcher at Google.)
 Joshua Baron (Math Ph.D., 2012, now researcher at RAND corporation.)
 Clint Givens (Math Ph.D., 2012, now tenure track Math faculty at University of Science and Arts of Oklahoma)
 Vladimir Braverman
(C.S. Ph.D. 2011, C.S. tenuretrack faculty at Johns Hopkins University.)
 Nishanth Chandran (C.S. Ph.D. 2011, now a researcher at MSR India)
 Omkant Pandey (CS Ph.D., 2010, nowa tenure track faculty at Stony Brook Computer Sccience Department.)
 Brett Hemenway (Math Ph.D., 2010, now a tenuretrack research faculty at U. Penn.)
 Paul Bunn (Math Ph.D., 2010, researcher at Google.)
 Ryan Moriarty (CS Ph.D., 2010,
entrepreneur in Silicon Valley. Startups: apprats, flotate.)
 Vipul Goyal (CS Ph.D., 2009, now a tenuretrack associate professor at CMU.)
 Steve Lu (Math Ph.D., 2009, researcher at Stealth Software Technologies, Inc.)
 William Skeith (Math Ph.D., 2007; CS tenured associated professor at City College of NY).
 Jonathan Katz (CS Ph.D. 2002, Full Professor of CS at U. of Marylandm, head of their cybersecurity center.)
My Postdoctoral Researchers:
 Wutichai Chongchitmate (postdoctoral researcher 2016  present)
 Silas Richelson (postdoc 2014  2015; now tenuter track professor at UC Riverside Computer Science)
 Anat Paskin (postdoc 2012  2015; now a tenuretrack faculty at Ariel University, Israel)
 Vassilis Zikas (postdoc 2012  2015; now a tenuretrack faculty ar RPI)
 Alessandra Scafuro (postdoc 2012  2015; now tenuretrack faculty at North Carolina State University. )
 Bhavana Kanukurthi (postodc 2011  2014; now a tenuretrack faculty at Indian Institute of Science (IISC), Bangalore, India)
 Jens Groth (20052007): Now full professor at University College of London.
Visitors:
 Prof. Vassilis Zikas (short term visits 2016  present)
 Michele Ciampi (Decemmber 2015  December 2016)
 Luisa Siniscalchi (December 2016  December 2016)
 Dr. Juan Garay (short term visits 2010  ppresent)
 Prof. Ivan Vinsconti (several short, medium and long term visits from 2009  present, including spending several sabbaticals))
 Prof. Yuval Ishai (Several sabbaticals, short and long term visits 2009  present)
 Prof. Giuseppe (a.k.a. Pino) Persiano (short term visit 2012 present)
 Prof. Yuval Rabani (short term visits 2009  present)
 Prof. Eyal Kushulevitz (sabbatical, short term visits, 2011  present)
 Dr. Serge Fehr (short term visit, 2011)
 Prof. Alon Rosen (summer visit 2010)
 Claudio Orlandi (6month visit from Aaharus, 2010)
Useful: Fun:
Professor Rafail Ostrovsky
University of California, Los Angeles
Department of Computer Science
Office 475, Engineering VI
Los Angeles CA 900951596
(310) 2065283 (office)
(310) 8257578 (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) 8251322;
Email: osannak (at) cs.ucla.edu