Paper 2022/883

Differentially Oblivious Turing Machines

Ilan Komargodski, Hebrew University of Jerusalem, NTT Research
Elaine Shi, Carnegie Mellon University

Oblivious RAM (ORAM) is a machinery that protects any RAM from leaking information about its secret input by observing only the access pattern. It is known that every ORAM must incur a logarithmic overhead compared to the non-oblivious RAM. In fact, even the seemingly weaker notion of differential obliviousness, which intuitively ``protects'' a single access by guaranteeing that the observed access pattern for every two ``neighboring'' logical access sequences satisfy $(\epsilon,\delta)$-differential privacy, is subject to a logarithmic lower bound. In this work, we show that any Turing machine computation can be generically compiled into a differentially oblivious one with only doubly logarithmic overhead. More precisely, given a Turing machine that makes $N$ transitions, the compiled Turing machine makes $O(N \cdot \log\log N)$ transitions in total and the physical head movements sequence satisfies $(\epsilon,\delta)$-differential privacy (for a constant $\epsilon$ and a negligible $\delta$). We additionally show that $\Omega(\log\log N)$ overhead is necessary in a natural range of parameters (and in the balls and bins model). As a corollary, we show that there exist natural data structures such as stack and queues (supporting online operations) on $N$ elements for which there is a differentially oblivious implementation on a Turing machine incurring amortized $O(\log\log N)$ overhead per operation, while it is known that any oblivious implementation must consume $\Omega(\log N)$ operations unconditionally even on a RAM. Therefore, we obtain the first \emph{unconditional} separation between obliviousness and differential obliviousness in the most natural setting of parameters where $\epsilon$ is a constant and $\delta$ is negligible. Before this work, such a separation was only known in the balls and bins model. Note that the lower bound applies in the RAM model while our upper bound is in the Turing machine model, making our separation stronger.

Available format(s)
Publication info
Published elsewhere. ITCS 2021
Differential privacy Turing machines obliviousness
Contact author(s)
ilank @ cs huji ac il
runting @ gmail com
2022-07-07: approved
2022-07-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ilan Komargodski and Elaine Shi},
      title = {Differentially Oblivious Turing Machines},
      howpublished = {Cryptology ePrint Archive, Paper 2022/883},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.