Perfectly Secure Oblivious Algorithms for Geometric Problems

Beim wahlfreien Zugriff auf einzelne Speicherzellen hängen die Speicherzugriffsmuster von Programmen von deren Eingaben oder Parametern ab. Darunter können auch sensible Daten wie beispielsweise Passwörter oder Krankenakten fallen. Wenn ein Angreifer Kenntnis des Speicherzugriffsmusters erlangt, dann können auch diese Informationen offenbart werden. Data-Oblivious Algorithmen und Datenstrukturen vermeiden dieses Datenschutzrisiko, indem sie Seitenkanäle im Zusammenhang mit dem Speicherzugriffsmuster beweisbar schließen. In dieser Arbeit betrachten wir Data-Oblivious Algorithmen für mehrere geometrische Probleme: Wir nutzen Eigenschaften der Probleme, um effiziente Data-Oblivious Algorithmen zu entwerfen, und wir erweitern unsere Ansätze zu allgemeineren Strukturen und Techniken. Dabei entwickeln wir Oblivious Datenstrukturen als Werkzeug für unsere Algorithmen, die auch für sich allein genommen von Interesse sind.