How to create RAW data for honest majority MPC?

In this blog we will focus on an alternative method of generation of shared multiplication triplets in honest majority MPC in the semi-honest setting with improved online/offline complexity. Let us start by recalling how multiplication triplets generated in the offline phase can be used to evaluate multiplication gates using Beaver’s technique.

Suppose a secret multiplication triplet of the form (a, b, c = a.b), where a and b are random and private, is shared between all players in the offline phase. So the i^th player will have the shares [a_i], [b_i], [c_i]. In the online phase say the parties want to compute the product (x.y), where x and y are the actual inputs; Beaver’s trick is used to express “xy” as linear combination of a.b, a, b where the combiners will be publicly known and do not leak any information about x and y :

x.y = (x – a + a) (y – b + b) = (α + a) (β + b) = ab + αb + βa + αβ.

Using the sharing of a, b, x and y, α = (x – a) and β = (y – b) can be reconstructed using the linearity of sharing. Now each party can compute c_i + αb_i + βa_i + αβ. This corresponds to the share of x.y.  

Thus the online evaluation of multiplication is reduced to just two reconstructions. Our main concern is the offline complexity. In the lecture we have seen how multiplication triples are generated by first generating sharing of random, secret value ‘a’ and ‘b’ and then using the multiplication sharing protocol. This incurred an offline complexity is O(n². C_M ), where C_M denotes the number of multiplication gates in the circuit. This was in the scenario of honest majority with n = 2t + 1.

Now let us look at an alternate method of creating shared random multiplication triples with O(n) amortized complexity. Here we consider a stronger honest majority namely, n = 3t + 1. Here the approach is more natural - each party generates sharing of a local random multiplication triplet (x_i, y_i, z_i). We have thus obtained t-sharing of (3t + 1) random multiplication triplets out of which atmost t are known to the adversary (since t parties might be corrupted). The goal is to extract sharing of random multiplication triples unknown to the adversary.

The (3t+1) t-shared independent input multiplication triples (x_i, y_i, z_i) are transformed to (3t+1) t-shared correlated multiplication triples (x_i, y_i, z_i) such that the x, y and z values lie on polynomials of degree atmost 3t/2, 3t/2 and 3t respectively. Namely there exist polynomials X( ),Y( ) and Z( ) of degree at most 3t/2 , 3t/2 and 3t respectively, where X(α_i) = x_i ,Y(α_i) = y_i and Z(α_i) = z_i for (3t+1) distinct α_i. The transformation satisfies 2 properties –

(1).the ith output triple is a multiplication triple if and only if the ith input triple is a multiplication triple.

(2). the ith output triple is known to Adversary if and only if the ith input triple is known to Adv.

The former guarantees that the relation Z(·) = X(·)Y(·) is true if and only if all the 3t + 1 input triples are multiplication triples, while the later guarantees that if Adversary knows t input triples, then it implies 3t/2 +1−t = (t/2 + 1) “degree of freedom” in the polynomials X( ),Y( ) and Z( ). Thus (t/2 + 1) sharing of random triples unknown to the adversary can be extracted from these output triples.

The idea for construction of the polynomials is as follows - X( ) and Y( ) are defined by the first two components of the 3t/2 + 1 input triples . Using these (3t/2 + 1) sharings , 3t/2 “new points” are obtained on the polynomials X() and Y(). This is feasible since they are polynomials of degree 3t/2. Then the sharing of the product of these new points is obtained by applying Beaver’s trick. The remaining (3t/2) input triples (not used so far) are used as the offline-triples in the Beaver’s technique. We have obtained (3t+1) sharing of points on the product polynomial i.e the third component of the first (3t/2 + 1) input triples and (3t/2) shared product of the new points. These are sufficient to define the polynomial Z( ). We can check that this transformation satisfies the above mentioned constraints. It is trivial for the first (3t/2 + 1) triples since the first (3t/2 + 1) output and input triples are one and the same. Regarding the remaining (3t/2) triples, the proof of the first property follows by the correctness of the Beaver’s technique. The proof of the second property follows from the fact that in beaver’s technique (x_i - x_i ) and (y_i - y_i) will be leaked and thus the output triple will be known if the input triple is known. Atmost t output triples will be known, which enables us to obtain (3t/2 + 1 – t) shared triples ( X(β_i) = x_i ,Y(β_i) = y_i and Z(β_i) = z_i ) for (3t/2 + 1) distinct β_i s. Thus we saw how to extract O(n) triples with a protocol incurring O(n²) complexity thus achieving O(n) amortized complexity.   

Lastly, we saw another kind of circuit evaluation where threshold homomorphic encryption is used. Here the invariant maintained in the circuit is that if “t” decryption shares are needed to decrypt the input, “t” decryption shares are needed to decrypt the output as well. By the homomorphic properties of encryption, it is clear addition and multiplication by constant operations will involve only local computation. The bottleneck of multiplication can be overcome using Beaver’s in the same way as we have seen. Here the raw data i.e the multiplication triple is of the form ( E_k(a), E_k(b), E_k(ab)) where a,b are secret and random. Such triples can be generated as follows- We start with a triple say ( E_k(1), E_k(1), E_k(1)). This is clearly a multiplication triple but not random. Then we send it to (t + 1) parties for “randomization”. The party does “randomization” as follows – Suppose it gets as input (A_i,B_i,C_i) , it outputs triple

(A_i+1,B_i+1,C_i+1) = (A_i + E_k (u), B_i + E_k (v) , C_i + E_k (uv) + (u . B_i) + (v. A_i))

where u and v are uniformly random plaintext chosen by party P_i 

The output will be a random multiplication triple not known to the adversary since atleast one out of the (t+1) parties is honest. The proof of correctness follows from the homomorphic properties of encryption. This is another way to generate shared random multiplication triples.

In the session we explored two alternate ways to generate multiplication triples in the offline phase which act as handy tools for circuit evaluation of multiplication gates.