The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency [Arpita Patra, CSA]

In STOC’88, Ben-Or, Goldwasser, and Wigderson established an important milestone in the field of cryptography by showing that every function can be computed with perfect security tolerating up to 1/3rd corruptions. We show that every function can be computed securely in only four rounds of interaction, and that some functions cannot be computed in three rounds. This resolves a long line of research. We further completely settle the round complexity of secure computation when a negligible statistical error is allowed.

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.

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

Click image to view enlarged version

Scroll Up