Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues
<|reference_start|>Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues: 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 $\Theta(\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 $\Theta(\frac{1}{B} \log \frac{N}{M})$ per operation (amortized), and for the cache-oblivious setting we achieve a near-optimal I/O complexity of $O(\frac{1}{B} \log \frac{N}{M} \log\log_M N)$ per operation (amortized).<|reference_end|>
@article{thießen2024optimal,
    title={Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority
  Queues},
    author={Thore Thie{ss}en and Jan Vahrenhold},
    journal={Thore Thie{\ss}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), 19 pages. 2024},
    year={2024},
    doi={10.4230/LIPIcs.ISAAC.2024.36},
    archivePrefix={arXiv},
    eprint={2409.12021},
    primaryClass={cs.DS cs.CR}
}