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:
DMS-9206267;
CNS-0430254;
CNS-0716835;
CNS-0716389;
CNS-0830803;
CCF-0916574;
IIS-1065276;
CCF-1016540;
CNS-1118126;
CNS-1136174);
DARPA (Defense Advanced Research Projects Agency through the U.S. Office of Naval Research under Contract N00014-11-1-0392);
Binational Science Foundation
(BSF-2002354; BSF-2008411);
OKAWA Foundation;
B. John Garrick Foundation;
UC Microelectonrics Innovation and Computer Research grants;
Intel Corporation;
IBM;
Lockheed-Martin Corporation;
Teradata Corporation; and
Xerox Corporation.
I am interested in all aspects of theory of computation,
especially in cryptography, network algorithms,
and search and classification of large-scale, high-dimensional data.
I find these topics fascinating to work on, not only due to their
philosophical and theoretical centrality in computer science, but also due
to their practical significance.
Below, is a more detailed list of topics, with links to papers
written on each topic.
(You can also search Publications by Year
or
Google Scholar or
DBLP.)
The papers below are also available in a chronological list or organized by topics.
More information can be found at
DBLP.
For additions in 2009-2010, look for the signs.
Survey:
Rafail Ostrovsky, William Skeith
A Survey of Single-Database Private Information Retrieval: Techniques and Applications.
Preliminary version (PKC-2007). Full version appeared as a book chapter in
"Homeland Security Technology Challenges From Sensing and Encrypting to Mining a
nd Modeling" Franceschetti and Grossi, (EDT), Artec-House publishers.
Rafail Ostrovsky, William Skeith.
Private Searching on Streaming Data, Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) Springer-Verlag/IACR Lecture Notes in Computer Science.
Full version in Journal of Cryptography, 2007.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Sufficient Conditions for Collision-Resistant Hashing,
In Proceedings of Second Theory of Cryptography Conference (TCC-2005)Springer-Verlag Lecture Notes in Computer Science, 2005.
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Batch Codes and Their Applications,
In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC-2004).
Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Guiseppe Persiano
Public Key Encryption with Keyword Search,
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2004)
Springer-Verlag/IACR Lecture Notes in Computer Science.
Giovanni De-Crescenzo,
Yuval Ishai, Rafail Ostrovsky
Universal Service-Providers for
Database Private Information Retrieval
,
In
Proceedings of Seventeenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-98). Journal
version appears in Journal of Cryptology 14(1): 37-74 (2001).
Rafail Ostrovsky, Victor Shoup
Private Information Storage
,
In Proceedings of
The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97).
Rafail Ostrovsky
Software Protection and Simulation on Oblivious RAMs.
,
M.I.T. Ph.D. Thesis, 1992. Preliminary version appeared in
Proceedings of 22nd annual ACM Symposium on Theory of
Computing (STOC-90) pp. 514-523.
Journal version appeared in the Journal of the JACM,
Vol. 43, No. 3, May 1996, pp.431-473.
written jointly with Oded Goldreich.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Efficient Arguments without Short PCPs.
Preliminary version appeared in IEEE Conference on Computational Complexity 2007
: 278-291 (ECCC-2007).
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Zero-Knowledge from Secure Multiparty Computation,
In Proceedings of the ACM 2007 Symposium on Theory of Computing (STOC-2007).
Full version
invited and accepted to SIAM Journal of Computing (SICOMP)
special issue devoted to STOC-2007.
Jens Groth, Rafail Ostrovsky, Amit Sahai.
Non-interactive Zaps and New Techniques for NIZK,
In Proceedings of Advances in Cryptology, (CRYPTO-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
Jens Groth, Rafail Ostrovsky, Amit Sahai.
Perfect Non-Interactive Zero Knowledge for NP,
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin
Identity-Based Zero-Knowledge,
In Proceedings of Security in Communication Networks: 4th International Conference, SCN-2004
Springer-Verlag Lecture Notes in Computer Science.
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai
Robust Non-Interactive Zero Knowledge,
In Proceedings of Advances in Cryptology, (CRYPTO-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
Computational Complexity and Knowledge Complexity.
,
Preliminary
version in
the
Twenty-sixth ACM Symposium on Theory of Computing (STOC-94)
Full version in SIAM Journal on Computing, 27(4):1116-1141, 1998.
Joe Kilian, Silvio Micali, Rafail Ostrovsky
Minimum Resource Zero-Knowledge Proofs.
,
In Proceedings of 30th annual
IEEE Symposium on
the Foundations of Computer Science (FOCS-89).
Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith.
Secure Authentication Using Biometric Data,
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2005) Springer-Verlag/IACR Lecture Notes in Computer Science.
Jonathan Katz, Rafail Ostrovsky, Moti Yung
Forward Security in Password-Only Key Exchange Protocols,
In Proceedings of Security in Communication Networks 2002 conference (CSN-2002)
Springer-Verlag Lecture Notes in Computer Science.
Ari Juels, Michael Luby, Rafail Ostrovsky
Security of Blind Digital Signatures
,
In Proceedings of advances in cryptology, (CRYPTO-97)
Springer-Verlag Lecture Notes in Computer Science.
Jonathan Katz, Rafail Ostrovsky
Round-Optimal Secure Two-Party Computation,
In Proceedings of Advances in Cryptology, (CRYPTO-2004) Springer-Verlag/IACR Lecture Notes in Computer Science.
Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky
Minimal Complete Primitives for Secure Multi-Party Computation
,
Journal of Cryptology
Springer-Verlag
Volume 18, Number 1, January 2005
pp.37 - 61.
Preliminary version in
Proceedings of Advances in Cryptology, (CRYPTO-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Randomness vs. Fault-Tolerance
,
In
Proceedings of Sixteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-97).
Journal version in Journal of Cryptology 13(1): 107-142 (2000).
Eyal Kushilevitz, Rafail Ostrovsky,
Adi Rosen
Characterizing Linear Size Circuits in Terms of Privacy.
,
Invited paper to the
Journal of Computer and System
Sciences
special issue for STOC 96. In Vol 58, JCSS 58(1): 129-136 (1999).
Preliminary version appeared in the
Proceedings of
The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96).
Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky
Reducibility and Completeness In Multi-Party Private Computations.
,
Preliminary version appeared in
Proceedings of Thirty-fifth Annual
IEEE Symposium on
the Foundations of Computer Science (FOCS-94).
Journal version in SIAM J. Comput. 29(4): 1189-1208 (2000).
Rafail Ostrovsky, Moti Yung.
How to Withstand Mobile Virus Attacks.
In Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC-91).
Rafail Ostrovsky and Moti Yung.
On Necessary Conditions for Secure Distributed Computation.
,
In
DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, Volume 2. 1990.
Proceedings of a DIMACS
workshop, October 4-6, 1989, pp. 229-234.
Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith
Efficient and Non-interactive Non-malleable Commitment
,
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung Fair Games Against an All-Powerful
Adversary, Presented in DIMACS Complexity and Cryptography Workshop, Princeton, October 1990.
Extended abstract in proceedings of Sequences II, June 1991, Positano, Italy, R.M. Capocelli, A. De-Santis and U. Vaccaro (Eds.), Springer-Verlag.
Journal version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 13. (Jin-Yi Cai ed.) pp. 155-169, 1991.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Sufficient Conditions for Collision-Resistant Hashing,
In Proceedings of Second Theory of Cryptography Conference (TCC-2005)Springer-Verlag Lecture Notes in Computer Science, 2005.
Shlomi Dolev, Rafail Ostrovsky
Efficient Anonymous Multicast and Reception
,
Preliminary version in proceedings of advances in cryptology, (CRYPTO-97)
Springer-Verlag Lecture Notes in Computer Science.
Journal version in ACM Trans. Inf. Syst. Secur. 3(2): 63-84 (2000)
William Aiello, Sachin Lodha, Rafail Ostrovsky
Fast Digital Identity Revocation
,
In Proceedings
of advances in cryptology, (CRYPTO-98)
Springer-Verlag Lecture Notes in Computer Science.
Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky
Deniable Encryption.,
In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
Richard J. Lipton, Rafail Ostrovsky
Micro-Payments via Efficient Coin-Flipping
,
In Proceedings of Second
Financial Cryptography Conference,
(FINANCIAL CRYPTO-98)
February 1998. Lecture Notes in Computer Science
LNCS volume 1465
Publications: Search and Analysis of High-Dimensional Data
Rafail Ostrovsky, William Skeith.
Private Searching on Streaming Data, Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) Springer-Verlag/IACR Lecture Notes in Computer Science.
Full version in Journal of Cryptography, 2007.
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Lower Bounds for High Dimensional Nearest Neighbor Search
and Related Problems
,
Book Chapter In Discrete and Computational Geometry -
The Goodman-Pollack Festschrift. Algorithms and Combinatorics Series 3143,
Springer Verlag, Berlin, August 2003, pages 252-274.
Preliminary version appeared in STOC '99.
William Aiello,
Eyal Kushilevitz, Rafail Ostrovsky,
Adi Rosen
Adaptive Packet Routing for Bursty Adversarial Traffic
,
In
Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC-98).
Journal version appeared in JCSS 60(3): 482-509 (2000).
Eyal Kushilevitz, Nati Linial, Rafail Ostrovsky
The Linear-Array Conjecture in Communication Complexity is False.
,
Preliminary version in
Proceedings of
The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96)
Journal version in Combinatorica 19(2): 241-254 (1999)
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
LOG-Space
Polynomial End-to-End Communication
,
In SIAM Journal of Computing Volume 27, 1998. SIAM J. Comput. 27(6): 1531-1549 (1998).
Preliminary version appeared in the Proceedings of
Twenty-seventh ACM Symposium on Theory of Computing STOC-95.
Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir.
The Las-Vegas Processor Identity Problem
,
In Proceedings of the Second
Israel Symposium on Theory of Computing and Systems (ISTCS-93)
Journal version appeared in
J. Algorithms 37(2): 468-494 (2000).
Rafail Ostrovsky, Yuval Rabani, Leonard Schulman.
Error-Correcting Codes for Automatic Control,
In Proceedings of 46th Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2005).
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Batch Codes and Their Applications,
In Proceedings of the ACM 2004 Symposium on Theory of Computing (STOC-2004).
Noga Alon, Manuel Blum, Amos Fiat, Sampath K. Kannan, Moni
Naor, Rafail Ostrovsky Matching Nuts and
Bolts. , In Proceedings of the Fifth Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA-94),
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 high-dimensional search
problems.
Prof. Ostrovsky is a Fellow of the IACR; he has 10 U.S. patents issued and over 170 papers
published in refereed journals
and conferences.
Dr. Ostrovsky currently serves as Vice-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
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 serves on UC-wide
Privacy and Information Security Steering Committee, appointed by University of California President Mark G. Yudof.
Dr. Ostrovsky is also a
Board Member of UCLA Advisory Board On Privacy and Data Protection.
Dr. Ostrovsky was invited (among only a few academics) to participate in U.S. Air Force Third Annual National Security Scholars Conference in 2011, 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:
the Best Paper Award of the 2008 International Conference on Computing and
Combinatorics (COCOON-2008);
2006 and 2005 Xerox Corporate Innovation Faculty Awards;
2006 IBM Faculty Award;
2006 Xerox Corporation Distinguished Lecture Series;
2005 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 PC-ranked STOC/FOCS articles.
At UCLA, Prof. Ostrovsky heads security and cryptography
multi-disciplinary
Research Center
(http://www.cs.ucla.edu/security/)
at Henry Samueli School of Engineering and Applied Science.
Invited talk:
Novel Privacy-Enhancing Technologies
UCLA Henry Samueli School of Enginnering and Applied Science, 2012 Technology Forum,
March 13, 2012.
Invited talk: Bertinoro
Invited one-week course, International PhD School
on Mathematical Aspects of Modern Cryptography, Bertinoro, Italy
September 4-9, 2005.