TU Darmstadt / ULB / TUprints

Compilation for More Practical Secure Multi-Party Computation

Büscher, Niklas (2018)
Compilation for More Practical Secure Multi-Party Computation.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
thesis_nbuescher_1.0.pdf - Published Version
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Compilation for More Practical Secure Multi-Party Computation
Language: English
Referees: Katzenbeisser, Prof. Dr. Stefan ; Kerschbaum, Prof. Dr. Florian
Date: 21 November 2018
Place of Publication: Darmstadt
Date of oral examination: 11 January 2019
Abstract:

Within the last decade, smartphone applications and online services became universal resources and an integral part of nowadays life. Unfortunately, the ongoing digitization trend is also a huge risk for the individual's privacy because users of these interconnected devices and services become more and more transparent and reveal sensitive data to an untrusted and possibly unknown service provider. Yet, since the 1980's it is known that any computation between two or more parties can be evaluated securely such that the parties do not learn more about the inputs of the other parties than they can derive from the output of the computation. For a long time considered to be a purely theoretical concept, in the last fifteen years, this technique known as Secure Multi-Party Computation (MPC), transitioned into a powerful cryptographic tool to build privacy-enhancing technology. As such MPC could prevent mass surveillance of online services while maintaining the majority of their business use cases. Furthermore, MPC could be an enabler for novel business-to-business use cases, where mutually distrusting parties corporate by sharing data without losing control over it. Albeit its potential, the practicality of MPC is hindered by the difficulty to implement applications on top of the underlying cryptographic protocols. This is because their manual construction requires expertise in cryptography and hardware design. The latter is required as functionalities in MPC are commonly expressed by Boolean and Arithmetic circuits, whose creation is a complex, error-prone, and time-consuming task.

To make MPC accessible to non-domain experts, in this thesis we design, implement, and evaluate multiple compilation techniques that translate the high-level language ANSI C into circuit representations optimized for different classes of MPC protocols. Split in two parts, we focus on Boolean circuit based protocols in the first part of this thesis. We begin with an introduction into compilation and optimization of circuits with minimal size, which is required for constant round MPC protocols over Boolean circuits, such as Yao's Garbled Circuits protocol. For this purpose, we identify and evaluate classic logic minimization techniques for their application in compilation for MPC. Then, we present compiler assisted parallelization approaches for Yao's Protocol that distribute the computational workload onto multiple processors, which can allow a faster or possibly more energy efficient protocol evaluation. By extending the protocol, we further show that parallelization leads to speed-ups even in single-core settings. As not only size minimization is of relevance for MPC, we also propose a compilation chain for the creation of depth-minimized Boolean circuits, optimized for their use in multi-round protocols, such as the GMW protocol. For this purpose, we propose and implement new hand-optimized building blocks as well as code and circuit minimization techniques. In most cases the presented compilers create applications from high-level source code that outperform previous (hand-optimized) work.

In the second part, we introduce compilers for two advanced hybrid MPC protocols. First, we study the creation of MPC applications using multiple (standalone) MPC protocols at once. By combining protocols with different paradigms, e.g., Boolean and Arithmetic circuits based protocols, faster applications can be created. For the compilation of these hybrid applications we design and present novel code decomposition and optimization techniques. Moreover, we introduce solutions to the protocol selection problem to efficiently combine multiple protocols. Thus, we are able to present the first compiler that achieves full automatization from source code to hybrid MPC. Second, we investigate compilation for the combination of Oblivious RAM with MPC, also known as RAM based secure computation (RAM-SC). RAM-SC is required in data intensive applications, where circuit based protocols show limited scalability. A multitude of ORAMs based on different design principles with different trade-offs has been proposed. We explore all these design principles and corresponding deployment costs in different scenarios, before introducing a compiler that identifies an optimal selection of ORAM schemes for a given input source code. As such, we present the first fully automatized compile chain for RAM-SC programs.

In summary, we contribute in making MPC practical by improving both, efficiency and automatized application generation.

Alternative Abstract:
Alternative AbstractLanguage

Eine der größten technischen Entwicklungen in den letzten 15 Jahren ist der Fortschritt des Smartphones, die ständige Verfügbarkeit von Informationen und Konnektivität, sowie die damit verbundene Nutzung von mächtigen Onlinediensten. Leider birgt dieser Digitalisierungstrend auch große Risiken für die Privatsphäre der Nutzer, denn diese werden immer transparenter für den teilweise unbekannten Dienstanbieter. Es ist jedoch bereits seit Mitte der 1980er-Jahre bekannt, dass jegliche Art von Berechnung oder Interaktion zwischen zwei oder mehreren Parteien auch privatsphärefreundlich durchgeführt werden kann, so dass die teilnehmenden Parteien nicht mehr über die Eingaben der anderen Parteien lernen können, als das was sie sich von der gemeinsame Ausgabe ableiten können. Lange war diese Idee der sicheren Mehrparteienberechnung (MPC) nur ein theoretisches Konzept, jedoch hat es sich in den letzten 15 Jahren in ein sehr praktisches kryptographisches Werkzeug entwickelt, um privatsphäreschützende Anwendungen zu realisieren. Als solches könnte MPC helfen die Massenüberwachung der Onlinedienste zu unterbinden, ohne deren Geschäftsmodelle komplett außer Kraft zu setzen. MPC ermöglicht auch neuartige Geschäftsmodelle, so dass beispielsweise zwei sich nicht vertrauende Unternehmen kooperieren und Daten teilen, ohne dabei die Kontrolle über diese Daten an den Geschäftspartner zu verlieren. Trotz des immensen Potentials von MPC findet es kaum Anwendung in der Praxis. Dies liegt vor allem an der Komplexität und dem Aufwand, um Anwendungen für existierende MPC Protokolle zu entwickeln. Die Erstellung dieser Anwendungen benötigt nämlich umfangreiche Kenntnisse der Kryptographie und des Logikdesigns (Schaltungsbau). Letzteres wird benötigt, da Funktionen in MPC üblicherweise in Form von logischen oder arithmetischen Schaltungen dargestellt werden, deren händische Erzeugung sehr fehleranfällig und zeitaufwendig ist.

Um MPC auch Nicht-Experten zugängliche zu machen, haben wir im Rahmen dieser Arbeit verschiedene Übersetzungstechniken (Compiler) entwickelt, implementiert und evaluiert, die es ermöglichen standard ANSI C Programmcode automatisiert in Schaltungen für verschiedene Klassen von MPC Protokollen zu übersetzen. Diese Arbeit besteht aus zwei Teilen, wobei sich der erste Teil mit der Erzeugung von logischen Schaltkreisen beschäftigt. Wir beginnen mit einer Betrachtung der Konstruktion von Schaltungen mit minimaler Größe. Diese werden üblicherweise in MPC Protokollen mit konstanter Rundenanzahl eingesetzt, wie beispielsweise Yao's Garbled Circuits Protokoll. Zu diesem Zweck analysieren und adaptieren wir klassische Logikminimierungstechniken für MPC. Anschließend zeigen wir, wie Yao's Protokoll mit Hilfe eines Compilers effektiv parallelisiert werden kann, um die Protokollausführung auf Mehrprozessorsystemen zu beschleunigen. Weiterhin präsentieren wir eine Protokollerweiterung, die selbst auf einem einzigen Rechenkern die Berechnungszeit durch Parallelisierung reduzieren kann. Neben der Minimierung der Schaltungsgröße, ist die Minimierung der Schaltungstiefe von besondere Relevanz für MPC Protokolle mit variabler Rundenanzahl, wie beispielsweise dem GMW Protokoll. Für diese Art von Protokollen präsentieren wir einen Übersetzungsansatz, bestehend aus neuen handminimierten Schaltungsbausteinen und Schaltungsminimierungstechniken. Die im Rahmen dieser Arbeit entstandenen Compiler, die die vorgestellten Techniken implementieren, erzeugen Schaltungen aus einer Hochsprache, die meist schneller evaluiert werden können als die zuvor vorgestellten und oft händisch optimierten Schaltungen.

Im zweiten Teil dieser Arbeit beschäftigen wir uns mit der Schaltungserzeugung für hybride MPC Protokolle. Hier zeigen wir zum einen die automatisierte Konstruktion von Anwendungen, die verschiedene MPC Protokolle in einer Anwendung kombinieren. Durch die Kombination von Protokollen mit verschiedenen Designprinzipien, beispielsweise logische und arithmetische Schaltungen, können Anwendungen weiter beschleunigt werden. Zur Erzeugung dieser hybriden Anwendungen präsentieren wir neue Codezerlegungs- und Optimierungstechniken. Weiterhin stellen wir Lösungen vor, welche die effizienteste Kombination von Protokollen für eine gegebene Anwendungszerlegung identifizieren kann. Mit diesem Beitrag können wir den ersten Compiler präsentieren, der eine vollständige Automatisierung von Programmcode zu hybriden Anwendungen erzielt. Als zweite hybride Protokollklasse betrachten wir die Compilierung von RAM basierten Protokollen. Diese so genannten RAM-SC Protokolle kombinieren klassische MPC Protokolle mit Oblivious RAM (ORAM) Techniken und werden für datenintensive Anwendungen benötigt. Da existierende ORAMs verschiedenste Designprinzipien verwenden, präsentieren wir eine umfangreiche ORAM Kostenanalyse mit der die Laufzeit von RAM-SC in beliebigen Einsatzszenarien abgeschätzt werden kann. Diese Abschätzung ermöglicht es uns, den ersten voll automatisierten Compiler für RAM-SC vorzustellen, der sämtliche Speicherzugriffe in einem gegebenen Programmcode erfasst und die effizientesten ORAMs ermitteln kann.

Zusammenfassend trägt diese Arbeit dazu bei, MPC praxistauglicher und zugänglicher für Nicht-Experten zu machen, indem die Entwicklungsprozesse automatisiert und die Effizienz von MPC Anwendungen gesteigert wird.

German
URN: urn:nbn:de:tuda-tuprints-84950
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Security Engineering
DFG-Graduiertenkollegs > Research Training Group 2050 Privacy and Trust for Mobile Users
Profile Areas > Cybersecurity (CYSEC)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments
Date Deposited: 22 Feb 2019 10:54
Last Modified: 09 Jul 2020 02:31
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/8495
PPN: 44555617X
Export:
Actions (login required)
View Item View Item