Paper 2015/570

Constant Communication ORAM with Small Blocksize

Tarik Moataz, Travis Mayberry, and Erik-Oliver Blass


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2015
oblivious ram
Contact author(s)
tmoataz @ cs colostate edu
2015-08-13: last of 3 revisions
2015-06-17: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.