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
-
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},
url = {https://eprint.iacr.org/2015/1116}
}