I am a professor of computer science and a professor of mathematics at UCLA.
My research has been supported by
National Science Foundation (NSF awards:
DMS9206267;
CNS0430254;
CNS0716835;
CNS0716389;
CNS0830803;
CCF0916574;
IIS1065276;
CCF1016540;
CNS1118126;
CNS1136174);
DARPA (Defense Advanced Research Projects Agency through the U.S. Office of Naval Research under Contract N000141110392);
Binational Science Foundation
(BSF2002354; BSF2008411);
OKAWA Foundation;
B. John Garrick Foundation;
UC Microelectonrics Innovation and Computer Research grants;
Intel Corporation;
IBM;
LockheedMartin Corporation;
Teradata Corporation; and
Xerox Corporation.
 WINTER 2016:
 Recent courses at UCLA:
 CS282A/M209A Cryptography;
 CS282B/M209B Cryptographic Protocols;
 CS289A Current Topics in Computer Science Theory
 CS180 Intro to Algorithms;
 CS289A Seminar on Probabilistically Checkable Proofs;
 CS 289A Seminar on Byzantine Agreement.
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.)
 Cryptography:
 Search and
Analysis of Largescale, HighDimensional Data:
 Distributed Control Theory, Network Algorithms and
Combinatorial Algorithms:

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

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.

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

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Postion Based Quantim Cryptography: Impossibility and Constructions.
(manuscript)

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.

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.

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.

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.

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.
Publications: Search and Analysis of HighDimensional Data

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
Effective Computations on Sliding Windows.
To appear in SIAM Journal on Computing (SICOMP).

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

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.

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).
Rafail Ostrovsky is a Professor of
Computer Science and Professor of Mathematics at UCLA.
Prof. Ostrovsky came to UCLA in 2003 from Bell
Communications Research (Bellcore) 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,
in the Theory of Computation Group
(advisor: Silvio Micali, thesis:
Software Protection), supported by IBM Graduate Fellowship.
Prof. Ostrovsky's research centers on various
issues in theoretical computer science, including
cryptography, distributed network algorithms,
and highdimensional search
problems.
Prof. Ostrovsky is an honorary Fellow of the IACR; he has 11 U.S. patents issued and over 230 papers
published in refereed journals
and conferences.
Dr. Ostrovsky currently serves as a Chair of the IEEE Technical Committee on Mathematical Foundations of Computing and has served on
38 international conference Program Committees
including serving as a 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;
he serves on the Editorial
and Advisory Board of the
International Journal of Information and Computer Security
and
is a member of the steering committee of the international symposium of Security
in Communication Networks (SCN).
Dr. Ostrovsky is also a
Board Member of UCLA Advisory Board On Privacy and Data Protection.
Dr. Ostrovsky has served from 2012 to 2014 on UCwide
Privacy and Information Security Steering Committee, appointed by University of California President Mark Yudof.
Dr. Ostrovsky was invited (among only a few academics) to participate in U.S. Air Force Third Annual National Security Scholars Conference in 2011, personally invited by the Honorable Michael B. Donley, Secretary of the Air Force.
Dr. Ostrovsky was invited to be the
Plenary Speaker at a conference organized by FBI in 2009, and was invited to be
the Plenary Keynote Speaker for Public Key Cryptography International
Conference in 2007.
Dr. Ostrovsky's awards include:
2014 Rosalinde and Arthur Gilbert Foundation Research Award;
2012 Pazy Memorial Research Award;
the Best Paper Award of the 2008 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;
OKAWA Foundation 2004 Research Award;
three SAIC Awards for the best published work of the year (1999, 2001, 2002) in computer science and mathematics;
the 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.
At UCLA, Prof. Ostrovsky heads security and cryptography
multidisciplinary
Research Center
(http://www.cs.ucla.edu/security/)
at Henry Samueli School of Engineering and Applied Science.
Current:Past:
 Program Committee Chair
FOCS 2011 (October 2225, 2011 in Palm Springs, CA.)
 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 program dedicated to
Cybersecurity. September  December, 2006.
 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 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 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 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:
 Will Rosenbaum (MATH)
 Wutichai Chongchitmate (MATH)
 Josh Lampkins (MATH)
 Arman Yousefi (CS)
 Prabhanjan Ananth (CS)
 Dakshita Khurana (CS)
 Saikrishna Badrinarayanan (CS)
Doctoral Students (listed by graduation year):
 David Felber (CS Ph.D. 2015, currently on the job market)
 Alan Roytman (CS Ph.D. 2014, now Postdoc at TelAviv University Computer Science)
 Ran Gelles (CS Ph.D. 2014, now Postdoc at Princeton University Computer Science)
 Silas Richelson (MATH Ph.D. 2014, now Postdoc at MIT)
 Akshay Wadia (CS Ph.D. 2014, now postdoc EE Department UCLA)
 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, now a researcher at UC Berkeley)
 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, researcher at Microsoft Research, India.)
 Steve Lu (Math Ph.D., 2009, researcher at Stealth Software Technologies, Inc.)
 William Skeith (Math Ph.D., 2007; CS tenuretrack faculty at City College of NY).
 Jonathan Katz (CS Ph.D. 2002, Full Professor of CS at U. of Maryland.)
Postdocs:
 Dr. Anat Paskin (postdoc 2012  2015)
 Dr. Vassilis Zikas (postdoc 2012  2015)
 Dr. Alessandra Scafuro (postdoc 2012  2015)
 Dr. Bhavana Kanukurthi (postodc 2011  2014)
 Jens Groth (20052007): Now tenured faculty at University College of London.
Visitors:
 Dr. Juan Garay (short term visits 2010, 2011, 2012, 2013)
 Prof. Ivan Vinsconti (short term visit 2013)
 Prof. Yuval Ishai (short term visits, 2012)
 Prof. Giuseppe (a.k.a. Pino) Persiano (short term visit 2012)
 Prof. Yuval Rabani (short term visits 2009,2010,2011,2012)
 Prof. Eyal Kushulevitz (short term visits, 2011, 2012)
 Prof. Ivan Vinsconti (Sabbatical from U. Salerno, 201012)
 Dr. Serge Fehr (short term visit, 2011)
 Prof. Yuval Ishai (3year Sabbatical from Technion 20092011)
 Claudio Orlandi (6month visit from Aaharus, 2010)
 Prof. Eyal Kushilevitz (6month sabbatical from Technion, 2010)
Useful: Fun:
Rafail Ostrovsky
University of California, Los Angeles
Department of Computer Science
3732D Boelter Hall
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:
Janice Wheeler Martin ;
Phone: (310) 8257879;
Email: jjmartin (at) cs.ucla.edu