Paper 2017/924

Oblivious Hashing Revisited, and Applications to Asymptotically Efficient ORAM and OPRAM

T-H. Hubert Chan, Yue Guo, Wei-Kai Lin, and Elaine Shi

Abstract

Oblivious RAM (ORAM) is a powerful cryptographic building block that allows a program to provably hide its access patterns to sensitive data. Since the original proposal of ORAM by Goldreich and Ostrovsky, numerous improvements have been made. To date, the best asymptotic overhead achievable for general block sizes is $O(\log^2 N/\log \log N)$, due to an elegant scheme by Kushilevitz et al., which in turn relies on the oblivious Cuckoo hashing scheme by Goodrich and Mitzenmacher. In this paper, we make the following contributions: we first revisit the prior $O(\log^2 N/\log \log N)$-overhead ORAM result. We demonstrate the somewhat incompleteness of this prior result, due to the subtle incompleteness of a core building block, namely, Goodrich and Mitzenmacher's oblivious Cuckoo hashing scheme. Even though we do show how to patch the prior result such that we can fully realize Goodrich and Mitzenmacher's elegant blueprint for oblivious Cuckoo hashing, it is clear that the extreme complexity of oblivious Cuckoo hashing has made understanding, implementation, and proofs difficult. We show that there is a conceptually simple $O(\log^2 N/\log \log N)$-overhead ORAM that dispenses with oblivious Cuckoo hashing entirely. We show that such a conceptually simple scheme lends to further extensions. Specifically, we obtain the first $O(\log^2 N/\log \log N)$ Oblivious Parallel RAM (OPRAM) scheme, thus not only matching the performance of the best known sequential ORAM, but also achieving super-logarithmic improvements in comparison with known OPRAM schemes.

Note: minor edits in numbers and references

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in ASIACRYPT 2017
Keywords
Oblivious RAMOblivious PRAM
Contact author(s)
wklin @ cs cornell edu
History
2020-08-18: last of 7 revisions
2017-09-24: received
See all versions
Short URL
https://ia.cr/2017/924
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/924,
      author = {T-H.  Hubert Chan and Yue Guo and Wei-Kai Lin and Elaine Shi},
      title = {Oblivious Hashing Revisited, and Applications to Asymptotically Efficient ORAM and OPRAM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/924},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/924}},
      url = {https://eprint.iacr.org/2017/924}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.