Struct Interpolator 

pub struct Interpolator<I, F> { /* private fields */ }

An interpolator allows recovering a polynomial’s constant from values.

This is useful for polynomial secret sharing. There, a secret is stored in the constant of a polynomial. Shares of the secret are created by evaluating the polynomial at various points. Given enough values for these points, the secret can be recovered.

Using an Interpolator can be more efficient, because work can be done in advance based only on the points that will be used for recovery, before the value of the polynomial at these points is known. The interpolator can use these values to recover the secret at a later time.

Usage

    let interpolator = Interpolator::new([(0, p0), (1, p1)]);
    assert_eq!(
        Some(*f.constant()),
        interpolator.interpolate(&[(0, f.eval(&p0)), (1, f.eval(&p1))].into_iter().try_collect().unwrap(), &Sequential)
    );
    assert_eq!(
        Some(*g.constant()),
        interpolator.interpolate(&[(1, g.eval(&p1)), (0, g.eval(&p0))].into_iter().try_collect().unwrap(), &Sequential)
    );

Implementations

impl<I: PartialEq, F: Ring> Interpolator<I, F>

pub fn interpolate<K: Space<F>>( &self, evals: &Map<I, K>, strategy: &impl Strategy, ) -> Option<K>

Interpolate a polynomial’s evaluations to recover its constant.

The indices provided here MUST match those provided to Self::new exactly, otherwise None will be returned.

impl<I: Clone + Ord, F: Field> Interpolator<I, F>

pub fn new(points: impl IntoIterator<Item = (I, F)>) -> Self

Create a new interpolator, given an association from indices to evaluation points.

If an index appears multiple times, the implementation is free to use any one of the evaluation points associated with that index. In other words, don’t do that, or ensure that if, for some reason, an index appears more than once, then it has the same evaluation point.

impl<I: Clone + Ord, F: FieldNTT> Interpolator<I, F>

pub fn roots_of_unity(total: NonZeroU32, points: BiMap<I, u32>) -> Self

Create an interpolator for evaluation points at roots of unity.

This uses the fast O(n log n) algorithm from crate::ntt::lagrange_coefficients.

Each (I, u32) pair maps an index I to an evaluation point w^k where w is a primitive root of unity of order next_power_of_two(total).

Indices k >= total are ignored.