Paper 2017/964

Recursive ORAMs with Practical Constructions

Sarvar Patel, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAM
Contact author(s)
kwlyeo @ google com
History
2017-10-01: received
Short URL
https://ia.cr/2017/964
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/964,
      author = {Sarvar Patel and Giuseppe Persiano and Kevin Yeo},
      title = {Recursive ORAMs with Practical Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/964},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/964}},
      url = {https://eprint.iacr.org/2017/964}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.