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
- Seminar: LearningCenter Informatik [108028]
(in cooperation with Jan Vahrenhold) - Short practical outside term-time: Softwarepraktikum [108093]
(in cooperation with Dietmar Lammers and Carina da Silva)
- V/Ü: Einführung in Java [104507]
(in cooperation with Jacqueline Strob and Jan Vahrenhold) - Practice: Übungen zur Vorlesung Informatik I [104509]
(in cooperation with Carolin Wortmann, Phil Steinhorst, Jacqueline Strob, Jan Vahrenhold and Maria Herick)
- Practice: Übungen zur Informatik II - Datenstrukturen und Algorithmen [102064]
(in cooperation with Maria Herick, Marina Evers and Karim Huesmann)
- V/Ü: Ressourceneffiziente Algorithmen [100028]
(in cooperation with Jan Vahrenhold) - Seminar: Seminar: Algorithmische Graphentheorie [100034]
(in cooperation with Jan Vahrenhold)
- Seminar: Datenstrukturen [108029]
(in cooperation with Jan Vahrenhold)
- Practice: Übungen zur Vorlesung "Algorithmische Geometrie" [106088]
(in cooperation with Jan Vahrenhold and Maria Herick)
- Practice: Übungen zur Informatik II - Datenstrukturen und Algorithmen [104088]
(in cooperation with Philipp Kather, Jan Vahrenhold and Maria Herick)
- Practice: Übungen zur Vorlesung Informatik I [102090]
(in cooperation with Phil Steinhorst, Philipp Kather and Jan Vahrenhold)
- Seminar: LearningCenter Informatik [108028]
Research Articles in Edited Proceedings (Conferences)
- Krishnamurthi S, Thießen T, Vahrenhold J. Porpoise: An LLM-Based Sandbox for Novices to Practice Writing Purpose Statements in: Henz M, Hermans F, Patterson D, eds. SPLASH-E '25: Proceedings of the 2025 ACM SIGPLAN International Symposium on SPLASH-E proceedings of the SPLASH-E 2025 - 2025 ACM SIGPLAN International Symposium on SPLASH-E (SPLASH-E 2025), Singapore. New York, NY: ACM Press pp. 75–89. doi: 10.1145/3758317.3759683.
- Thießen T, Vahrenhold J. Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues in: Mestre J, Wirth A, eds. Proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024) proceedings of the 35th International Symposium on Algorithms and Computation, Sydney. Saarbrücken/Wadern: Dagstuhl Publishing pp. 55:1–55:18. (LIPIcs - Leibniz International Proceedings in Informatics). doi: 10.4230/LIPIcs.ISAAC.2024.55.
- Thießen T, Vahrenhold J. 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.
- Thießen T, Vahrenhold J. 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.
Thore Thießen, MSc
Einsteinstr. 62, room 702a
>48149 >Münster
T: +49 251 83-38412
t.thiessen@uni-muenster.de