Paper 2018/471

Efficient Range ORAM with $\mathbb{O}(\log^{2}{N})$ Locality

Anrin Chakraborti, Adam J. Aviv, Seung Geol Choi, Travis Mayberry, Daniel S. Roche, and Radu Sion

Abstract

Oblivious RAM protocols (ORAMs) allow a client to access data from an untrusted storage device without revealing to that device any information about their access pattern. Typically this is accomplished through random shuffling of the data such that the storage device cannot determine where individual blocks are located, resulting in a highly randomized access pattern. Storage devices however, are typically optimized for \emph{sequential} access. A large number of random disk seeks during standard ORAM operation induce a substantial overhead. In this paper, we introduce rORAM, an ORAM specifically suited for accessing ranges of \emph{sequentially logical blocks} while \emph{minimizing the number of random physical disk seeks}. rORAM obtains significantly better asymptotic efficiency than prior designs (Asharov et al., ePrint 2017, Demertzis et al., CRYPTO 2018) reducing {\em both} the number of seeks and communication complexity by a multiplicative factor of $\mathbb{O}(\log N)$. An rORAM prototype is 30-50x times faster than Path ORAM for similar range-query workloads on local HDDs, 30x faster for local SSDs, and 10x faster for network block devices. rORAM's novel disk layout can also speed up standard ORAM constructions, e.g., resulting in a 2x faster Path ORAM variant. Importantly, experiments demonstrate suitability for real world applications -- rORAM is up to 5x faster running a file server and up to 11x faster running a range-query intensive video server workloads compared to standard Path ORAM.

Note: Fixes in Abstract

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. Network and Distributed System Security (NDSS 2019)
Keywords
Applied Cryptography
Contact author(s)
anchakrabort @ cs stonybrook edu
History
2018-12-11: last of 3 revisions
2018-05-22: received
See all versions
Short URL
https://ia.cr/2018/471
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/471,
      author = {Anrin Chakraborti and Adam J.  Aviv and Seung Geol Choi and Travis Mayberry and Daniel S.  Roche and Radu Sion},
      title = {Efficient Range {ORAM} with $\mathbb{O}(\log^{2}{N})$ Locality},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/471},
      year = {2018},
      url = {https://eprint.iacr.org/2018/471}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.