I asked a question yesterday on Envoy Backups and Magic backups and the answer defines the magic backup and how it is created and used.
Shamir Secret Sharing (SSS) is a cryptographic method developed by Adi Shamir in 1979 for securely distributing a secret among a group of participants. Instead of giving the entire secret to one person (which creates a single point of failure), the secret is divided into multiple parts called “shares.”
The key property is that only specific combinations of these shares can reconstruct the original secret. This is known as a threshold scheme.
How It Works
The system uses polynomial interpolation over finite fields. Here’s the step-by-step process:
1. Secret Division
- The secret (let’s call it S) is embedded as the constant term of a polynomial
- Create a random polynomial of degree (k-1) where k is the threshold number
- The polynomial looks like: $f(x) = S + a_1x + a_2x^2 + … + a_{k-1}x^{k-1}$
- The coefficients $a_1, a_2, …, a_{k-1}$ are randomly chosen
2. Share Generation
- Generate n shares by evaluating the polynomial at different points
- Each share is a pair $(x_i, f(x_i))$ where $x_i$ is a unique value
- Any k shares can reconstruct the polynomial, but k-1 shares reveal nothing
3. Secret Reconstruction
- Use Lagrange interpolation with k shares to reconstruct the polynomial
- The secret is the constant term $f(0)$ of the reconstructed polynomial
Key Properties
Threshold Security: Exactly k shares are needed to reconstruct the secret. Fewer than k shares provide no information about the secret.
Perfect Information Theoretic Security: The scheme is mathematically proven to be secure - with fewer than k shares, the secret could be any value with equal probability.
Flexibility: You can choose any threshold (k) and total number of shares (n) where k ≤ n.
Practical Example
If you want to split a secret among 5 people where any 3 can reconstruct it:
- Set k=3, n=5
- Create a degree-2 polynomial
- Generate 5 shares
- Any 3 of the 5 people can combine their shares to get the secret
- 2 people together learn nothing useful
Common Applications
- Cryptocurrency wallet recovery schemes
- Nuclear launch codes
- Corporate secret management
- Database encryption key distribution
- Multi-party authentication systems
The beauty of Shamir’s scheme is its mathematical elegance - it’s simple to implement yet provides provable security guarantees without requiring complex computational assumptions.