Rafail Ostrovsky

Biography

Awards

• 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

  Publications

• 1990 Introduced the notion of proved essential for constructing statistical zero-knowledge proofs for NP based on any one-way function.
• 1991 Introduced the notion of
• 1992 Proved the existence of asymptotically optimal scheme assuming the existence of Tamper-resistant Microprocessor
• 1993 Proved equivalence of one-way functions and zero-knowledge .
• 1996 Introduced the notion of deniable encryption .
• 1997 Invented the first single server private information retrieval protocol .
• 1997 Showed poly-time and poly-size approximate-nearest neighbor search for high-dimensional data for L1-norm and Euclidean space.