International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 17 June 2015

Tarik Moataz, Travis Mayberry, Erik-Oliver Blass
ePrint Report ePrint Report
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 com- putation. However, it has a number of drawbacks. It requires a very large block size of B = Ω(log^5 N), with large constants. Although it needs only polylogarithmic computation complexity, that computation consists mostly of expensive homomorphic mul- tiplications. Finally, it achieves O(1) communication complexity but only amortized over a number of accesses. In this work we aim to address these problems, reducing the required block size to Ω(log^3 N), removing almost all of the homomorphic multiplica- tions and achieving O(1) worst-case communication complexity. We achieve this by replacing their homomorphic eviction routine with a much less expensive permute-and-merge one which elim- inates homomorphic multiplications while maintaining the same level of security. In turn, this removes the need for layered encryp- tion that Onion ORAM relies on and reduces both the minimum block size and worst-case bandwidth.

Expand

Additional news items may be found on the IACR news page.