3 ms·

Shamir's Secret Sharing is probably my favourite algorithm for showing the deep relationship between algebra and cryptography. The Fundamental Theorem of Algebr

by pdpi 8y ago

Shamir's Secret Sharing is probably my favourite algorithm for showing the deep relationship between algebra and cryptography. The Fundamental Theorem of Algebra is a relatively straightforward result to show to a layperson, and Shamir's is basically as direct an application of it as you could want. Then the part where using integers leaks information, and how to attack that, gets a bit hairier but is still a moderately accessible way to show cryptanalysis in practice. The fix using finite fields is then probably a step too far for most laypeople, and can be used as a lesson in how the fundamentals can be simple, but the devil is in the details.

antidesitter 8y ago
Finite fields can be explained to laypeople as arithmetic on a clock (with a prime number of hours), so additions and multiplications wrap around.
- pdpi 8y ago
  Sure, but the whys and wherefores of how they fix the security issues in SSS are harder.
  - drostie 8y ago
    Maybe somewhat. I think you can offer a simple explanation, but it depends a little on how you have already set up the problem. Here's the problem setup: So we want to share a secret byte (178) among Alice, Bob, and Carol, so that we need all 3 of them to contribute to it. Three points defines a parabola so we choose two more random bytes: [38, 68], our polynomial is y = 178 + 38x + 68x². We then give Alice the point (1, 284), Bob the point (2, 526), and Carol the point (3, 904). Now supposing that we have compromised both Bob and Carol's points we know that we have the two equations, 9a + 3b + c = 904 4a + 2b + c = 526 We can then eliminate b to get: 6a - c = 230 which we can rearrange as c = 6a - 230. Since `a` cannot be a fraction, we must be able to cut down the number of possibilities for c to just 42 possibilities, {4, 10, 16, 22, 28, ...}, since they must be separated by sixes. I'm not 100% sure but I think this factor grows like n!/(n-k)! for "I have compromised k of n secrets, by what factor have I reduced the search space?" Here's how modular arithmetic solves this: It turns out that modulo a prime, all fractions are also whole numbers. That is, if I am working modulo the prime 13, I will find that I can divide 7/5 to find 4. Remember what division means, it inverts multiplication: I can find that 5 × 4 = 20 and then that 20 = 13 + 7, so they are at the same place "on the clock". In fact it suffices to just find 1/5 and multiply by 7, so you can find that 1/5 is 8 in the mod-13 ring, 8 × 5 = 40 = 39 + 1. You can also find that 1/6 is 11, so 6 × 11 = 66 = 65 + 1. The proof that this must be the case is that if you take [1, 2, ..., p-1].map(x => (x * n) % p) this list cannot repeat itself: if it did, the resulting `x1 - x2` would divide `p`, by the distributive law of multiplication. It also is confined to only contain the numbers 1 through p-1, and so it must contain all of them exactly once: so if it doesn't repeat itself, it has to have a 1 in there somewhere. That's kind of a brute force argument so you may want to also mention that there are two efficient ways to find these, one is called the "Extended Euclidean algorithm" (do a GCD computation to find that the GCD=1, but you can take the dividends that you discarded and cleverly assemble them to recover the constants from Bezout's identity, which in this case gives you the modular inverse) and the other is called "Fermat's little theorem" (since a^(p-1) % p == 1 for prime p, raise something to the p-2 power. Using exponentiation by squaring you only need ~log p multiplications that each take no more than ~log p time.
tzs 8y ago
I don't think you actually need FTA. I think you just need that an n'th degree polynomial has at most n roots. That might be better to show to a layperson, because if the layperson remembers their middle school algebra you can probably actually prove it to them. For the part on leaking information, you can do the special case of two shares being required to recover the secret. You can then fairly straightforwardly show that if someone obtains just one share it does not help by showing that no matter what the secret, it is possible for that share to be a share for that secret. It's conceptually similar to how you show that xor with a true random key is unbreakable. It's not the general case, but it can demonstrate how using modular arithmetic can fix an information leak.
y7 8y ago
What does Shamir's (or any) secret-sharing scheme have to do with the fundamental theorem of algebra?
- fusiongyro 8y ago
  The real question is what the fundamental theorem of algebra has to do with algebra.

by pdpi 8y ago

antidesitter 8y ago

Finite fields can be explained to laypeople as arithmetic on a clock (with a prime number of hours), so additions and multiplications wrap around.

pdpi 8y ago
Sure, but the whys and wherefores of how they fix the security issues in SSS are harder.
- drostie 8y ago
  Maybe somewhat. I think you can offer a simple explanation, but it depends a little on how you have already set up the problem. Here's the problem setup: So we want to share a secret byte (178) among Alice, Bob, and Carol, so that we need all 3 of them to contribute to it. Three points defines a parabola so we choose two more random bytes: [38, 68], our polynomial is y = 178 + 38x + 68x². We then give Alice the point (1, 284), Bob the point (2, 526), and Carol the point (3, 904). Now supposing that we have compromised both Bob and Carol's points we know that we have the two equations, 9a + 3b + c = 904 4a + 2b + c = 526 We can then eliminate b to get: 6a - c = 230 which we can rearrange as c = 6a - 230. Since `a` cannot be a fraction, we must be able to cut down the number of possibilities for c to just 42 possibilities, {4, 10, 16, 22, 28, ...}, since they must be separated by sixes. I'm not 100% sure but I think this factor grows like n!/(n-k)! for "I have compromised k of n secrets, by what factor have I reduced the search space?" Here's how modular arithmetic solves this: It turns out that modulo a prime, all fractions are also whole numbers. That is, if I am working modulo the prime 13, I will find that I can divide 7/5 to find 4. Remember what division means, it inverts multiplication: I can find that 5 × 4 = 20 and then that 20 = 13 + 7, so they are at the same place "on the clock". In fact it suffices to just find 1/5 and multiply by 7, so you can find that 1/5 is 8 in the mod-13 ring, 8 × 5 = 40 = 39 + 1. You can also find that 1/6 is 11, so 6 × 11 = 66 = 65 + 1. The proof that this must be the case is that if you take [1, 2, ..., p-1].map(x => (x * n) % p) this list cannot repeat itself: if it did, the resulting `x1 - x2` would divide `p`, by the distributive law of multiplication. It also is confined to only contain the numbers 1 through p-1, and so it must contain all of them exactly once: so if it doesn't repeat itself, it has to have a 1 in there somewhere. That's kind of a brute force argument so you may want to also mention that there are two efficient ways to find these, one is called the "Extended Euclidean algorithm" (do a GCD computation to find that the GCD=1, but you can take the dividends that you discarded and cleverly assemble them to recover the constants from Bezout's identity, which in this case gives you the modular inverse) and the other is called "Fermat's little theorem" (since a^(p-1) % p == 1 for prime p, raise something to the p-2 power. Using exponentiation by squaring you only need ~log p multiplications that each take no more than ~log p time.

tzs 8y ago

I don't think you actually need FTA. I think you just need that an n'th degree polynomial has at most n roots. That might be better to show to a layperson, because if the layperson remembers their middle school algebra you can probably actually prove it to them. For the part on leaking information, you can do the special case of two shares being required to recover the secret. You can then fairly straightforwardly show that if someone obtains just one share it does not help by showing that no matter what the secret, it is possible for that share to be a share for that secret. It's conceptually similar to how you show that xor with a true random key is unbreakable. It's not the general case, but it can demonstrate how using modular arithmetic can fix an information leak.

y7 8y ago

What does Shamir's (or any) secret-sharing scheme have to do with the fundamental theorem of algebra?

fusiongyro 8y ago
The real question is what the fundamental theorem of algebra has to do with algebra.