Information-Theoretically Secure MPC

Multi-Party Computation (MPC) allows a group of people, each holding some input, to compute a function of their inputs. An MPC protocol must be correct and secure: all honest parties must get the correct function value and no dishonest party must learn anything more about the honest parties' values than what follows from the result.

Information-theoretically secure MPC achieves these properties even against computationally unbounded adversaries. It does not rely on any computational assumptions and is "forward secure" in the sense that future advances in breaking cryptographic algorithms cannot harm an already executed protocol.

This strong security property comes at a cost: such protocols can only exist if strictly fewer than a third of parties are dishonest (or less than a half if they do not cheat in the protocol).

The basic operation in IT-MPC is Shamir's polynomial secret sharing (other options like arithmetic codices are also available). The function to be computed is modelled as a circuit over a suitably large finite field with INPUT, ADD, MUL, RAND and OUTPUT gates.

Inputs are simply secret shared and addition gates can be computed by adding shares; to obtain an output one reconstructs the share involved.

Multiplying Shamir shares gives a "sharing" that has twice the degree in the polynomial and is not uniformly distributed. What is required is a kind of "refresh" operation to get such a share back down to an ordinary one. 

(Substitute "ciphertext" for "share" everywhere and read "noise" for "degree" to see an interesting conceptual analogy to fully-homomorphic encryption.)

The refresh operation is performed with the help of everyone having shared some random values for each multiplication gate in advance. More such random values can be used to handle random gates.

Setting up these random shares is easy against passive adversaries but harder against active ones. Earlier papers used verifiable secret sharing: this works but has a known lower bound of Omega(n^2) per VSS operation making it rather inefficient.

A better way is to use player eliminiation. The idea is that everyone cross-checks their values and complains if something is amiss. In other words, we are replacing error correction with the (easier) error detection. If anyone has cheated then someone is guaranteed to notice as honest players are assumed to outnumber dishonest ones more than 2:1. If there is a complaint then everyone is forced to reveal all their inputs to this round and the complainer and at least one complainee are eliminiated. All but one of the eliminated players must have been dishonest so, in spirit of the "Mafia" party game, the honest players can use their numerical advantage to eliminiate all cheaters (or get a sharing set up if the dishonest players decide not to cheat).

The techinical tool presented to achieve player eliminiation in random sharing is a hyperinvertible matrix. This is a square matrix of which all square submatrices are invertible.

(One could also take the "PCP" approach and open a random linear combination of everyone's shares: unless everyone created a correct sharing this is only negligibly likely to verify. But we want the soundness error to be exactly zero, hence this approach is not good enough.)