A Primer on Multi-party Computation (MPC)

In the world of cryptography, there’s a concept called secure multiparty computation(MPC/SMPC). It’s a way of sharing information that involves several parties but guarantees privacy and security. MPC can be used for all sorts of things, from data analysis to medical research.

It may not seem like it, but you’re probably using secure multiparty computation daily without realizing it. For example, when you use your bank’s website to make a payment, your bank is likely using secure multiparty computation to keep your account number private while still letting the other party know how much money was transferred.

So what is secure multiparty computation? How does it work? And why should you care? We’ll take a look at these questions below!

History

Secure multiparty computation started early in the 1970s. It was known as multiparty computation at that time. It did not gain popularity then as it was not implemented practically. In the 1982’s, it was introduced as secure two-party multiparty computation. It is used to solve many computation problems without revealing the inputs to other parties. Finally, it came with a name as secure multiparty computation in which the functions of different types are computed; that is the reason it is sometimes called SFE- Secure Function Evaluation.

1. Secure multiparty computation is used to utilize data without compromising privacy.
2. It is the cryptographic subfield that helps in preserving the privacy of the data.
3. Emerging technologies like blockchain, mobile computing, IoT, and cloud computing have resulted in the rebirth of secure multiparty computation.
4. Secure multiparty computation has become a hot area of research in the last decade due to the rise of blockchain technology.
5. The researchers are now more interested in implementing secure multiparty computation in distributed systems.
6. Unlike centralized systems, the secure multiparty computation may perform better in distributed systems.

Architecture

The secure multiparty computation provides a protocol where no individual can see the other parties data while distributing the data across multi parties. It enables data scientists and analysts to compute privately on the distributed data without exposing it.

Multiparty sharing data among each other with any third party using a specified protocol.

The co-workers want to compute the maximum salary without revealing their salaries to others. We want to perform such a computation; the secure multiparty computation is implemented to calculate the maximum salary. In a distributed manner, the parties jointly perform a function to calculate it without revealing the salary. Data in use is kept in encrypted form, broken up, and distributed across parties; there are no chances of quantum attacks. It is impossible to have a trusted party in the real world, as all parties communicate in one way or another. In such a scenario, the parties may get corrupted. The corrupted parties have behavior like semi-honest and malicious.

1. A semi-honest opponent follows the specified protocol but makes the parties corrupted. The protocol is run honestly, but they try to extract information from the messages exchanged between parties.
2. A malicious adversary attempts to breach security and does not follow the specified protocol. The adversary can make the changes during the execution process of the protocol. While using multiparty computation, we assume the party is honest and follows all the protocols.

Example

Suppose we want to compute the average salary among three employees without revealing the actual salary. For such problems, one can use secure multiparty computation. Let’s take an example-

Example of computing average salary of multiparty using additive sharing.

A mathematical representation of the problem can be given as:

F(A, B, C) = Average (A, B, C)

Sam, Bob, and Cassy want to calculate their average salary.

1. Say Sam’s salary is $40k. Using additive sharing, $40k is split into randomly generated three pieces $44k, $-11k, and $7k.
2. Sam keeps one of these secret pieces with herself and distributes the other two to each.
3. The same procedure is followed by all three.
4. Secret sharing keeps the data in encrypted form when in use. The procedure is given below-

SamBobCassy 44–117$40–63224$5020040$60$58$21$71

Total salary = $150
Average Salary = 150/3
               = $50

From the above data shared there is no clue about the actual salary, but the average salary is being calculated.

Techniques

Several techniques developed for secure multiparty computation protocol construction have different features. Some techniques used in secure Multiparty computation are listed below:

1. Shamir Secret Sharing: Secret sharing is utilized as the primary tool when there is an honest majority in secure multiparty computation. A secret sharing scheme is that a secret s is shared among n parties, such that t+1 or more parties come together to reconstruct the secret. The parties lesser than t cannot get any information or reconstruct the secret. The scheme which fulfills the requirements of t+1 out of n is called the threshold secret sharing scheme.
2. Honest Majority MPC: The function can either be represented by Boolean or arithmetic circuit in an honest majority. For MPC-based secret sharing having the honest majority, there is a finite field Zp with p>n for the arithmetic circuit, and the circuit is Turing complete.
3. Input sharing: Every party shares the input using the Shamir secret sharing. The circuit is provided as the input for computation. Every party keeps its input private by adding some random number to the input, and finally, after getting the output, the random number known to the party is removed, and we get the output.
4. Circuit evaluation: The circuit is evaluated by parties one gate at a time. The gates are evaluated serially from input to output. The evaluation consists of the computation of addition and multiplication gates. For inputs a(x) and b(x), the output of addition for the ith party is calculated as c(i) = a(i) + b(i). Similarly, the multiplication output for the ith party is calculated as c(i) = an (i). b(i).
5. Private set intersection: The private set intersection protocol efficiently solves the two parties’ problems. For two parties who wish to find the elements of intersection with a private set of inputs without revealing the input, the private set intersection is a better approach for both honest and dishonest adversaries.
6. Threshold cryptography: Threshold cryptography aims to carry out cryptographic operations for a set of parties without holding the secret by any single party. RSA algorithm is used for the scheme where the primary function is y=xe mod n. RSA is used for encrypting secrets or messages.
7. Dishonest majority MPC: In the secure multiparty computation, there can be both honest and dishonest parties. The Multiparty computation is secure as long as there is an honest majority. If the adversaries are corrupt more than the majority, new approaches are required for security. There are protocols like GMW oblivious transfer, garbled circuit, Tiny oz, and many more for the dishonest majority.

Benefits Of Secure Multiparty Computation

Let’s discuss some benefits of secure multiparty computation:

1. Trusted third party: In Secure Multiparty Computation, we can share data in a distributed manner with different organizations without any third party, and even the privacy of data will be preserved while sharing data.
2. Data Privacy: The private data of organizations can be shared for computation purposes. The concern of data privacy is provided by using secure multiparty computation, which keeps the data in use in encrypted form. Thus, the data is not revealed or compromised.
3. High accuracy: Secure Multiparty Computation provides highly accurate results for different computations using cryptography.
4. Quantum safe: The data shared between parties is safe against quantum attacks, as the data is broken up and encrypted when distributed among parties for computation.

Limitations Of Secure Multiparty Computation

Secure multiparty computation is used to solve different problems, but there are a few limitations. The main limitations are the computational overhead and high communication costs.

1. Computational overhead: To provide the security we need to generate the random numbers, the random number generation requires more computation overhead, slowing down runtime.
2. High communication costs: Distributing the data to multiple parties for computation over the networks leads to higher communication costs.

Original：

What is Secure Multiparty Computation? - GeeksforGeeks

MPC 101 | What is MPC (Multi-Party Computation)? | Digital Asset Security

zkPass Official Links:

Website | Twitter | Discord | Medium | Github