Paper 2019/736

Onion Ring ORAM: Efficient Constant Bandwidth Oblivious RAM from (Leveled) TFHE

Hao Chen, Ilaria Chillotti, and Ling Ren

Abstract

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to hide access pattern to its data encrypted and stored at a remote server. Traditionally, ORAM algorithms assume the server acts purely as a storage device. Under this assumption, ORAM has at least $\log(N)$ bandwidth blowup for $N$ data entries. After three decades of improvements, ORAM algorithms have reached the optimal logarithmic bandwidth blowup. Nonetheless, in many practical use-cases, a constant bandwidth overhead is desirable. To this purpose, Devadas et al. (TCC 2016) formalized the server computation model for ORAM and proposed Onion ORAMwhich relies on homomorphic computation to achieve constant worst-case bandwidth blowup. This line of work is generally believed to be purely theoretical, due to the large overheads of homomorphic computation. In this paper, we present Onion Ring ORAM, the first efficient constant bandwidth ORAM scheme in the single server model, based on the Onion ORAM construction and the leveled version of the TFHE scheme by Chillotti et al.. We propose a series of improvements, most notably including a more efficient homomorphic permutation protocol. We implement Onion Ring ORAM and show that it can outperform state-of-the-art logarithmic-bandwidth ORAM like Path ORAMs and Ring ORAM when the network throughput is limited. Under one setting, our construction reduces monetary cost per access by 40\% and end-to-end latency by 35\% over Ring ORAM.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. CCS
Keywords
Homomorphic EncryptionOblivious RAM
Contact author(s)
haoche @ microsoft com
renling @ illinois edu
History
2019-09-19: revised
2019-06-21: received
See all versions
Short URL
https://ia.cr/2019/736
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/736,
      author = {Hao Chen and Ilaria Chillotti and Ling Ren},
      title = {Onion Ring {ORAM}: Efficient Constant Bandwidth Oblivious {RAM} from (Leveled) {TFHE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/736},
      year = {2019},
      url = {https://eprint.iacr.org/2019/736}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.