Towards Practical ORAMs

  • Tarik Moataz | Colorado State University and Telecom Bretagne

Although Oblivious RAM (ORAM) has recently received a lot of attention, its high communication and storage cost still render it impractical for real-world scenarios. We present a general construction to reduce the communication cost of all recent tree-based ORAMs. The main idea behind our new construction dubbed “r-ORAM” is a recursive ORAM tree structure, where nodes in the tree are roots of other trees. We demonstrate that the expected cost saving is around 35% for any binary tree ORAMs. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 20%. r-ORAM is general and can be applied to all recent tree ORAMs, both constant memory or poly-log client memory ORAMs. Furthermore, we will introduce first steps towards “Resizable ORAM”, enabling a client to adapt and change their ORAM’s storage requirement and therefore cost in any tree based ORAM.

Speaker Details

Tarik Moataz is a second year Ph.D. student in a French-American joint Ph.D. program between Colorado State University and Telecom Bretagne. His main interest lies in designing new cryptographic protocols for operating on outsourced data. Tarik received his M.S. degree in information technology from Telecom Bretagne and an M.S. in mathematics and computer science from the University of Rennes 1. His master thesis on searchable encryption was done while at Bell Labs France. Currently, he is a visiting scholar at Northeastern University.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks