DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.55

Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues

Authors: Thore Thießen and Jan Vahrenhold

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

Oblivious RAM (ORAM) is a well-researched primitive to hide the memory access pattern of a RAM computation; it has a variety of applications in trusted computing, outsourced storage, and multiparty computation. In this paper, we study the so-called offline ORAM in which the sequence of memory access locations to be hidden is known in advance. Apart from their theoretical significance, offline ORAMs can be used to construct efficient oblivious algorithms. We obtain the first optimal offline ORAM with perfect security from oblivious priority queues via time-forward processing. For this, we present a simple construction of an oblivious priority queue with perfect security. Our construction achieves an asymptotically optimal (amortized) runtime of Θ(log N) per operation for a capacity of N elements and is of independent interest. Building on our construction, we additionally present efficient external-memory instantiations of our oblivious, perfectly-secure construction: For the cache-aware setting, we match the optimal I/O complexity of Θ(1/B log N/M) per operation (amortized), and for the cache-oblivious setting we achieve a near-optimal I/O complexity of O(1/B log N/M log log_M N) per operation (amortized).

Cite as

Thore Thießen and Jan Vahrenhold. Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{thieen_et_al:LIPIcs.ISAAC.2024.55,
  author =	{Thie{\ss}en, Thore and Vahrenhold, Jan},
  title =	{{Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.55},
  URN =		{urn:nbn:de:0030-drops-221832},
  doi =		{10.4230/LIPIcs.ISAAC.2024.55},
  annote =	{Keywords: offline ORAM, oblivious priority queue, perfect security, external memory algorithm, cache-oblivious algorithm}
}

Search Results

Documents authored by Thießen, Thore

Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues

Abstract

Cite as

Thanks for your feedback!

Could not send message