Shamir’s Secret Sharing Scheme

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.

> If that's the key insight you could do SSSS before any actual digital computers were built

The time window between Gödel's incompleteness theorems and the first digital computers seems to be roughly 1931 to 1946 (if you count ENIAC as the first). That very, very closely overlaps with the Second World War--and even the years before the war were treated by many governments as exactly that, years to prepare for war. I suspect that would put a damper on publishing any interesting results in cryptographic techniques, though to be fair, there is also no evidence that anyone secretly, independently invented SSSS during that period or during the 24 years afterward.

> "You can encode arbitrary data in numeric form" is Kurt Gödel in the first half of the 20th century.

Specifically, that's something like the first two thirds of his incompleteness proof spent establishing that as a fairly novel result, followed by rigorous mathematics to the effect of "Given a formula P(x,y) that asserts "We can't prove x(y,y).", can we prove P(P,P)?".

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!

I really do not understand your frustration. We are running 5 node cluster in production with the keepalived and nobody needs to wake up unsealing if one, or two instances fail. Perfectly good to do it in the morning by copy pasting curl oneliner from the keepass.