### Differentially Oblivious Turing Machines

##### Abstract

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)
Category
Foundations
Publication info
Published elsewhere. ITCS 2021
Keywords
Differential privacy Turing machines obliviousness
Contact author(s)
ilank @ cs huji ac il
runting @ gmail com
History
2022-07-07: approved
See all versions
Short URL
https://ia.cr/2022/883

CC BY

BibTeX

@misc{cryptoeprint:2022/883,
author = {Ilan Komargodski and Elaine Shi},
title = {Differentially Oblivious Turing Machines},
howpublished = {Cryptology ePrint Archive, Paper 2022/883},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/883}},
url = {https://eprint.iacr.org/2022/883}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.