Scheme Comparison

Structural & security properties

Shamir, Feldman, and Traceable Shamir are dealer-driven ("top-down"): a dealer picks the secret polynomial and hands each guardian a specific share. BUSS and Traceable BUSS are guardian-driven ("bottom-up"): each guardian independently derives their own contribution from their own long-term key, and the dealer only interpolates through the values guardians already picked. That structural difference is what drives most of the rows below — guardian storage, on-chain data, and deniability especially.

Property	Shamir SSS	Feldman VSS	Traceable Shamir	BUSS	Traceable BUSS
Threshold	(t+1)-of-(n−1)	(t+1)-of-(n−1)	t-of-n	(t+1)-of-(n−1)	(t+1)-of-(n−1)
Share generation	Top-down (dealer)	Top-down (dealer)	Top-down (dealer)	Bottom-up (guardian)	Bottom-up (guardian)
Guardian evaluation point	Fixed integer	Fixed integer	Random scalar	Fixed integer	Random scalar
Guardian storage	Store shares	Store shares	Store shares	Stateless — σⱼ = H(owner_id ‖ skⱼ) rederivable on demand	σⱼ rederivable; xⱼ must be remembered (or re-derived by the deployment) per owner
Public / on-chain data	None	t+1 group commitments Cⱼ	None (trace key stays with the dealer)	φ: n−t−1 scalars	φ: n−t−1 shares, and vk if tracing is set up
Key rotation (update one guardian's key without a full re-share)	No — requires a fresh split	No — requires a fresh split	No — requires a fresh split	Yes — `update_public_shares` shifts φ by a guardian-supplied Δ	Yes — same Δ-shift, over (x, y) φ entries
Share verifiability	None — trust the dealer	Yes — check gʸ = Σⱼ Cⱼ·xʲ	None (combinable with Feldman)	—	—
Traceability against leakers	No	No	Yes — up to f < t, black-box oracle	No	Yes — up to f ≤ t, imperfect reconstruction box
Non-imputability	—	—	Yes	—	Yes
Guardian-set deniability — public (no public record of who a guardian is)	No — guardian set is fixed by the dealer at setup	No — same as Shamir, plus public commitments	No — same as Shamir	Structural — φ is opaque; no guardian is named anywhere public	Weaker than BUSS — an actual trace event reveals a specific guardian's participation
Guardian-set deniability — interactive (a prober impersonating the owner can't tell if a node is really their guardian)	No — a real guardian must hold a share stored under this owner's identifier; probing for it leaks membership	No — same as Shamir	No — same as Shamir	Yes — σⱼ = H(owner_id ‖ skⱼ) is a stateless, total function of any owner_id; every node computes an equally valid-looking response whether or not they're a real guardian	σⱼ still gives this; xⱼ breaks it — only real guardians hold stored state for this owner (unless a deployment derives xⱼ deterministically too, restoring the property)
Security model	Information-theoretic	Info-theoretic secrecy; verifiability needs discrete-log hardness	Info-theoretic secrecy; non-imputability needs hash preimage-resistance	Information-theoretic	Info-theoretic secrecy; non-imputability needs hash preimage-resistance

On "deniability" and "non-imputability": these describe three different things. Non-imputability is about a corrupt tracer framing an honest guardian after the fact. The two deniability rows are about whether guardian-set membership can be learned at all, before anything goes wrong — but from two different vantage points: public deniability asks whether an outside observer can learn the guardian set from data that's published (φ, commitments, …); interactive deniability asks whether an active attacker who impersonates the owner and directly probes a node can tell it apart from a random one. BUSS gets the interactive property "for free" because guardian_share is a stateless function that produces an equally plausible-looking output for any owner_id, guardian or not — there's nothing guardian-specific to be caught holding. Only Traceable BUSS's non-imputability claim comes with a concrete cryptographic argument (forging a witness means inverting a hash); both deniability rows are structural consequences of BUSS's bottom-up design, not claims this crate formally proves — like everything else here, treat them as design properties to evaluate for your threat model, not an audited guarantee.

Choosing a scheme: reach for Shamir for simple, fast, dealer-driven sharing. Add Feldman when guardians need to catch a cheating dealer before reconstruction. Use a Traceable variant when you need to identify (and prove) which guardian leaked. Prefer the BUSS family when guardians should stay stateless and their identities shouldn't be tied to a public registry — social key recovery is the target use case; add the Traceable variant on top when you also need accountability without sacrificing non-imputability.

Performance

Every scheme has a dedicated Criterion benchmark file under benches/ covering share creation, reconstruction, and (where applicable) tracing and trace verification. Full methodology, every measured size, and how to reproduce these numbers are in BENCHMARK.md. The table below is a snapshot at a mid-sized community (n=50, t=25; trace/verify_trace at t=10, n=20, f=1) to compare schemes at a glance. For Shamir, Feldman, and Traceable Shamir, "Split" includes generating the random polynomial first — BUSS's split() has no separate polynomial-construction step to exclude (it interpolates from guardian shares and evaluates in one call), so timing only the evaluation half of the dealer-driven schemes would understate their cost relative to BUSS's.

Test machine: Intel Core i9-14900HX (24 cores / 32 threads, up to 5.8 GHz), 62 GiB RAM, Ubuntu 24.04.4 LTS, rustc 1.93.1, release profile. Benchmarks are single-threaded, so only single-core performance is reflected here. Numbers are Criterion's median estimate — re-run cargo bench for figures specific to your own machine.

Scheme	Split	Reconstruct	Update public shares	Trace	Verify trace
Shamir SSS	32.7 µs	54.3 µs	—	—	—
Feldman VSS	33.8 µs	54.0 µs	—	—	—
Traceable Shamir	45.7 µs	51.4 µs	—	2.07 ms	240 ns
BUSS	304 µs	158 µs	1.34 ms	—	—
Traceable BUSS	292 µs	151 µs	1.29 ms	2.94 ms	234 ns

Why BUSS's split is still slower than Shamir's at the same size: Shamir interpolates a degree-t polynomial from t+1 points; BUSS's bottom-up structure means the dealer interpolates a degree-(n−1) polynomial through all n points (every guardian's self-chosen share participates, not just a threshold subset) — an O(n²) Lagrange interpolation instead of O(n·t). Reconstruct doesn't pay this cost (it only ever combines φ with a threshold subset), which is why BUSS's reconstruct stays close to Shamir's. This gap used to be ~65× at n=50 (2.14 ms vs 32.7 µs) before a bug fix in Polynomial::interpolate — it was accidentally O(k³) instead of O(k²), rebuilding each point's Lagrange basis from scratch instead of dividing down a shared node polynomial — brought it to ~9×. See benches/buss.rs and benches/shamir.rs for the full size sweep.