# BGW multiplication by Gennaro et al.: Why does H(x) have exactly degree t and why is $2t + 1 \le n$ necessary?

With this question I am referring to the BGW multiplication by Gennaro et al (PDF here). The multiplication is described on the 4th page. (Another source for me was "A pragmatic Introduction to Secure Multi-Party Computation" p. 43-44)

Summary of BGW Multiplication Procedure: To do the multiplication of 2 secret values $$\alpha$$ and $$\beta$$ of every player $$P_i$$ has to have the share $$f_{\alpha}(i)$$ and $$f_{\beta}(i)$$ where $$f_{\alpha}$$ and $$f_{\beta}$$ are the random degree t polynomials from the Shamir secret sharing. Now every player $$P_i$$ computes $$f_{\alpha}(i) \cdot f_{\beta}$$ and sends shares of this value $$h_i(j)$$ created with the random degree t polynomial $$h_i$$ (so that $$h_i(0) = (f_{\alpha} \cdot f_{\beta})(i)$$) to player $$P_j$$ for $$1 \le j \le n$$.

Next the paper from above describes how the players can obtain random degree t shares of the value $$\alpha \cdot \beta$$ (so that they can then reconstruct the result of the multiplication with these shares): Every player $$P_i$$ computes the value $$H(i)$$ from the degree t polynomial $$H$$ which is defined as:

$$H(x) = \sum_{i=1}^{n} \lambda_i h_i(x)$$

($$the \lambda_i$$s are the appropiate Lagrange coefficients).

$$H$$ is a random polynomial with

$$H(0) = \sum_{i=1}^{n} \lambda_i h_i(0) = \sum_{i=1}^{n} \lambda_i (f_{\alpha} \cdot f_{\beta})(i) = (f_{\alpha} \cdot f_{\beta})(0) = \alpha \cdot \beta$$

My Question: Is H(x) really of degree t? Couldn't it also be bigger because $$n$$ points from different degree t polynomials $$h_i$$ for $$1 \le i \le n$$ are used for the interpolation? Usually it is argued that linear operations on $$(t,n)$$ shared shares result in new $$(t,n)$$ shares and because the $$h_i$$ functions are of degree $$t$$ linear combinations of values $$h_i{j}$$ for $$1 \le i \le i$$ should result in $$(t,n)$$ shares as well. Does this also hold in this scenario, since we always combine values from different degree $$t$$ polynomials at the same $$x$$ value?

Another question: It is also noted that $$t$$ hast to be such that $$2t+1 \le n$$. Is this really necessary? Wouldn't $$t+1 \le n$$ suffice because $$H(x)$$ is degree $$t$$ anyways or is the information from 2t+1 shares necessary to properly construct $$H(x)$$? (My hypothesis was that, without the $$2t+1$$ Lagrange coefficients $$\lambda_i$$, $$H(0)$$ would no be $$\alpha \cdot \beta$$)

The "Pragmatic Intro" p. 44 says that only with $$2t+1 \le n$$ the players have enough information to determine the value $$(f_{\alpha} \cdot f_{\beta})(0)$$. Why is this the case?

• Welcome to cryptoSE! I think that you mean $2t+1\le n$ rather than $2t+1<n$, but let me know if this is not the case. Oct 27 at 19:47
• Thank you for pointing that out. That was exactly what I meant. Oct 28 at 9:43

For your first question: $$H(x)$$ is of degree at most $$t$$ provided that the players generate $$h_i$$ of degree $$t$$. The $$\lambda_i$$ are constants and so it is a linear combination of polynomials of degree $$t$$ and so is of degree at most $$t$$.
For your second question: yes it is necessary. In multiplying shares the group notionally constructs a degree $$2t$$ product polynomial $$q(x)=f_\alpha(x)\cdot f_\beta(x)$$ with $$2t+1$$ coefficients. Player $$i$$ knows the value of this notional polynomial $$q(i)$$, and we know $$q(0)$$ can be written as a linear combination of $$n$$ of these by cancelling the contribution of higher degree coefficients. Specifically we solve the following system for $$\{\lambda_i:1\le i\le n\}$$ $$\left(\begin{matrix} n^{2t} & (n-1)^{2t} & (n-2)^{2t} & \ldots & 2^{2t} & 1\\ n^{2t-1} & (n-1)^{2t-1} & (n-2)^{2t-1} & \ldots & 2^{2t-1}& 1\\ n^{2t-2} & (n-1)^{2t-2} & (n-2)^{2t-2} & \ldots & 2^{2t-2}& 1\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ n & (n-1) & (n-2) & \ldots & 2 & 1\\ 1 & 1 & 1 & \ldots & 1 & 1\\ \end{matrix}\right)\left(\begin{matrix} \lambda_{n}\\\lambda_{n-1}\\\lambda_{n-2}\\\vdots\\\lambda_2\\\lambda_1\end{matrix}\right)= \left(\begin{matrix} 0\\0\\0\\\vdots\\0\\1\end{matrix}\right)$$ and deduce that for the $$\lambda_i$$ that we recover $$\sum_i\lambda_iq(i)=q(0)$$. To be soluble, this system needs to have at least as many columns as rows so that $$n\ge 2t+1$$. Note that we can specify $$n-(2t+1)$$ of the $$\lambda_i$$ to be zero and still have a solvable system. By inducing the players with $$\lambda_i\neq 0$$ to act as dealers to share out $$q(i)$$ using the degree $$t$$ polynomial $$h_i(x)$$, the group can notionally construct $$H(x)=\sum\lambda_ih_i(x)$$ which is a degree $$t$$ polynomial with $$H(0)=q(0)=f_\alpha\cdot f_\beta(0)$$.
• Thank you very much for your helpful answer. Do I understand it correctly then that the constant $\lambda_i$ term is equal to the Lagrange basis polynomial $\delta_i(0) = \prod_{j=1;j \ne i}^{n} \frac{0 - j}{i - j} = \prod_{j=1;j \ne i} \frac{-j}{i-j}$ or is it defined otherwise? Oct 28 at 10:08