kyber_rs/share/
poly.rs

1/// module `share` implements Shamir secret sharing and polynomial commitments.
2/// Shamir's scheme allows you to split a secret value into multiple parts, so called
3/// shares, by evaluating a secret sharing polynomial at certain indices. The
4/// shared secret can only be reconstructed (via Lagrange interpolation) if a
5/// threshold of the participants provide their shares. A polynomial commitment
6/// scheme allows a committer to commit to a secret sharing polynomial so that
7/// a verifier can check the claimed evaluations of the committed polynomial.
8/// Both schemes of this package are core building blocks for more advanced
9/// secret sharing techniques.
10use byteorder::LittleEndian;
11use byteorder::WriteBytesExt;
12use digest::Digest;
13use serde::Deserialize;
14use serde::Serialize;
15use thiserror::Error;
16
17extern crate alloc;
18use alloc::vec;
19use core::fmt::{Debug, Display, Formatter};
20use std::collections::HashMap;
21
22use crate::encoding::BinaryMarshaler;
23
24use crate::encoding::MarshallingError;
25use crate::group::HashFactory;
26use crate::{cipher::Stream, Group, Point, Scalar};
27
28/// [`ScalarMap`] is an handy type alias for a map of [`Scalar`].
29type ScalarMap<GROUP> = HashMap<usize, <<GROUP as Group>::POINT as Point>::SCALAR>;
30
31/// [`PointMap`] is an handy type alias for a map of [`Point`].
32type PointMap<GROUP> = HashMap<usize, <GROUP as Group>::POINT>;
33
34/// [`PriShare`] represents a private share.
35#[derive(Copy, Clone, Eq, PartialEq, Default, Serialize, Deserialize)]
36pub struct PriShare<SCALAR> {
37    /// Index of the private share
38    pub i: usize,
39    /// Value of the private share
40    pub v: SCALAR,
41}
42
43impl<SCALAR: Scalar> Debug for PriShare<SCALAR> {
44    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
45        f.debug_struct("PriShare").field("i", &self.i).finish()
46    }
47}
48
49impl<SCALAR: Scalar> Display for PriShare<SCALAR> {
50    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
51        write!(f, "PriShare( index: {} )", self.i)
52    }
53}
54
55impl<SCALAR: Scalar> PriShare<SCALAR> {
56    /// [`hash()`] returns the hash representation of this [`PriShare`]
57    pub fn hash<HASHFACTORY: HashFactory>(&self, s: HASHFACTORY) -> Result<Vec<u8>, PolyError> {
58        let mut h = s.hash();
59        self.v.marshal_to(&mut h)?;
60        h.write_u32::<LittleEndian>(self.i as u32)?;
61        Ok(h.finalize().to_vec())
62    }
63}
64
65/// [`PriPoly`] represents a secret sharing polynomial.
66#[derive(Clone, Default, Serialize, Deserialize, Eq, PartialEq)]
67pub struct PriPoly<GROUP: Group> {
68    /// Cryptographic [`Group`]
69    pub g: GROUP,
70    /// Coefficients of the polynomial
71    pub(crate) coeffs: Vec<<GROUP::POINT as Point>::SCALAR>,
72}
73
74impl<GROUP: Group> Debug for PriPoly<GROUP> {
75    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
76        f.debug_struct("PriPoly").field("g", &self.g).finish()
77    }
78}
79
80impl<GROUP: Group> Display for PriPoly<GROUP> {
81    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
82        write!(f, "PriPoly( group: {} )", self.g)
83    }
84}
85
86/// [`new_pri_poly()`] creates a new secret sharing polynomial using the provided
87/// cryptographic [`Group`], the secret sharing `threshold t`, and the `secret` to be
88/// shared `s`. If s is `None`, a new `s` is chosen using the provided randomness
89/// stream `rand`.
90pub fn new_pri_poly<GROUP: Group, STREAM>(
91    group: GROUP,
92    t: usize,
93    s: Option<<GROUP::POINT as Point>::SCALAR>,
94    mut rand: STREAM,
95) -> PriPoly<GROUP>
96where
97    STREAM: Stream,
98{
99    let mut coeffs: Vec<<GROUP::POINT as Point>::SCALAR> = vec![];
100    coeffs.push(match s {
101        Some(v) => v,
102        None => group.scalar().pick(&mut rand),
103    });
104    for _ in 1..t {
105        coeffs.push(group.scalar().pick(&mut rand));
106    }
107    PriPoly { g: group, coeffs }
108}
109
110/// [`coefficients_to_pri_poly()`] returns a [`PriPoly`] based on the given coefficients
111pub fn coefficients_to_pri_poly<GROUP: Group>(
112    g: &GROUP,
113    coeffs: &[<GROUP::POINT as Point>::SCALAR],
114) -> PriPoly<GROUP> {
115    PriPoly {
116        g: g.clone(),
117        coeffs: coeffs.to_vec(),
118    }
119}
120
121impl<GROUP: Group> PriPoly<GROUP> {
122    /// [`threshold()`] returns the secret sharing threshold.
123    pub fn threshold(&self) -> usize {
124        self.coeffs.len()
125    }
126
127    /// [`secret()`] returns the shared secret `p(0)`, i.e., the constant term of the polynomial.
128    pub fn secret(&self) -> <GROUP::POINT as Point>::SCALAR {
129        self.coeffs[0].clone()
130    }
131
132    /// [`eval()`] computes the private share `v = p(i)`.
133    pub fn eval(&self, i: usize) -> PriShare<<GROUP::POINT as Point>::SCALAR> {
134        let xi = self.g.scalar().set_int64(1 + i as i64);
135        let mut v = self.g.scalar().zero();
136        for j in (0..self.threshold()).rev() {
137            v = v * xi.clone();
138            v = v + self.coeffs[j].clone();
139        }
140        PriShare { i, v }
141    }
142
143    /// [`shares()`] creates a list of n private shares `p(1),...,p(n)`.
144    pub fn shares(&self, n: usize) -> Vec<Option<PriShare<<GROUP::POINT as Point>::SCALAR>>> {
145        let mut shares = Vec::with_capacity(n);
146        for i in 0..n {
147            shares.push(Some(self.eval(i)));
148        }
149        shares
150    }
151
152    /// [`add()`] computes the component-wise sum of the polynomials `p` and `q` and returns it
153    /// as a new polynomial.
154    pub fn add(&self, q: &PriPoly<GROUP>) -> Result<PriPoly<GROUP>, PolyError> {
155        if self.g.to_string() != q.g.to_string() {
156            return Err(PolyError::NoGroupsMatch);
157        }
158        if self.threshold() != q.threshold() {
159            return Err(PolyError::WrongCoefficientsNumber);
160        }
161        let mut coeffs = Vec::with_capacity(self.threshold());
162        //coeffs := make([]kyber.Scalar, p.Threshold())
163        for i in 0..self.threshold() {
164            coeffs.push(self.coeffs[i].clone() + q.coeffs[i].clone());
165        }
166        Ok(PriPoly {
167            g: self.g.clone(),
168            coeffs,
169        })
170    }
171
172    /// [`equal()`] checks equality of two secret sharing polynomials `p` and `q`. If `p` and `q` are trivially
173    /// unequal (e.g., due to mismatching cryptographic groups or polynomial size), this routine
174    /// returns in variable time. Otherwise it runs in constant time regardless of whether it
175    /// eventually returns `true` or `false`.
176    pub fn equal(&self, q: &PriPoly<GROUP>) -> Result<bool, PolyError> {
177        if self.g.to_string() != q.g.to_string() {
178            return Ok(false);
179        }
180        if self.coeffs.len() != q.coeffs.len() {
181            return Ok(false);
182        }
183        let mut b = true;
184        for i in 0..self.threshold() {
185            let pb = self.coeffs[i].marshal_binary()?;
186            let qb = q.coeffs[i].marshal_binary()?;
187            b &= pb.eq(&qb);
188            //b &= subtle.ConstantTimeCompare(pb, qb)
189        }
190        Ok(b)
191    }
192
193    /// [`commit()`] creates a public commitment polynomial for the given base point `b` or
194    /// the standard base if `b == nil`.
195    pub fn commit(&self, b: Option<&GROUP::POINT>) -> PubPoly<GROUP> {
196        let mut commits = vec![];
197        for i in 0..self.threshold() {
198            commits.push(self.g.point().mul(&self.coeffs[i], b));
199        }
200
201        PubPoly {
202            g: self.g.clone(),
203            b: b.cloned(),
204            commits,
205        }
206    }
207
208    /// [`mul()`] multiples `p` and `q` together. The result is a polynomial of the sum of
209    /// the two degrees of `p` and `q`. NOTE: it does not check for empty coefficients
210    /// after the multiplication, so the degree of the polynomial is "always" as
211    /// described above. This is only for use in secret sharing schemes. It is not
212    /// a general polynomial multiplication routine.
213    pub fn mul(&self, q: &Self) -> Self {
214        let d1 = self.coeffs.len() - 1;
215        let d2 = q.coeffs.len() - 1;
216        let new_degree = d1 + d2;
217        let mut coeffs = Vec::with_capacity(new_degree + 1);
218        for _ in 0..new_degree + 1 {
219            coeffs.push(self.g.scalar().zero());
220        }
221        for (i, cp) in self.coeffs.iter().enumerate() {
222            for (j, cq) in q.coeffs.iter().enumerate() {
223                let mut tmp = cp.clone();
224                tmp = tmp * cq.clone();
225                coeffs[i + j] = coeffs[i + j].clone() + tmp;
226            }
227        }
228        PriPoly {
229            g: self.g.clone(),
230            coeffs,
231        }
232    }
233
234    /// [`Coefficients()`] return the list of coefficients representing `p`. This
235    /// information is generally `PRIVATE` and should not be revealed to a third party
236    /// lightly.
237    pub fn coefficients(&self) -> Vec<<GROUP::POINT as Point>::SCALAR> {
238        self.coeffs.clone()
239    }
240}
241
242/// [`recover_secret()`] reconstructs the shared secret `p(0)` from a list of private
243/// shares using Lagrange interpolation.
244pub fn recover_secret<GROUP: Group>(
245    g: GROUP,
246    shares: &[Option<PriShare<<GROUP::POINT as Point>::SCALAR>>],
247    t: usize,
248    n: usize,
249) -> Result<<GROUP::POINT as Point>::SCALAR, PolyError> {
250    let (x, y) = xy_scalar(&g, shares, t, n);
251    if x.len() < t {
252        return Err(PolyError::NotEnoughSharesForSecret);
253    }
254
255    let mut acc = g.scalar().zero();
256    let mut num = g.scalar();
257    let mut den = g.scalar();
258    let mut tmp = g.scalar();
259
260    for (i, xi) in x.iter() {
261        let yi = &y[i];
262        num = num.set(yi);
263        den = den.one();
264        for (j, xj) in x.iter() {
265            if i == j {
266                continue;
267            }
268            num = num * xj.clone();
269            tmp = tmp.sub(xj, xi);
270            den = den * tmp.clone();
271        }
272        let num_clone = num.clone();
273        num = num.div(&num_clone, &den);
274        acc = acc + num.clone();
275    }
276
277    Ok(acc)
278}
279
280/// [`xy_scalar()`] returns the list of `(x_i, y_i)` pairs indexed. The first map returned
281/// is the list of `x_i` and the second map is the list of `y_i`, both indexed in
282/// their respective map at index `i`.
283fn xy_scalar<GROUP: Group>(
284    g: &GROUP,
285    shares: &[Option<PriShare<<GROUP::POINT as Point>::SCALAR>>],
286    t: usize,
287    n: usize,
288) -> (ScalarMap<GROUP>, ScalarMap<GROUP>) {
289    // we are sorting first the shares since the shares may be unrelated for
290    // some applications. In this case, all participants needs to interpolate on
291    // the exact same order shares.
292    let mut sorted = Vec::with_capacity(n);
293    shares.iter().for_each(|share| {
294        if let Some(share) = share {
295            sorted.push(share);
296        }
297    });
298    sorted.sort_by(|i, j| i.i.cmp(&j.i));
299
300    let mut x = HashMap::new();
301    let mut y = HashMap::new();
302    for s in sorted {
303        let idx = s.i;
304        x.insert(idx, g.scalar().set_int64((idx + 1) as i64));
305        y.insert(idx, s.v.clone());
306        if x.len() == t {
307            break;
308        }
309    }
310    (x, y)
311}
312
313fn minus_const<GROUP: Group>(g: &GROUP, c: <GROUP::POINT as Point>::SCALAR) -> PriPoly<GROUP> {
314    let neg = g.scalar().neg(&c);
315    PriPoly {
316        g: g.clone(),
317        coeffs: vec![neg, g.scalar().one()],
318    }
319}
320
321/// [`recover_pri_poly()`] takes a `list of shares` and the parameters `t` and `n` to
322/// reconstruct the secret polynomial completely, i.e., all private
323/// coefficients.  It is up to the caller to make sure that there are enough
324/// shares to correctly re-construct the polynomial. There must be at least t
325/// shares.
326pub fn recover_pri_poly<GROUP: Group>(
327    g: &GROUP,
328    shares: &[Option<PriShare<<GROUP::POINT as Point>::SCALAR>>],
329    t: usize,
330    n: usize,
331) -> Result<PriPoly<GROUP>, PolyError> {
332    let (x, y) = xy_scalar(g, shares, t, n);
333    if x.len() != t {
334        return Err(PolyError::NotEnoughSharesForPublic);
335    }
336
337    let mut acc_poly = PriPoly {
338        g: g.clone(),
339        coeffs: vec![],
340    };
341    //den := g.Scalar()
342    // Notations follow the Wikipedia article on Lagrange interpolation
343    // https://en.wikipedia.org/wiki/Lagrange_polynomial
344    for j in x.keys() {
345        let mut basis = lagrange_basis(g, *j, x.clone());
346        for (i, _) in basis.coeffs.clone().iter().enumerate() {
347            basis.coeffs[i] = basis.coeffs[i].clone() * y[j].clone();
348        }
349
350        if acc_poly.coeffs.is_empty() {
351            acc_poly = basis;
352            continue;
353        }
354
355        acc_poly = acc_poly.add(&basis)?;
356    }
357
358    Ok(acc_poly)
359}
360
361impl<GROUP: Group> PriPoly<GROUP> {
362    pub fn string(&self) -> String {
363        let mut strs = Vec::with_capacity(self.coeffs.len());
364        for c in self.coeffs.clone() {
365            strs.push(format!("{c}"));
366        }
367        "[ ".to_string() + &strs.join(", ") + " ]"
368    }
369}
370
371/// [`PubShare`] represents a public share.
372#[derive(Clone, Copy, Default, Debug, Serialize, Deserialize, Eq, PartialEq)]
373pub struct PubShare<POINT: Point> {
374    /// Index of the public share
375    pub i: usize,
376    /// Value of the public share
377    #[serde(deserialize_with = "POINT::deserialize")]
378    pub v: POINT,
379}
380
381impl<POINT: Point> Display for PubShare<POINT> {
382    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
383        write!(f, "PubShare( index: {}, value: {} )", self.i, self.v)
384    }
385}
386
387impl<POINT: Point> PubShare<POINT> {
388    /// [`hash`] returns the hash representation of this [`PubShare`]
389    pub fn hash<HASHFACTORY: HashFactory>(&self, s: HASHFACTORY) -> Result<Vec<u8>, PolyError> {
390        let mut h = s.hash();
391        self.v.marshal_to(&mut h)?;
392        h.write_u32::<LittleEndian>(self.i as u32)?;
393        Ok(h.finalize().to_vec())
394    }
395}
396
397/// [`PubPoly`] represents a public commitment polynomial to a secret sharing polynomial.
398#[derive(Clone, Eq, PartialEq, Debug, Default, Serialize, Deserialize)]
399pub struct PubPoly<GROUP: Group> {
400    /// Cryptographic [`Group`]
401    g: GROUP,
402    /// Base point, `None` for standard base
403    b: Option<GROUP::POINT>,
404    /// Commitments to coefficients of the secret sharing polynomial
405    commits: Vec<GROUP::POINT>,
406}
407
408impl<GROUP: Group> Display for PubPoly<GROUP> {
409    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
410        write!(f, "PubPoly( group: {},", self.g,)?;
411
412        write!(f, " base_point:")?;
413        match self.b {
414            Some(ref base) => write!(f, " Some({}),", base),
415            None => write!(f, " None,"),
416        }?;
417
418        write!(f, " commits: [")?;
419        let commits = self
420            .commits
421            .iter()
422            .map(|c| c.to_string())
423            .collect::<Vec<_>>()
424            .join(", ");
425        write!(f, "{}] )", commits)
426    }
427}
428
429impl<GROUP: Group> PubPoly<GROUP> {
430    /// [`new()`] creates a new public commitment polynomial.
431    pub fn new(g: &GROUP, b: Option<GROUP::POINT>, commits: &[GROUP::POINT]) -> PubPoly<GROUP> {
432        PubPoly {
433            g: g.clone(),
434            b,
435            commits: commits.to_vec(),
436        }
437    }
438}
439
440impl<GROUP: Group> PubPoly<GROUP> {
441    /// [`info()`] returns the `base point` and the `commitments` to the polynomial coefficients.
442    pub fn info(&self) -> (Option<GROUP::POINT>, Vec<GROUP::POINT>) {
443        (self.b.clone(), self.commits.clone())
444    }
445
446    /// [`threshold()`] returns the secret sharing threshold.
447    pub fn threshold(&self) -> usize {
448        self.commits.len()
449    }
450
451    /// [`commit()`] returns the secret commitment `p(0)`, i.e., the constant term of the polynomial.
452    pub fn commit(&self) -> GROUP::POINT {
453        self.commits[0].clone()
454    }
455
456    /// [`eval()`] computes the public share `v = p(i)`.
457    pub fn eval(&self, i: usize) -> PubShare<GROUP::POINT> {
458        // x-coordinate of this share
459        let xi = self.g.scalar().set_int64(1 + (i as i64));
460        let mut v = self.g.point();
461        v = v.null();
462        for j in (0..=(self.threshold() - 1)).rev() {
463            let v_clone = v.clone();
464            v = v.mul(&xi, Some(&v_clone));
465            let v_clone = v.clone();
466            v = v.add(&v_clone, &self.commits[j]);
467        }
468        PubShare { i, v }
469    }
470
471    /// [`shares()`] creates a list of n public commitment shares `p(1),...,p(n)`.
472    pub fn shares(&self, n: usize) -> Vec<Option<PubShare<GROUP::POINT>>> {
473        let mut shares = Vec::with_capacity(n);
474        for i in 0..n {
475            shares.push(Some(self.eval(i)));
476        }
477        shares
478    }
479
480    /// [`add()`] computes the component-wise sum of the polynomials `p` and `q` and returns it
481    /// as a new polynomial. NOTE: If the base points `p.b` and `q.b` are different then the
482    /// base point of the resulting [`PubPoly`] cannot be computed without knowing the
483    /// discrete logarithm between `p.b` and `q.b`. In this particular case, we are using
484    /// `p.b` as a default value which of course does not correspond to the correct
485    /// base point and thus should not be used in further computations.
486    pub fn add(&self, q: &Self) -> Result<Self, PolyError> {
487        if self.g.to_string() != q.g.to_string() {
488            return Err(PolyError::NoGroupsMatch);
489        }
490
491        if self.threshold() != q.threshold() {
492            return Err(PolyError::WrongCoefficientsNumber);
493        }
494
495        let mut commits = vec![];
496        for i in 0..self.threshold() {
497            commits.push(self.g.point().add(&self.commits[i], &q.commits[i]));
498        }
499
500        Ok(PubPoly {
501            g: self.g.clone(),
502            b: self.b.clone(),
503            commits,
504        })
505    }
506
507    /// [`equal()`] checks equality of two public commitment polynomials `p` and `q`. If `p` and
508    /// `q` are trivially unequal (e.g., due to mismatching cryptographic groups),
509    /// this routine returns in variable time. Otherwise it runs in constant time
510    /// regardless of whether it eventually returns `true` or `false`.
511    pub fn equal(&self, q: &PubPoly<GROUP>) -> Result<bool, PolyError> {
512        if self.g.to_string() != q.g.to_string() {
513            return Ok(false);
514        }
515        let mut b = true;
516        for i in 0..self.threshold() {
517            let pb = self.commits[i].marshal_binary()?;
518            let qb = q.commits[i].marshal_binary()?;
519            b &= pb.eq(&qb);
520            //b &= subtle.ConstantTimeCompare(pb, qb)
521        }
522        Ok(b)
523    }
524
525    /// [`check()`] a private share against a public commitment polynomial.
526    pub fn check(&self, s: &PriShare<<GROUP::POINT as Point>::SCALAR>) -> bool {
527        let pv = self.eval(s.i);
528        let ps = self.g.point().mul(&s.v, self.b.as_ref());
529        pv.v.eq(&ps)
530    }
531}
532
533/// [`xy_commits()`] is the public version of [`x_scalars()`].
534pub fn xy_commit<GROUP: Group>(
535    g: &GROUP,
536    shares: &[Option<PubShare<GROUP::POINT>>],
537    t: usize,
538    n: usize,
539) -> (ScalarMap<GROUP>, PointMap<GROUP>) {
540    // we are sorting first the shares since the shares may be unrelated for
541    // some applications. In this case, all participants needs to interpolate on
542    // the exact same order shares.
543    let mut sorted = Vec::with_capacity(n);
544    shares.iter().for_each(|share| {
545        if let Some(share) = share {
546            sorted.push(share);
547        }
548    });
549    sorted.sort_by(|i, j| i.i.cmp(&j.i));
550
551    let mut x = HashMap::new();
552    let mut y = HashMap::new();
553    for s in sorted {
554        let idx = s.i;
555        x.insert(idx, g.scalar().set_int64((idx + 1) as i64));
556        y.insert(idx, s.v.clone());
557        if x.len() == t {
558            break;
559        }
560    }
561    (x, y)
562}
563
564/// [`recover_commit()`] reconstructs the secret commitment `p(0)` from a list of public
565/// shares using Lagrange interpolation.
566pub fn recover_commit<GROUP: Group>(
567    g: GROUP,
568    shares: &[Option<PubShare<GROUP::POINT>>],
569    t: usize,
570    n: usize,
571) -> Result<GROUP::POINT, PolyError> {
572    let (x, y) = xy_commit(&g, shares, t, n);
573
574    if x.len() < t {
575        return Err(PolyError::NotEnoughtGoodPublics);
576    }
577
578    let mut num = g.scalar();
579    let mut den = g.scalar();
580    let mut tmp = g.scalar();
581    let mut acc = g.point().null();
582    let mut tmp_p = g.point();
583
584    for (i, xi) in x.iter() {
585        num = num.one();
586        den = den.one();
587        for (j, xj) in x.iter() {
588            if i == j {
589                continue;
590            }
591            num = num * xj.clone();
592            tmp = tmp.sub(xj, xi);
593            den = den * tmp.clone();
594        }
595        let num_clone = num.clone();
596        num = num.div(&num_clone, &den);
597        tmp_p = tmp_p.mul(&num, Some(&y[i]));
598        let acc_clone = acc.clone();
599        acc = acc.add(&acc_clone, &tmp_p);
600    }
601
602    Ok(acc)
603}
604
605/// [`recover_pub_poly()`] reconstructs the full public polynomial from a set of public
606/// shares using Lagrange interpolation.
607pub fn recover_pub_poly<GROUP: Group>(
608    g: GROUP,
609    shares: &[Option<PubShare<GROUP::POINT>>],
610    t: usize,
611    n: usize,
612) -> Result<PubPoly<GROUP>, PolyError> {
613    let (x, y) = xy_commit(&g, shares, t, n);
614    if x.len() < t {
615        return Err(PolyError::NotEnoughtGoodPublics);
616    }
617
618    let mut acc_poly = PubPoly::new(&g, None, &[]);
619
620    for (j, _) in x.iter().enumerate() {
621        let basis = lagrange_basis(&g, j, x.clone());
622
623        // compute the L_j * y_j polynomial in point space
624        let tmp = basis.commit(Some(&y[&j]));
625        if acc_poly.commits.is_empty() {
626            acc_poly = tmp;
627            continue;
628        }
629
630        // add all L_j * y_j together
631        acc_poly = acc_poly.add(&tmp)?;
632    }
633
634    Ok(acc_poly)
635}
636
637/// [`lagrange_basis()`] returns a [`PriPoly`] containing the Lagrange coefficients for the
638/// `i`-th position. xs is a mapping between the indices and the values that the
639/// interpolation is using, computed with [`xy_scalar()`].
640fn lagrange_basis<GROUP: Group>(
641    g: &GROUP,
642    i: usize,
643    xs: HashMap<usize, <GROUP::POINT as Point>::SCALAR>,
644) -> PriPoly<GROUP> {
645    let mut basis = PriPoly {
646        g: g.clone(),
647        coeffs: vec![g.clone().scalar().one()],
648    };
649    // compute lagrange basis l_j
650    let mut den = g.scalar().one();
651    let mut acc = g.scalar().one();
652    for (m, xm) in xs.iter() {
653        if &i == m {
654            continue;
655        }
656        basis = basis.mul(&minus_const(g, xm.clone()));
657        den = den.sub(&xs[&i], xm); // den = xi - xm
658        let den_clone = den.clone();
659        den = den.inv(&den_clone); // den = 1 / den
660        acc = acc * den.clone(); // acc = acc * den
661    }
662
663    // multiply all coefficients by the denominator
664    for (i, _) in basis.coeffs.clone().iter().enumerate() {
665        basis.coeffs[i] = basis.coeffs[i].clone() * acc.clone();
666    }
667    basis
668}
669
670#[derive(Error, Debug)]
671pub enum PolyError {
672    #[error("marshalling error")]
673    MarshallingError(#[from] MarshallingError),
674    #[error("io error")]
675    IoError(#[from] std::io::Error),
676    #[error("not enough good public shares to reconstruct secret commitment")]
677    NotEnoughtGoodPublics,
678    #[error("non-matching groups")]
679    NoGroupsMatch,
680    #[error("different number of coefficients")]
681    WrongCoefficientsNumber,
682    #[error("not enough shares to recover private polynomial")]
683    NotEnoughSharesForPublic,
684    #[error("not enough shares to recover secret")]
685    NotEnoughSharesForSecret,
686}
kyber_rs/share/poly.rs

kyber_rs/share/
poly.rs
