The foundational (t+1)-of-(n−1) threshold scheme — polynomial evaluation over a finite field, Lagrange interpolation at zero, and information-theoretic security with no computational assumptions.
Adi Shamir's 1979 construction remains the cornerstone of threshold cryptography. The dealer chooses a uniformly random polynomial f of degree t over a finite field with f(0) equal to the secret. Each of the n−1 guardians receives a single evaluation (i, f(i)). Any t+1 of these points determine f uniquely via Lagrange interpolation; t or fewer points are information-theoretically independent of the secret — the scheme requires no computational hardness assumption whatsoever.
Pleiades implements Shamir SSS over a elliptic curve's scalar field
Fr (~255-bit prime order). The primary split path uses
Horner's method (O(t·n)); an FFT variant runs in O(n log n) when n ≫ t and the
field has suitable roots of unity.
ShamirSecretSharing::new(t, n)
creates a (t+1)-of-(n−1) scheme — n−1 shares are produced and any
t+1 suffice to reconstruct. Constraints: n ≥ 2 and
t < n−1.
Sample a uniformly random degree-t polynomial f with f(0) = s. Evaluate at points 1, 2, …, n−1 using Horner's method — or the FFT variant for large n — to produce n−1 shares.
Hand share (i, f(i)) to guardian i.
Each share is two field elements — small and portable over any channel.
Any t+1 guardians submit their shares. Lagrange interpolation at x = 0 recovers s = f(0). An iFFT fast-path applies when shares are at roots of unity.
use arc_pleiades::{ShamirSecretSharing, Share};
use midnight_curves::Fr as Scalar;
use rand::thread_rng;
// t=2, n=5 → 4 shares (n−1), threshold 3 (t+1)
let sss = ShamirSecretSharing::new(2, 5)?;
let secret = Scalar::from(42u64);
// Standard split — O(t·n) via Horner's method
let shares: Vec<Share<Scalar>> = sss.split(secret, &mut thread_rng())?;
assert_eq!(shares.len(), 4);
// FFT split — O(n log n), efficient when n ≫ t
let shares_fft = sss.split_fft(secret, &mut thread_rng())?;
// Reconstruct from any 3 shares (uses iFFT fast-path when possible)
let recovered = sss.reconstruct(&shares[1..4])?;
assert_eq!(secret, recovered);