Comment by ndr_
11 hours ago
Bruce Schneier described this in his seminal book Applied Cryptography, and HashiCorp Vault used to have an implementation in Go. On the practical side, I always wondered how large - in bits - the shares should be. One answer I got on a news group was "1 bit more than the actual key length". Nowadays, I wonder how the quantum computing threat would inform 1) share size choice and 2) pro/con Secret Sharing in general. Does anyone know?
Plain vanilla Shamir is information-theoretic secure and is completely impervious to QC. I can take a 1-byte secret, make 'threshold of 10' Shamir shares from it, give you 9 of the 1-byte shares, and no computer in the universe can determine the secret. (In practice, Shamir systems need to add a MAC or checksum as an integrity check, so IRL they're a few bytes larger.)
You usually do secret sharing in a finite field because computers don't like real numbers. The size of your share is a point (x, y), x can be small (typically log n in case of n participants), y is a random point in the field.
Since Shamir Secret Sharing is information-theoretically secure (if you do not know k points from the k-out-of-n secret then all secrets are equally plausible even when bruteforcing), the bitsize of your field can be whatever you want (but obviously bigger than the bitsize of your secret, you can't hide 100 bits in a finite field of 5 elements).
Usually, you don't want an attacker to be able to bruteforce your secret (while the scheme is ITS, your secret typically isn't, e.g. the seed of your wallet), hence randomness can be added to your secret and the bitsize of the field is taken big enough to thwart these attacks.
Depending on your attack model, an 80-bits or 128-bits field is more than secure enough, hence a share bitsize slightly above 80 or 128 bits.
And regarding quantum computer, since the scheme is ITS no attacks can exist.
I think hashicorp still have an implementation for vaults seal/unseal process. Unless something changed ofc
They still do indeed.
One point is that there is no reason for the entire secret to be one element of the underlying field, it can very well be a n-tuple of elements of a smaller field, with GF(2^8) being the somewhat obvious choice if you do not expect ridiculous numbers of shares, no need to deal with bignum math.
Shamir's is based on the fundamental theorem of algebra — you need n+1 points to uniquely define a degree n polynomial. So you achieve an n of k setup by building a degree n-1 polynomial p(x) and taking k random points from that polynomial. The i-th share is just (xi, yi), so the number of bits is defined by the field you're building the polynomial on. Because the field has to be wide enough to store the whole secret and you have to store two values (x, y), share sizes are at least two times the size of the secret. (You'll want some sort of integrity check to make sure your share isn't corrupted, though)
As I understand it, quantum computing changes nothing here — if you're missing even one point, that last point could change the secret to anything at all, with no way to disambiguate.
Do you remember why 1 bit more?