A Simple Recursive Tree Oblivious RAM

Benny Pinkas and Tzachy Reinman

Abstract

Oblivious RAM (ORAM) has received increasing attention in the past few years. The goal of oblivious RAM is to enable a client, that can locally store only a small (preferably constant) amount of data, to store remotely N data items, and access them while hiding the identities of the items that are being accessed. Most of the earlier ORAM constructions were based on the hierarchical data structure of Goldreich and Ostrovsky. Shi et al. introduced a binary tree ORAM, which is simpler and more efficient than the classical hierarchical ORAM. Gentry et al. have improved the scheme. In this work, we improve these two constructions. Our scheme asymptotically outperforms all previous tree based ORAM schemes that have constant client memory, with an overhead of O(log^{2+eps}(N) * log^2(log(N))) per operation for a O(N) storage server. Although the best known asymptotic result for ORAM is due to the hierarchical structure of Kushilevitz et al. (O(log^2(N)/log(log(N)))), tree based ORAM constructions are much simpler

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAM
Contact author(s)
benny @ pinkas net
History
Short URL
https://ia.cr/2014/418

CC BY

BibTeX

@misc{cryptoeprint:2014/418,
author = {Benny Pinkas and Tzachy Reinman},
title = {A Simple Recursive Tree Oblivious RAM},
howpublished = {Cryptology ePrint Archive, Paper 2014/418},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/418}},
url = {https://eprint.iacr.org/2014/418}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.