Oblivious RAM with O((logN)^3) Worst-Case Cost

TitleOblivious RAM with O((logN)^3) Worst-Case Cost
Publication TypeBook Chapters
Year of Publication2011
AuthorsElaine Shi, Chan T, Stefanov E, Li M
EditorLee D, Wang X
Book TitleAdvances in Cryptology – ASIACRYPT 2011
Series TitleLecture Notes in Computer Science
Pagination197 - 214
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-642-25384-3
KeywordsComputer science

Oblivious RAM is a useful primitive that allows a client to hide its data access patterns from an untrusted server in storage outsourcing applications. Until recently, most prior works on Oblivious RAM aim to optimize its amortized cost, while suffering from linear or even higher worst-case cost. Such poor worst-case behavior renders these schemes impractical in realistic settings, since a data access request can occasionally be blocked waiting for an unreasonably large number of operations to complete. This paper proposes novel Oblivious RAM constructions that achieves poly-logarithmic worst-case cost, while consuming constant client-side storage. To achieve the desired worst-case asymptotic performance, we propose a novel technique in which we organize the O-RAM storage into a binary tree over data buckets, while moving data blocks obliviously along tree edges.