Yifan Song

Communication Complexity of Information-Theoretic Multiparty Computation Degree Type: Ph.D. in Computer Science
Advisor(s): Vipul Goyal
Graduated: August 2022

Abstract:

Since the notion of Multiparty Computation (MPC) was proposed three decades ago, a lot of research and effort has been done to improve the efficiency of MPC protocols. However, the inefficiency of the current state-of-the-art is still the major barrier that prevents MPC from being used more broadly. In this thesis, we study the communication complexity of information-theoretic MPC protocols.

Part I: Information Theoretic MPC with Honest Majority.
First, we study the honest majority setting, i.e., the number of corrupted parties is t < n ⁄ 2, where n is the number of parties. We consider both the semi-honest security and malicious security (with abort).

In the setting of semi-honest security, we propose two improvements over the previously best-known result by Damgård and Nielsen (CRYPTO 2007). Our first protocol improves the communication complexity of the Damgård and Nielsen protocol from 6 field elements per party per gate to 4 elements. Our second protocol reduces the round complexity by a factor of 2 and achieves 4.5 field elements per party per gate.

As for malicious security, we show that it can be achieved with the same concrete efficiency as the semi-honest security. Previously best known results have a factor of 2 in the communication complexity when compiling a semi-honest protocol to a maliciously secure one. Our result closes the communication efficiency gap between semi-honest security and malicious security (with abort).

Part II: Information-Theoretic MPC with Dishonest Majority in the Preprocessing Model.
Then, we study the dishonest majority setting in the circuit-independent preprocessing model. We consider a sub-optimal corruption threshold where t = (1 − ε) ⋅ n for a constant ε.

In this thesis, we construct the first MPC protocols in the preprocessing model for dishonest majority which achieves sub-linear amount of preprocessing data and communication complexity per gate in the number of parties n. To achieve our results, we extend the use of packed secret sharing to the dishonest majority setting. For a constant fraction of corrupted parties (i.e. if 99 percent of the parties are corrupt), we achieve O(1) field elements in both of the amount of preprocessing data and communication complexity per gate across all parties.

Thesis Committee:
Vipul Goyal (Chair)
Bryan Parno
Elaine Shi
Yuval Ishai (Technion, Israel)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Information-Theoretic Cryptography, Multiparty Computation, Communication Complexity