Thore Thießen, MSc

Einsteinstr. 62, room 702a
48149 Münster

T: +49 251 83-38412

Academic Profile
Doctoral AbstractThesis

Perfectly Secure Oblivious Algorithms for Geometric Problems

Supervisor
Prof. Dr. Jan Vahrenhold
Doctoral Subject
Informatik
Targeted Doctoral Degree
Dr. rer. nat.
Awarded by
Department 10 – Mathematics and Computer Science

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.

Teaching

Research Articles in Edited Proceedings (Conferences)

  • , . Klee’s Measure Problem Made Oblivious in: Castañeda A, Rodríguez-Henríquez F, eds. LATIN 2022: Theoretical Informatics, 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings proceedings of the Latin American Symposium on Theoretical Informatics, Guanajuato. Cham: Springer pp. 121–138. (Lecture Notes in Computer Science; Vol. 13568). doi: 10.1007/978-3-031-20624-5_8.

  • , . Oblivious Median Slope Selection in: He M, Sheehy D, eds. Proceedings of the 33rd Canadian Conference on Computational Geometry proceedings of the 33rd Canadian Conference on Computational Geometry, Virtual (orginally Halifax, Nova Scotia, Canada). pp. 320–331.