SECURE MULTIPARTY COMPUTATION

Introduction

Secure multi-party computation (also known as secure computation, multi-party computation/MPC, or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where the adversary is outside the system of participants (an eavesdropper on the sender and receiver), the adversary in this model controls actual participants. These types of tasks started in the late 1970s with the work on mental poker, cryptographic work that simulates game playing over distances without requiring a trusted third party.

Problem Definition  To devise methods for parties to jointly compute a function over their inputs while keeping those inputs private. The goal of MPC is to design a protocol, where, by exchanging messages only with each other.

Informally speaking, the most basic properties that a multi-party computation protocol aims to ensure are:

• ·        Input privacy: No information about the private data held by the parties can be inferred from the messages sent during the execution of the protocol. The only information that can be inferred from the private data is whatever could be inferred from seeing the output of the function alone.
• ·        Correctness: Any proper subset of adversarial colluding parties willing to share information or deviate from the instructions during the protocol execution should not be able to force honest parties to output an incorrect result. This correctness goal comes in two flavors: either the honest parties are guaranteed to compute the correct output (a “robust” protocol), or they abort if they find an error (an MPC protocol “with abort”).

 Problem Description

In an MPC, a given number of participants, p1, p2, ..., pn, each has private data, respectively d1, d2, ..., dn. Participants want to compute the value of a public function on that private data: F(d1, d2, ..., dn) while keeping their own inputs secret.

For example, suppose we have three parties Ajay, Bala, and Champak, with respective inputs x, y, and z denoting their salaries. They want to find out the average of the three salaries, without revealing to each other how much each of them makes. Mathematically, this translates to them computing:

F(x,y,z) = AVG(x,y,z)

The goal of MPC is to design a protocol, where, by exchanging messages only with each other, Ajay, Bala, and Champak can still learn F(x, y, z) without revealing who makes what.

In particular, all that the parties can learn is what they can learn from the output and their own input. So in the above example, if the output is z, then Champak learns that his z is the maximum value, whereas Ajay and Bala learn (if x, y and z are distinct), that their input is not equal to the maximum, and that the maximum held is equal to z. The basic scenario can be easily generalized to where the parties have several inputs and outputs, and the function outputs different values to different parties.

Application

There is a wide range of practical applications, varying from simple tasks such as coin tossing to more complex ones like electronic auctions (e.g. compute the market clearing price), electronic voting, or privacy-preserving data mining. A classic example is the Millionaires' Problem: two millionaires want to know who is richer, in such a way that neither of them learns the net worth of the other. A solution to this situation is essential to securely evaluate the comparison function.

Solution

The solution can be achieved for 03 Participants by using the protocol. This protocol can be used to fulfill these requirements:

1.      Ajay generates a Random Number, add that number to his salary, Encrypts value with the public key of Bala and sends it to Bala.

2.      Bala decrypts the information received from Ajay with his private key; he then adds his salary to the decrypted number (Ajay’s Salary + Random Number). He then encrypts it with the Public Key of Champak and sends it to Champak.

3.      Champak with do the same, first decrypt the information received by his private Key, he then adds his salary to the decrypted number (Bala’s Salary + Ajay’s Salary + Random Number). He then encrypts it with the public key of Ajay and sends it to Ajay.

4.      Ajay will now decrypt the value received by Champak with his Private Key. He then subtracts the original value with the original Random Number and receives the total Salary.

5.      Ajay will now divide the total Salary by no. of participants (3) to get the Average Salary without knowing the Salaries of Bala and Champak.