The BGW is a secure multiparty computation protocol for polynomials over a finite field.

Model

Let pp be a prime number, and let Fp\mathbb{F}_p be a finite field of order pp.

In the setting, there are nn parties, where the party ii holds data bi,0∈Fpb_{i, 0} \in \mathbb{F}_p. The objective is to compute a polynomial f(x1,…,xn)f (x_1, \ldots, x_n) over Fp\mathbb{F}_p in a privacy-preserving manner.

Privacy Guarantee. We assume all parties are curious but honest. A protocol is considered tt-private, if any set of up to tt players cannot learn more from protocol's outcome than they could jointly infer from their own private inputs and outputs.

Protocol

We need the following protocol as a primitive for sharing information between the parties.

Shamir Secret Sharing Scheme S\mathcal{S}
Party i∈[n]:i \in [n] :

  1. Sample independent random primes bi,1,…,bi,t∈Fpb_{i, 1}, \ldots, b_{i, t} \in \mathbb{F}_p.
  2. Let b⃗i≐(bi,0,bi,1,…,bi,t).\vec{b}_i \doteq (b_{i, 0}, b_{i, 1}, \ldots, b_{i, t}).
  3. Let gb⃗i(x)≐bi,0+bi,1⋅x+…+bi,t⋅xtg_{\vec{b}_i} (x) \doteq b_{i, 0} + b_{i, 1} \cdot x + \ldots + b_{i, t} \cdot x^t.
  4. For each user j∈[n]j \in [n]:
  5. \quad Send gb⃗i(j)g_{\vec{b}_i} (j) to user jj

We call gb⃗i(j)g_{\vec{b}_i} (j) a share of the secret bi,0b_{i, 0}.

Privacy Guarantee. It is easy to verify that S\mathcal{S} is tt-private.

The key result we would like to establish is that a polynomial f(x1,…,xn)f(x_1, \ldots, x_n) can also be computed in a tt-private manner.

Since a polynomial can be constructed through additions, scalar multiplication, and the multiplication of (smaller) polynomials, it is sufficient to demonstrate how these operations can be performed in a tt-private manner. We begin by discussing the addition protocol. Protocols for subtraction and scalar multiplication can be derived using similar techniques. Finally, we present the multiplication protocol.

Addition

We start with a simple protocol, which tries to add up bk,0b_{k, 0} and bℓ,0b_{\ell, 0}, for some parties k,ℓ∈[n]k, \ell \in [n].

Adding bk,0b_{k, 0} and bℓ,0b_{\ell, 0}:

Party kk:

  • Invoke S\mathcal{S} to send gb⃗k(j)g_{\vec{b}_k}(j) to each j∈[n]j \in [n].

Party ℓ\ell:

  • Invoke S\mathcal{S} to send gb⃗ℓ(j)g_{\vec{b}_\ell} (j) to each j∈[n]j \in [n].

Party i∈[n]i \in [n]:

  • On receiving gb⃗k(i)g_{\vec{b}_k}(i) and gb⃗ℓ(i)g_{\vec{b}_\ell}(i), compute gb⃗k(i)+gb⃗ℓ(i)g_{\vec{b}_k}(i) + g_{\vec{b}_\ell}(i).

The key observation is that the following relation holds for polynomials:

gb⃗k(x)+gb⃗ℓ(x)=gb⃗k+b⃗ℓ(x)=(bk,0+bℓ,0)+(bk,1+bℓ,1)⋅x+…+(bk,t+bℓ,t)⋅xt. \begin{aligned} g_{\vec{b}_k}(x) + g_{\vec{b}_\ell}(x) &= g_{\vec{b}_k + \vec{b}_\ell}(x) \\ &= (b_{k, 0} + b_{\ell, 0}) + (b_{k, 1} + b_{\ell, 1}) \cdot x + \ldots + (b_{k, t} + b_{\ell, t}) \cdot x^t. \end{aligned}

Composition in the View of a Virtual Party

Thus, the addition operation can be viewed as a virtual party vv holding data bk,0+bℓ,0b_{k, 0} + b_{\ell, 0}, which is then shared with all parties i∈[n]i \in [n] via the Shamir Secret Sharing Scheme. In this scheme, the polynomial coefficients are b⃗k+b⃗ℓ\vec{b}_k + \vec{b}_\ell. Consequently, each party ii receives a share of the secret, denoted as gb⃗k+b⃗ℓ(i)g_{\vec{b}_k + \vec{b}_\ell}(i).

Virtual Party vv:

  • Invoke S\mathcal{S} to send gb⃗k+b⃗ℓ(j)g_{\vec{b}_k + \vec{b}_\ell}(j) to each j∈[n]j \in [n].

This alternative view facilitates a clearer understanding of composition.

For example, suppose we want to compute bk,0+bℓ,0+bm,0b_{k, 0} + b_{\ell, 0} + b_{m, 0} for some parties k,ℓ,m∈[n]k, \ell, m \in [n]. First, we can apply the protocol described above to compute bk,0+bℓ,0b_{k, 0} + b_{\ell, 0}.

Then, we consider two parties: a virtual party vv holding data bk,0+bℓ,0b_{k, 0} + b_{\ell, 0}, and party mm with data bm,0b_{m, 0}. We can then invoke the addition protocol again to compute bk,0+bℓ,0+bm,0b_{k, 0} + b_{\ell, 0} + b_{m, 0}. Importantly, communication with the virtual party is not actually required, as after the first protocol invocation, each party ii already possesses the secret share gb⃗k+b⃗ℓ(j)g_{\vec{b}_k + \vec{b}_\ell}(j).

Privacy Guarantee. After the addition protocol, each party ii receives a share of the secret bk,0+bℓ,0b_{k, 0} + b_{\ell, 0}, represented by gb⃗k+b⃗ℓ(i)g_{\vec{b}_k + \vec{b}_\ell}(i). Since gb⃗k+b⃗ℓ(x)g_{\vec{b}_k + \vec{b}_\ell}(x) is a random polynomial of degree tt, the output of the addition protocol remains tt-private.

Multiplication

The multiplication is more intricate. Note that:

gb⃗k(x)⋅gb⃗ℓ(x)=gb⃗k×b⃗ℓ(x)=(bk,0⋅bℓ,0)+(∑i,j≥0, i+j=1bk,i⋅bℓ,j)⋅x+⋯+(∑i,j≥0, i+j=2tbk,i⋅bℓ,j)⋅x2t. \begin{aligned} g_{\vec{b}_k}(x) \cdot g_{\vec{b}_\ell}(x) &= g_{\vec{b}_k \times \vec{b}_\ell}(x) \\ &= \left( b_{k, 0} \cdot b_{\ell, 0} \right) + \left(\sum_{i, j \ge 0, \, i + j = 1} b_{k, i} \cdot b_{\ell, j}\right) \cdot x + \cdots + \left(\sum_{i, j \ge 0, \, i + j = 2 t} b_{k, i} \cdot b_{\ell, j}\right) \cdot x^{2 t}. \end{aligned}

There are two problems with this polynomial:

  1. The coefficients of this polynomial are not independent.
  2. The polynomial has degree 2t2t, instead of tt.

Hence the previous security analysis of the Shamir Secret Sharing Scheme does not hold.

Rerandomization

To fix the first problem, each party ii can generate a random polynomial

gi(x)=0+ci,1⋅x+ci,2⋅x2+⋯+ci,2t⋅x2t, g_i (x) = 0 + c_{i, 1} \cdot x + c_{i, 2} \cdot x^2 + \cdots + c_{i, 2t} \cdot x^{2t},

then they sends the shares gi(1),…,gi(n)g_i(1), \ldots, g_i(n) to other parties.

After sending and receiving new shares, each party ii then computes gb⃗k×b⃗ℓ(i)+∑j∈[n]gj(i)g_{\vec{b}_k \times \vec{b}_\ell}(i) + \sum_{j \in [n]} g_j(i). The polynomial of interest is given by

gb⃗k×b⃗ℓ(x)+∑i∈[n]gi(x)=(bk,0⋅bℓ,0)+(∑i,j≥0, i+j=1bk,i⋅bℓ,j+∑i∈[n]ci,1)⋅x+⋯+(∑i,j≥0, i+j=2tbk,i⋅bℓ,j+∑i∈[n]ci,2t)⋅x2t. \begin{aligned} g_{\vec{b}_k \times \vec{b}_\ell}(x) + \sum_{i \in [n]} g_i (x) &= \left( b_{k, 0} \cdot b_{\ell, 0} \right) + \left(\sum_{i, j \ge 0, \, i + j = 1} b_{k, i} \cdot b_{\ell, j} + \sum_{i \in [n]} c_{i, 1} \right) \cdot x + \cdots + \left(\sum_{i, j \ge 0, \, i + j = 2 t} b_{k, i} \cdot b_{\ell, j} + \sum_{i \in [n]} c_{i, 2t} \right) \cdot x^{2 t}. \end{aligned}

Note this is a random polynomial, in the sense that the coefficients of this polynomial are independent. Therefore, the outputs gb⃗k×b⃗ℓ(i)+∑j∈[n]gj(i),i∈[n]g_{\vec{b}_k \times \vec{b}_\ell}(i) + \sum_{j \in [n]} g_j(i), i \in [n] are 2t2t-private.

Remark. It appears sufficient for one party ii (if trusted) to generate a random polynomial gig_i and share gi(1),…,gi(n)g_i(1), \ldots, g_i(n) with other parties. Essentially, this adds a random coefficient to each coefficient of gb⃗k×b⃗ℓ(x)g_{\vec{b}_k \times \vec{b}_\ell}(x).

Truncation

To simplify notation, let

h(x)≐c0+c1⋅x+…+c2t⋅x2t h(x) \doteq c_0 + c_1 \cdot x + \ldots + c_{2t} \cdot x^{2t}

be a shorthand for the polynomial gb⃗k×b⃗ℓ(x)+∑i∈[n]gi(x)g_{\vec{b}_k \times \vec{b}_\ell}(x) + \sum_{i \in [n]} g_i (x). We have shown that c1,…,cnc_1, \ldots, c_n are random integers from Fp\mathbb{F}_p.

Our goal is to truncate its degree from 2t2t to tt:

hˉ(x)≐c0+c1⋅x+…+ct⋅xt, \bar{h}(x) \doteq c_0 + c_1 \cdot x + \ldots + c_{t} \cdot x^{t},

and for each party i∈[n]i \in [n], replaces its share h(i)h(i) by hˉ(i)\bar{h}(i).

A naive approach is to reveal the secret shares of a set of 2t2t clients, for example h(1),…,h(2t)h(1), \ldots, h(2 t), so that we can recover the entire polynomial h(x)h(x) (and therefore the secret value h(0)=c0h(0) = c_0).

Can we achieve this in a tt-private manner? The answer is "Yes"! We are going to show that, there is a matrix TT, s.t.,

hˉ1:n≐[hˉ(1)hˉ(2)⋮hˉ(n)],h1:n=[h(1)h(2)⋮h(n)],hˉ1:n=T×h1:n. \bar{h}_{1 : n} \doteq \begin{bmatrix} \bar{h}(1) \\ \bar{h}(2) \\ \vdots \\ \bar{h}(n) \end{bmatrix}, \quad h_{1 : n} = \begin{bmatrix} h(1) \\ h(2) \\ \vdots \\ h(n) \end{bmatrix}, \quad \bar{h}_{1 : n} = T \times h_{1 : n}.

Observe that, multiplying h1:nh_{1 : n} by TT only involves addition and scalar multiplications of secret shares, which we have already shown can be performed in a tt-private manner. It remain to explain what TT is.

Define

V=[1,1,⋯ ,11,2,⋯ ,2n−1⋯ 1,i,⋯ ,in−1⋯ 1,n,⋯ ,nn−1],c⃗=[c0c1⋮c2t0⋮0],cˉ=[c0c1⋮ct0⋮0]. V = \begin{bmatrix} 1, &1, &\cdots, &1 \\ 1, &2, &\cdots, &2^{n - 1} \\ &&\cdots\, \\ 1, &i, &\cdots, &i^{n - 1} \\ &&\cdots\, \\ 1, &n, &\cdots, &n^{n - 1} \end{bmatrix}, \quad \vec{c} = \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_{2t} \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \quad \bar{c} = \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_{t} \\ 0 \\ \vdots \\ 0 \end{bmatrix}.

Then h1:n=V×c⃗h_{1: n} = V \times \vec{c}, and hˉ1:n=V×cˉ\bar{h}_{1: n} = V \times \bar{c}. We also know that there exists a projection matrix PP, s.t., cˉ=Pc⃗\bar{c} = P \vec{c}. It follows that

hˉ1:n=V×cˉ=V×P×c⃗=V×P×V−1×h1:n. \bar{h}_{1 : n} = V \times \bar{c} = V \times P \times \vec{c} = V \times P \times V^{-1} \times h_{1 : n}.

Taking T=V×P×V−1T = V \times P \times V^{-1} computes the proof.

Remark. If we directly compute V−1×h1:nV^{-1} \times h_{1 : n}, we recover all coefficients of h(x)h(x). The key trick is to compute (V×P×V−1)×h1:n(V \times P \times V^{-1}) \times h_{1 : n} instead, bypassing the explicit computation of V−1×h1:nV^{-1} \times h_{1 : n}.

Reference

[1] M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, New York, NY, USA: Association for Computing Machinery, 2019, pp. 351–371. Accessed: Nov. 07, 2024. Online Available.