[war1025]

I thought that algorithm was crazy magic when I first heard of it.

The method behind it is pretty fascinating.

A nth degree polynomial is uniquely identified by n+1 points.

So the algorithm interprets your secret to a binary numeric value, sets that as the value at x=0 (i.e. the constant term of the polynomial), picks random coefficients for all the polynomial degrees, then computes coordinate pairs for however many shards you need the secret split into.

Then you give one of the shards to anyone who is sharing the secret.

When enough of the points are input at the same time, the x=0 value can be calculated and the secret is revealed.

The really neat thing about that is if you have something like "There are 500 people in the organization and 6 of them need to be present to perform this procedure", you generate 500 unique points, and any six of those points will let you compute the original secret.

There is some added math bit that gets added on top to make the polynomial less easy to guess, but the concept remains the same.

When the method finally clicked for me, I was left feeling like "that is so obvious, anyone could come up with it", and I feel like those are some of the best discoveries.

[nullc]

"Cool value" often makes for poor security however. The same kind of excitement you felt goes on to cause people to homebrew insecure versions or inappropriately deploy Shamir's Secret Sharing.

https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil

[btilly]

There is some added math bit that gets added on top to make the polynomial less easy to guess, but the concept remains the same.

The added math bit is that you calculate the polynomials modulo some prime number.

That means that you're doing integer arithmetic, but with even one missing point you've gained no information about the secret. (As long as your points were actually generated with good randomness that is...)

[Dylan16807]

While it's a clever method, it's also worth noting that for moderately-sized groups you can achieve the same thing with a much simpler method and almost no math.

Let's say you have a 256 bit key as the secret, and you want any 5 out of 15 people to have access.

For each combination of 5 people, pick 4 random 256 bit numbers. 4 people get those and 1 gets the key encrypted with those numbers as a one time pad.

Once you do every combination, each person will end up with a list of a thousand numbers. Any 5 of them can get together, each grab their number for that group, and XOR them to access the secret.

That's only 32KB of data to hang onto. With 15 people the absolute max is 107KB. Even printed as plain text it would need less than 20 sheets of paper.

[DennisP]

Oh that's great. At one point I wanted to use SSS just for two out of three. I can't believe it never occurred to me to just say "if you're pairing with Jack, xor his number with this one." It's even simple enough to do by hand.

[StavrosK]

What happens if 5 people who have encrypted random numbers (and no key) get together?

[Dylan16807]

What's an "encrypted random number"?

If they have 5 random numbers and XOR them together, then they won't get the key as output.

[StavrosK]

So then it's not "any" 5 out of 15, it's "any group of these three", which is a significant disadvantage compared to SSS.

[dmurray]

No, it's any 5 of the 15. You do the procedure for each of the 15c5 = 3003 groups of 5.

Each person is part of 1001 groups and has a separate 256-bit number for each group. To recombine the numbers, each of the 5 needs to select the number corresponding to that group.

I think this works just as well as SSS for small/moderate sized groups. It's a little less elegant because you need to know which group you're participating in at decode-time, and because it's not scalable (but there are few serious applications that need the scalability).

[rakoo]

The real magic is that even if you can bribe 5 people and discover their point, you don't gain any information: there is an infinite number of degree-6 polynomials that go through 5 points, so you don't know which polynomial is the correct one. With this method it's either "you have it" or "you don't", there's no step in between.

[sasaf5]

Your description made it click for me too! Thank you!