#
Lower Bounds for Oblivious Data Structures

## Riko Jacobs

An oblivious data structure is a data structure where the memory
access patterns reveals no information about the operations performed
on it. Such data structures were introduced by Wang \emph{et al.} [ACM SIGSAC'14] and are intended for
situations where one wishes to store the data structure at an
untrusted server. One way to obtain an oblivious data structure is
simply to run a classic data structure on an oblivious RAM
(ORAM). Until very recently, this resulted in an overhead of
$\omega(\lg n)$ for the most natural setting of parameters. Moreover,
a recent lower bound for ORAMs by Larsen and Nielsen [CRYPTO'18]
show that they always incur an overhead
of at least $\Omega(\lg n)$ if used in a black box manner. To circumvent the
$\omega(\lg n)$ overhead, researchers have instead studied
classic data structure problems more directly and have obtained
efficient solutions for many such problems such as stacks, queues, deques,
priority queues and search trees. However, none of these data
structures process operations faster than $\Theta(\lg n)$, leaving open the
question of whether even faster solutions exist. In this paper, we
rule out this possibility by proving $\Omega(\lg n)$ lower bounds for
oblivious stacks, queues, deques, priority queues and search trees.