Rafail Ostrovsky

Rafail Ostrovsky received his Ph.D. from MIT in 1992.

He is a member of the Editorial Board of Algorithmica , Editorial Board of Journal of Cryptology and Editorial and Advisory Board of the International Journal of Information and Computer Security .

• 2018 RSA Award for Excellence in Mathematics
• 2006 IBM Faculty Award
• 2006 and 2005 Xerox Innovation Group Award
• 2004 OKAWA Research Award; the 1993 Henry Taub Prize
• 1999, 2001, and 2002 best published work of the year at SAIC in computer science and mathematics.
• 1996 Bellcore prize for excellence in research

Some of Ostrovsky's contributions to computer science include:

• 1990 Introduced (with R. Venkatesan and M. Yung) the notion of interactive hashing proved essential for constructing statistical zero-knowledge proofs for NP based on any one-way function (see NOVY and ECCC TR06-075).
• 1991 Introduced (with M. Yung) the notion of mobile adversary (later renamed proactive security) (see survey of Goldwasser 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 Microprocessor
• 1993 Proved (with A. Wigderson) equivalence of one-way functions and zero-knowledge .
• 1996 Introduced (with R. Canetti, C. Dwork and M. Naor) the notion of deniable encryption .
• 1997 Invented (with E. Kushilevitz) the first single server private information retrieval protocol (see over 400 citations in Google Scholar).
• 1997 Showed (with E. Kushilevitz and Y. Rabani) (1+ε) poly-time and poly-size approximate-nearest neighbor search for high-dimensional data for L1-norm and Euclidean space (see over 320 citations in Google Scholar).

• Ostrovsky's home page
• Some of Ostrovsky's publications