Cryptology ePrint Archive: Report 2015/570

Constant Communication ORAM with Small Blocksize

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

Category / Keywords: cryptographic protocols / oblivious ram

Original Publication (in the same form): ACM CCS 2015

Date: received 9 Jun 2015, last revised 13 Aug 2015

Contact author: tmoataz at cs colostate edu

Available format(s): PDF | BibTeX Citation

Version: 20150813:185056 (All versions of this report)

Short URL: ia.cr/2015/570

Discussion forum: Show discussion | Start new discussion