Paper 2018/471
Efficient Range ORAM with 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
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
-
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} }