The development of secure multi-party computation

1. Introduction

Secure Multi-Party Computation is one of the most popular computational methods in using data without leaking or exposing private information. Parties can get their desired computed function output without gaining any knowledge of the data’s specific inputs. In general, MPC works to ensure two properties: input privacy and robustness. To maintain input privacy, no party can interfere with the input data to affect the output function and results and to maintain robustness, dishonest parties also cannot interfere with the accuracy of results for the output result [1-3].

The process of MPC undergoes a three-step process. First, the input parties enter data into computation. Then, the computing parties undergo confidential computation. Finally, the result parties receive the output results [1-3]. The general idea of Secure MPC is shown in Figure 1 below:

With record-high accuracy and wide-ranging applications and abilities, many elements of Secure Multi-Party Computation are worth further consideration and development. This paper will explore the significance of Secure Multi-Party Computation in various modern-day applications and discuss its advantages and disadvantages and how it can be improved for the future.

As seen in the data graph above, almost 10 times the number of SMPC papers from the 1980s are being published today [2]. This shows how SMPC is constantly growing and holds an important place in society.

2. The Development of SMPC

First theoretical developments in Secure Multi-Party Computation occurred in 1982 by computational theorist and computer scientist Andrew Yao through the Millionaire Problem. In the Millionaire Problem, Yao questioned how two millionaires could determine who is the wealthiest without revealing their individual riches, and Secure Multi-Party Computation was born [5].

2.1. The Millionaire Problem

Suppose two people, Sally and Tristan want to determine who has more money among them without telling each other the specific amount they have. Sally has X dollars and Tristan has Y dollars and they want to determine if X > Y or Y > X. The goal of Secure Multi-Party Computation is to determine if X > Y or Y > X without knowing the specific values of X and Y. Let both X and Y be in the set of values {1, 15} [6].

First, Tristan sends Sally a random number n and Tristan also chooses a secret number N where |N| is a natural number. Then n + Y - 1is the encryption of N where Y is in the set {1, 15}. Sally then decrypts numbers n, n + 1, n + 2…n + 14 to get the corresponding A₁…A_15. A_Y, which is Tristan’s secret N. However, Sally does not know which one it is, so Sally reduces all the values A₁…A₁₅ mod a random prime p, resulting in Z₁…Z₁₅ where Z_Y = N mod p and all the other Z values look random. Looking at all the Z_i values, she adds 1 (mod p) to all the Z_i values where i > X creating a new set of numbers W₁…W_15. From the new set of numbers Sally sends Tristan, if W_Y = N mod p, that means that X ≥ Y. Otherwise, Y > X.

This was the beginning of Secure Multi-Party Computation. Following Yao’s initial introduction to Secure Multi-Party Computation, David Chaum introduced the Dining Cryptographers Problem.

2.2. The Dining Cryptographers Problem

Suppose three cryptographers are dining together in their favorite restaurant. They are informed that arrangements have been made for them to pay the bill anonymously or the National Security Agency (NSA) has already paid for them. The way to find out if the NSA has not paid while keeping the identity of the payer is presented below [7-8]:

Each cryptographer flips a coin (0 - tails, 1 - heads). Ally’s number is a, Bobby’s number is b, and Carl’s number is c. Let

A = a ^ c and B = b ^ a and C = c ^ b (^ stands for xor)

If NSA has paid for the meal, then if we xor all of these computed values together, we get

A ^ B ^ C = a ^ c ^ b ^ a ^ c ^ b

In this case, each pair of equivalent values cancel out, so

A ^ B ^ C = 0

If NSA has not paid for the meal, then whoever paid for the meal can flip the value of their own computed result. If Bobby paid for the meal, then

B = ¬(b ^ a) (¬ stands for not) and A ^ B ^ C = (a ^ c) ^ ¬(b ^ a) ^ (c ^ b) = (b ^ a) ^ ¬(b ^ a) = 1

2.3. The Multi-Party Case

Olded Goldreich, Silvio Micali, and Avi Wigderson applied Yao’s ideas to a multi-party case in 1987, expanding the applications of MPC in real-life [2]. Suppose we wanted to determine the average age of the 20 students in our class:

The first person would choose a random number N and whisper it to the second student. The second student would add his own age to N and whisper N + A₂ to the third student. The third student would add his own age to N + A₂ and whisper N + A₂ + A₃ to the fourth student and so on. The final twentieth student would whisper N + A₂ + A₃ + … + A₂₀ to the first person and the first person would add his age A₁ to the sum as well getting N + A₁ + A₂ + … + A₂₀. The first person would then just subtract N from the total sum and divide by 20 to get the average age without knowing any of the other students’ ages [9].

2.4. Recent Developments

More recently, in the 2008 Danish Sugar Beet auction, farmers were able to bid for contracts at the auction without revealing the exact amount they were willing to pay for. They could participate in the bid without revealing their own economic circumstances. This was the first large-scale real-life application of MPC [10].

3. Applications in Finance, Statistics and Privacy

In the past five years, the usage of MPC has increased worldwide. They have been applied to various aspects of society such as evaluating gender pay disparities, detecting tax fraud in Estonia, and preventing satellite collisions in space [10]. Apart from theoretical frameworks for its working system, Secure Multi-Party Computation also has many real-world applications, spanning 3 main areas: finance, statistics and data collection, and secure data exchange [1].

3.1. Finance

In the financial sector, some of the main problems burdening its industry are fraud and money laundering [11]. This paper will discuss three main projects to explore the use of MPC to solve this problem, including the tax fraud detection pilot project, collaborative statistics in finance, and off-exchange matching. In general, finance follows the following steps for data anonymization and analysis for business. First, they collect financial indicators, which include: total return (annual and semi-annual), number of employees (annual and semi-annual), percentage of export (annual and semi-annual), added value (annual and semi-annual), labor costs (annual), training costs (annual), and profit (annual). Second, the data set is then anonymized and sent to the Information Technology Laboratory, where the data is finally sorted and analyzed [12].

3.1.1. Tax Fraud Detection Projects. Starting off with the tax fraud detection projects, tax enforcement organizations require a database of information in order to conduct their research and investigations. They usually use mass surveillance systems to achieve this goal and engage in data collection on a grander scale. The processing of this collected data can help them discover potential suspects of tax evasion and fraud. However, this process of data processing requires Secure Multi-Party Computation.

For example, in 2016, the Estonian Tax and Customs Board wanted to process data from companies that detail their transactions with their partners. Specifically, if the transactions cost over 1000 euros, information will be used in the fight against Value Added Tax fraud. However, this lack of privacy resulted in backlash from the companies, so computer scientists invented an MPC system to solve this problem. As a result, companies entered the program as anonymous input parties, protected by cryptography. Similar to the systems mentioned in the generalization examples above, parties had access to their desired output information, but no details on the input values [13].

3.1.2. Collaborative Statistics in Finance. In collaborative statistics in finance, there exists an application system called Collaborative Statistics that allows for encrypted data to be shared between finance companies with only the results returned to the users, namely, the bank and its customers. The MPC system can aid in this process in three main ways. Firstly, they can help customers select banks and products by providing relevant information on their credit score and funds. Secondly, they can also help banks access customer information by collecting consumer performance data and records. Finally, it can also use this private input information to compare banks against their competitors and customers against other users, analyzing this data without any breach of privacy [1].

3.1.3. Off-Exchange Matching. Another application of MPC in finance is off-exchange matching. In many instances, buyers and sellers need to be matched through specialized matching services called Alternative Trading Systems. In this system, a lot of private information is held regarding how much a buyer is willing to buy and how much the seller is willing to sell. Using this private information, the system determines the compatibility between buyer and seller and makes recommendations based on these computed values. However, often, this system relies on trust to solve problems. This is where MPC comes in. With the development of MPC, people no longer need to rely on trust to undergo such processes. Instead, they can rely on their information being fully encrypted and protected in most possible scenarios [1].

3.2. Data Analysis

For large scale data collection and analysis, there are two main applications: KPI analysis for an industrial sector and social studies on tax and education records. Both require widespread authorization and collection of data through private-preserving means such as MPC.

3.2.1. KPI Analysis. Regarding KPI analysis in an industrial sector, the Estonian government wanted to collect data on the specific financial situations and performance of various industrial companies and processes to gain a better understanding of the state of the industry. They also wanted to gain more knowledge on the state of their industry against competitors. In 2011, this goal was fulfilled through a secure MPC system that allowed input parties to upload their financial metrics to respective computing parties to obtain their desired results [12].

3.2.2. Records Analysis. In Social Studies on Tax and Education Records, researchers wanted to test their question: does working during studies cause students to extend or quit their studies? In Estonia, the Tax and Customs Board and the Ministry of Education and Research both acted as input parties in this project, finding their desired product from the MPC system. The study was officially conducted in 2015. However, the researchers were unable to get their desired result and further study needs to be conducted in order to create a fool proof system [14-15].

3.3. Privacy

Finally, as hinted in the previous applications, the main purpose and application of secure MPC is quite obviously, preservation of privacy. One specific application of this aspect of MPC is privacy-preserving statistics. This was mainly developed in the Danish R&D project “Big Data by Security” [16], focusing on how MPC can aid in the use of sensitive data in statistics and large collections of private information. Similar to the above applications, data inputted into the system is encrypted, later adapted into user-specific information that still maintains privacy above all else. Users are aware of the system analysis that happens in the computation of data and agree to its terms and conditions beforehand [1]. Figure 3 shows the process of privacy preservation in Secure MPC.

4. Advantages and Disadvantages

Given the many applications of Secure MPC in the modern world, it is important to discuss its advantages and disadvantages.

4.1. Advantages

First considering its advantages, there are many reasons as to why Secure MPC is becoming increasingly popular in systematic cryptographic methods. These benefits include: commercial readiness, consistent data protection, high accuracy and precision, speed, and compliance to all privacy regulations [17].

Commercial readiness is the product's ability to handle and adapt to the existing consumer market apart from its technological maturity [18]. Compared to other forms of cryptography, MPC is one of the foremost programs for in-market use. It is easily programmable and easily used as one of the most widespread systems for this privacy preservation. This is mainly due to its flexibility. It can be altered to serve all purposes in various industries [19]. Suppose a company had an existing set of funds in Data Box A. If they want to move the set of funds into Data Box B while maintaining encryption and working through the same address and system, usually, this involves a certain risk of losing the funds or data because of the following steps. First, they create the new Data Box B. Then, they have to move all funds to a new Box. Finally, they also have to notify everyone of the change in Box.

Through Secure MPC, they can easily achieve this without risking the possibility of losing the funds. This is advantageous because funds do not need to be moved and no new Data Box must be created. Furthermore, no new address or system is created, simplifying the process for users too, making it among one of the most applicable cryptography systems to date [19].

Furthermore, Secure MPC is reliable and provides consistent data protection. In MPC, the private key, or the variable that encrypts data, is never held in one single place, lowering the risk of breaches from cybercriminals. Often, there are multiple keys to further ensure privacy. No employee can steal the digital assets as not everything is concentrated in one place [19]. The system is also fast and efficient, using minimal time to achieve its purposes.

Most importantly, Secure MPC can fulfill most requirements for privacy, offering the highest level of encryption.

4.2. Disadvantages

However, Secure MPC still has many faults and many realistic failures. There are still instances of passive and active corruption within the system. For example, competing parties may plant spy technology or viruses in each other’s MPC systems, possibly leaking company information and data [20]. The main problem with MPC is that people need to place their trust in technology. Even if technology is a much safer and reliable source to trust, there are still so many things out of one’s control.

5. Conclusion

Even with minor faults within its system, Secure Multi-Party Computation is by far the most innovative and progressive form of cryptography. Being applied to almost every single field requiring technology in the world, its impacts are constantly growing. The unique characteristic of Secure MPC is its potential. Ranging from two-party cases to million-party ones, SMPC has an unlimited range of use in a multitude of industries. In this paper, I have discussed some of the most overarching applications of SMPC in modern society, as well as its advantages and disadvantages in various computer programs. Evidently, SMPC is a highly impressive tool in data collection and privacy that needs to be developed. In the upcoming decades, it is important to further study in this area of cryptography, as it has the potential to completely change the world for the better.