Cryptology ePrint Archive: Report 2010/108

Perfectly Secure Oblivious RAM Without Random Oracles

Ivan Damg\aa{}rd and 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.

Category / Keywords: protocols, oblivious RAM

Date: received 27 Feb 2010, last revised 1 Mar 2010

Contact author: ivan at cs au dk, stm@cs au dk, jbn@cs au dk

Available formats: PDF | BibTeX Citation

Version: 20100302:063920 (All versions of this report)

Discussion forum: Show discussion | Start new discussion