Private Function Evaluation mit Oblivious RAM

Abstract

Diese Arbeit untersucht inwiefern Oblivious Random Access Machines zur Private Function Evaluation genutzt werden können. Dazu werden zuerst Grundlagen zur Secure Computation vorgestellt und insbesondere der Stand der Forschung im Bereich Oblivious RAM zum Einsatz als Secure-Computation-Datenzugriffsstruktur betrachtet. Danach werden aktuelle bestehende Konstruktionen zur privaten Evaluation von Funktionen vorgestellt und untersucht. Hierbei werden besonders Effizienz, Sicherheit, Ausdrucksstärke der Gatter, Speicherbedarf und Kommunikationsaufwand betrachtet. Es wird ein eigene PFE-Konstruktion vorgestellt, die auf Integer Werten rechnet und Oblivious RAM zur Adressierung der Variablen nutzt. Dies ermöglicht eine Implementation von Funktionsauswertungen als Programme basierend auf CPU-Step-Circuits, die ähnlich wie vorher betrachtete Garbeled RAM-Konstruktionen, Kontrollfluss und somit auch die Berechnung komplexerer arithmetischer Funktionen zulässt. Schlussendlich wird eine Implementation dieses PFE-Schemas vorgestellt und mit den vorherig betrachteten Protokollen verglichen. Das Schema berechnet arithmetische Funktionen in linearer Zeit respektive der Schrittgröße und polylogaritmischer Zeit respektive der Variablenanzahl. Allerdings entsteht ein hoher konstanter Aufwand pro Auswertungsschritt, der die Praktikabilität deutlich einschränkt.