Cryptology ePrint Archive: Report 2017/924

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

T-H. Hubert Chan and Yue Guo and 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.

Category / Keywords: cryptographic protocols / Oblivious RAM, Oblivious PRAM

Original Publication (in the same form): IACR-ASIACRYPT-2017

Date: received 21 Sep 2017, last revised 31 Jan 2018

Contact author: wklin at cs cornell edu

Available format(s): PDF | BibTeX Citation

Note: minor edits in numbers and references

Short URL: ia.cr/2017/924

[ Cryptology ePrint archive ]