License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.554
URN: urn:nbn:de:0030-drops-44876
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4487/
Go to the corresponding LIPIcs Volume Portal

Mitchell, John C. ; Zimmerman, Joe

Data-Oblivious Data Structures

pdf-format:
45.pdf (0.6 MB)

Abstract

An algorithm is called data-oblivious if its control flow and memory access pattern do not depend on its input data. Data-oblivious algorithms play a significant role in secure cloud computing, since programs that are run on secret data—as in fully homomorphic encryption or secure multi-party computation—must be data-oblivious. In this paper, we formalize three definitions of data-obliviousness that have appeared implicitly in the literature, explore their implications, and show separations. We observe that data-oblivious algorithms often compose well when viewed as data structures. Using this approach, we construct data-oblivious stacks, queues, and priority queues that are considerably simpler than existing constructions, as well as improving constan factors. We also establish a new upper bound for oblivious data compaction, and use this result to show that an "offline" variant of the Oblivious RAM problem can be solved with O(log(n).log(log(n))) expected amortized time per operation - as compared with O(log^2(n)/log(log(n))), the best known upper bound for the standard online formulation.

BibTeX - Entry

@InProceedings{mitchell_et_al:LIPIcs:2014:4487,
  author =	{John C. Mitchell and Joe Zimmerman},
  title =	{{Data-Oblivious Data Structures}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{554--565},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4487},
  URN =		{urn:nbn:de:0030-drops-44876},
  doi =		{10.4230/LIPIcs.STACS.2014.554},
  annote =	{Keywords: Data-oblivious algorithms, Data-oblivious data structures, Oblivious RAM, Secure multi-party computation, Secure cloud computing}
}

Keywords: Data-oblivious algorithms, Data-oblivious data structures, Oblivious RAM, Secure multi-party computation, Secure cloud computing
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI