Demystifying Shamir's Secret Sharing: how to protect critical assets without single points of failure

Every serious key custody conversation ends up at the same wall.

Put the key in one place and that place is a single point of failure. One compromised laptop, one disgruntled administrator, one seized server, one flood in the wrong room, and either the key is gone or it belongs to somebody else.

Copy the key to three places and you have not solved the problem, you have tripled it. Now there are three complete copies, each one sufficient on its own, each one a full compromise if it leaks.

The instinct at this point is to reach for process. Two people must be present. The safe needs two keys. Access requires a second approval. All of that is worth doing, and none of it changes the underlying fact that somewhere in the building there is a complete copy of the secret, and the controls around it are a promise rather than a property.

There is a way out of this, it is nearly fifty years old, and it is one of the few pieces of cryptography that is genuinely easy to understand once somebody draws it.

The idea, in one picture

Adi Shamir published it in November 1979, in a two page paper in Communications of the ACM titled "How to Share a Secret". Two pages. It has not needed revision since.

Start with the thing everybody learns in school and forgets: two points define a straight line. Give me any two points on a line and I can draw the line exactly. Give me one point and I cannot, because an infinite number of lines pass through a single point, and I have no way to prefer one over another.

Now go up a degree. Three points define a parabola. Two points on that parabola are consistent with infinitely many parabolas, so two points tell you nothing about which one it was.

That is the entire mechanism.

Take your secret and treat it as a number. Make it the value of a polynomial at x equals zero, the point where the curve crosses the vertical axis. Then choose the rest of the polynomial's coefficients at random. If you want a threshold of three, you use a curve of degree two, a parabola. If you want a threshold of five, degree four.

Now pick any number of points along that curve and hand one to each shareholder. Those points are the shares. Nobody holds the secret. Everybody holds a coordinate.

When enough of them come together, they have enough points to reconstruct the one curve that passes through all of them, and once you have the curve you evaluate it at x equals zero and the secret falls out. Three shareholders on a parabola, five on a degree four curve. The number of shares you hand out has nothing to do with the threshold, so ten of one and any three can rebuild it is a perfectly ordinary configuration.

The property that makes it different from everything else

Here is the part that gets lost when people describe this as "splitting a key into pieces", which is the wrong mental model and undersells it badly.

If you split a password into three chunks and hand them out, two chunks give an attacker two thirds of the password. They have made real progress. Brute force on the remaining third is now trivial.

Shamir's scheme does not do that. With one share short of the threshold, an attacker has learned nothing. Not "not enough". Nothing.

Every possible secret remains exactly as likely as it was before they had any shares at all. For any value you propose for the secret, there exists a curve passing through the shares they hold that produces it. Their information about the answer has not moved.

This is called information-theoretic security, and it is a stronger claim than almost anything else in applied cryptography. Most of what we rely on is computationally secure, which means breaking it requires an amount of work we believe is infeasible with current mathematics and current machines. That belief has a shelf life, and quantum computing is the reason everyone is currently rewriting their assumptions about it.

Information-theoretic security makes no assumption about the attacker's computing power. An adversary with infinite computation and infinite time, holding one share fewer than the threshold, still cannot determine the secret, because the information required to distinguish the right answer from every wrong one is not present in what they hold. There is nothing to compute.

That is a rare guarantee, and it is the reason this scheme is still load-bearing five decades later.

Where it is already holding something up

This is not a laboratory technique waiting for adoption.

The DNSSEC root key ceremony uses it. The root of trust for DNS validation on the public internet is protected in a facility with a documented, filmed ceremony, and part of that design is a Storage Master Key exported under a five of seven threshold scheme and distributed to seven Recovery Key Share Holders, each organisationally separate from the operators, each keeping their share in a bank safe deposit box. Five of them, physically present with their shares, is what it takes to recover the key backups if every hardware security module is lost at once.

HashiCorp Vault ships with it as the default unseal mechanism. Initialise a Vault and it generates five key shares with a threshold of three, and the master key does not exist in any single place at rest. Three of five operators is what it takes to bring the system back after a restart. Most teams running Vault in production are using Shamir's scheme daily without ever calling it that.

Custody in the cryptocurrency sector runs on the same principle, and so do the recovery designs behind serious hardware wallets.

The pattern in all of them is the same. The thing being protected is not stored. It is reconstituted, briefly, under quorum, when there is a reason to.

The two limits nobody puts on the slide

A method that hides its limits is not a method. There are two, and both matter more than the elegance of the maths.

The reconstruction moment is the whole attack surface. The shares are useless individually, which is the point, but at some instant the quorum has to combine them somewhere, and at that instant the machine performing the reconstruction holds the complete secret in memory. Everything the scheme bought you is concentrated into that window. If that reconstruction happens on an ordinary laptop, on a general purpose operating system, connected to a network, then you have five people with perfect share hygiene protecting a secret that appears in plaintext on the least trustworthy device in the room. This is why serious deployments do the combining inside a hardware security module or on an air gapped machine, and why the ICANN ceremony is a physical ritual in a locked room rather than a script. The maths does not protect you at the moment of use. Nothing does, except the environment you chose.

The scheme has no idea whether a share is honest. Classical Shamir's Secret Sharing has no integrity check. If a shareholder submits a corrupted share, whether through a disk error or on purpose, the reconstruction does not fail and does not warn you. It produces a different curve, and that curve evaluates to a different number at x equals zero, and out comes a perfectly well formed secret that is simply wrong. You will not learn this from the algorithm. You will learn it when you try to decrypt something and it does not open, if you are lucky, or considerably later if you are not. This is the reason verifiable secret sharing exists as a separate research line, and if you are deploying this in anger you either use a scheme with commitments or you attach your own integrity check to the reconstructed value before you trust it.

Neither of these breaks the technique. Both of them break naive implementations of it, which is a different thing and a more common one.

Why this shapes how we build

The reason this sits in the Signal series rather than in a paper somewhere is that the property it gives you is the property we want everywhere.

A person should have the final say over their own information. What stays hidden, what can be proven, and what gets destroyed. Every one of those depends on key custody, and key custody without a single point of failure is the difference between a company that promises it cannot read your data and a company for which reading your data is not an available operation.

The distinction between those two sentences is not marketing. It is architecture. One of them survives an acquisition, a court order, and a bad hire. The other one does not.

Shamir gave the industry a way to hold something valuable without any one party holding it. Two pages, 1979, and most systems still store the key in a file.

Sources

Adi Shamir, "How to Share a Secret", Communications of the ACM, Volume 22, Issue 11, November 1979: https://dl.acm.org/doi/10.1145/359168.359176

Root Zone KSK Operator Key Management Policy, IANA: https://www.iana.org/dnssec/procedures/ksk-operator/KSK_Key_Management_Policy_v3.8.pdf

HashiCorp Vault, Seal and unseal concepts: https://developer.hashicorp.com/vault/docs/concepts/seal