What is secure multi-party computation?

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.

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.

Evolution of Secure Multi-Party Computation

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.

Secure Multi-Party Computation Examples

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 of secure multi-party computations are described below:

• In 2017, it was used by the Boston Women’s Workforce Council [3] to compute statistics on the workers compensation in Boston. Due to privacy concerns, companies provided their data only because of the use of MPC. This application helped uncover the wage-gap between men and women in a manner that did not compromise the privacy of individual compensations.
• MPC is being used to distribute trust for the problem of key-management. Key compromise is a big enterprise problem and unbound security is using MPC to solve this problem.  
• MPC has been used by Google to accurately estimate the conversion rates from advertisements to actual purchase. Once again, Google as well as the seller of the goods (entities such as Nike, Macy’s etc.) have serious privacy concerns sharing their data with the other party but are interested in jointly computing the conversion rate (which is a function of both parties’ data).

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).
   

Devron is a next-generation federated learning and data science platform that enables decentralized analytics. Learn more about our solutions, read more of our knowledge base articles, about our federated learning platform, or schedule a demo with us today.