Sichere Mehrparteienberechnungen (im Englischen secure multi-party computation, MPC) erlauben zwei oder mehr Parteien, eine beliebige Funktion basierend auf geheimen Eingabewerten auszuwerten, ohne etwas außer der Ausgabewerten preiszugeben. MPC ist eine generische Technik, die für die Realisierung Privatsphäre-schützender Lösungen für eine Vielzahl praktischer Anwendungen mit Bezug auf private Daten eingesetzt werden kann. Beispielsweise ist MPC für medizinische Kooperationsforschung und maschinelles Lernen auf sensiblen Daten einsetzbar. Hierbei gibt es jedoch zwei Herausforderungen: 1) die aktuellen Tools für MPC sind auf konkrete Aufgaben entworfen worden und sind nur schwer für andere Aufgaben einsetz- oder anpassbar. Dies ist allerdings in vielen Anwendungszenarien unvermeidbar. 2) Im Vergleich zur Klartextberechnung bringt MPC mit sich einen erheblichen Mehraufwand in Bezug auf die Kommunikations- und Rechnerkosten mit sich, was die “naive” Konstruktion der Privatsphäre-schützender Protokolle in der Regel ineffizient für praktische Anwendungen macht. In dieser Dissertation gehen wir beide Herausforderungen an. Erstens konstruieren und implementieren wir ein quelloffenes, flexibles und effizientes Framework für MPC und sicheres Outsourcing, wo MPC an eine kleinere Anzahl von nicht-kolludierenden Parteien ausgelagert wird. Diese Parteien erhalten keine Informationen über die Eingabe-, Zwischen- und Ausgabewerte. Zweitens konstruieren, implementieren und evaluieren wir das erste Protokoll für Schaltkreis-basierte private Schnittmengenberechnung (im Englischen private set intersection, PSI) mit linearen Kommunikationskosten. Schaltkreis-basiertes PSI ermöglicht beliebige weitere Berechnungen auf der Schnittmenge, z.B. dass die Schnittmenge preisgegeben wird, wenn eine Mindestgröße erreicht wird. Drittens konstruieren, implementieren und evaluieren wir zwei MPC-Protokolle für spezifische Aufgaben: 1) WiFi-Fingerprint-basierte Indoor-Lokalisierung und 2) Similärgensequenzanfragen.

Generische MPC-Tools und MPC-Protokolle

Um MPC-Protokolle für praktische Aufgaben zu verwenden, werden Tools für MPC benötigt, die die Privatsphähre-schützende Implementierung beliebiger Anwendunen ermöglichen. Es existieren bereits mehrere quelloffene MPC-Frameworks, die allerdings entweder effizient oder leichet anpassbar sind, aber nicht beides gleichzeitig. Als Folge müssen Forscher einen erheblichen Anteil ihrer Zeit mit Bemühungen verbringen, die existierenden MPC-Frameworks zu verstehen und zu modifizieren. Diese stürzen außerdem durch unvorsichtige Modifikationen häufig ab. Dies führt zu beträchtlicher Verlangsamung der MPC-Forschung. Um dieses Problem anzugehen, entwickeln wir MOTION, ein quelloffenes C++-Framework für die Implementierung und Kombinierung der MPC-Protokolle und Primitive. Im Gegensatz zu früheren Ansätzen verfügt MOTION über beide Eigenschaften: Effizienz und Flexibilität. Außerdem ermöglicht MOTION die Implementierung und Kombinierung der MPC-Protokolle und MPC-Optimierungen. Dabei müssen nur die relevanten Komponenten des Frameworks verstanden beziehungsweise geändern werden, was dem asynchronen Design zu verdanken ist. In MOTION sind bereits drei verschiedene generische MPC-Protokolle kombiniert, die zwei oder mehr Parteien zulassen. Darüber hinaus entwickeln und implementieren wir neue Konvertierungen zwischen einiger dieser Protokolle und optimieren die MPC-Grundbausteine. Schließlich zeigen wir, dass MOTION häufig wesentlich schneller ist als andere MPC-Frameworks. Über MOTION hinaus, das für beliebige Anwendungen verwendet werden kann, erforschen wir auch eine spezifischere aber zugleich generische Funktionalitätsklasse. PSI ist ein weitverbreiteter Baustein für Privatsphäre-schützende Anwendungen, das eine lange Reihe von Forschungsergebnissen generiert hat. PSI ermöchlicht zwei Parteien die Schnittmenge ihrer geheimen Eingabewerten zu berechnen, ohne etwas außer der Schnittmenge preiszugeben. In diesem Teil der Dissertation verbessern wir das Konzept von PSI, das auf Schaltkreisen basiert (im Englischen circuit-based PSI, C-PSI). Dieses ermöglicht weitere beliebige sichere Berechnungen auf dem Ergebnis von C-PSI, ohne die Schnittmenge preiszugeben. Beispielsweise können die Parteien komplexe Statistiken auf der Schnittmenge berechnen. Wir konstruieren das erste Protokoll für C-PSI mit linearen Kommunikationskosten. Unser Protokoll basiert auf ausgefeilten Hashing-Techniken und “oblivious” programmierbaren pseudozufälligen Funktionen. Außerdem zeigen wir, dass unser Protokoll für C-PSI nicht nur niedrigere asymptotische Kommunikationskosten im Vergleich zu früheren Arbeiten aufweist, sondern auch konkret wesentlich niedrigere Rechner- und Kommunikationskosten hat. Dieser Abschnitt der Dissertation basiert auf folgenden zwei Publikationen: [BDST22] L. BRAUN, D. DEMMLER, T. SCHNEIDER, O. TKACHENKO. “MOTION - A Framework for Mixed-Protocol Multi-Party Computation”. In: ACM Transactions on Privacy and Security (TOPS) 25 (2 2022). Accepted for publication. Online: https://ia.cr/2020/1137. Code: https://encrypto.de/code/MOTION. CORE Rank A. Appendix A. [PSTY19] B. PINKAS, T. SCHNEIDER, O. TKACHENKO, A. YANAI. “Efficient Circuit-based PSI with Linear Communication”. In: Advances in Cryptology – EUROCRYPT’19. Bd. 11478. LNCS. Online: https://ia.cr/2019/241. Code: https://encrypto.de/code/OPPRF- PSI. Springer, 2019, S. 122–153. CORE Rank A*. Appendix B.

MPC-Anwendungen & MPC-Optimierungen

MPC wird derzeit noch nicht flächendeckend in praktischen Anwendungen verwendet. Der Hauptgrund dafür sind die hohen Kommunikations- sowie Rechnerkosten von MPC im Vergleich zu Klartextberechungen. Darüber hinaus ist für die Konstruktion effizienter MPC-Protokolle Expertenwissen in den Bereichen Informatik, Kryptographie und Schaltkreis-Design notwendig. Tools wie HyCC (Büscher et al., CCS’19) heben diese Anforderung für kleine Anwendungen auf, sind aber für große und komplexe Probleme nicht einsetzbar. In dieser Dissertation konstruieren wir MPC-basierte Protokolle für zwei praktische Anwendungen mit sensiblen Daten: 1) Indoor-Lokalisierung und 2) Similärgensequenzeanfragen. Um die Performance unserer Protokolle zu verbessern, verwenden wir optimierte Bausteine wie unseren derzeit kleinsten Schaltkreis für die Suche nach den k nächsten Nachbarn eines Eingabeelements. Dieser Abschnitt der Dissertation basiert auf folgenden zwei Publikationen: [JLL+ 19] K. JÄRVINEN, H. LEPPÄKOSKI, E. S. LOHAN, P. RICHTER, T. SCHNEIDER, O. TKACHENKO, Z. YANG. “PILOT: Practical Privacy-Preserving Indoor Localization using OuTsourcing”. In: IEEE European Symposium on Security and Privacy (EuroS&P’19). IEEE, 2019, S. 448–463. Appendix C. [ST19] T. SCHNEIDER, O. TKACHENKO. “EPISODE: Efficient Privacy-PreservIng Similar Sequence Queries on Outsourced Genomic DatabasEs”. In: ACM ASIA Conference on Computer and Communications Security (ASIACCS’19). Full version: https://ia.cr/2021/029. ACM, 2019, S. 315–327. CORE Rank A. Appendix D. Diese Dissertation trägt dazu bei, die generische Nutzung von MPC flexibler sowie effizienter zu machen, was durch Optimierung von Grundbausteinen erreicht wird. Außerdem stellt diese Dissertation effiziente Privatsphäre-schützende Lösungen für zwei konkrete praktische Anwendungen vor.