Shamir's Secret Share Over the Reals

Question

What about using Shamir's secret share over the real numbers leaks information? I know there is a problem with random number generation, and someone suggested it leaks the parity of the polynomial, but I can't see very many other problems.

Answer 1

It's simply not secure. Sure, it "works", in the sense that you can generate shares and reconstruct the secret from a sufficient number of them, but the essential security property of Shamir's secret sharing — namely, that knowing less than the required threshold number of shares reveals no information about the secret — does not hold.

Since it's easier to understand why this is the case if you actually see it happen, let me give an example. To keep the example simple, let's assume that you're sharing the secret $S \in \mathbb R$ among two people, and want to require both of those two shares to reconstruct it.

So, since the reconstruction threshold is two, you need to choose one random number $a_1 \in \mathbb R$ and evaluate the polynomial $p(x) = S + r x$ at two non-zero points $x_1, x_2 \in \mathbb R \setminus \{0\}$. The shares are then $y_1 = p(x_1) = S + rx_1$ and $y_2 = p(x_2) = S + rx_2$, and the secret can be reconstructed from them by linearly interpolating between the points $(x_1,y_1)$ and $(x_2,y_2)$ and taking the constant term of the resulting interpolation polynomial.

Now, so far so good. But let's say that I know $y_1$ but not $y_2$. Then, if I guess a value for the secret $S$, I can calculate the unique random value $r = (y_1-S)/x_1$ that gives me the share $y_1$, assuming that $S$ has the value I guessed.

Now, let's say (again for simplicity) that I'm sure that either $S = S_1$ or $S = S_2$ for some specific values $S_1$ and $S_2$. Thus, I know that $r$ equals either $r_1 = (y_1-S_1)/x_1$ or $r_2 = (y_1-S_2)/x_1$.

Furthermore, let's say that, a priori, I believe that $S = S_1$ with probability $\mathrm{Pr}[S = S_1] = p_0$, and thus $S = S_2$ with probability $1-p_0$. Now, using Bayes' rule, I can calculate the conditional probability $p^*$ that $S = S_1$ given that I have the share $y_1$ as:

$$\begin{aligned} p^* &= \mathrm{Pr}[S = S_1 \mid y_1] = \frac{\mathrm{Pr}[y_1 \mid S = S_1]}{\mathrm{Pr}[y_1]} \mathrm{Pr}[S = S_1] \\ &= \frac{\mathrm{Pr}[r = r_1]}{\mathrm{Pr}[y_1]} p_0 = \frac{\pi(r_1)}{\mathrm{Pr}[y_1]} p_0\\ \end{aligned}$$

where $\pi(r)$ denotes the probability that you picked the random number $r$, and the denominator $\mathrm{Pr}[y_1] =$ $\pi(r_1)\, p_0 +$ $\pi(r_2)\, (1-p_0)$ is just a normalization constant that ensures that the conditional probabilities $\mathrm{Pr}[S = S_1 \mid y_1]$ and $\mathrm{Pr}[S = S_2 \mid y_1]$ sum to one.

Now, in general, $p^* = p_0$ if and only if the probability distribution $\pi$ is uniform, i.e. if every random number $r$ is equally likely to be picked. In this case, knowing $y_1$ gives me no additional information about $S$. When Shamir's secret sharing is implemented over a finite field, this is (or should be, if the implementation is correct) the case.

Conversely, if the probability distribution $\pi$ is not uniform (i.e. if some values of $r$ are more likely to be picked than others), then I can learn some information about $S$ just by knowing my own share $y_1$. In particular, if $\pi$ is not uniform, then there will always be some pairs of possible secrets $S_1$ and $S_2$ such that $\pi(r_1) \ne \pi(r_2)$, and so $p^* \ne p_0$.

OK, you say, so just make $\pi$ uniform, then. The problem, however, is that there is no uniform distribution over the real numbers, so any choice of random numbers necessarily leaks some information about the secret.

That issue — the need to pick uniform random numbers over the field we're working in — is the real reason why Shamir's secret sharing requires a finite field.