Software Protection and Simulation on Oblivious RAMs: Every Oblivious Simulation of t Steps Makes max{|y|, Ω(t log t)} AccessesResearch Paper
Programs often reveal information through the memory locations they touch, even when the contents of those locations are hidden. An oblivious RAM simulation aims to conceal this access pattern. Goldreich and Ostrovsky studied the cost of doing so for arbitrary RAM programs and showed that the access sequence itself imposes a lower bound on simulation…