Compilation for More Practical Secure Multi-Party Computation.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication
|
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: |
|
||||
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: |
View Item |