How many rounds of conversation needed for Secure Computation?

The round complexity of interactive protocols is one of the most important efficiency-measures and it determines the number of consecutive interactions needed amongst the parties until completion. Both theoretically and practically, it is important to know what the limits are on rounds. My works have significant contribution in understanding the round complexity of MPC in three classic settings: (a) perfect (b) statistical (c) cryptographic from minimal assumption.

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every function can be computed with perfect (information-theoretic and error-free) security at the presence of a Byzantine (aka. active) unbounded-powerful adversary that controls up to n/3 of the parties. Our work in FOCS’20 has settled the round complexity of perfect MPC. Our main result shows that every function can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds.

In STOC 1989, Rabin and Ben-Or (RB) established yet another important milestone by showing that every functional can be computed with statistical (information-theoretic with negligible error) security in the presence of a Byzantine adversary that controls up to half of the parties. Our work in TCC’20 shows that four rounds of interaction is necessary, while a paper accepted in STOC’23 resolves the notoriously hard sufficiency part.

In STOC 1987, Goldreich, Micali and Wigderson (GMW), established a landmark result by showing that every functionality can be computed with cryptographic security at the presence of an active adversary that controls arbitrary number of the parties, and that this problem reduces to solving an elementary finite two-party function called oblivious transfer (OT). In my work published in CRYPTO’21 and CRYPTO’22, three rounds are shown to be optimal for MPC against arbitrary corruption from (black-box use of) OT.

References:

Benny Applebaum, Eliran Kachlon and Arpita Patra. The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency. 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 1277-1284, 2020. https://eprint.iacr.org/2020/581

Benny Applebaum, Eliran Kachlon and Arpita Patra. The Resiliency of MPC with Low Interaction: The Benefit of Making Errors. The 18th Theory of Cryptography Conference (TCC), LNCS 12551, pp. 562–594 2020.

Benny Applebaum, Eliran Kachlon, Arpita Patra. The Round Complexity of Statistical MPC with Optimal Resiliency. Submitted to STOC 2023.

Benny Applebaum, Yuval Ishai, Or Karni, Arpita Patra. Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications. CRYPTO 2022.

Arpita Patra and Akshayaram Srinivasan. Three-Round Secure Multiparty Computation from Black-Box Two-Round Oblivious Transfer. 41st Annual International Cryptology Conference (CRYPTO), LNCS 12826, pp. 185-213, 2021

Website: https://www.csa.iisc.ac.in/~arpita/