Perfectly Secure Oblivious Algorithms for Geometric Problems

Many programs rely on the power of classical computers to access individual cells of the memory arbitrarily. The resulting memory access patterns can depend on the input or parameters of the program, including sensitive data such as passwords or medical records. Research in the past decades, especially after the discovery of the Spectre and Meltdown vulnerabilities as well as the advent of cloud computing, has shown that this power does not come without risks: In many settings, the memory access pattern can become known to an attacker. In these cases, memory access patterns depending on sensitive information can reveal this information to the attacker. Data-oblivious algorithms and data structures provably mitigate this privacy risk by closing side channels related to the memory access pattern. This makes them an indispensable tool for secure computation. In this thesis, we consider data-oblivious algorithms for several geometric problems: We exploit the properties of the problems to obtain efficient data-oblivious algorithms, and we generalize our approaches to develop more general frameworks and techniques for data-oblivious algorithms. Along the way, we develop oblivious data structures as a tool for our algorithms; these are also of independent interest.