Random evaluation points transform Shamir SSS into a traceable scheme: if up to f < t guardians leak their shares, the dealer can identify exactly who — using only black-box oracle access to the adversary's reconstruction box.
Boneh, Partap, and Rotem (ePrint 2024/405) showed that a single structural change —
using uniformly random evaluation points instead of fixed integers — turns Shamir SSS
into a traceable scheme. The dealer's trace key
tk = (H(x₁), …, H(xₙ)) stores a one-way hash of each evaluation
point rather than the raw value. If up to f < t guardians leak their shares, calling
trace() with those leaked shares internally issues N synthetic
reconstruction queries, collects evaluations of the "traitor polynomial"
h*(X) = Πj∈corrupt(xⱼ − X)/xⱼ, and recovers it via Guruswami-Sudan list
decoding. The roots of h* are the leaked evaluation points — matched back to guardian
identities by re-hashing each root and comparing against the trace key.
Reconstruction is unchanged from Shamir: Lagrange interpolation at x = 0 on any t shares. The random evaluation points are perfectly valid Lagrange nodes; no additional cost beyond the key generation phase.
Sample n distinct nonzero random evaluation points x₁,…,xₙ ←$ 𝔽* and a random
degree-(t−1) polynomial q with q(0) = s. Distribute
(xᵢ, q(xᵢ)) to party i.
compute_tracing_keys derives
tk = (H(x₁),…,H(xₙ)) — trace key and verification key coincide.
Any t parties submit their shares. Lagrange interpolation at x = 0 recovers s = q(0). The random evaluation points are valid Lagrange nodes — reconstruction is identical to standard Shamir.
Given the leaked shares directly, trace() internally issues
N reconstruction queries against synthesized fresh shares plus the leaked ones,
collecting (x'ℓ, zℓ) pairs that evaluate the traitor polynomial h*. The
Guruswami-Sudan decoder finds all degree-≤f polynomials matching ≥ C pairs
(N and C are derived automatically from f and a security parameter fixed at
construction). The roots of the recovered h* are the leaked xᵢ — matched back to
party indices by re-hashing each root and comparing against the trace key.
trace() returns (accused, witness)
where witness[k] = x_{accused[k]}. Anyone holding tk can call
verify_trace to check in O(f) hashes that
H(witness[k]) == tk[accused[k]].
use arc_pleiades::TraceableShamir;
use arc_pleiades::secret_sharing::{SecretSharing, TraceableSS};
use midnight_curves::Fq as Scalar;
use sha2::Sha512;
use rand::thread_rng;
let mut rng = thread_rng();
// 3-out-of-5: any 3 shares reconstruct; can trace up to f=1 leaker
let ts = TraceableShamir::<Sha512>::new(3, 5, 1, 4)?;
let secret = Scalar::random(&mut rng);
// Split — random evaluation points; tk/vk hold H(xᵢ), not the raw xᵢ
let poly = ts.polynomial(secret, &mut rng);
let shares = ts.split(&poly)?;
let (tk, vk) = ts.compute_tracing_keys(&poly)?;
// Reconstruct from any 3 shares (Lagrange at x=0)
let recovered = ts.reconstruct(&shares[..3])?;
assert_eq!(secret, recovered);
// ── Tracing: party 2 (shares[2]) leaked their share ──
let corrupted = [shares[2]];
let (accused, witness) = ts.trace(&tk, &corrupted, &mut rng)?
.expect("should find the corrupt party");
assert_eq!(accused, vec![2]); // 0-based index of the leaker
ts.verify_trace(&accused, &witness, &vk)?;