Function RecoverPriPoly

share/poly.go:229–274

RecoverPriPoly takes a list of shares and the parameters t and n to reconstruct the secret polynomial completely, i.e., all private coefficients. It is up to the caller to make sure that there are enough shares to correctly re-construct the polynomial. There must be at least t shares.

(g kyber.Group, shares []*PriShare, t, n int)

// shares to correctly re-construct the polynomial. There must be at least t
// shares.
func RecoverPriPoly(g kyber.Group, shares []*PriShare, t, n int) (*PriPoly, error) {
	x := xScalar(g, shares, t, n)
	if len(x) != t {
		return nil, errors.New("share: not enough shares to recover private polynomial")
	}

	var accPoly *PriPoly
	var err error
	den := g.Scalar()
	// Notations follow the Wikipedia article on Lagrange interpolation
	// https://en.wikipedia.org/wiki/Lagrange_polynomial
	for j, xj := range x {
		var basis = &PriPoly{
			g:      g,
			coeffs: []kyber.Scalar{g.Scalar().One()},
		}
		var acc = g.Scalar().Set(shares[j].V)
		// compute lagrange basis l_j
		for m, xm := range x {
			if j == m {
				continue
			}
			basis = basis.Mul(xMinusConst(g, xm)) // basis = basis * (x - xm)

			den.Sub(xj, xm)   // den = xj - xm
			den.Inv(den)      // den = 1 / den
			acc.Mul(acc, den) // acc = acc * den
		}

		for i := range basis.coeffs {
			basis.coeffs[i] = basis.coeffs[i].Mul(basis.coeffs[i], acc)
		}

		if accPoly == nil {
			accPoly = basis
			continue
		}

		// add all L_j * y_j together
		accPoly, err = accPoly.Add(basis)
		if err != nil {
			return nil, err
		}
	}
	return accPoly, nil
}

func (p *PriPoly) String() string {
	var strs = make([]string, len(p.coeffs))