Perfectly Secure Oblivious RAM Without Random Oracles

Ivan Damgård; Sigurd Meldgaard; Jesper Buus Nielsen

Paper 2010/108

Perfectly Secure Oblivious RAM Without Random Oracles

Ivan Damgård, Sigurd Meldgaard, and Jesper Buus Nielsen

Abstract

We present an algorithm for implementing a secure oblivious RAM where the access pattern is perfectly hidden in the information theoretic sense, without assuming that the CPU has access to a random oracle. In addition we prove a lover bound on the amount of randomness needed for information theoretically secure oblivious RAM.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: protocols oblivious RAM
Contact author(s): ivan @ cs au dk
stm @ cs au dk
jbn @ cs au dk
History: 2010-03-02: revised; 2010-03-01: received; See all versions
Short URL: https://ia.cr/2010/108
License: CC BY

BibTeX

@misc{cryptoeprint:2010/108,
      author = {Ivan Damgård and Sigurd Meldgaard and Jesper Buus Nielsen},
      title = {Perfectly Secure Oblivious {RAM} Without Random Oracles},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/108},
      year = {2010},
      url = {https://eprint.iacr.org/2010/108}
}