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.2018.52
URN: urn:nbn:de:0030-drops-85014
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8501/
Go to the corresponding LIPIcs Volume Portal

Onodera, Taku ; Shibuya, Tetsuo

Succinct Oblivious RAM

pdf-format:
LIPIcs-STACS-2018-52.pdf (0.6 MB)

Abstract

As online storage services become increasingly common, it is important that users' private information is protected from database access pattern analyses. Oblivious RAM (ORAM) is a cryptographic primitive that enables users to perform arbitrary database accesses without revealing any information about the access pattern to the server. Previous ORAM studies focused mostly on reducing the access overhead. Consequently, the access overhead of the state-of-the-art ORAM constructions are almost at practical levels in certain application scenarios such as secure processors. However, we assume that the server space usage could become a new important issue in the coming big-data era. To enable large-scale computation in security-aware settings, it is necessary to rethink the ORAM server space cost using big-data standards.
In this paper, we introduce "succinctness" as a theoretically tractable and practically relevant criterion of the ORAM server space efficiency in the big-data era. We, then, propose two succinct ORAM constructions that also exhibit state-of-the-art performance in terms of the bandwidth blowup and the user space. We also give non-asymptotic analyses and simulation results which indicate that the proposed ORAM constructions are practically effective.

BibTeX - Entry

@InProceedings{onodera_et_al:LIPIcs:2018:8501,
  author =	{Taku Onodera and Tetsuo Shibuya},
  title =	{{Succinct Oblivious RAM}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8501},
  URN =		{urn:nbn:de:0030-drops-85014},
  doi =		{10.4230/LIPIcs.STACS.2018.52},
  annote =	{Keywords: Oblivious RAM, Succinct data structure, Balls-into-bins}
}

Keywords: Oblivious RAM, Succinct data structure, Balls-into-bins
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

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