3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Daniel S
    Oct 27 at 19:47
  • $\begingroup$ Thank you for pointing that out. That was exactly what I meant. $\endgroup$
    – ht332932
    Oct 28 at 9:43
1
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – ht332932
    Oct 28 at 10:08
  • $\begingroup$ Yes, the two formulations are equivalent. This can be proven using vandermonde determinants. $\endgroup$
    – Daniel S
    Oct 28 at 10:54

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.