Shamir secret sharing (k-of-n)

Deep dive

How it works

In: secret bytes, threshold k, share count n (k <= n <= 255 over GF(2^8)), a random source · Out: n shares (x, y) with distinct non-zero x and y as long as the secret · State: none, shares live with their holders · Cost: split n*(k-1) multiplications per byte, combine about k per byte after O(k^2) setup.

1. Choose a field: a prime field GF(p) with p larger than the secret and n, or byte-wise GF(2^8) with the AES polynomial x^8+x^4+x^3+x+1 (0x11B). Addition in GF(2^8) is XOR.
2. For each secret byte s draw a_1..a_{k-1} uniformly at random and set f(t) = s + a_1 t + ... + a_{k-1} t^{k-1}, so f(0) = s.
3. Holder i gets (x_i, f(x_i)) for distinct, non-zero x_i (1..n works; x = 0 is the secret). Only the polynomial is secret; x values are public labels.
4. To recover, take k shares with distinct x and compute the Lagrange weights at zero: w_i = prod_{j != i} x_j / (x_i + x_j) (minus is plus in characteristic 2).
5. The secret byte is f(0) = sum_i w_i y_i. The weights depend only on the x values, so compute them once for all bytes.

Why k-1 shares reveal nothing: together with a guessed secret they fix exactly one degree k-1 polynomial, so every guess is equally consistent. The code checks this exhaustively for k=3 and a one-byte secret. Shares of a and b add to shares of a+b, which makes the scheme a building block of MPC.

Code

Rust, std only. mul is the AES-field multiply without branches or tables, inv is a^254. The xorshift generator is a demo: use a CSPRNG in real code. Asserts: all 10 three-subsets reconstruct, the exhaustive secrecy check, a flipped bit gives a wrong secret silently, a duplicate x is rejected. Timed on an aarch64 Mac, release build.

use std::{hint::black_box, time::Instant};

/// GF(2^8) multiply, AES polynomial x^8+x^4+x^3+x+1 (0x11B). No branches, no tables.
pub fn mul(mut a: u8, mut b: u8) -> u8 {
    let mut r = 0u8;
    for _ in 0..8 {
        r ^= a & 0u8.wrapping_sub(b & 1);          // add a if low bit of b is set
        a = (a << 1) ^ (0x1B & 0u8.wrapping_sub(a >> 7)); // times x, reduce if bit 7 was set
        b >>= 1;
    }
    r
}
/// a^254 = a^-1 (a != 0): square-and-multiply, fixed 7 rounds.
pub fn inv(a: u8) -> u8 {
    let (mut r, mut p) = (1u8, a);
    for _ in 0..7 { p = mul(p, p); r = mul(r, p); } // r = a^2 * a^4 * ... * a^128
    r
}
#[derive(Clone)]
pub struct Share { pub x: u8, pub y: Vec<u8> }

/// Degree k-1 polynomial per secret byte, f(0)=secret, other coefficients uniform random.
pub fn split(secret: &[u8], k: usize, n: usize, rng: &mut impl FnMut() -> u8) -> Vec<Share> {
    assert!(2 <= k && k <= n && n <= 255);
    let polys: Vec<Vec<u8>> = secret.iter()
        .map(|&s| std::iter::once(s).chain((1..k).map(|_| rng())).collect()).collect();
    (1..=n as u8).map(|x| Share { x, y: polys.iter()
        .map(|c| c.iter().rev().fold(0, |acc, &ci| mul(acc, x) ^ ci)).collect() }).collect() // Horner
}
/// Lagrange interpolation at x = 0 over the given shares (any k or more).
pub fn combine(sh: &[Share]) -> Result<Vec<u8>, &'static str> {
    for (i, s) in sh.iter().enumerate() {
        if s.x == 0 { return Err("x = 0 is the secret"); }
        if sh[..i].iter().any(|t| t.x == s.x) { return Err("duplicate x"); }
    }
    let w: Vec<u8> = sh.iter().enumerate().map(|(i, si)| { // w_i = prod_j x_j / (x_i + x_j)
        let (mut num, mut den) = (1u8, 1u8);
        for sj in sh.iter().enumerate().filter(|&(j, _)| j != i).map(|(_, s)| s) { num = mul(num, sj.x); den = mul(den, si.x ^ sj.x); }
        mul(num, inv(den))
    }).collect();
    Ok((0..sh[0].y.len()).map(|b| sh.iter().zip(&w).fold(0, |acc, (s, &wi)| acc ^ mul(wi, s.y[b]))).collect())
}
fn main() {
    let mut st = 0x9E3779B97F4A7C15u64; // demo xorshift64: use a CSPRNG (OS random bytes) in real code
    let mut rng = move || { st ^= st << 13; st ^= st >> 7; st ^= st << 17; (st >> 24) as u8 };
    assert_eq!(mul(0x57, 0x83), 0xC1); // FIPS 197 example
    assert!((1..=255u8).all(|a| mul(a, inv(a)) == 1));
    let secret = b"correct horse battery staple".to_vec();
    let sh = split(&secret, 3, 5, &mut rng);
    for a in 0..5 { for b in a + 1..5 { for c in b + 1..5 { // all 10 subsets of 3
        assert_eq!(combine(&[sh[a].clone(), sh[b].clone(), sh[c].clone()]).unwrap(), secret);
    }}}
    // k-1 = 2 shares (x=1,2) of a 1-byte secret: for every secret the 65536 coefficient pairs map
    // one-to-one onto all (y1,y2) pairs, so the pair carries no information about the secret.
    for s in 0..=255u8 {
        let mut hist = vec![0u8; 65536];
        for c in 0..=65535u16 {
            let mut it = [c as u8, (c >> 8) as u8].into_iter();
            let t = split(&[s], 3, 5, &mut || it.next().unwrap());
            hist[t[0].y[0] as usize * 256 + t[1].y[0] as usize] += 1;
        }
        assert!(hist.iter().all(|&h| h == 1));
    }
    let mut bad = sh[..3].to_vec();
    bad[1].y[0] ^= 1; // one flipped bit in one share
    assert_ne!(combine(&bad).unwrap(), secret); // silently wrong
    let dup = [Share { x: 1, y: vec![5] }, Share { x: 1, y: vec![6] }];
    assert_eq!(combine(&dup).err(), Some("duplicate x"));
    let big = vec![0xA5u8; 1 << 16];
    let t = Instant::now(); let sh = black_box(split(&big, 3, 5, &mut rng)); let ts = t.elapsed();
    let t = Instant::now(); let out = black_box(combine(&sh[..3])); let tc = t.elapsed();
    assert_eq!(out.unwrap(), big);
    println!("split k=3 n=5: {:.1} ns/byte, combine 3 shares: {:.1} ns/byte",
        ts.as_nanos() as f64 / big.len() as f64, tc.as_nanos() as f64 / big.len() as f64);
}

Output: split k=3 n=5: 66.0 ns/byte, combine 3 shares: 7.9 ns/byte (runs vary by a few percent).

Complexity and constants

• Split: n*(k-1) multiplications per secret byte (Horner) plus k-1 random bytes per secret byte; here 10 multiplications. Combine: k multiplications per byte plus O(k^2) weight setup with one field inversion per share.
• Memory: n shares of L+1 bytes; a 32-byte secret in 5 shares is 165 bytes.
• Measured: about 66 ns/byte split, 8 ns/byte combine, so a 32-byte key splits in order of 2 µs. The split figure includes one small heap allocation per secret byte and overstates the arithmetic.
• Cost drivers: random-byte supply (syscalls), the multiply, and for bulk data n full-size outputs.

Efficiency

Cost: a 16-32 byte key costs order of microseconds on a laptop core (measured above) and n*(L+1) bytes; compute-bound on the field multiply, irrelevant next to gathering k holders.

Levers:

• Share a random data key, not the data — shares stay 16-32 bytes instead of the file size (arithmetic) — for anything beyond a key.
• Precompute the Lagrange weights once per quorum — the O(k^2) setup and inversions leave the per-byte loop (combine ran at 8 ns/byte here) — when reconstructing many bytes.
• Draw all random bytes with one bulk CSPRNG call — one syscall instead of one per byte — always.
• Table, carry-less or GFNI multiply instead of the bit loop — faster (from memory, unmeasured) — bulk data only, and tables only if cache timing is out of scope.

Naive → standard → state of the art:

• Per-byte coefficient vectors, bit-serial multiply · about 66 ns/byte split (measured)
• Reused buffers, bulk randomness, precomputed weights · lower, unmeasured
• Vectorised GF(2^8) multiply · memory-bandwidth bound; irrelevant at key size

Implementation notes

• Randomness: coefficients must be uniform, independent and fresh on every split; two secrets shared with the same coefficients leak their XOR.
• Constant time: log/exp-table multiplication indexes memory with secret-dependent values and leaks through cache timing. Use a branch-free loop as above (Vault's shamir package does) or hardware multiply; see constant-time code. Zero the buffers afterwards (zeroization).
• Share format: carry x, version, threshold, a set id and a checksum so shares of different splits are not mixed and typos are caught. SLIP-0039 adds a three-word RS1024 checksum per share.
• Integrity of the result: a share has no way to prove itself. SLIP-0039 uses f(255) for the secret and f(254) for a digest (4 bytes of HMAC-SHA256 of the secret under a random key) and checks it after recovery. Alternatives: a hash or MAC of the secret, or decrypting a known blob.
• Limits: over GF(2^8) n <= 255; for more holders use GF(2^16) or a prime field. Reconstruct on a locked-down machine, use the secret at once, wipe it.

Pitfalls

• One corrupt or mistyped share gives a plausible wrong secret with no error. Always verify against a digest, MAC or trial decryption.
• A malicious holder can submit a bad share and spoil recovery unnoticed. Use verifiable sharing when holders do not trust each other.
• Duplicate x breaks reconstruction and x = 0 hands out the secret. Reject both (the code does).
• k colluding holders have everything. Choose k and n for the real threat; keep shares in separate places under separate custodians.
• Share size leaks the secret length; pad if that matters. Changing k needs a new polynomial, hence reconstruction first (or MPC).

Variants and alternatives

In production

• HashiCorp Vault: vault operator init splits the root key with Shamir; documented defaults are 5 key shares and a threshold of 3. The Go shamir package works byte-wise in GF(2^8), appends x as an extra byte to each share and uses a branch-free multiply (read from source).
• SLIP-0039 (Trezor and other wallets): GF(256) with the Rijndael polynomial, a digest share, checksums, mnemonic words and two levels (groups of members) for seed backup.
• HSM key ceremonies and backups: M-of-N operator cards to activate or restore a key (HSMs, secrets management).
• Cold-storage backups, emergency or estate access: common practice, no single reference.

Implementations

Sources

• Adi Shamir, How to share a secret, Communications of the ACM 22(11), 1979, pp. 612-613. DOI (publisher blocks automated checks; metadata confirmed via Crossref)
• Paul Feldman, A practical scheme for non-interactive verifiable secret sharing, FOCS 1987, pp. 427-438. DOI
• Torben Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, CRYPTO '91, LNCS 576, 1992, pp. 129-140. DOI
• SatoshiLabs, SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes. spec · code
• HashiCorp, Vault documentation. operator init · seal · shamir package
• NIST, FIPS 197: Advanced Encryption Standard, sections 3.2, 4.1, 4.2. DOI