Paper 2015/1116

CHf-ORAM: A Constant Communication ORAM without Homomorphic Encryption

Tarik Moataz, Erik-Oliver Blass, and Travis Mayberry


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Oblivious RAM
Contact author(s)
tarik moataz @ colostate edu
2016-05-25: last of 2 revisions
2015-11-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tarik Moataz and Erik-Oliver Blass and Travis Mayberry},
      title = {CHf-ORAM: A Constant Communication ORAM without Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1116},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.