confium_tc_frost_p256/
shamir.rs

1//! Real Shamir secret sharing over the P-256 scalar field.
2//!
3//! Splits a `Scalar` secret into N shares using a random polynomial
4//! of degree T-1. Any T shares can reconstruct the secret via Lagrange
5//! interpolation.
6
7use crate::scalar;
8use p256::FieldBytes;
9use p256::Scalar;
10use p256::elliptic_curve::PrimeField;
11use sha2::{Digest as _, Sha256};
12
13/// A Shamir share: (x, y) where x is the party index and y is a scalar.
14/// The secret `y` field is zeroized on drop.
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub struct Share {
17    /// Party index (the x-coordinate). Typically 1-based per FROST convention.
18    pub x: u32,
19    /// The share value (the y-coordinate).
20    pub y: Scalar,
21}
22
23impl Drop for Share {
24    fn drop(&mut self) {
25        use zeroize::Zeroize;
26        self.y.zeroize();
27    }
28}
29
30/// Errors during Shamir operations.
31#[derive(Debug, thiserror::Error)]
32pub enum ShamirError {
33    /// Fewer than T shares provided for recovery.
34    #[error("insufficient shares: have {have}, need at least {need}")]
35    InsufficientShares {
36        /// Count received.
37        have: usize,
38        /// Threshold.
39        need: u32,
40    },
41    /// Duplicate x-coordinates would cause divide-by-zero.
42    #[error("duplicate x-coordinate: {0}")]
43    DuplicateX(u32),
44}
45
46/// Split a `secret` into `n` shares with threshold `t`. Any `t` of the
47/// `n` shares can reconstruct the secret.
48///
49/// Polynomial: f(x) = secret + a_1*x + a_2*x^2 + ... + a_{t-1}*x^{t-1}
50/// Share i: (i, f(i)) for i in 1..=n
51pub fn split_secret(secret: &Scalar, t: u32, n: u32) -> Vec<Share> {
52    assert!(t >= 1, "threshold must be at least 1");
53    assert!(n >= t, "n must be >= t");
54
55    // Generate random polynomial coefficients
56    let mut coeffs: Vec<Scalar> = Vec::with_capacity(t as usize);
57    coeffs.push(*secret);
58    for _ in 1..t {
59        coeffs.push(scalar::random_scalar());
60    }
61
62    // Evaluate polynomial at x = 1, 2, ..., n
63    (1..=n)
64        .map(|i| {
65            let x = u32_to_scalar(i);
66            Share {
67                x: i,
68                y: evaluate_polynomial(&coeffs, &x),
69            }
70        })
71        .collect()
72}
73
74fn evaluate_polynomial(coeffs: &[Scalar], x: &Scalar) -> Scalar {
75    // Horner's method
76    let mut result = Scalar::ZERO;
77    for c in coeffs.iter().rev() {
78        result = scalar::scalar_mul(&result, x);
79        result = scalar::scalar_add(&result, c);
80    }
81    result
82}
83
84/// Reduce 32 bytes to a scalar by rejection sampling with re-hash;
85/// never falls back to a constant.
86fn reduce_to_scalar(mut bytes: [u8; 32]) -> Scalar {
87    loop {
88        if let Some(s) = Option::<Scalar>::from(Scalar::from_repr(FieldBytes::from(bytes))) {
89            return s;
90        }
91        let mut h = Sha256::new();
92        h.update(b"confium-scalar-reduce-v1");
93        h.update(bytes);
94        bytes = h.finalize().into();
95    }
96}
97
98fn u32_to_scalar(v: u32) -> Scalar {
99    let mut arr = [0u8; 32];
100    arr[28..32].copy_from_slice(&v.to_be_bytes());
101    reduce_to_scalar(arr)
102}
103
104/// Recover the secret (the polynomial evaluated at x=0) from at least
105/// `t` shares via Lagrange interpolation.
106pub fn recover_secret(shares: &[&Share]) -> Result<Scalar, ShamirError> {
107    if shares.is_empty() {
108        return Err(ShamirError::InsufficientShares { have: 0, need: 1 });
109    }
110
111    // Check for duplicate x values
112    let mut seen = std::collections::HashSet::new();
113    for s in shares {
114        if !seen.insert(s.x) {
115            return Err(ShamirError::DuplicateX(s.x));
116        }
117    }
118
119    // Lagrange interpolation at x=0:
120    // f(0) = sum_i y_i * prod_{j != i} (0 - x_j) / (x_i - x_j)
121    let mut sum = Scalar::ZERO;
122    for s_i in shares {
123        let x_i = u32_to_scalar(s_i.x);
124        let mut numerator = Scalar::ONE;
125        let mut denominator = Scalar::ONE;
126        for s_j in shares {
127            if s_j.x == s_i.x {
128                continue;
129            }
130            let x_j = u32_to_scalar(s_j.x);
131            // numerator *= (0 - x_j) = -x_j
132            numerator = scalar::scalar_mul(&numerator, &scalar::scalar_sub(&Scalar::ZERO, &x_j));
133            // denominator *= (x_i - x_j)
134            denominator = scalar::scalar_mul(&denominator, &scalar::scalar_sub(&x_i, &x_j));
135        }
136        let denom_inv = scalar::scalar_invert(&denominator);
137        let lagrange_coeff = scalar::scalar_mul(&numerator, &denom_inv);
138        let term = scalar::scalar_mul(&s_i.y, &lagrange_coeff);
139        sum = scalar::scalar_add(&sum, &term);
140    }
141    Ok(sum)
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn split_and_reconstruct_at_threshold() {
150        let secret = scalar::random_scalar();
151        let shares = split_secret(&secret, 3, 5);
152        let subset: Vec<&Share> = shares.iter().take(3).collect();
153        let recovered = recover_secret(&subset).unwrap();
154        assert_eq!(recovered, secret);
155    }
156
157    #[test]
158    fn different_threshold_subsets_same_secret() {
159        let secret = scalar::random_scalar();
160        let shares = split_secret(&secret, 3, 5);
161        let subset_a: Vec<&Share> = vec![&shares[0], &shares[1], &shares[2]];
162        let subset_b: Vec<&Share> = vec![&shares[2], &shares[3], &shares[4]];
163        assert_eq!(recover_secret(&subset_a).unwrap(), secret);
164        assert_eq!(recover_secret(&subset_b).unwrap(), secret);
165    }
166
167    #[test]
168    fn duplicate_x_fails() {
169        let secret = scalar::random_scalar();
170        let shares = split_secret(&secret, 3, 5);
171        let subset: Vec<&Share> = vec![&shares[0], &shares[0]];
172        let result = recover_secret(&subset);
173        assert!(matches!(result, Err(ShamirError::DuplicateX(_))));
174    }
175
176    #[test]
177    fn empty_shares_fail() {
178        let result = recover_secret(&[]);
179        assert!(matches!(
180            result,
181            Err(ShamirError::InsufficientShares { .. })
182        ));
183    }
184
185    #[test]
186    fn threshold_one() {
187        let secret = scalar::random_scalar();
188        let shares = split_secret(&secret, 1, 3);
189        let subset: Vec<&Share> = vec![&shares[0]];
190        let recovered = recover_secret(&subset).unwrap();
191        assert_eq!(recovered, secret);
192    }
193}
194
195#[cfg(test)]
196mod proptests {
197    use super::*;
198    use proptest::prelude::*;
199
200    // Any threshold T in [1, 10], any party count N in [T, 20]:
201    // any subset of T distinct shares reconstructs the same secret.
202    proptest! {
203        #[test]
204        fn any_t_of_n_reconstructs_secret(t in 1u32..=10, n in 10u32..=20) {
205            let secret = scalar::random_scalar();
206            let shares = split_secret(&secret, t, n);
207            prop_assert_eq!(shares.len() as u32, n);
208
209            // First T shares
210            let subset_a: Vec<&Share> = shares.iter().take(t as usize).collect();
211            prop_assert_eq!(recover_secret(&subset_a)?, secret);
212
213            // Last T shares (different subset when N > T)
214            if n > t {
215                let subset_b: Vec<&Share> = shares.iter().skip((n - t) as usize).collect();
216                prop_assert_eq!(recover_secret(&subset_b)?, secret);
217            }
218
219            // A "middle" subset
220            if n > t {
221                let mid = (n - t) / 2;
222                let subset_c: Vec<&Share> = shares.iter().skip(mid as usize).take(t as usize).collect();
223                prop_assert_eq!(recover_secret(&subset_c)?, secret);
224            }
225        }
226    }
227
228    // Reconstruction is deterministic: same shares in different orders
229    // give the same secret.
230    proptest! {
231        #[test]
232        fn reconstruction_order_invariant(t in 1u32..=8, n in 8u32..=16) {
233            let secret = scalar::random_scalar();
234            let shares = split_secret(&secret, t, n);
235            let mut subset: Vec<&Share> = shares.iter().take(t as usize).collect();
236            let expected = recover_secret(&subset)?;
237
238            // Reverse the subset — should still reconstruct the same secret.
239            subset.reverse();
240            prop_assert_eq!(recover_secret(&subset)?, expected);
241        }
242    }
243
244    // Threshold invariant: T shares suffice, T-1 do not (different secret).
245    // The T-1 reconstruction gives SOME scalar, but it shouldn't match the
246    // original with overwhelming probability.
247    proptest! {
248        #[test]
249        fn below_threshold_gives_different_secret(t in 2u32..=8, n in 8u32..=16) {
250            let secret = scalar::random_scalar();
251            let shares = split_secret(&secret, t, n);
252
253            // (T-1) shares — reconstruction should NOT match the secret
254            // (probability 1/p ≈ 1/2^256 of accidental match).
255            let subset: Vec<&Share> = shares.iter().take((t - 1) as usize).collect();
256            if let Ok(recovered) = recover_secret(&subset) {
257                prop_assert_ne!(
258                    recovered, secret,
259                    "below-threshold reconstruction accidentally matched (p ≈ 1/2^256)"
260                );
261            }
262        }
263    }
264}
confium_tc_frost_p256/shamir.rs

confium_tc_frost_p256/
shamir.rs
