Shamir Secret Sharing

Information-Theoretic Secret Splitting — n-of-m Threshold Recovery

1. Protocol Overview

What is Shamir Secret Sharing?

Shamir Secret Sharing (SSS) is a threshold cryptographic scheme where a secret (like a 12-word mnemonic or private key) is split into m shares, and any n shares can recover the secret. Fewer than n shares reveal nothing about the secret — not even a single bit.

Key property: Information-theoretic security. Unlike MPC, SSS is computationally secure without relying on hard problems (ECDLP, factoring). Perfect secrecy: even with infinite computing power, t-1 shares reveal zero information.

Aspect	Shamir SSS	MPC (Threshold Signature)
Offline	Yes (purely local)	No (interactive protocol)
Recovery Model	Reconstruct secret	Each party keeps their share
Information Theory	Perfect secrecy	Computational secrecy
Use Case	Backup, recovery codes	Signing, key derivation

2. Mathematics Behind SSS

Polynomial Interpolation over a Prime Field

SSS uses Lagrange polynomial interpolation over a finite field GF(p) (integers modulo a large prime p).

Secret: S (a 256-bit integer, e.g., private key) Threshold: t (number of shares needed) Total shares: m (total shares created) Step 1: Generate polynomial P(x) with degree t-1 P(x) = S + a_1*x + a_2*x^2 + ... + a_(t-1)*x^(t-1) where S = P(0) (the constant term is the secret!) a_1, a_2, ..., a_(t-1) are random coefficients in GF(p) Step 2: Generate m shares by evaluating P at x = 1, 2, ..., m share_1 = P(1) = S + a_1 + a_2 + ... share_2 = P(2) = S + 2*a_1 + 4*a_2 + ... share_3 = P(3) = S + 3*a_1 + 9*a_2 + ... ... share_m = P(m) = S + m*a_1 + m^2*a_2 + ...

Recovery: Any t shares can uniquely determine the polynomial via Lagrange interpolation, thus revealing S = P(0).

Security: Any t-1 shares are uniformly random in GF(p). No information about S is leaked.

Horner Evaluation (Efficient)

To evaluate P(x) = S + a_1*x + a_2*x^2 + ... + a_t*x^t: Naive: P(x) = S + a_1*x + a_2*x^2 + a_3*x^3 + ... Requires: t multiplications and t additions Horner: P(x) = S + x*(a_1 + x*(a_2 + x*(a_3 + ...))) Requires: t multiplications and t additions (same!) But: More cache-friendly, avoids computing large powers

Example with t=2 (linear): P(x) = 0x4a2b + x*0x7c3f (mod p)

P(1) = 0x4a2b + 1*0x7c3f = 0xc66a (share 1) P(2) = 0x4a2b + 2*0x7c3f = 0x44a9 (share 2) P(3) = 0x4a2b + 3*0x7c3f = 0xbce8 (share 3)

Lagrange Interpolation (Recovery)

Given t shares: (x_1, y_1), (x_2, y_2), ..., (x_t, y_t) Lagrange basis polynomial: L_i(x) = ∏(x - x_j) / (x_i - x_j) for j != i Secret S = P(0) = sum(y_i * L_i(0) for i=1..t) where L_i(0) = ∏(-x_j) / (x_i - x_j) for j != i

This is offline and deterministic — no network communication needed.

Example: 2-of-3 Recovery

With shares y_1 and y_2 at x_1=1 and x_2=2, the secret is:

S = y_1 * (0 - 2)/(1 - 2) + y_2 * (0 - 1)/(2 - 1)

= y_1 * (-2)/(-1) + y_2 * (-1)/(1)

= 2*y_1 - y_2

3. Secret Export Workflow

Typical use: Split a 12 or 24-word BIP39 mnemonic into shares for backup.

3.1 Export Flow Diagram

User Input: Mnemonic

→

Select Threshold (n-of-m)

Polynomial P(x) = Secret + random coefficients

Generate m Shares

→

P(1), P(2), ..., P(m)

Evaluate polynomial at x = 1, 2, ..., m

Verify Shares

→

Lagrange Check

Any n shares must reconstruct original secret

Generate QR Codes

→

Display Share Cards

Print, photograph, or write down

User Securely Stores Shares

→

Erase Original from Device

Explicit memory zeroing to prevent recovery

3.2 Step-by-Step Breakdown

Entropy Selection

User selects 128, 160, 192, or 256 bits of entropy. The app generates a BIP39 mnemonic or uses one from a hardware wallet.

Configure Threshold

User selects n-of-m: e.g., "2-of-3" means any 2 shares can recover, but 1 alone cannot.

Generate Shares

App creates m random shares using Horner evaluation. Each share is a sequence of hex values or BIP39 words.

Verify Shares

App re-runs Lagrange interpolation to verify that combining any t shares recovers the original secret.

Display & Export

Show each share as a card (with duplicate QR codes). User can print, photograph, or write them down.

Erase Original

Once exported, the original mnemonic is securely erased from device memory using explicit zeroing.

4. Secret Recovery Workflow

Typical use: Recover a lost or stolen mnemonic using saved shares.

4.1 Recovery Flow Diagram

User Selects n Shares

→

Gather from Storage

From printed cards, USB, safes, vaults, etc.

Scan/Input Shares

→

QR Camera or Manual

Read hex values or BIP39 words

Validate Checksums

→

Verify x-Coordinates

Check: x₁ ≠ x₂ ≠ ... ≠ xₙ and all in valid range

Lagrange Interpolation

→

Solve P(0) = Secret

All arithmetic modulo p (prime field), local computation only

Convert Secret

→

BIP39 Mnemonic

24-word phrase from 256-bit integer

Display on Screen

→

Import to Wallet

User can verify and import into crypto wallet or hardware device

4.2 Step-by-Step Breakdown

Select Shares to Recover

User picks which n shares (out of m) to use. App shows the threshold requirement.

Scan/Input Shares

App uses camera to scan QR codes, or user manually types in hex/BIP39 words.

Validate Share Format

Verify checksum and that shares belong to the same scheme (same x-coordinates).

Perform Lagrange Interpolation

Recover P(0) = secret using Lagrange basis polynomials. All math is local.

Convert to Mnemonic/Key

Convert the recovered secret to BIP39 words or derive crypto keys.

Display Results

Show mnemonic on screen. User can import into wallet, hardware device, or MPC app.

Mobile Experience

5. iOS App — Share Creation and Recovery

5.1 Export: Creating Shares

Create Secret Shares

Entropy Source

Security

256-bit entropy = 24-word BIP39 mnemonic. Highest security.

Entropy

Configure Threshold

Recovery Threshold (n-of-m)

n: 2

m: 3

2 of 3 shares required to recover

Loss of 1 share: OK
Loss of 2 shares: Secret lost forever

Threshold

Share Cards

SHARE 1
x=1
y: 0x7f2a5c8b... (hex)

SHARE 2
x=2
y: 0x3e8d1f4a... (hex)

Cards

5.2 Recovery: Scanning Shares

Recover Secret

📱

Share 1 (scanned)

Share 2 (scanned)

Share 3 (needed: 2/2)

Scan 2 share QR codes or enter manually

Scan

Recovering Secret

⏳

Validate shares

Lagrange interpolation

Verify mnemonic

All computations local to device...

Recovering

Secret Recovered ✓

✓

24-Word Mnemonic

1. abandon 2. ability 3. able 4. about 5. above 6. absent

Recovered

6. Shamir SSS vs. MPC vs. Single Device

Comparison

Aspect	Shamir SSS	MPC (Threshold Signing)	Single Device
Interactive	No (offline)	Yes (network required)	No
Secret Recovery	Reconstruct original	Each party keeps share	N/A
Security Type	Information-theoretic	Computational	Single point of failure
Use Case	Backup, recovery codes	Signing, key derivation	Custodial wallets
Storage	Print, air-gap storage	Device Secure Enclave	Device storage
Loss Tolerance	Lose m-n shares safely	Lose fewer than t parties	Device lost = key lost

Best Use Cases

Shamir SSS: Backup a 24-word seed phrase into 5 cards, store them in vaults. Recover with any 3 cards. Perfect for long-term cold storage.

MPC: Day-to-day signing with your phone + server. No single device can sign alone. Better for frequent transactions.

Combination: Generate a master seed via MPC key generation, then back it up via Shamir SSS for ultimate redundancy.