Skip to main content
main-content

Über dieses Buch

This book presents a holistic view on compiler assisted practical secure multi-party computation (MPC) over Boolean circuits. It discusses that two or more parties jointly evaluate a function over their inputs in such a way that each party keeps its input unknown to the other parties in MPC. MPC provides a generic way to construct Privacy-Enhancing Technologies, which protect sensitive data during processing steps in untrusted environments. A major obstacle in the past was to generate MPC applications by hand. Recently, special compilers have been developed to build all kinds of applications.

This book also explains in detail how efficient MPC applications can be created automatically from ANSI-C, thus, bridging the areas of cryptography, compilation and hardware synthesis. It also gives an insight into the requirements for creating efficient applications for MPC and is hence of interest to not only researchers in the area of MPC but also developers realizing practical applications with MPC. For a better understanding of the complete compile chain from ANSI-C to circuits, which is the ‘machine code’ of MPC, the authors first give the necessary background information on MPC protocols, Boolean logic, and logic synthesis. Then the authors describe the various compilation steps required to translate any code into an adequate circuit description. Afterwards, the authors introduce a variety of optimization techniques for two classes of MPC protocols, namely techniques that improve the runtime of applications in constant- and multi-round MPC protocols. The authors also illustrate how efficient parallelization of MPC protocols can be achieved using the assistance of compilers. It presents the effectiveness of the proposed techniques by giving a detailed evaluation on benchmarking applications. Most of the aforementioned techniques are implemented in our open source compiler that is accompanying this book and allows to study compilation for MPC in practice.Researchers who are interested in practical secure multi-party computation (MPC), and developers who are interested in realizing MPC applications in practice will find this book useful as a reference, as well as advanced-level students in computer science.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Recent years have seen an increase in applications that collect and analyze private data on potentially untrusted machines. With the predominant use of cloud services, computations that were previously performed on local computing environments tend to be outsourced to service providers. At the same time, the trend towards “big data” yields to unprecedented collections of sensitive private data. As a remedy to negative effects on privacy, Privacy-Enhancing Technologies (PETs) have emerged as prime technical protection mechanism. PETs follow the idea of “privacy by design”, demanding that privacy aspects need to be taken into account during the entire engineering process of a product or service.
Niklas Büscher, Stefan Katzenbeisser

Chapter 2. Background

Abstract
In this chapter, we give the necessary background information on secure computation and Boolean circuits to follow the ideas presented in the book. We describe Boolean circuits, two secure computation protocols, namely Yao’s garbled circuits and GMW, which are prototypic for constant-round and multi-round MPC protocols over Boolean circuits. Furthermore, we discuss multiple applications that are used for benchmarking purposes.
Niklas Büscher, Stefan Katzenbeisser

Chapter 3. Compiling ANSI-C Code into Boolean Circuits

Abstract
The practicality of Secure Multi-party Computation (MPC) is hindered by the difficulty to implement applications on top of the underlying cryptographic protocols. This is because the manual construction of efficient applications, which need to be represented as Boolean or arithmetic circuits, is a complex, error-prone, and time-consuming task. For the practical use of MPC, and thus, the development of further privacy-enhancing technologies, compilers supporting common programming languages are desirable to provide developers an accessible interface to MPC. In this chapter (This chapter is based in parts on our paper “Secure Two-party Computations from ANSI-C” (Holzer et al. ACM CCS 12: 19th Conference on Computer and Communications Security. ACM Press, New York, 2012).) we describe a general approach to translate source code into Boolean circuits for MPC. We illustrate this compilation chain alongside our compiler CBMC-GC capable of compiling ANSI C.
Niklas Büscher, Stefan Katzenbeisser

Chapter 4. Compiling Size-Optimized Circuits for Constant-Round MPC Protocols

Abstract
Even though MPC became practical in recent years, it is still multiple orders of magnitude slower than generic computation. Therefore, when designing efficient applications for MPC protocols, it is of interest to optimize these to the full extent. In this chapter, we first study the need for optimization in application development for MPC, before deriving requirements for efficient circuit design for constant-round MPC protocols. We then describe the approach applied in CBMC-GC to optimize circuits for this class of protocols. CBMC-GC uses hand-optimized building blocks as well as a fix-point optimization algorithm employing multiple techniques, such as rewrite patterns or SAT sweeping. The effectiveness of our approach is demonstrated by a practical evaluation of various benchmarking functionalities.
Niklas Büscher, Stefan Katzenbeisser

Chapter 5. Compiling Parallel Circuits

Abstract
Practical MPC has seen a lot of progress over the past decade. Yet, compared with generic computation, MPC is still multiple orders of magnitude slower. To improve the efficiency of secure computation protocol, we describe a practical and compiler assisted parallelization scheme (This chapter is based on our paper “Faster Secure Computation through Automatic Parallelization” Büscher and Katzenbeisser (24th USENIX Security Symposium, USENIX Security 15, 2015).), exemplary applied to Yao’s garbled circuits: First, we study how Yao’s garbled circuits can be parallelized effectively following a fine-grained and coarse-grained parallelization approach. Then we present a compiler extension to CBMC-GC that detects parallelism at the source code level and automatically transforms C code into parallel circuits. These circuits allow more scalable execution on parallel hardware, as we show in an evaluation of three example applications.
Niklas Büscher, Stefan Katzenbeisser

Chapter 6. Compiling Depth-Optimized Circuits for Multi-Round MPC Protocols

Abstract
Many MPC protocols, such as GMW and SPDZ, have a round complexity that is dependent on the circuit’s depth. When deploying these protocols in real world network settings, with network latencies in the range of tens or hundreds of milliseconds, the round complexity quickly becomes a significant performance bottleneck. In this chapter, we describe compiler extension to CBMC-GC (This chapter is based on our paper “Compiling Low Depth Circuits for Practical Secure Computation” (Büscher et al. ESORICS 2016: 21st European Symposium on Research in Computer Security, Part II. Springer, Heidelberg, 2016).) that optimizes circuits for a minimal depth. We first introduce novel optimized building blocks that are up to 50% shallower than previous constructions. Second, we present multiple high- and low-level depth-minimization techniques. Our implementation achieves significant depth reductions over hand-optimized circuits (for some applications up to 2.5). Moreover, evaluating exemplary functionalities in the GMW protocol, we show that depth reductions lead to significant speed-ups in real-world network setting.
Niklas Büscher, Stefan Katzenbeisser

Chapter 7. Towards Scalable and Optimizing Compilation for MPC

Abstract
The drawback of holistic optimizations on the gate level, as in CBMC-GC, are their very limited scalability. Therefore, previous efforts in compiler research for MPC focussed either on the development of scalable compilers or on the optimization of smaller circuits. In this section, we give a design of a scalable optimizing MPC compiler (This chapter is based on our paper “Scalable Secure Computation from ANSI-C” (Büscher et al. IEEE International Workshop on Information Forensics and Security, WIFS 2016, 2016).), and show as such that both goals are not mutually exclusive. We introduce a technique called source code guided optimization to guide the circuit minimization efforts more effectively. A prototype implementation and experimental evaluation illustrate the practicality of our approach.
Niklas Büscher, Stefan Katzenbeisser

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise