I could not understand how multiplication is carried out in the BGW protocol for 3 parties. Reference: https://crypto.stanford.edu/pbc/notes/crypto/bgw.html

I've understood that in multiplication, we calculate r(x) = p(x)q(x) but this means that r(x) is a polynomial of degree 2t. How is this polynomial redistributed in the circuit to get an O(n^2) complexity in multiplication over BGW protocol?

Note that p(x) and q(x) are both polynomials of degree t and as I am taking the case of semi-honest adversaries, t < n/2.


We can use the notation of the source document, except I will say we are trying to compute $ab = c$ (for $a,b,c\in\mathbb{F}_p$), so I can use $x$ as a variable when discussing polynomials.

Let $a_1,\dots, a_n$ and $b_1,\dots, b_n$ be $t$-out-of-$n$ secret sharings of $a, b$. Recall this means that they're computed by taking random $t$-degree polynomials: $$A(x) = \sum_{i = 0}^t \alpha_i x^i,\quad B(x) = \sum_{i = 0}^t\beta_i x^i$$ Where $A(0) = a, B(0) = b$ (so random subject to this condition). The shares are then created by evaluating the polynomials on the points $\{1,2,\dots,n\}$. In particular: $$\forall i \in\{1,\dots,n\} : a_i = A(i),\quad b_i = B(i)$$ Now we want to compute the product. The polynomial $C(x) = A(x)B(x)$ has the right constant term (as $C(0) = A(0)B(0) = ab$), but is too high of degree (as you mention). Moreover the "shares" of $C(i)$ can be computed locally, as $C(i) = A(i)B(i) = a_ib_i$.

But $C(x)$ is degree $2t$ (as you mention). We want to find some other polynomial $\mathcal{C}(x)$ such that:

  1. $\mathcal{C}(0) = C(0) = ab$
  2. $\mathcal{C}(x)$ is degree $t$
  3. Computing $\mathcal{C}(i)$ isn't "too expensive" (in communication) if you already know $A(i)$ and $B(i)$

What will we do then? The idea is to utilize that there are two different ways of representing degree $t$ polynomials:

  1. Through their $t+1$ coefficients (this is the "obvious") way
  2. Through the evaulation of them on (at least) $t+1$ distinct points

Either of these is enough information to uniquely reconstruct the polynomial. The surprising thing is that you can convert from one to the other using a linear operation.

To see how we might establish this, recall that for an $n\times n$ matrix $D$ and vector $\vec{v} = (v_1,\dots, v_n)$, we have that: $$(D\vec{v})_i = \sum_{k = 0}^{n-1}D_{i, k} v_k $$

Note that this is similar to the expression: $$A(x) = \sum_{i = 0}^t \alpha_i x^i$$ If we fix evaluation points $\{1,\dots, n\}$, then we have in fact that: $$A(i) = \sum_{k = 0}^t \alpha_k i^k$$ This suggests setting $D_{i, k} = i^k$ and $v_k = \alpha_k$. This is precisely what we'll do, by defining the Vandermonde matrix (with respect to the aforementioned evaluation points): $$V = \begin{pmatrix} 1^0 & 1^1 & \dots & 1^{n-1}\\ 2^0 & 2^1 & \dots & 2^{n-1} \\ \vdots && \ddots & \vdots\\ n^0 & n^1 & \dots & n^{n-1} \end{pmatrix}$$ Note that: $$V\begin{pmatrix}\alpha_0\\\vdots\\\alpha_{n-1}\end{pmatrix} =\begin{pmatrix} \sum_{k = 0}^{n-1} \alpha_i 1^i\\ \sum_{k = 0}^{n-1} \alpha_i 2^i\\ \vdots\\ \sum_{k = 0}^{n-1} \alpha_i n^i\\ \end{pmatrix} = \begin{pmatrix}A(1)\\ A(2)\\ \vdots\\ A(n) \end{pmatrix} = \begin{pmatrix}a_1\\ a_2\\ \vdots\\ a_n \end{pmatrix} $$ So the Vandermonde Matrix precisely maps the "coefficient representation" of a polynomial to its "evaluation representation". This ends up being extremely closely related to the Fourier transform. The Discrete Fourier Transform can be written as a Vandermonde Matrix, and the Fast Fourier Transform can be explained that it's Vandermonde Matrix is Toeplitz (and in fact circulant), so admits especially efficient representations and matrix/vector multiplications, but this is an ahistorical aside.

So, we have an (invertible) matrix that maps an $n$-dimensional "coefficient vector" representation of a polynomial to an $n$-dimensional "evaluation vector" representation of a polynomial. For the moment, don't worry about how all of the people move around all the shares --- just make sure you understand how to do the computation.

We start with the "evaluation vector" representation $C(i) = A(i)B(i)$ for $i\in\{1,\dots,n\}$, which we can write as $\vec c = (c_1,\dots, c_n)$. We convert this to the "coefficient vector" representation via $V^{-1}\vec{c}$. This gives the coefficients of the polynomial $C(x) = A(x)B(x)$ as a vector. While there are $n$ coefficients, as discussed before this polynomial (uniquely determined from $\vec{c}$) is of degree $2t$, so the higher-order coefficients are 0.

We can convert this to a degree $t$ polynomial via truncation. Let: $$P = \begin{pmatrix} I_{t+1} & 0\\ 0 & 0\end{pmatrix}$$ Be an $n\times n$ block matrix, where $I_{t+1}$ is the $(t+1)\times (t+1)$ identity matrix. Then $PV^{-1}\vec{c}$ will "drop" higher order coefficients, leaving a degree $t$ polynomial. Importantly, it doesn't touch the constant term (so $\mathcal{C}(0) = C(0) = ab$ is preserved).

All that's left is to convert back to shares, so to convert from the "coefficient representation" to the "evaluation representation", again by using $V$. Thus $VPV^{-1}\vec{c}$ will output the shares (of a degree $t$ polynomial) that you want. Moreover, $VPV^{-1}$ can be precomputed by all participants in the protocol (it's just some $n\times n$ matrix. I could probably even write it out here, but won't).

This reduces the problem of multiplying shares to the problem of "computing a linear equation" of shares, which your source also discusses (at this link). As this is getting long I'll leave the answer here, but if you don't understand the linear case I encourage you to ask a new question about it.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.