8 ms·

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

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.

sasaf5 6y ago
Your description made it click for me too! Thank you!
nullc 6y ago
"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 https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil
btilly 6y ago
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 6y ago
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.
- StavrosK 6y ago
  What happens if 5 people who have encrypted random numbers (and no key) get together?
  - Dylan16807 6y ago
    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 6y ago
      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 6y ago
        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 6y ago
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 6y ago

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

nullc 6y ago

"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 https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil

btilly 6y ago

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 6y ago

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.

StavrosK 6y ago
What happens if 5 people who have encrypted random numbers (and no key) get together?
- Dylan16807 6y ago
  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 6y ago
    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 6y ago
      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 6y ago

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.