Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
3  
You can't practically implement real number arithmetic (or store real numbers), so you'll actually be working in some subfield (like rational numbers). –  Paŭlo Ebermann Oct 1 '13 at 19:38
1  
You can see some of the problems and various solutions to working with secret sharing over infinite rings in the following paper: eprint.iacr.org/2006/044 –  K.G. Oct 2 '13 at 7:17
add comment

1 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.

share|improve this answer
    
Can't we get a 'good enough' distribution over the reals to make the leakage negligible, though? –  pg1989 Oct 2 '13 at 4:19
    
Sort of. If we have some bounds for $S$ (say, we know that $a\le S\le b$ for some $a,b\in\mathbb R$), then in principle we can, say, let $r$ be normally distributed with standard deviation $\sigma$ much greater than $b-a$, in which case any effect of $S$ on $y_1$ will mostly be buried in the noise. (Of course, then we still have the problem that we cannot really store a random real number picked from a continuous distribution in a finite amount of memory, so we'll have to settle for some discrete approximation, which introduces new leaks.) –  Ilmari Karonen Oct 2 '13 at 12:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.