shard.go raw

   1  package gnarlring
   2  
   3  import (
   4  	"crypto/rand"
   5  	"io"
   6  )
   7  
   8  // LWEKeyAgg aggregates multiple LWE public keys sharing the same A element
   9  // into a single group public key. B_agg = Σ B_i.
  10  // All keys must share identical A elements (generated from a common reference).
  11  func LWEKeyAgg(pks []*LWEPublicKey) *LWEPublicKey {
  12  	if len(pks) == 0 {
  13  		return nil
  14  	}
  15  	if len(pks) == 1 {
  16  		return &LWEPublicKey{A: pks[0].A.Clone(), B: pks[0].B.Clone()}
  17  	}
  18  
  19  	bAgg := pks[0].B.Clone()
  20  	for i := 1; i < len(pks); i++ {
  21  		bAgg = Add(bAgg, pks[i].B)
  22  	}
  23  	return &LWEPublicKey{A: pks[0].A.Clone(), B: bAgg}
  24  }
  25  
  26  // GenerateSharedA generates a common A element from a public seed for key
  27  // aggregation. All participants use the same seed to derive identical A.
  28  func GenerateSharedA(seed []byte) *Poly27 {
  29  	input := append([]byte("gnarl-lwe-shared-a-v1"), seed...)
  30  	return hashBytesToPoly(input)
  31  }
  32  
  33  // LWEKeyGenWithA generates a key pair using a pre-specified A element.
  34  // Used for multi-party key aggregation.
  35  func LWEKeyGenWithA(a *Poly27) (*LWEPublicKey, *LWESecretKey) {
  36  	return LWEKeyGenWithAFrom(a, rand.Reader)
  37  }
  38  
  39  // LWEKeyGenWithAFrom generates with a given RNG.
  40  func LWEKeyGenWithAFrom(a *Poly27, rng io.Reader) (*LWEPublicKey, *LWESecretKey) {
  41  	if rng == nil {
  42  		rng = rand.Reader
  43  	}
  44  	s := ternaryPoly(rng)
  45  
  46  	gs := NewGaussSamplerFrom(DefaultSigma(), rng)
  47  	e := gs.SamplePoly()
  48  	for i := range e.Coeffs {
  49  		if e.Coeffs[i] > Q/2 {
  50  			e.Coeffs[i] = Q - 1
  51  		} else if e.Coeffs[i] != 0 {
  52  			e.Coeffs[i] = 1
  53  		}
  54  	}
  55  
  56  	as := Mul(a, s)
  57  	b := Add(as, e)
  58  
  59  	pk := &LWEPublicKey{A: a.Clone(), B: b}
  60  	sk := &LWESecretKey{S: s, PK: pk}
  61  	return pk, sk
  62  }
  63  
  64  // ShareSecret splits a master secret s into k additive shares.
  65  // Returns k shares where Σ shares[i] = s. The caller distributes each share
  66  // to a different participant.
  67  func ShareSecret(s *Poly27, k int) []*Poly27 {
  68  	shares := make([]*Poly27, k)
  69  	gs := NewGaussSampler(DefaultSigma())
  70  
  71  	// Generate k-1 random shares, final share = s - Σ random shares.
  72  	sum := NewPoly27()
  73  	for i := 0; i < k-1; i++ {
  74  		shares[i] = gs.SamplePoly()
  75  		sum = Add(sum, shares[i])
  76  	}
  77  	// Last share: s - sum (mod q).
  78  	shares[k-1] = Sub(s, sum)
  79  	return shares
  80  }
  81  
  82  // PartialDecryption computes one child's contribution to distributed
  83  // decryption: d_i = share_i * u. The coordinator sums all partials
  84  // to recover aggregate decryption.
  85  func PartialDecryption(share *Poly27, u *Poly27) *Poly27 {
  86  	return Mul(share, u)
  87  }
  88  
  89  // CombinePartials sums partial decryptions and recovers the plaintext bit.
  90  // d_agg = Σ d_i = s_agg * u. Then m = decode(v - d_agg).
  91  func CombinePartials(v *Poly27, partials []*Poly27) int {
  92  	if len(partials) == 0 {
  93  		return 0
  94  	}
  95  	dAgg := partials[0].Clone()
  96  	for i := 1; i < len(partials); i++ {
  97  		dAgg = Add(dAgg, partials[i])
  98  	}
  99  	noisy := Sub(v, dAgg)
 100  	return decodeBit(noisy)
 101  }
 102  
 103  // GroupDecryptData holds the per-child shares and the aggregate LWE key
 104  // for distributed decryption.
 105  type GroupDecryptData struct {
 106  	AggPK   *LWEPublicKey // aggregated B (common A)
 107  	Shares  []*Poly27     // one share per child
 108  }
 109  
 110  // EncryptGroup encrypts a bit under the aggregated group key. Only used
 111  // by the coordinator to test the distributed decryption path.
 112  func EncryptGroup(aggPK *LWEPublicKey, bit int) *LWECiphertext {
 113  	return LWEEncrypt(aggPK, bit)
 114  }
 115  
 116  // DistributedDecrypt performs k-of-n distributed decryption. The caller
 117  // provides partial decryptions from k children. Returns the plaintext bit.
 118  func DistributedDecrypt(ct *LWECiphertext, partials []*Poly27) int {
 119  	return CombinePartials(ct.V, partials)
 120  }
 121