corona/primitives/shamir.go

package primitives

import (
	"crypto/rand"
	"io"
	"math/big"

	"github.com/luxfi/corona/utils"

	"github.com/luxfi/lattice/v7/ring"
	"github.com/luxfi/lattice/v7/utils/structs"
	"github.com/luxfi/mlwe/share"

	"github.com/zeebo/blake3"
)

// ShamirSecretSharing shares each coefficient of a vector of ring.Poly across k parties using (t, k)-threshold Shamir secret sharing.
func ShamirSecretSharingGeneral(r *ring.Ring, s []ring.Poly, t, k int) map[int]structs.Vector[ring.Poly] {

	degree := r.N() // Number of coefficients in each ring.Poly
	q := r.Modulus()

	// Initialize shares for each party
	shares := make(map[int]structs.Vector[ring.Poly], k)

	for i := 0; i < k; i++ {
		shares[i] = make([]ring.Poly, len(s))
		for j := range shares[i] {
			shares[i][j] = r.NewPoly()
		}
	}

	for polyIndex, poly := range s {
		coeffs := make([]*big.Int, degree)
		r.PolyToBigint(poly, 1, coeffs)

		for coeffIndex, secret := range coeffs {
			polyCoeffs := make([]*big.Int, t)
			polyCoeffs[0] = secret
			for i := 1; i < t; i++ {
				randomCoeff, _ := rand.Int(rand.Reader, q)
				polyCoeffs[i] = randomCoeff
			}

			for i := 1; i <= k; i++ {
				x := big.NewInt(int64(i))
				shareValue := big.NewInt(0)
				xPow := big.NewInt(1)

				for _, coeff := range polyCoeffs {
					term := new(big.Int).Mul(coeff, xPow)
					shareValue.Add(shareValue, term)
					shareValue.Mod(shareValue, q)
					xPow.Mul(xPow, x)
				}

				if shares[i-1][polyIndex].Coeffs[0] == nil {
					shares[i-1][polyIndex].Coeffs[0] = make([]uint64, degree)
				}

				shares[i-1][polyIndex].Coeffs[0][coeffIndex] = shareValue.Uint64()
			}
		}
	}

	return shares
}

// ShamirSecretSharingGeneralWithSeed is a deterministic variant of
// ShamirSecretSharingGeneral. Instead of drawing the (t-1) random
// polynomial coefficients per coordinate from crypto/rand, it draws them
// from a BLAKE3(seed) XOF stream using qByteLen big-endian bytes per draw,
// reduced mod q via big.Int.Mod. The byte-stream contract matches the
// existing corona_oracle_v2 deterministicShamir (see
// cmd/corona_oracle_v2/main.go) and is the canonical KAT input for the
// C++ port at luxcpp/crypto/corona/cpp/shamir_general.{hpp,cpp}.
//
// Iteration order MUST match ShamirSecretSharingGeneral exactly:
//
//	for polyIndex, poly := range s {
//	    for coeffIndex, secret := range poly.coeffs {
//	        draw a_1..a_{t-1}
//	        for partyIdx in 1..k { share_partyIdx[polyIndex][coeffIndex] = P(partyIdx) }
//	    }
//	}
func ShamirSecretSharingGeneralWithSeed(r *ring.Ring, s []ring.Poly, t, k int, seed []byte) map[int]structs.Vector[ring.Poly] {
	degree := r.N()
	q := r.Modulus()
	qByteLen := len(q.Bytes())

	rng := blake3.New()
	_, _ = rng.Write(seed)
	stream := rng.Digest()
	pullBig := func() *big.Int {
		buf := make([]byte, qByteLen)
		if _, err := io.ReadFull(stream, buf); err != nil {
			panic(err)
		}
		v := new(big.Int).SetBytes(buf)
		return v.Mod(v, q)
	}

	shares := make(map[int]structs.Vector[ring.Poly], k)
	for i := 0; i < k; i++ {
		shares[i] = make([]ring.Poly, len(s))
		for j := range shares[i] {
			shares[i][j] = r.NewPoly()
		}
	}

	for polyIndex, poly := range s {
		coeffs := make([]*big.Int, degree)
		r.PolyToBigint(poly, 1, coeffs)

		for coeffIndex, secret := range coeffs {
			polyCoeffs := make([]*big.Int, t)
			polyCoeffs[0] = secret
			for i := 1; i < t; i++ {
				polyCoeffs[i] = pullBig()
			}

			for i := 1; i <= k; i++ {
				x := big.NewInt(int64(i))
				shareValue := big.NewInt(0)
				xPow := big.NewInt(1)

				for _, coeff := range polyCoeffs {
					term := new(big.Int).Mul(coeff, xPow)
					shareValue.Add(shareValue, term)
					shareValue.Mod(shareValue, q)
					xPow.Mul(xPow, x)
				}

				if shares[i-1][polyIndex].Coeffs[0] == nil {
					shares[i-1][polyIndex].Coeffs[0] = make([]uint64, degree)
				}

				shares[i-1][polyIndex].Coeffs[0][coeffIndex] = shareValue.Uint64()
			}
		}
	}

	return shares
}

// ShamirSecretSharing shares each coefficient of a vector of ring.Poly across k parties using (t, k)-threshold Shamir secret sharing. This optimized implementation only works when t = k.
func ShamirSecretSharing(r *ring.Ring, s []ring.Poly, k int, lambdas []ring.Poly) map[int]structs.Vector[ring.Poly] {

	degree := r.N() // Number of coefficients in each ring.Poly
	q := r.Modulus()

	// Initialize shares for each party
	shares := make(map[int]structs.Vector[ring.Poly], k)

	for i := 0; i < k; i++ {
		shares[i] = make([]ring.Poly, len(s))
		for j := range shares[i] {
			shares[i][j] = r.NewPoly()
		}
	}

	for polyIndex, poly := range s {
		coeffs := make([]*big.Int, degree)
		r.PolyToBigint(poly, 1, coeffs)

		for coeffIndex, secret := range coeffs {
			randomShares := make([]*big.Int, k-1)
			for i := 0; i < k-1; i++ {
				randomShares[i] = utils.GetRandomInt(q)
			}

			sum := big.NewInt(0)
			for i := 0; i < k-1; i++ {
				lambdaCoeff := new(big.Int).SetUint64(lambdas[i].Coeffs[0][0])
				shareTerm := new(big.Int).Mul(randomShares[i], lambdaCoeff)
				sum.Add(sum, shareTerm)
				sum.Mod(sum, q)
			}

			lastShare := new(big.Int).Sub(secret, sum)
			lastShareLambdaCoeff := new(big.Int).SetUint64(lambdas[k-1].Coeffs[0][0])
			lastShare.Mul(lastShare, new(big.Int).ModInverse(lastShareLambdaCoeff, q))
			lastShare.Mod(lastShare, q)

			for i := 0; i < k-1; i++ {
				if shares[i][polyIndex].Coeffs[0] == nil {
					shares[i][polyIndex].Coeffs[0] = make([]uint64, degree)
				}
				shares[i][polyIndex].Coeffs[0][coeffIndex] = randomShares[i].Uint64()
			}

			if shares[k-1][polyIndex].Coeffs[0] == nil {
				shares[k-1][polyIndex].Coeffs[0] = make([]uint64, degree)
			}
			shares[k-1][polyIndex].Coeffs[0][coeffIndex] = lastShare.Uint64()
		}
	}

	return shares
}

// ComputeLagrangeCoefficients computes the Lagrange reconstruction
// coefficients lambda_i = prod_{j!=i} (-x_j)/(x_i - x_j) over GF(modulus)
// for the party points x_i = T[i]+1, i.e. the basis that interpolates a
// shared secret back to x=0.
//
// The interpolation and field arithmetic are the shared Module-LWE
// primitive github.com/luxfi/mlwe/share.Lagrange (evaluated at point 0);
// this function is only the adapter that lifts each scalar coefficient
// into the Corona R_q wire (a constant-term ring.Poly). modulus is
// Corona's prime q in every production call. Invalid input (non-prime
// modulus, or x_i that are zero/duplicated) is a caller-side invariant
// violation and panics — matching the prior nil-inverse crash, never a
// silent wrong answer on a signing path.
func ComputeLagrangeCoefficients(r *ring.Ring, T []int, modulus *big.Int) []ring.Poly {
	field, err := share.NewPrimeField(modulus.Uint64())
	if err != nil {
		panic("corona/primitives: ComputeLagrangeCoefficients needs a prime field modulus: " + err.Error())
	}
	xs := make([]uint64, len(T))
	for i, ti := range T {
		xs[i] = uint64(ti + 1)
	}
	lambda, err := share.Lagrange(xs, 0, field)
	if err != nil {
		panic("corona/primitives: ComputeLagrangeCoefficients invalid evaluation points: " + err.Error())
	}
	lagrangeCoefficients := make([]ring.Poly, len(T))
	for i := range T {
		coeff := new(big.Int).SetUint64(lambda[i])
		lagrangePoly := r.NewPoly()
		r.SetCoefficientsBigint([]*big.Int{coeff}, lagrangePoly)
		lagrangeCoefficients[i] = lagrangePoly
	}
	return lagrangeCoefficients
}