Perfectly-Secure MPC With Linear Communication Complexity

In this discussion, we will see it is possible to achieve perfect security with communication of O(n) field elements, where n is the number of players participating in MPC. We consider an active, adaptive adversary corrupting t<n/3 players participating in MPC. To achieve this they use Shamir secret sharing and hyper-invertible matrices, which we will explain later. We assume symmetric authenticated channels between the players.

The protocol has two phases – Preparation phase and Computation phase (similar to the offline-online paradigm). As the name says, in preparation phase, we will collect all the raw materials required for the computation in the next phase. First let’s look into computation phase (which is very similar to the semi-honest MPC protocols), and then find out what all we need in preparation phase.

Computation Phase:

Usually, for input gates, in semi-honest setting, each player who needs to give input to a gate, secret share the input, but in malicious setting, the corrupted player may give inconsistent shares to the players. If we have a random value r pre-shared, then, we can reconstruct it to the player and the player can broadcast (a-r), where a is the player’s input. Now every player can add (a-r) to their share for r, and thus get a sharing of a. Note that, we only need to reconstruct r to one player, and so we can use private reconstruction to achieve this.

Due to the linearity of the Shamir secret sharing scheme, linear gates can be computed locally simply by applying the linear function to the shares.

Now, if there is any random gate, we need a sharing for a random value which is independent to input, which means, we can compute the sharing of random value in preparation phase and use it directly here.

For multiplication gates, we know how to compute share of x*y, if we have sharing of x and y, with the help of multiplication triples. So if we have shares of random multiplication triples, with just two reconstructions we can get the sharings of x*y. Note that unlike the previous case, reconstruction is not private; every player should get the reconstructed value. The public reconstruction they used in this paper, efficiently reconstruct T=n-2t values at a time, and so it is efficient to evaluate T/2 multiplication gates at once. This of course requires that these multiplication gates do not depend on each other. If we don’t have these many multiplication gates in same depth, then we won’t be able to use this optimization.

All the secret sharing we said in this phase use Shamir secret sharing with degree t as usual. Before going to the preparation phase, let us see the techniques used in this protocol.

Player Elimination Framework:

          Player elimination framework is used to transform non-robust protocols into robust protocols at essentially no additional cost. To use this, the non-robust protocol should be fault detectable. A detectable protocol is a passively secure protocol that can produce incorrect output, however this will be detected by at least one honest player and this player sets his/her happy bit to unhappy.

          First divide the computation into segments (according to depth). The actual non-robust protocol is invoked to compute each segment. If fault is detected, check if there are any unhappy players. If all players are happy, the computation of the segment is successful and proceeds to the next segment. Otherwise, the segment failed, the output is discarded and a pair of players, containing at least one corrupted player is localized in the fault localization, eliminated from the actual player set and segment is repeated with the new player set. We denote the new player set as P', number of players as n' up to t' corrupted players.

          By selecting the size of a segment such as there are t segments, the overall cost of the resulting robust protocol are at most twice the costs of the non-robust protocol (since there are at most t corrupted players and so the total number of segment failures is t) plus the overhead costs for fault detection and the player elimination.

Hyper Invertible Matrix:

          Hyper-invertible matrix is a matrix of which every (non-trivial) square sub-matrix is invertible. The rows and columns considered in the sub-matrix need not be consecutive rows or columns. A hyper-invertible matrix can be constructed using Lagrange interpolation. Hyper-invertible matrix has a nice property that any subset of n input/output values can be expressed as a linear function of the remaining n input/output values.y=Mx, then, if M is a hyper-invertible matrix, y is the output and x is the input.

Private Reconstruction:

          If a shared secret of d degree is reconstructed to a player P_R, then every player sends his/her share to P_R. If there exists a degree d polynomial p such that at least d+t'+1 of the received shares lie on it, then P_R computes the secret s=p(0). Otherwise P_R gets unhappy. As we can see this protocol communicates O(nk) bits.

Public Reconstruction:

        The public reconstruction protocol takes T=n-2t correct d-sharings [s₁]_d,…,[s_T]_d and publicly output s₁,…,s_T or fails with at least one honest player unhappy. First these T shares are expanded using linear error-correcting code (similar to Reed-Solomon code) to n' sharings [u₁]_d,…,[u_n']_d, each of which is reconstructed towards one player using private reconstruction. Then every player sends his/her reconstructed value u_i to every other player, who tries to decode the received code word (u₁,…,u_n') to (s₁,…,s_T). This protocol communicates O(n²k) bits to reconstruct T sharings.

Preparation Phase:

       As we have seen before, we need sharing of independent and random multiplication triples for each multiplication gate and sharing of random values for input gates and random gates.  For simplicity we represent x, which is d-shared among the players is denoted as [x]_d and for double sharing-if x is d-shared as well as d'-shared then it is denoted as  [x]_d,d'. We use Player-Elimination framework throughout this phase to transform non-robust protocols into robust protocols at essentially no additional cost. The generation of the c_M+ c_R+ c_I triples into t segments of length = ((c_M+ c_R+ c_I)/t) where c_M, c_R, c_I are the number of multiplication gates, random gates and input gates respectively. In each segment the non-robust protocol to generate triples (explained protocol below), then the players reach agreement on whether or not all players are happy (can use byzantine agreement). If yes, they proceed to the next segment. Otherwise, a pair of players is identified in fault localization, excluded from the player set P' and the segment is repeated.

Generate triples:

        First, the players generate random a and b values, both simultaneously shared with degree t (for outputting) and degree t' (for multiplication). Additionally, the players generate random value r, simultaneously shared with degree t'and 2t' (How to generate double shared random values is explained below). Then, they locally compute the 2t'-sharing [ab]_2t' (by every player multiplying their respective shares), publicly reconstruct the difference [ab]_2t' − [r]_2t' and add it (locally) to [r]_t, resulting in [ab]_t. Finally, the players output the triple ([a]_t, [b]_t, [ab]_t).

Generate Random Double-Sharings:

          The non-robust protocol either generates T independent secret random values r₁,…,r_T, each independently (d,d')-shared among P', or fails with at least one honest player being unhappy. First every player P­_i selects and double-shares a random value s_i. Then the players compute double-sharings of the values r_i, defined as (r₁,…, r_n')=M(s₁,…,s_n'), where M is a hyper-invertible n'-by-n' matrix. 2t' of the resulting double-sharings are reconstructed, each towards a different player, who verify the correctness and gets unhappy if not correct. The remaining T double-sharings are outputted. This procedure guarantees ­–that if all honest players are happy, then at least n' double-sharings are correct (n'-t' sharings inputted by honest players and the t' verified by honest players). Due to hyper-invertibility of M, all 2n' double sharings must be correct.

Communication Complexity:

       The MPC protocol consisting of preparation phase and computation phase evaluates a circuit with communicating O((c₁n+c_Rn+c_Mn+c_On+D_Mn²)k+(c_I+n)BA(k)) bits, which amounts to O((c₁n²+c_Rn+c_Mn+c_On+D_Mn²)k +n³k) bits, where D_M denotes the multiplicative depth of the circuit.