The Secret Sharing Problem

You have a master key that must survive, be accessible in emergencies, yet never be compromised by a single person. How do you store it? Giving the full key to multiple people means any one of them can misuse it. Keeping one copy creates a single point of failure.

Splitting a 128-bit key into two 64-bit halves and giving each half to two people seems clever but is insecure: each half reduces the brute-force cost from 2^128 to 2^64. An adversary who compromises one person gains a 64-bit head start.

A proper secret sharing scheme must be: (1) Threshold: any k-of-n shares reconstruct the secret. (2) Security: any (k-1) shares reveal zero information about the secret. (3) Perfect: no computational assumptions required.

Bitcoin wallets, HSM master keys, certificate authority private keys, nuclear launch codes, and cryptocurrency exchange cold wallets all need threshold access. Loss of the single key = catastrophic. Compromise by one insider = also catastrophic.

To share secret S between two parties: generate random R. Give share1=R to party 1, share2=S XOR R to party 2. To reconstruct: share1 XOR share2 = R XOR (S XOR R) = S. Either share alone is perfectly random — reveals nothing about S.

XOR sharing is perfect 2-of-2 but does not generalize to k-of-n threshold schemes. You cannot create a 3-of-5 scheme where any 3 shares reconstruct the secret but any 2 reveal nothing. Polynomial interpolation solves this.

Perfect secrecy means the shares contain zero mutual information about the secret with fewer than k shares. This is stronger than computational security — even a computationally unbounded adversary learns nothing from k-1 shares.

AWS CloudHSM uses M-of-N quorum authentication. PGP key escrow splits master keys. Cryptocurrency custody providers (Fireblocks, BitGo) use MPC or Shamir sharing for hot wallet keys. Certificate Authority offline keys use 5-of-7 ceremonies.

A key ceremony is a formal, audited process for generating and splitting a master key. Example: 7 keyholders present in a secure room, each receiving a hardware token with one share. Video-recorded, two auditors present, each step documented.

Secret sharing reconstructs the full secret (risk: single point at reconstruction time). Multisig distributes signing: each party signs independently and signatures are combined. Threshold signatures (TSS) are secret sharing applied to the signing operation itself.

Secure Multi-Party Computation (MPC) eliminates the reconstruction step entirely — parties jointly compute using their shares without revealing the secret. Threshold ECDSA and threshold BLS are deployed in production custody systems.

In a 2-of-2 XOR secret sharing scheme, how many shares does an attacker need to learn the secret?

Naive key splitting is insecure. Proper secret sharing requires threshold access with perfect secrecy. XOR handles 2-of-2; polynomial interpolation handles k-of-n. Next: Shamir's Secret Sharing math.