Welcome to the resource topic for 2022/883
Title:
Differentially Oblivious Turing Machines
Authors: Ilan Komargodski and Elaine Shi
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.
ePrint: https://eprint.iacr.org/2022/883
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .