What is Secure Multiparty Computation?

In the last few decades, data privacy and security has become the primary concern to everyone. Due to the rise in technological advancements and the internet, it has been a challenging task to provide data security and data privacy of the data, when data is distributed over large distributed networks. As everyone is now concerned with their data, a lot of research is going on how to provide data security and privacy to the participants in the network. One of the techniques which provide the solution to the problems of data security and data privacy is Secure Multiparty Computation.
The secure multiparty computation may be defined as the problem of ‘n’ players to compute jointly on an agreed function securely on the inputs without revealing them.

History

Secure multiparty computation started early in the 1970s. It was known as multiparty computation at that time. It does not gain popularity at that time as it was not implemented practically. In the 1982’s it was introduced as secure two-party multiparty computation. It is used to solve a lot of problems of computation 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. The secure multiparty computation is used for the utilization of 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, cloud computing has resulted in the rebirth of secure multiparty computation.
4. Secure multiparty computation has become the hot area of research in the last decade due to the rise of blockchain technology.
5. The researchers are now more interested to implement secure multiparty computation in distributed systems.
6. Unlike in centralized systems, secure multiparty computation may have better performance 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 the 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 individual salary to others. To perform such a computation, secure multiparty computation is implemented to calculate the maximum salary. The parties in a distributed manner 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 with each other in one or the other way In such a scenario, the parties may get corrupted. The corrupted parties have behavior like semi-honest and malicious. 

1. A semi-honest opponent is one who 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 makes an attempt 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 which 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.

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-

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

There are a number of techniques developed for secure multiparty computation protocol construction having different features. Some techniques used in secure Multiparty computation are listed below:

1. Shamir Secret Sharing: Secret sharing is utilized as the basic 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 finite field Zp with p>n for arithmetic circuit and the circuit is Turing complete.
3. Input sharing: Every party shares the input using the Shamir secret sharing. The circuit is being provided the input for computation. Every party keeps his input private by adding some random number to the input and finally, after getting the output the random number is 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 output of multiplication for the ith party is calculated as c(i) = a(i) . b(i).
5. Private set intersection: The private set intersection protocol is very efficient for the two parties’ problems. Two parties who wish to find the elements of intersection with private set of inputs without revealing the input, the private set intersection is better approach for both honest and dishonest adversaries.
6. Threshold cryptography: Threshold cryptography aims to carry out the cryptographic operations for a set of parties without holding the secret by any of the single party. RSA algorithm is used for the scheme where the basic 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 secure 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. For the dishonest majority, there are protocols like GMW oblivious transfer, garbled circuit, Tiny oz and many more protocols.

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 being used for solving different problems, but there are 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 which slows down runtime.
2. High communication costs: Distributing the data to multiple parties for computation over the networks leads to higher costs of communication.