A Survey and Analysis of Solutions to the Oblivious Memory Access Problem
Erin Chapman · 2000
Despite the use of strong encryption schemes, one can still learn information about encrypted data using side channel attacks [2]. Watching what physical memory is being accessed can be such a side channel. One can hide this information by using oblivious simulation - hiding the true access pattern of a program. In this paper we will review the model behind oblivious simulation, attempt to formalize the problem and define a security game. We will review the major solutions pro- posed so far, the square root and hierarchical solutions, as well as propose a new variation on the square root solution. Additionally, we will show a new formalization for providing software protection by using an encryption scheme and oblivious simulation.