Secure Multi-Party Computation (MPC) is a central problem in modern cryptography, that allows mutually distrusting parties to collaborate with each other on computational tasks, without compromising their private data (beyond what the output of the computation reveals). In this tutorial we shall cover some of the basic concepts behind MPC, informed by recent developments in the field. The first half of the tutorial will introduce the concept of MPC and briefly present some of the classic constructions, including Yao's Garbled Circuits, the GMW protocol and the BGW protocol. We shall then see some blackbox transformations that can be applied to simpler protocols, to achieve higher security or efficiency goals. The second half of the tutorial will deal with fundamental issues in the theory of MPC. These include definitions of security, classification of MPC tasks according to their cryptographic complexity (including characterization of tasks as possible or impossible to carry out), and questions regarding the communication complexity of MPC.
展开▼