Oblivious RAM

In this crypto bite, we'll have a look at Oblivious RAM, a protocol which cryptographically hides the access pattern to untrusted memory.

What is Oblivious RAM?

How to implement ORAM

Hierarchical ORAM

Square Root ORAM

Binary Tree ORAM

Path ORAM

Parallel ORAM (OPRAM)

Server-assisted ORAM

Ring ORAM

Covered in [Fletcher16]

Onion ORAM

Covered in [Fletcher16]

Tiny ORAM

Covered in [Fletcher16]

A Case Study: ObliviSync

Covered in [ACRM16]

Testing ORAM Implementations

If you'd like to experiment with ORAM, you can either implement the ORAM schemes yourself (in any language that supports overloading getters and setters to an array-like structure), or you may als well try SEAL-ORAM, a C++ framework[SealORAM].

Another interesting project is the implementation of ORAM on an FPGA-Board as explained in [FRKDSSD14] and implemented in [OramFPGA]. Hardware ORAM can be embedded in a more general setup of Hardware Obfuscation (HOP) [NFRCLSG17].

Sources

Elaine Shi gave a nice introduction to Oblivious RAM in her talk "Oblivious RAM I" (no slides) at UC Berkeley's Simons Institute Cryptography Boot Camp 2015:

Benny Pinkas ORAM talk (slides) at the 5th BIU Winter School on Cryptography:

Mariana Raykova's talk "Secure Computation with RAMs" (no slides) is a good introduction to and overview of Oblivious RAM:

Daniel Wichs talk "Oblivious RAM II" (no slides) at the Cryptography Boot Camp 2015 is about offloading ORAM computations to the server:

Literature

  • [Goldreich87] Oded Goldreich: Towards a Theory of Software Protection. In: STOC '87 Proceedings of the nineteenth annual ACM symposium on Theory of computing. Pages 182-194. (acm.org paywalled). Extended Abstract in: Advances in Cryptography, CRYPTO '86. LNCS 263, pp 426-439, 1987 (full pdf)
  • [GO93] Oded Goldreich, Rafail Ostrovsky: Software Protection and Simulation on Oblivious RAMs. TR-93-072, November 1993. (full pdf, 1996 version in JACM paywalled)
  • [WST12] Peter Williams, Radu Sion, Alin Tomescu: PrivateFS, A Parallel Oblivious File System. In: CCS'12 Proceedings of the 2012 ACM conference on Computer and communications security, pp 977-988. (acm.org paywalled, full pdf, another source)
  • [BCP15] Elette Boyle, Kai-Min Chung, Rafael Pass: Oblivious Parallel RAM and Applications. August 31, 2015. In: Kushilevitz E., Malkin T. (eds) Theory of Cryptography. TCC 2016. Lecture Notes in Computer Science, vol 9563, Springer, Berlin, Heidelberg (link.springer.com paywalled, iacr.org 2014/594, full pdf)
  • [CLT15] Binyi Chen, Huijia Lin, Stefano Tessaro: Oblivious Parallel RAM, Improved Efficiency and Generic Constructions. (iacr.org 2015/1053, full pdf)
  • [Fletcher16] Christopher W. Fletcher: Oblivious RAM, From Theory to Practice. PhD-Thesis at MIT, June 2016. (full pdf)
  • [CGLS17] T-H. Hubert Chan, Yue Guo, Wei-Kai Lin, Elaine Shi: Oblivious Hashing Revisited, and Applications to Asymptotically Efficient ORAM and OPRAM. January 30, 2018. In: Takagi T., Peyrin T. (eds) Advances in Cryptology, ASIACRYPT 2017. Lecture Notes in Computer Science, vol. 10624, pp 660-690. Springer, Cnam. (link.springer.com paywalled, iacr.org 2017/924, full pdf)
  • [AKSL18] Adil Ahmad, Kyungtae Kim, Muhammad Ihsanulhaq Sarfaraz, Byoungyoung Lee: OBLIVIATE: A Data Oblivious File System for Intel SGX. In: NDSS'18 Network and Distributed Systems Security Symposium 2018, 18-21 February 2018. (full pdf, another source, yet another source, slides)
  • [FUSE] libfuse on github.com
  • [ObliVM] ObliVM: A Privacy Preserving Computation Framework. Paper.
  • [SealORAM] SEAL-ORAM: A unified testbed for evaluating Oblivious RAM
  • [FRKDSSD14] Christopher W. Fletcher, Ling Ren, Albert Kwon, Marten van Dijk, Emil Stefanov, Dimitrios Serpanos, Srinivas Devadas: A Low-Latency, Low-Area Hardware Oblivious RAM Controller. (iacr.org 2014/431, full pdf, slides)
  • [OramFPGA] Fletcher et. al.: FPGA related files for ORAM.
  • [NFRCLSG17] Kartik Nayak, Christopher W. Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal: HOP, Hardware makes Obfuscation Practical. NDSS Symposium 2017 (full pdf, slides, video)
  • [ACMR16] Adam J. Aviv, Seung Geol Choi, Travis Mayberry, Daniel S. Roche: ObliviSync, Practical Oblivious File Backup and Synchronization. (iacr.org 2016/543 full pdf, pdf alternative source, video, slides, github repo)