Cryptology ePrint Archive: Report 2015/1116

CHf-ORAM: A Constant Communication ORAM without Homomorphic Encryption

Tarik Moataz and Erik-Oliver Blass and Travis Mayberry

Abstract: Recent techniques reduce ORAM communication complexity down to constant in the number of blocks N. However, they induce expensive homomorphic encryption on both the server and the client. In this paper, we present an alternative approach CHf-ORAM. This ORAM features constant communication complexity without homomorphic encryption, in exchange for expanding the traditional ORAM setting from single-server to multiple non-colluding servers. We show that adding as few as 4 servers allows for substantially reduced client and server computation compared to existing single-server alternatives. Our approach uses techniques from information-theoretically secure Private Information Retrieval to replace homomorphic encryption with simple XOR operations. Besides O(1) communication complexity, our construction also features O(1) client memory and a block size of only Omega(log^3 N). This leads to an ORAM which is extremely lightweight and suitable for deployment even on memory and compute constrained devices. Finally, CHf-ORAM features a circuit size which is constant in the blocksize making it especially attractive for secure RAM computations.

Category / Keywords: cryptographic protocols / Oblivious RAM

Date: received 17 Nov 2015, last revised 25 May 2016

Contact author: tarik moataz at colostate edu

Available format(s): PDF | BibTeX Citation

Version: 20160525:211851 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]