Paper 2015/1116

CHf-ORAM: A Constant Communication ORAM without Homomorphic Encryption

Tarik Moataz, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAM
Contact author(s)
tarik moataz @ colostate edu
History
2016-05-25: last of 2 revisions
2015-11-18: received
See all versions
Short URL
https://ia.cr/2015/1116
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1116,
      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{https://eprint.iacr.org/2015/1116}},
      url = {https://eprint.iacr.org/2015/1116}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.