I'm trying to find an approach for recovering the coefficients of a polynomial (the "sum polynomial") that is the sum of a bunch of polynomials. The application is to build a secure protocol for adding up secret inputs, based on Shamir's secret sharing.
For example, if we have a bunch of $x, y$ pairs on a polynomial, like this, where $y_i$ is a specific $y$ coordinate:
$$ \begin{matrix} x & 1 & 2 & 3 & 4 & 5 \\ y & y_1 & ?? & y_3 & y_4 & y_5 \\ \end{matrix} $$
In our context, some $y$ coordinates might be missing (??). We can recover the coefficients by interpolation (even if some are missing, as long as the degree is low enough).
Now imagine extending this to many polynomials $p_i$, where we have $x,y$ pairs for each and we want to recover the coefficients of the sum of these polynomials (which we call the "sum polynomial"):
$$ \begin{matrix} x & 1 & 2 & 3 & 4 & 5 \\ p_1 & y_{1, 1} & y_{1, 2} & y_{1, 3} & ?? & y_{1, 5} \\ p_2 & ?? & y_{2, 2} & y_{2, 3} & y_{2, 4} & y_{2, 5} \\ p_3 & y_{3, 1} & y_{3, 2} & y_{3, 3} & y_{3, 4} & y_{3, 5} \\ p_4 & y_{4, 1} & y_{4, 2} & ?? & y_{4, 4} & y_{4, 5} \\ \end{matrix} $$
As above, some of the entries might be missing. There are two obvious approaches:
- Interpolate each polynomial separately (i.e. each row of the matrix) and then add the coefficients - but this is slow, as it requires many interpolations.
- Add up each column to get the $y$ coordinate of the "sum polynomial" $p_1 + p_2 + p_3 + p_4$ and then do a single interpolation to recover its coefficients - but this doesn't work if some of the entries are missing.
The question is: is there a way to recover the coefficients of the "sum polynomial" without doing many interpolations, even when some of the $y$ values are missing?