Re-randomization and information leakage in MPC multiplication using Shamir secret sharing

(inspired by discussions with my colleagues Giorgos Zirdelis & Vishruti Ganesh; any mistakes are my own).

Consider the case of multiplication in 2-of-3 Shamir secret sharing. The goal is to compute the product of two secrets $a,b$; the parties should learn the product $ab$, but learn nothing else about $a$ and $b$ than could already be deduced from $ab$. After each party computes the product locally, they possess (in a sense) 3-of-3 Shamir shares of the product $ab$. As we’ll see below, however, if the parties reveal their shares without first re-randomizing, then information about the original secrets is leaked. Indeed, one of the parties is guaranteed to be within one bit of full knowledge of $a$ and $b$.

We wish to compute the product of two secrets $a,b$ in 2-of-3 Shamir. Write ${\alpha }_i$ for the evaluation point corresponding to the $i$th party for $i=1,2,3$. For simplicity, let’s store the secret as the constant term of the polynomial (so assume $0\ne {\alpha }_i$ for all $i$). So two random polynomials $p,q$ such that $$p(0)=a,q(0)=b,\text{deg}(p)<2,\text{deg}(q)<2$$ are chosen by the dealer. Note that, because of the degree bound, these polynomials have only one root each! For all $i$, the $i$th party takes its share $p({\alpha }_i)$ of $p$ and $q({\alpha }_i)$ of $q$ and multiplies them locally, obtaining $(pq)({\alpha }_i)$. Assume that the parties now reveal their shares $(pq)({\alpha }_i)$. Then the product polynomial $pq$ can be interpolated (since it is quadratic, and there are 3 parties, so 3 evaluations). So each of the parties now know $pq$. Since $pq$ is a product of two linear polynomials, it has two roots, say $\beta$ and $\gamma$ (not necessarily distinct). Each party can compute these roots from $pq$. By uniqueness of factorization, either $\beta$ is a root of $p$ and $\gamma$ a root of $q$, or vice versa. Since there are 3 evaluation points and only two roots, we can choose $i$ such that ${\alpha }_i\ne \beta ,\gamma$. Then party $i$ is only 1 bit of information away from full knowledge of the values of the secrets $a,b$:

• if $\beta$ is a root of $p$, then party $i$ knows two distinct points $(\beta ,0)$, $({\alpha }_i,p({\alpha }_i))$ on the graph of $p$, and this fully determines $a$; $\gamma$ is then a root of $q$, and in a similar fashion $b$ is also determined.
• if instead $\gamma$ is a root of $p$ (and so $beta$ is a root of q) then the values of $a$ and $b$ are similarly fully determined.

It’s either one, or the other! That’s why party $i$ is “1-bit short” of full knowledge.

(Note that this can not be saved by the parties multiplying with the evaluation of their Lagrange polynomial before sharing, since these are public constants (and hence these multiplications can be undone)).