Shamir's secret sharing

First off, if you haven't read the paper, please do it. It's extremely short, and quite readable. You'll also need to have read Andy's article before reading further.

The secret sharing method

Essentially, the problem is this: You have a secret number, [tex dpi=72]A_0[/tex], that you want to share. You want to split it into [tex dpi=72]n[/tex] pieces such that you need at least [tex dpi=72]k[/tex] of those pieces to reconstruct [tex dpi=72]A_0[/tex]. If you only have [tex dpi=72]k-1[/tex] pieces, you can discover nothing at all about [tex dpi=72]A_0[/tex].

Shamir's method solves this problem by generating random numbers [tex dpi=72]A_1 \ldots A_{k-1}[/tex] and forming a polynomial:

The "pieces" are [tex dpi=72]n[/tex] distinct points on this curve, but not zero. Given [text dpi=72]k[/tex] points, you can reconstruct the polynomial and hence determine [tex dpi=72]A_0[/tex].

So far, so good. However, does this method guarantee that given fewer than [tex dpi=72]k[/tex] points, you can't determine anything about [tex dpi=72]A_0[/tex]?

Andy points out that using the example on the Wikipedia entry, you can find out something about it.

Andy is right. If anything, it's the Wikipedia page that's misleading.

The example

Here's the relevant part of the Wikipedia example, which has a problem in it:

Suppose that our secret is our ATM code: 1234 (S=1234) [ed: that's [tex dpi=72]A_0=1234[/tex] in our notation]. We wish to divide the secret into 6 parts (n=6), where any subset of 3 parts (k=3) is sufficient to reconstruct the secret. At random we obtain 2 numbers: 166, 94.

Did you spot the problem?

No? Here's that last sentence again:

At random we obtain 2 numbers: 166, 94.

This is an instance of the famous two envelopes problem. Essentially, the problem here is that for Shamir's system to be secure, you need to pick two positive integers completely at random. The problem is that it's not possible to pick two arbitrary positive integers in such a way that every integer is equally likely to be chosen.

The reasoning is simple: Suppose I pick x and y completely at random, and each positive integer has an equal probability of being chosen. There are a finite number of positive integers less than or equal to x, and an infinite number greater than it. So with probability 1, y is greater than x.

But by analogous reasoning, with probability 1, x is greater than y. This is a contradiction, so the assumption that it's possible to choose integers in such a manner is false.

Finite fields

The Wikipedia page misses a very important point in the paper:

To make this claim more precise, we use modular arithmetic instead of real arithmetic. The set of integers modulo a prime number p forms a field in which interpolation is possible.

In fact, this condition is overly-restrictive and, in fact, impractical. If the secret is a number between 0 and N, then we need to find a prime number bigger than N to use as our modulus. If N is large, then finding a prime is hard. (Probabilistic techniques exist for finding large things that look enough like primes for RSA to work, however, if you turn out to pick a non-prime, then you get a non-field, and interpolation doesn't work.) However, thanks to Galois, we can easily construct finite fields with at least as many elements as we need. In particular, you can always form a field with [tex dpi=72]2^b[/tex] elements for any [tex dpi=72]b[/tex]; for computer implementations, this is invariably the most convenient finite field to work in. (It's what they use in Diffie-Hellman key exchange, for example.)

So let's look at this again, this time using a smaller example.

Suppose that we're working modulo 5 (which is a prime), and the secret that we want to share is 2. We want to split this into three parts, such that you need two parts to reconstruct the secret.

We pick a random number between 0 and 4 (because we're working in a finite range, the two envelope paradox doesn't apply). Let's say it's 1.

So we form our polynomial:

Let's suppose that we know the value of [tex dpi=72]f(1)=3[/tex]. What do we know about [tex dpi=72]f(0)[/tex]?

The answer is: Nothing.

Why? There are five possible polynomials that satisfy [tex dpi=72]f(1)=3[/tex], all of which have different values at 0, and they're all equally likely.

Work it out and see.

The same reasoning works for any finite field, but for the moment, we'll stick with "sufficiently large prime".

Divisibility

Andy argument contains, in part:

Because [tex dpi=72]g(0)[/tex] is a positive integer, we know that [tex dpi=72]D_1 > 1000[/tex], and that [tex dpi=72]D_1[/tex] is a multiple of 2.

It should now be obvious why Andy's argument doesn't apply in arithmetic modulo a sufficiently large prime: All sufficiently large primes are odd, and when working in such a modulus, just because a number is multiplied by 2, that doesn't make it even. In our example, we used modulo 5. What's 3 times 2 modulo 5? Is it even or odd?

It gets more complicated in arbitrary fields (and I wish I had the time to go into Galois fields a bit further), but this is basically all you need to know: When working with fields, the concept of "divisibility" doesn't come up. In a field, every number can be divided by any other non-zero number. Using the most familiar example of a field, the rationals, you can see that It doesn't even make sense to ask if 2/3 is even or odd. The same thing is going on here.

Anyway, it's 2am. I hope this helped. Feel free to ask any questions.

And I expect that somebody will probably fix the Wikipedia example soonish.