**Recursive ORAMs with Practical Constructions**

*Sarvar Patel and Giuseppe Persiano and Kevin Yeo*

**Abstract: **We present Recursive Square Root ORAM (R-SQRT), a simple and flexible ORAM that can be
instantiated for different client storage requirements. R-SQRT requires significantly less bandwidth than
Ring and Partition ORAM, the previous two best practical constructions in their respective classes of
ORAM according to client storage requirements. Specifically, R-SQRT is a 4x improvement in amortized
bandwidth over Ring ORAM for similar server storage. R-SQRT is also a 1.33-1.5x improvement over
Partition ORAM under the same memory restrictions. R-SQRT-AHE, a variant of R-SQRT, is a 1.67-
1.75x improvement over the reported Partition ORAM results in the same settings. All the while,
R-SQRT maintains a single data roundtrip per query. We emphasize the simplicity of R-SQRT which
uses straightforward security and performance proofs.

Additionally, we present Twice-Recursive Square Root ORAM (TR-SQRT) with smaller client stor- age requirements. Due to its flexibility, we construct several instantiations under different memory requirements. TR-SQRT is asymptotically competitive with previous results, yet remarkably simple.

**Category / Keywords: **cryptographic protocols / Oblivious RAM

**Date: **received 30 Sep 2017

**Contact author: **kwlyeo at google com

**Available format(s): **PDF | BibTeX Citation

**Version: **20171001:122758 (All versions of this report)

**Short URL: **ia.cr/2017/964

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]