Trusting the Process, Not the Players: Secure Multiparty Computation Explained

Abstract

Secure Multi-Party Computation is a discipline within cryptography that focuses on computations performed by a group of participants, each holding some private information. The goal is to jointly compute a function of their private inputs without revealing any additional information, even in the presence of malicious participants.

In this thesis we explore a foundational result introduced by Ben-Or, Goldwasser, and Widgerson, who designed two protocols for Secure Multi-Party Computation. We first present Shamir’s secret sharing scheme, which is a key element in both protocols. Then, we discuss a t-private protocol, which ensures that no group of up to t players can learn additional information other than the output. Subsequently, we describe an extended t-private and t-resilient protocol, which additionally ensures correct working when malicious participants actively aim to disrupt it.

We prove that the first protocol is t-private for t < n/2, and that the second protocol is t-private and t-resilient for t < n/3. Furthermore, we analyze the complexity of both protocols.