Shamir’s Secret Sharing Scheme
Shamir’s is one of my favorite little crypto schemes. I’ve implemented it over GF(256) in a bunch of different languages just for fun:
Haskell: https://github.com/codahale/hs-shamir Go: https://github.com/codahale/sss Rust: https://github.com/codahale/sss.rs Java: https://github.com/codahale/shamir
This is really fun, I love it. One could devise a whole game around that. Define functions that give you coordinates on a sphere (in this case, the earth), where X (e.g. the "treasure") is hidden. Then plot the functions, make k shares and make them (and mod p) discoverable through different other games (e.g. programming challenges). Then the first person to win all k-1 challenges and mod p is able to interpolate the exact location of the "treasure". A wonderful mix of maths, programming and real world adventure.
vault (https://vaultproject.io) uses Shamir to generate shares for operators to unseal the vault. In the latest release (1.0beta), vault seal keys can be wrapped with something like AWS KMS which allow for operator-less unsealing of the seal keys, but trade that off with potential operator access to the seal key itself.
Collusion between operators is a real problem of Shamir-based key systems. If you have a crypto system that depends on Shamir keys and a few of your operators leave the organization or become untrustworthy for some reason, then you need to revoke / resplit the origin key data material.
Additionally, the output of the ssss command itself is not secure, so you should consider having that data going through GPG to give each operator a GPG / keybase'd output which has never been seen in cleartext by anyone but themselves.
Long story short, key management continues to be really hard and needs to be thought through from begin to end with operational procedures in place to handle the real life situations that occur (employee collusion, employee join/depart, breach).
This math and the key analogy makes me think of the Reed–Solomon error correction algorithm which underlies the parchive sets used to transmit data on systems that are prone to errors in transmission or storage or that don't have any ECC built into the transfer protocols. That's effectively the same result. You are trying to reconstruct the full, original message/file and the checksum for certain pieces show damage so you use the additional data to reconstruct it. The math for the Reed–Solomon is similar in concept to oversampling the points on a line. You only need two points on a line to determine the actual path/slope, etc. so if you take three points, any two will allow you recreate the line.
This is very very very old (not the link, but SSSS). I wonder why did it pop in HN today.
Dark Crystal[https://darkcrystal.pw] is perhaps my favorite implementation of this. It's built on top of Secure Scuttlebutt, and allows you to share private keys with trusted friends, so that you can later rebuild them when they are lost.
This is fascinating but being neither a CS nor Maths graduate I'm having trouble following the maths from the moment modulo operations are introduced.
Would someone be able to suggest a self-learning resource (book, app, ...) that goes into cryptography and the required maths but doesn't demand too much pre-knowledge?
Thanks in advance!
The Blockchain project zcoin (XZC) has implemented this and plan to apply it in to elections back in Thailand.
Whoever posted this may be interested in this (exploded) thread about decentralized surveillance, no spooks needed, which crucially relies on treshold crypto:
Interesting to see an article on this ... had written one a few months back ... https://www.polarsparc.com/xhtml/SecretSharing.html
If anyone is interested in code, this is an implementation in Java made by a friend: https://github.com/comodal/secret-shamiracle
https://vault12.com/ - take a look at this
If you run FreeBSD, you can easily use it for disk encryption: https://www.freebsd.org/cgi/man.cgi?query=gshsec&apropos=0&s...
I would expect this relates to Hashicorp's Vault product. It's gaining some notoriety and employs Shamir's secrets to seal/unseal the main vault.
Shamir's Secret Sharing is probably my favourite algorithm for showing the deep relationship between algebra and cryptography. The Fundamental Theorem of Algebra is a relatively straightforward result to show to a layperson, and Shamir's is basically as direct an application of it as you could want.
Then the part where using integers leaks information, and how to attack that, gets a bit hairier but is still a moderately accessible way to show cryptanalysis in practice. The fix using finite fields is then probably a step too far for most laypeople, and can be used as a lesson in how the fundamentals can be simple, but the devil is in the details.