Secure multi-party computation

Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao’s garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the “free XOR,” the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.