How Shamir's Secret Sharing Works (opens in new tab)

My masters thesis was on this! I created an app where you can store your data across all the common data storage providers (dropbox, google drive, onedrive, etc.) and used the secret sharing to aid with the encryption. The benefit was that:

- They could no longer read your data

- Additional redundancy (as you only need 2 to be available)

- Compared to other secure storage apps which rely on a master password, which if you forget, you are screwed, you could still use all the usual account recovery methods.

We use this technique in our team to distribute passphrases for our secondary secret stores (that contain instructions on how to access our primary secret stores) in a "democratically secure and safe" manner.

https://packages.debian.org/trixie/ssss is a nice and rather straightforward implementation.

Shamir saved my bottom once, by helping me reconstruct random password used for almost forgotten backup, suddenly needed to be restored at once. Thank God I distributed shares in my family, "just in case".

This part:

"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."

Reminds me of factoring numbers with the Quadratic Sieve or its variants. You find a system of congruences mod n that eventually allow you to compute prime factors, but until you have enough of them that isn't possible. I've often wondered... Each congruence must contain some information right? What space are we reducing degrees of freedom in?

Same thing here, each piece restricts the space of polynomials, but does not restrict it enough to tell where the key crosses the axis.

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.

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?

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

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 very nice explanation which needs no maths. really cool. I read about this a few times in articles without images etc and its hard to digest if you dont have a good background but this was wonderfully easy to understand. Thanks a lot.

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?

SSS is amazing, though managing shares over a long period (people come and go) and dealing with collusion risk can be rough.

Instead of going from two lines to curves, parabolas etc, couldn't you also add another dimension instead?

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.

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/

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

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.

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

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

SSS works pretty well. IIRC somebody in bitcoin community started using this for storing private keys using 3/5 schema. they basically divide the secret keys into 5 parts out of which you only need 3 to recover original private key. IDK if there are any hardware wallets that actually support it yet though.

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