How Shamir's Secret Sharing Works

It seems like a cool idea, did you follow up with a product or an open source app?

Done something similar for mine as well, although the word of the year that day was blockchain, so implemented the same onto Ethereum. It was a fun project, and Secret Sharing is quite an interesting topic!

Where is your thesis available?

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.

It's the same idea as how GPS works. Fun to see someone's eyes light up when they get why that third satellite is needed to fix a 2D position.

(Actual GPS is a little more complicated than that because the real system needs accurate time information.)

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.

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

I think hashicorp still have an implementation for vaults seal/unseal process. Unless something changed ofc

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.

Do you remember why 1 bit more?

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.

This is my favorite one yet, very user friendly. I only wish it was a bit more configurable. Ideally I'd be able to set up something like:

  3 of 4: A B C D
  - OR -
    2 of 3: E F G
    - AND -
    1 of 1: H

Or any similar combination. Maybe also with a way to name the cards so it's clear exactly what's needed when restoring.

Though there's something to be said for the simplicity of the current design.

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

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/

I’ve been noodling over this exact business idea for a couple years! Part of my value prop was to make ops scale down to as close to zero as possible by having the encrypted data and most of the front end for accessing it live in S3 objects (or some similar mega-cheap object store). Aside from that, all you need is the dead man’s switch mechanism. And the secret fragments would live on QR codes that bring you to the static SPA with one of the fragments already loaded up, prompting you to scan more to complete the decryption.

Good work doing it. I guess now I don’t have to. :D You may have gained a customer from this HN thread.

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

They go into extreme detail about DNSsec root key security

https://blog.apnic.net/2021/10/12/dns-security-and-key-cerem...

Trezor supports it.

I wrote something like that about 15 years ago for a financial institution.

For what we needed, we intentionally wanted both people to be at the same terminal (it was going to be used to give shell access to a specific unix account that ran a critical system).

That mean that we could implement it as a setuid (root) binary that required both users to authenticate. It had a config file that worked like sudoers, and defined a list of commands that could be called, how many people were needed to authenticate, and which unix groups they had to belong to.

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.

There's a related 2-man sudo login system here, not sure how finegrained it is.

https://github.com/Argonne-National-Laboratory/Pam-2man-Auth

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

this story is wildd

which is in fact by Max Levchin: https://max.levch.in/post/724289457144070144/shamir-secret-s...

Yes?

If I use 3 shares and require all three to recover, then I think I could let the 3 points define a plane. Then the plane would intersect the axis at a unique point.

If I want 4 or more shares, I can make them by just generating more points on that same plane. Then I think any three of those should recover the secret. So it seems like that would all work about the same as with the polynomials? Then I can go to still more dimensions when I want to require more shares to reveal the secret.

Probably, but the nice thing about polynomials is the secret is the value when x is 0. What is the point on the hyper geometry where I look up the secret?

Two points make a line in any number of dimensions.

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.

You can never be sure that duplicated information is destroyed, but if you combine SSS with a dead-man's switch protecting an asymmetric private key, you can periodically invalidate a set of shares.

As a bonus, when you refresh the shares, you'll discover that at least a couple of your trusted parties have absolutely no memory of receiving that mysterious piece of paper from you back in 2022.

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.

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.

> it's said to be one of the toughest Indian language to learn.

By who? My SO is now passably conversant in Malayalam after watching their cinema during the covid lockdowns (~1y to 2y).