Paper 2015/570

Constant Communication ORAM with Small Blocksize

Tarik Moataz, Travis Mayberry, and Erik-Oliver Blass

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
Published elsewhere. ACM CCS 2015
Keywords
oblivious ram
Contact author(s)
tmoataz @ cs colostate edu
History
2015-08-13: last of 3 revisions
2015-06-17: received
See all versions
Short URL
https://ia.cr/2015/570
License
Creative Commons Attribution
CC BY

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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.