Paper 2019/736

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

Hao Chen, Ilaria Chillotti, and Ling Ren


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. CCS
Homomorphic EncryptionOblivious RAM
Contact author(s)
haoche @ microsoft com
renling @ illinois edu
2019-09-19: revised
2019-06-21: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.