Shamir’s Secret Sharing Scheme

vault (https://vaultproject.io) uses Shamir to generate shares for operators to unseal the vault. In the latest release (1.0beta), vault seal keys can be wrapped with something like AWS KMS which allow for operator-less unsealing of the seal keys, but trade that off with potential operator access to the seal key itself.

Collusion between operators is a real problem of Shamir-based key systems. If you have a crypto system that depends on Shamir keys and a few of your operators leave the organization or become untrustworthy for some reason, then you need to revoke / resplit the origin key data material.

Additionally, the output of the ssss command itself is not secure, so you should consider having that data going through GPG to give each operator a GPG / keybase'd output which has never been seen in cleartext by anyone but themselves.

Long story short, key management continues to be really hard and needs to be thought through from begin to end with operational procedures in place to handle the real life situations that occur (employee collusion, employee join/depart, breach).

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.

It is possible to control both the number of key shares and the threshold required to unseal Vault (and now to do automatic unseal too), so I’m not certain this particular condition should be too much of a concern anymore. That said, considering as many scenarios as possible is definitely sensible!

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.

The Blockchain project zcoin (XZC) has implemented this and plan to apply it in to elections back in Thailand.