How Shamir's Secret Sharing Works

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?

Years ago I build a little tool to run shamir secret sharing in the browser (can be used full offline, just download the page)

https://simon-frey.com/s4/

This is such a cool technique, and you could even teach it in secondary schools as a neat thing computer scientists can do with polynomials.

This is such a cool neat trick.

Vibe-coded a little playground where you can generate secrets, see the polynomial, combine the secrets, and in general, play around:

https://shamirs-secret-sharing.pagey.site

Here is Ente's implementation: (https://2of3.ente.com/)

I also had written an article on the subject a while ago if you want to dig a bit deeper: https://petal.cafe/posts/shamir/

It's an incredible technique, when I came across it, it just changed the way I thought of solving giving out keys without "truly" giving them out. This gave me confidence for eternalvault.app, a project of mine.

Do the people who hold the root DNS keys do anything like this? Or is that too much complexity when a safe in a secure room works as an effective backup?

if the secret is large usually it's encrypted and the payload is distributed along with the shares of the key.

but you can also just use Reed-Solomon and split the payload, the difference with Shamir is that you lose information-theoretic security (you lose it the moment you use encryption anyway) and the payload also needs to undergo an all-or-nothing-transform (AONT).

AONT transforms the entire payload into an encrypted blob which also serves as its own key, a withheld piece is a de facto encryption key. this is required because Reed-Solomon can have pathological cases where pieces leak information.

ente means mine in Malayalam language. it's said to be one of the toughest Indian language to learn. FYI.

before I learned of shamir secret sharing, I wondered why one couldn't do the same exact thing with a par2 like system (albiet with smaller pieces than a par2 system would traditionally have). i.e. you have X bits of data, you create Y*X/N sized recovery blocks (where Y > N). You hand each recovery block to individual users. and any N users can get together to recover the key and decrypt the contents.

something tangentially i am interested in is computing following the 'two person rule' for things like sudo. Yes I am logged into server X at terinal Y, and so is my co-worker and we both sign off on running command X

See also a story about an implementation from Max Levchin: https://max.levch.in/post/724289457144070144/shamir-secret-s...

I also had written an article on the subject a while ago if you want to dig a bit deeper: https://petal.cafe/posts/shamir/

See also a story about an implementation from Max Levchin: https://max.levch.in/post/724289457144070144/shamir-secret-s...

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

Do you remember why 1 bit more?

This is such a cool technique, and you could even teach it in secondary schools as a neat thing computer scientists can do with polynomials.

I am a secondary math teacher and I do exactly this with my students. When working on retrieving the expression of an affine function, I tell them about Shamir'..., they choose a secret pin as the slope, generate two points, give them to two other students who have to pair together to find the pin again. The students are always very engaged.

Here is Ente's implementation: (https://2of3.ente.com/)

There are several browser-based versions which can be used online or downloaded to use offline.

https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

There's an implementation packaged up for most Linux distros: http://point-at-infinity.org/ssss

Do the people who hold the root DNS keys do anything like this? Or is that too much complexity when a safe in a secure room works as an effective backup?

They do something similar. Basically 5 people are needed in order to access the dns root keys plus some extra administrative/witness people. 3 Crypto Officers with smartcards to unlock the hsm, 2 other officials to unlock the vault that contains the hsm and the vault that contains safety deposit boxes with the smartcards. There are 7 crypto officers, of which any three will do.

https://www.cloudflare.com/learning/dns/dnssec/root-signing-...

if the secret is large usually it's encrypted and the payload is distributed along with the shares of the key.

Reed-Solomon is an Erasure code, and I definitely wouldn't look to that for Secret Splitting. Those leakage models are gnarly. But if you want something else that is more general - there are Monotone Span Programs. Seriously underused.

ente means mine in Malayalam language. it's said to be one of the toughest Indian language to learn. FYI.

There's an implementation packaged up for most Linux distros: http://point-at-infinity.org/ssss

https://www.cloudflare.com/learning/dns/dnssec/root-signing-...

Interesting, in Indonesia Ente means you. Derived from Arabic word Anta.

Fascinating how sometimes in different languages one word can have opposite meaning and the other times one word can have similar meaning.

Well in theory the base math is indeed the same; unfortunately though the "randomly chosen" part of shamir's secret sharing is fairly important to the security because information theoretic security of the scheme requires each fragment to be as large as the original secret by way of essentially including a desired count of random data blocks to the original before applying the reed-solomon-like erasure coding to it where now enough fragments to reconstruct the secret plus all random blocks have to be combined. Also the way of usage of the erasure code has to be selected to not be leaking information but that's more of an issue of not picking a bad way of how to implement the basic concept here. Basically just a case of "do follow the instructions to shamir's secret sharing, don't do something different just because it's a popular way of implementing reed-Solomon".

Yes, you can just GF(256), but if you're worried I'd also just use a prime field instead.

Had something like this at Google. There's a service running as root (or equivalent) which receives your desired command to run, and it has to get authorization from another user for the specific command to run, then runs it. That makes sense at Google, because those are production machines and have access to LDAP and who is allowed to run a command on a machine is defined by an LDAP group and you would need two of them (or more?) and there's already existing management website this can be shoe-horned into.

Your environment is unlikely to have all of that already, so you'll need to figure out equivalents for all those. But I think you're going to need a local service running as root and it's going to need to be able to tell the difference between distinct human users, if you want secure. Just typos is way easier.

That sounds like you might want to look into digital signatures.

    > Reed-Solomon is an Erasure code

which shares the same math as Shamir

    > Those leakage models are gnarly.

AONT solves that by making any leak other than the totality meaningless

Yes, you can just GF(256), but if you're worried I'd also just use a prime field instead.

That sounds like you might want to look into digital signatures.

    > Reed-Solomon is an Erasure code

which shares the same math as Shamir

    > Those leakage models are gnarly.

AONT solves that by making any leak other than the totality meaningless

Years ago I build a little tool to run shamir secret sharing in the browser (can be used full offline, just download the page)

https://simon-frey.com/s4/

Ha! Years ago i downloaded your page and stored it in some usb disks along with my kdb keepass database and a share of my password.

I gave that to some members of my family and instruct them to give them to my wife in case I die.

Thanks a lot Sir.

This is such a cool neat trick.

Vibe-coded a little playground where you can generate secrets, see the polynomial, combine the secrets, and in general, play around:

https://shamirs-secret-sharing.pagey.site

Do you remember why 1 bit more?

There are several browser-based versions which can be used online or downloaded to use offline.

https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

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.

Interesting, in Indonesia Ente means you. Derived from Arabic word Anta.

Fascinating how sometimes in different languages one word can have opposite meaning and the other times one word can have similar meaning.

Maybe it's the pronunciation - ente means "mine" and ante means "yours" (in Malayalam) which is what perhaps you may be referring to? (Former South Indian kingdoms and South East Asia have historical cultural ties due to trade and conquest, and thus they share some common words, which I assume is, largely borrowed from Tamil and Malayalam).

Ente also means "duck" in German.

Ha! Years ago i downloaded your page and stored it in some usb disks along with my kdb keepass database and a share of my password.

I gave that to some members of my family and instruct them to give them to my wife in case I die.

Thanks a lot Sir.

They still do indeed.

Ente also means "duck" in German.

Some people use ante to mean yours in the northern region, but it is not common in the southern region.

Some secrets are too important to trust to one person, and too important to lose if that person disappears.

A company wants three officers present before the master key is used. A family wants account recovery to need more than one envelope. A team wants a backup that survives a missing member without handing anyone the whole thing.

Adi Shamir (the S in RSA), published a way to do this in 1979. Split a secret into pieces so that some number of them can recover it, and any smaller number reveals nothing at all. Not "is hard to crack." Reveals nothing.

The core idea fits on a page.

Two points make a line

Start with something you already know: two distinct points determine exactly one straight line.

A single point does not. Infinitely many lines pass through one point, and each line crosses the vertical axis somewhere different.

Two points fix one line; one point allows infinitely many.

Now hide a secret where a line crosses the vertical axis. Say the secret is the number 7. Draw a random line through that height. The slope is not important. It is just randomness that hides the secret.

A line y = 2x + 7. The secret, 7, sits where it crosses the y-axis.

Give each person one point from the line. Nobody gets the line itself.

A person with one point can draw many possible lines through it. Each line implies a different secret. Their share is compatible with every possible answer, so it tells them nothing useful by itself.

Bob holds one share. Many candidate lines pass through it, each implying a different secret.

Put two points together and the line is fixed. Once you know the line, you can read the secret from where it crosses zero.

Alice and Bob's shares together pin down the line and reveal the secret.

That is a 2-of-n secret sharing scheme. You can create as many points as you want, but any two are enough to recover the line.

More people means more bend

For a higher threshold, use a curve with more bend.

A parabola needs three points to determine it. So if the secret is hidden where the parabola crosses the vertical axis, any three shares can recover the secret and any two cannot.

A parabola needs three points to determine; the secret sits at x = 0.

In general, a threshold of k uses a polynomial of degree k - 1.

2 shares: a line
3 shares: a parabola
4 shares: a cubic

Real implementations use finite-field arithmetic rather than graph paper, but the shape of the idea is the same. The secret is the value at zero. The random coefficients hide it. Each share is one point on the polynomial.

The useful part is not that the secret is hard to compute from too few shares. It is that too few shares contain no information about the secret. With one share missing, every possible secret is still possible.

Why we care

We use this idea in Ente's Legacy Kit.

Although, our problem was not just "how do we split a secret?", but also "how do we make recovery possible without turning the split secrets into a permanent recovery key?"

Legacy Kit uses Shamir's scheme as one layer inside a larger flow. The cards don't carry the recovery key. They reconstruct a separate secret locally, which then participates in a server-mediated recovery — so issued cards can be revoked, and a lost card is not a permanent liability.

This post is only the math behind the "any two, never one" part.

Hacker Times