Rafail Ostrovsky
Encyclopedia
Rafail Ostrovsky is a professor
of computer science
and mathematics
at UCLA
and a well-known researcher in algorithms and cryptography
. Prof. Ostrovsky received his Ph.D. from MIT
in 1992. He is a member of the Editorial Board of Algorithmica
http://www.cs.northwestern.edu/~kao/Algorithmica_Editors.htm, Editorial Board of Journal of Cryptology http://www.springer.com/west/home/computer/foundations?SGWID=4-156-70-1009426-detailsPage=journal|editorialBoard and Editorial and Advisory Board of the International Journal of Information and Computer Security http://www.icebnet.org/IJICS/.
Prof. Ostrovsky is a winner of the 2006 IBM Faculty Award; the 2006 and 2005 Xerox Innovation Group Award; the 2004 OKAWA Research Award; the 1993 Henry Taub Prize; 1996 Bellcore prize for excellence in research; and three-time winner of the best published work of the year (1999, 2001, 2002) at SAIC in computer science and mathematics.
Some notable achievements of Prof. Ostrovsky include:
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
of computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
at UCLA
University of California, Los Angeles
The University of California, Los Angeles is a public research university located in the Westwood neighborhood of Los Angeles, California, USA. It was founded in 1919 as the "Southern Branch" of the University of California and is the second oldest of the ten campuses...
and a well-known researcher in algorithms and cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. Prof. Ostrovsky received his Ph.D. from MIT
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
in 1992. He is a member of the Editorial Board of Algorithmica
http://www.cs.northwestern.edu/~kao/Algorithmica_Editors.htm, Editorial Board of Journal of Cryptology http://www.springer.com/west/home/computer/foundations?SGWID=4-156-70-1009426-detailsPage=journal|editorialBoard and Editorial and Advisory Board of the International Journal of Information and Computer Security http://www.icebnet.org/IJICS/.
Prof. Ostrovsky is a winner of the 2006 IBM Faculty Award; the 2006 and 2005 Xerox Innovation Group Award; the 2004 OKAWA Research Award; the 1993 Henry Taub Prize; 1996 Bellcore prize for excellence in research; and three-time winner of the best published work of the year (1999, 2001, 2002) at SAIC in computer science and mathematics.
Some notable achievements of Prof. Ostrovsky include:
- 1990 Introduced (with R. Venkatesan and M. Yung) the notion of interactive hashing proved essential for constructing statistical zero-knowledge proofZero-knowledge proofIn cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement....
s for NP based on any one-way functionOne-way functionIn computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
(see NOVY and ). - 1991 Introduced (with M. Yung) the notion of mobile adversary (later renamed proactive security) (see survey of GoldwasserShafi GoldwasserShafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
http://theory.lcs.mit.edu/~cis/pubs/shafi/1997-podc.pdf) or over 400 citations in Google Scholar) - 1992 Proved the existence of asymptotically-optimal software protection scheme (later renamed searching on encrypted data) assuming the existence of Tamper-resistant MicroprocessorMicroprocessorA microprocessor incorporates the functions of a computer's central processing unit on a single integrated circuit, or at most a few integrated circuits. It is a multipurpose, programmable device that accepts digital data as input, processes it according to instructions stored in its memory, and...
- 1993 Proved (with A. Wigderson) equivalence of one-way functions and zero-knowledge http://www.cs.ucla.edu/~rafail/PUBLIC/14.html.
- 1996 Introduced (with R. Canetti, C. Dwork and M. Naor) the notion of deniable encryptionDeniable encryptionIn cryptography and steganography, deniable encryption is encryption that allows its users to convincingly deny that the data is encrypted, or that they are able to decrypt it. Such convincing denials may or may not be genuine. For example, although suspicions might exist that the data is...
http://www.cs.ucla.edu/~rafail/PUBLIC/29.html. - 1997 Invented (with E. Kushilevitz) the first single server private information retrievalPrivate information retrievalIn cryptography, a private information retrieval protocol allows a user to retrieve an item from a server in possession of a database without revealing which item they are retrieving...
protocol http://www.cs.ucla.edu/~rafail/PUBLIC/34.html (see over 400 citations in Google Scholar). - 1997 Showed (with E. Kushilevitz and Y. Rabani) (1+ε) poly-time and poly-size approximate-nearest neighbor searchNearest neighbor searchNearest neighbor search , also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q...
for high-dimensional data for L1-normNorm (mathematics)In linear algebra, functional analysis and related areas of mathematics, a norm is a function that assigns a strictly positive length or size to all vectors in a vector space, other than the zero vector...
and Euclidean spaceEuclidean spaceIn mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
(see over 320 citations in Google Scholar).