How Shamir's Secret Sharing Works

compsciphd

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.

teravor

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.

Cider9986

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

_jackdk_

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.

calvinmorrison

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

3eb7988a1663

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?

cryptoz

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

sreekanth850

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

ghostfoxgod

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.

ndr_

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?