TU Darmstadt / ULB / TUprints

Towards Deployable MPC: Flexible and Efficient Tools for Real-World Applications

Tkachenko, Oleksandr (2022)
Towards Deployable MPC: Flexible and Efficient Tools for Real-World Applications.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00021253
Ph.D. Thesis, Primary publication, Publisher's Version

[img] Text
dissertation.pdf
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (4MB)
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Towards Deployable MPC: Flexible and Efficient Tools for Real-World Applications
Language: English
Referees: Schneider, Prof. Dr. Thomas ; Pinkas, Prof. Dr. Benny
Date: 2022
Place of Publication: Darmstadt
Collation: 146 Seiten in verschiedenen Seitenzählungen
Date of oral examination: 23 June 2022
DOI: 10.26083/tuprints-00021253
Abstract:

Secure multi-party computation (MPC) allows two or more parties to compute an arbitrary function on their private inputs while revealing nothing beyond the output of the function. MPC is a generic technique that can be used to build privacy-preserving solutions for a large number of real-world, privacy-sensitive applications such as collaborative medical research or machine learning on sensitive data. This, however, poses big challenges: 1) the current tools for MPC are fine-tuned for particular tasks and are challenging to adopt or extend to other tasks which is though required in many use cases, and 2) MPC imposes a significant communication and computational overhead compared to the cleartext computation, rendering most “naïvely constructed” privacy-preserving protocols impractical for the real-world use. We address both challenges in this thesis. Firstly, we design and implement an open-source flexible and efficient framework for MPC and secure outsourcing, where MPC is outsourced to a smaller number of non-colluding parties who gain no information about the inputs nor about the intermediate or final results of the computation. Secondly, we design, implement, and evaluate the first linear-communication circuit-based private set intersection (PSI) protocol, i.e., it can can be combined with arbitrary MPC functionalities, e.g., reveal the intersection only if the intersection size is larger than some threshold. Thirdly, we design, implement, and evaluate two MPC protocols for specific tasks: 1) WiFi fingerprint based indoor localization and 2) similar sequence queries on genomic data.

Generic MPC Tools and Protocols

To run MPC protocol for real tasks, we need tools for MPC that can be used to implement arbitrary applications in a privacy-preserving way. There exist several open-source MPC frameworks but all of them are either efficient or they can be modified without a significant time investment, but not both at the same time. As a consequence, a significant amount of time is spent by researchers in an attempt to understand and modify MPC frameworks, which often crash after incautious modifications, thus slowing down the research. To address this problem, we develop MOTION, an open-source C++ framework for implementing and combining MPC protocols and primitives. In contrast to prior work, MOTION combines both efficiency and flexibility. It allows to implement and combine MPC protocols and optimizations while learning and modifying only the relevant parts of the framework, which is due to the novel asynchronous design. In MOTION, we combine three different generic MPC protocols for two or more parties. We also design and implement novel efficient conversions between some of those protocols and optimize low-level building blocks. Finally, we show that MOTION is often substantially more efficient than other MPC frameworks. While MOTION can evaluate arbitrary functionalities, we also investigate a more specific but yet generic class of functionalities. PSI is a well-known building block for privacy-preserving applications, and it has generated a long line of research. PSI allows two parties to compute set intersection on their private input sets without revealing any information beyond the intersection. The notion of PSI we improve in this part of the thesis is called circuit-based PSI (C-PSI), and it allows to perform arbitrary MPC while hiding the intersection result, e.g., the parties can compute complex statistics on the intersection result. We design the first C-PSI protocol with linear communication based on sophisticated hashing techniques and oblivious programmable pseudo-random functions. Beyond better asymptotic communication complexity, we show that an implementation of our C-PSI protocol is significantly more efficient compared to prior work in terms of both computation and communication. This part of the thesis is based on the following publications: [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. Vol. 11478. LNCS. Online: https://ia.cr/2019/241. Code: https://encrypto.de/code/OPPRF- PSI. Springer, 2019, pp. 122–153. CORE Rank A*. Appendix B.

MPC Applications & Optimizations

MPC is not yet widely adopted in real applications. The main reason is the high communication and computational overhead of MPC compared to cleartext computation. Furthermore, the design of efficient MPC protocols requires expert knowledge in computer science, cryptography, and circuit design. Tools such as HyCC (Büscher et al., CCS’19) lift this requirement for small applications but are yet not suitable for large and complex problems. In this thesis, we build MPC-based protocols for two privacy-sensitive real-world applications: 1) indoor localization and 2) similar sequence queries on genomic databases. To improve the efficiency of our protocols, we use optimized building blocks such as our currently smallest circuit for finding k-nearest neighbors. This part of the thesis is based on the following two publications: [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, pp. 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, pp. 315–327. CORE Rank A. Appendix D. This thesis contributes to making MPC more flexible but also more efficient for a generic use by optimizing low-level building blocks, and it introduces efficient privacy-preserving solutions for two concrete real-world applications.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-212537
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Cryptography and Privacy Engineering (ENCRYPTO)
Date Deposited: 21 Jul 2022 12:10
Last Modified: 10 Aug 2022 12:31
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/21253
PPN: 497916258
Export:
Actions (login required)
View Item View Item