(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 couldn’t already have been deduced from $ab$. After each party computes the product of its shares 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 evaluation point corresponding to the $i$th party for $i=1,2,3$ (three distinct values). For simplicity, let’s store the secret as the constant term of the polynomial (so assume $0 \ne \alpha_i$ for all $i$). So the dealer chooses two random polynomials $p, q$ such that $$ p(0) = a,\quad q(0) = b, \quad \text{deg}(p) < 2, \quad \text{deg}(q) < 2.$$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.