Paper 2023/1676
FutORAMa: A Concretely Efficient Hierarchical Oblivious RAM
, Bar-Ilan University, Hebrew University of Jerusalem, NTT Research, Bar-Ilan UniversityAbstract
Oblivious RAM (ORAM) is a general-purpose technique for hiding memory access patterns. This is a fundamental task underlying many secure computation applications. While known ORAM schemes provide optimal asymptotic complexity, despite extensive efforts, their concrete costs remain prohibitively expensive for many interesting applications. The current state-of-the-art practical ORAM schemes are suitable only for somewhat small memories (Square-Root ORAM or Path ORAM). This work presents a novel concretely efficient ORAM construction based on recent breakthroughs in asymptotic complexity of ORAM schemes (PanORAMa and OptORAMa). We bring these constructions to the realm of practically useful schemes by relaxing the restriction on constant local memory size. Our design provides a factor of at least $6$ to $8$ improvement over an implementation of the original Path ORAM for a set of reasonable memory sizes (e.g., 1GB, 1TB) and with the same local memory size. To our knowledge, this is the first practical implementation of an ORAM based on the full hierarchical ORAM framework. Prior to our work, the belief was that hierarchical ORAM-based constructions were inherently too expensive in practice. We implement our design and provide extensive evaluation and experimental results.
Note: Full version. Code is available at: https://github.com/cryptobiu/FutORAMa
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ACM CCS 2023
- DOI
- 10.1145/3576915.3623125
- Keywords
- Oblivious RAMimplementation
- Contact author(s)
-
Gilad Asharov @ biu ac il
ilank @ cs huji ac il
Yehuda Michelson @ gmail com - History
- 2023-11-09: revised
- 2023-10-29: received
- See all versions
- Short URL
- https://ia.cr/2023/1676
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1676,
author = {Gilad Asharov and Ilan Komargodski and Yehuda Michelson},
title = {{FutORAMa}: A Concretely Efficient Hierarchical Oblivious {RAM}},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1676},
year = {2023},
doi = {10.1145/3576915.3623125},
url = {https://eprint.iacr.org/2023/1676}
}
