Oblivious RAM
Assume we can execute a program in a trusted environment (TEE), but we have only a limited amount of memory locally. We do have access to a lot of external memory, but this is not trusted.
As a first step, we can generate a private key in the TEE and use authenticating encryption to make it so only the TEE can read and write external memory (in this context referred to as RAM). Encrypting the
To make this efficient we encrypt individual pages of e.g. $4\ \mathrm{kB}$. This allows us to efficiently read and write individual pages of memory,
https://en.wikipedia.org/wiki/Oblivious_RAM
Linear scan
Simple ORAM
CP13 present a simple scheme
Ring ORAM
https://eprint.iacr.org/2014/997
Circuit ORAM
Path ORAM
https://crates.io/crates/mc-oblivious-ram
https://www.youtube.com/watch?v=jGr7Nj3KJ3c
https://github.com/odslib/EnigMap/tree/main/ods/oram