Oblivious RAM

An oblivious RAM (ORAM) simulator is a compiler that transforms algorithms in such a way that the resulting algorithms preserve the input-output behavior of the original algorithm but the distribution of memory access pattern of the transformed algorithm is independent of the memory access pattern of the original algorithm.

The definition of ORAMs is motivated by the fact that an adversary can obtain nontrivial information about the execution of a program and the nature of the data that it is dealing with, just by observing the pattern in which various locations of memory are accessed during its execution. An adversary can get this information even if the data values are all encrypted. The definition suits equally well to the settings of protected programs running on unprotected shared memory as well as a client running a program on its system by accessing previously stored data on a remote server. The concept was formulated by Oded Goldreich in 1987.[1]

References

  1. ^ Jump up to:ab c Goldreich, Oded (1987), “Towards a theory of software protection and simulation by oblivious RAMs”, in Aho, Alfred V.(ed.), Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC ’87), Association for Computing Machinery, pp. 182–194, doi:10.1145/28395.28416
  2. ^Pippenger, Nicholas; Fischer, Michael J. (1979), “Relations among complexity measures”, Journal of the ACM, 26 (2): 361–381, doi:10.1145/322123.322138, MR 0528038
  3. ^ Jump up to:ab c Chung, Kai-Min; Pass, Rafael (2013), “A simple ORAM”, IACR Cryptology ePrint Archive
  4. ^ Jump up to:ab Ostrovsky, Rafail (1990), “Efficient computation on oblivious RAMs”, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC ’90), Association for Computing Machinery, pp. 514–523, doi:10.1145/100216.100289
  5. ^ Jump up to:ab c d Goldreich, Oded; Ostrovsky, Rafail (1996), “Software protection and simulation on oblivious RAMs”, Journal of the ACM, 43 (3): 431–473, doi:10.1145/233551.233553, hdl:1721.1/103684, MR 1408562
  6. ^ Jump up to:ab Kushilevitz, Eyal; Lu, Steve; Ostrovsky, Rafail (2012), “On the (in)security of hash-based oblivious RAM and a new balancing scheme”, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 143–156, doi:10.1137/1.9781611973099.13, MR 3205204
  7. ^Ostrovsky, Rafail; Shoup, Victor (1997), “Private information storage (extended abstract)”, in Leighton, F. Thomson; Shor, Peter W. (eds.), Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC ’97), Association for Computing Machinery, pp. 294–303, doi:10.1145/258533.258606
  8. ^ Jump up to:ab Shi, Elaine; Chan, T.-H. Hubert; Stefanov, Emil; Li, Mingfei (2011), “Oblivious RAM with {\displaystyle O((\log N)^{3})} worst-case cost”, in Lee, Dong Hoon; Wang, Xiaoyun (eds.), Advances in Cryptology – ASIACRYPT 2011 – 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4–8, 2011, Proceedings, Lecture Notes in Computer Science, 7073, Springer, pp. 197–214, doi:10.1007/978-3-642-25385-0_11
  9. ^Goodrich, Michael T.; Mitzenmacher, Michael; Ohrimenko, Olga; Tamassia, Roberto (2011), “Oblivious RAM simulation with efficient worst-case access overhead”, in Cachin, Christian; Ristenpart, Thomas (eds.), Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, Chicago, IL, USA, Ofer Abarbanel – Executive Profile

    Ofer Abarbanel online library

    Ofer Abarbanel online library

    Ofer Abarbanel online library

    Ofer Abarbanel online library