Honest-Majority MPC with Secret Sharing

The first step in most protocols for general MPC is to represent the function being computed as a Boolean or arithmetic circuit. 

Let denote the number of participating parties and let denote a bound on the number of parties that may be corrupted. The arithmetic circuit is over a finite field with a prime .

Input sharing

• Each party shares its input with the other parties, using Shamir’s secret sharing.
• For each input wire to the circuit, the party whose input is associated with that wire plays the dealer in Shamir's secret sharing to share the value to all parties.
• The secret sharing used is -out-of- with .
• This provides security against any minority of corrupted parties, since no such minority can learn anything about the shared values.

Circuit evaluation

• the parties evaluate the circuit one gate at a time, from the input gates to the output gates.
• The evaluation maintains the invariant that for every gate for which the parties hold -out-of-n sharings of the values on the two input wires, the result of the computation is a -out-of-n secret sharing of the value on the output wire of the gate.

Computing addition gates

• According to the invariant, each party holds a secret sharing of the values on the input wires to the gate; we denote these polynomials by and and this means that the -th party holds the values and .

• is a degree- polynomial such that

• -th party locally setting its share on the output wire to be

Computing multiplication gates

• The parties generate two independent secret sharings of an unknown random value , via polynomials of degree and .

• By the -th party, for all playing the dealer and sharing a random value via a degree- polynomial and via a degree- polynomial
• Then, upon receiving such shares from each of the parties, the -th party for all defines its shares of and by computing and
• 
  

• The -th party can locally multiply its shares to define

• Compute the degree reduction step

• 
  

• the parties reconstruct by sending all of their shares to all other parties.
• The -th party for all computes its share on the output wire to be  

Output reconstruction

Once the parties have obtained shares on the output wires, they canobtain the outputs by simply sending their shares to each other and reconstructing the outputsvia interpolation.

The  above  protocol  is  secure  for semi-honest adversaries,  as  long  as  less  than  parties  are corrupted.