Secure Multi-Party Computation, also known simply as Multi-Party Computation in the literature and abbreviated as SMC or MPC, is an emerging privacy enhancing technology that allows a group of entities to jointly compute a function of their inputs while keeping those inputs private. This notion was formalized in a seminal work by Andrew Yao in the 1980s where he proposed the following problem which came to be known as Yao’s Millionaire Problem:
Two millionaires, say Alice and Bob, are interested in knowing who is richer among the two without revealing their salaries.
Stated more abstractly, this is equivalent to the problem of “securely” comparing two numbers a, b where a is held by Alice and b is held by Bob. Over the past few years, there has been significant algorithmic progress that now enables this technology to be practically studied. For instance, the first protocol[1] to implement Yao’s millionaire problem could compare two 32-bit values in about 1 second. In 2021, state-of-the-art protocols can compare two 32-bit values in about 1 microseconds[2], about 6 orders of magnitude faster.
More generally, tremendous research progress has been made over the years in secure computation of arbitrary functions (including emerging applications such as machine learning) and two of the important known theoretical results are (1) it is possible to securely compute any function with any number of parties assuming secure point-to-point communication channels and (2) it is possible to mis-trust all other participating parties and still compute a function securely.
These affirmative results have led to an interest in this technology. A number of works address challenges in bridging the gap between theoretical results and practical applications. A few of these practical applications are described below:
References:
[1] Dahlia Malkhi, Noam Nisan, Benny Pinkas, and Yaron Sella. “Fairplay – A secure two-party computation system.” In: USENIX Security Symposium (USENIX). 2004
[2] Sameer Wagh, Shruti Tople, Fabrice Benhamouda, Eyal Kushilevitz, Prateek Mittal, Tal Rabin: “Falcon: Honest-Majority Maliciously Secure Framework for Private Deep Learning.” Proceedings of Privacy Enhancing Technologies Symposium. 2021(1):
[3] Andrei Lapets, Frederick Jansen, Kinan Dak Albab, Rawane Issa, Lucy Qin, Mayank Varia, and Azer Bestavros. “Accessible Privacy-Preserving Web-Based Data Analysis for Assessing and Addressing Economic Inequalities.” Proceedings of ACM SIGCAS Conference on Computing and Sustainable Societies (COMPASS '18). 2018.
[4] Ion, Mihaela, Ben Kreuter, Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, David Shanahan, and Moti Yung. "Private intersection-sum protocol with applications to attributing aggregate ad conversions." Cryptology ePrint Archive (2017).