confium_tc_gg18/
lagrange.rs

1//! Lagrange interpolation in the P-256 scalar field.
2//!
3//! Both DKG verification and signing combine `T` per-party values that
4//! were generated as evaluations of a degree-`T-1` polynomial. The
5//! combination is a Lagrange-basis-weighted sum evaluated at `x = 0`:
6//!
7//! `f(0) = \sum_i \lambda_i \cdot y_i`, where
8//! `\lambda_i = \prod_{j \ne i} \frac{-x_j}{x_i - x_j}` and `x_k` is
9//! party `k`'s 1-based roster index.
10
11use p256::Scalar;
12
13/// Compute the Lagrange basis coefficient `\lambda_i` for evaluating
14/// the polynomial at `x = 0`, given the full set of participating
15/// x-coords `xs` and the specific coordinate `xi`.
16pub fn lagrange_basis_scalar(xi: Scalar, xs: &[Scalar]) -> Scalar {
17    let mut num = Scalar::ONE;
18    let mut den = Scalar::ONE;
19    for &xj in xs {
20        if xj == xi {
21            continue;
22        }
23        num *= -xj;
24        den *= xi - xj;
25    }
26    // Garbage-in-garbage-out on zero input; protocol callers pass
27    // non-zero scalars (sweep ledger: SEC-audit-notes).
28    let den_inv = den.invert().unwrap_or(Scalar::ZERO);
29    num * den_inv
30}
31
32/// Apply Lagrange interpolation at `x = 0` to `(x_i, y_i)` pairs.
33pub fn lagrange_weighted_sum(pairs: &[(Scalar, Scalar)]) -> Scalar {
34    let xs: Vec<Scalar> = pairs.iter().map(|(x, _)| *x).collect();
35    let mut acc = Scalar::ZERO;
36    for (i, &(_, yi)) in pairs.iter().enumerate() {
37        let lam = lagrange_basis_scalar(xs[i], &xs);
38        acc += lam * yi;
39    }
40    acc
41}
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    fn idx(i: u32) -> Scalar {
48        Scalar::from(i)
49    }
50
51    #[test]
52    fn lagrange_recovers_secret_for_2_of_3() {
53        let a0 = Scalar::from(42u64);
54        let a1 = Scalar::from(7u64);
55        let y1 = a0 + a1 * idx(1);
56        let y2 = a0 + a1 * idx(2);
57        let recovered = lagrange_weighted_sum(&[(idx(1), y1), (idx(2), y2)]);
58        assert_eq!(recovered, a0);
59    }
60
61    #[test]
62    fn lagrange_recovers_secret_for_3_of_3() {
63        let a0 = Scalar::from(123u64);
64        let a1 = Scalar::from(4u64);
65        let a2 = Scalar::from(9u64);
66        let eval = |x: Scalar| a0 + a1 * x + a2 * x * x;
67        let recovered = lagrange_weighted_sum(&[
68            (idx(1), eval(idx(1))),
69            (idx(2), eval(idx(2))),
70            (idx(3), eval(idx(3))),
71        ]);
72        assert_eq!(recovered, a0);
73    }
74
75    #[test]
76    fn lagrange_any_t_subset_recovers_same_secret() {
77        // Degree-1 polynomial (threshold T=2): any 2 of the 3
78        // evaluations recover the secret.
79        let a0 = Scalar::from(99u64);
80        let a1 = Scalar::from(2u64);
81        let eval = |x: Scalar| a0 + a1 * x;
82        let all: [(Scalar, Scalar); 3] = [
83            (idx(1), eval(idx(1))),
84            (idx(2), eval(idx(2))),
85            (idx(3), eval(idx(3))),
86        ];
87        for (i, j) in [(0usize, 1), (0, 2), (1, 2)] {
88            let subset = [all[i], all[j]];
89            let r = lagrange_weighted_sum(&subset);
90            assert_eq!(r, a0, "2-of-3 subset must recover secret");
91        }
92        let r = lagrange_weighted_sum(&all);
93        assert_eq!(r, a0);
94    }
95
96    #[test]
97    fn lagrange_handles_degree_zero() {
98        let a0 = Scalar::from(7u64);
99        let r = lagrange_weighted_sum(&[(idx(1), a0)]);
100        assert_eq!(r, a0);
101    }
102}
confium_tc_gg18/lagrange.rs

confium_tc_gg18/
lagrange.rs
