International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Rafail Ostrovsky (#341)
Name Rafail Ostrovsky
Personal Homepage
Topic of his/her doctorate. Software Protection and Simulation on Oblivious RAMs.
Category foundations
Year of completion 1992

A machine is oblivious if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, it is independent of the actual input.) What is the slowdown in the running time of any machine, if it is required to be oblivious? In 1979 Pippenger and Fischer showed how a two-tape oblivious Turing Machine can simulate, on-line, a one-tape Turing Machine, with a logarithmic slowdown in the running time. We show an analogue result for the random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of an arbitrary RAM input by a probabilistic oblivious RAM with a poly-logarithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound. Our proof yields a technique of efficiently hiding (through randomization) the access pattern into any composite data-structure which has many practical applications.

comment: M.I.T. Ph.D. Thesis, 1992. Preliminary version appeared as a single-author paper in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90) pp. 514-523.

Journal version (which combines my thesis with Oded Goldreich previous paper on the same subject) appeared in JACM Vol. 43, No. 3, May 1996, pp.431-473.

Last Change 2011-04-16 13:11:16
To provide an update on this entry, please click .

Rafail Ostrovsky's Students

Vipul Goyal - Stronger Notions of Secure Computation (foundations)
Nishanth Chandran - Theoretical Foundations of Position-Based Cryptography (cryptographic protocols)

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR