Cryptology ePrint Archive: Report 2019/736

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

Hao Chen and 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 ORAM which 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 improves the end-to-end latency by 1.5 times over Ring ORAM and 7.3 times over Path ORAM.

Category / Keywords: cryptographic protocols / Homomorphic Encryption, Oblivious RAM

Date: received 20 Jun 2019

Contact author: haoche at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20190621:135852 (All versions of this report)

Short URL: ia.cr/2019/736


[ Cryptology ePrint archive ]