Towards Practical ORAMs

Опубликовано 27 июня 2016, 20:34

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.