TY - CHAP T1 - Oblivious RAM with O((logN)^3) Worst-Case Cost T2 - Advances in Cryptology – ASIACRYPT 2011 Y1 - 2011 A1 - Elaine Shi A1 - Chan, T. A1 - Stefanov, Emil A1 - Li, Mingfei ED - Lee, Dong ED - Wang, Xiaoyun KW - Computer science AB - 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. JA - Advances in Cryptology – ASIACRYPT 2011 T3 - Lecture Notes in Computer Science PB - Springer Berlin / Heidelberg VL - 7073 SN - 978-3-642-25384-3 UR - http://www.springerlink.com/content/2214q8013376rj37/abstract/ ER -