Paper 2015/570 Original: eprint.iacr.org/2015/570 ↗
Constant Communication ORAM with Small Blocksize
Abstract
There have been several attempts recently at using homomorphic encryption to increase the efficiency of Oblivious RAM protocols. One of the most successful has been Onion ORAM, which achieves O(1) communication overhead with polylogarithmic server computation. However, it has two drawbacks. It requires a large block size of B = Omega(log^6 N) with large constants. Moreover, while it only needs polylogarithmic computation complexity, that computation consists mostly of expensive homomorphic multiplications. In this work, we address these problems and reduce the required block size to Omega(log^4 N). We remove most of the homomorphic multiplications while maintaining O(1) communication complexity. Our idea is to replace their homomorphic eviction routine with a new, much cheaper permute-and-merge eviction which eliminates homomorphic multiplications and maintains the same level of security. In turn, this removes the need for layered encryption that Onion ORAM relies on and reduces both the minimum block size and server computation.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2015-08-13: last updated
- 2015-06-17: published
- Short URL
- https://ia.cr/2015/570
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2015/570,
author = {Tarik Moataz and Travis Mayberry and Erik-Oliver Blass},
title = {Constant Communication ORAM with Small Blocksize},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/570},
year = {2015},
url = {https://eprint.iacr.org/2015/570}
}