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 lower bound on the amount of randomness needed for implementing an information theoretically secure oblivious RAM.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ajtai, M., Komlós, J., Szemerédi, E.: An 0(n log n) sorting network. In: STOC 1983: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 1–9. ACM, New York (1983)
Ajtai, M.: Oblivious rams without cryptographic assumptions. In: STOC 2010: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (2010) (to be published at STOC)
Batcher, K.E.: Sorting networks and their applications. In: AFIPS 1968 (Spring): Proceedings of the Spring Joint Computer Conference, April 30-May 2, pp. 307–314. ACM, New York (1968)
Beame, P., Machmouchi, W.: Making RAMs Oblivious Requires Superlogarithmic Overhead. Electronic Colloquium on Computational Complexity (ECCC) 10(104) (2010)
Goldreich, O.: Towards a theory of software protection and simulation by oblivious rams. In: STOC 1987: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 182–194. ACM, New York (1987)
Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious rams. J. ACM 43(3), 431–473 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 International Association for Cryptologic Research
About this paper
Cite this paper
Damgård, I., Meldgaard, S., Nielsen, J.B. (2011). Perfectly Secure Oblivious RAM without Random Oracles. In: Ishai, Y. (eds) Theory of Cryptography. TCC 2011. Lecture Notes in Computer Science, vol 6597. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19571-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-19571-6_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19570-9
Online ISBN: 978-3-642-19571-6
eBook Packages: Computer ScienceComputer Science (R0)