1 // Key aggregation for multi-party lattice cryptography.
2 //
3 // For Ring-LWE keys sharing the same public element a:
4 //
5 // pk_i = (a, b_i = a*s_i + e_i)
6 //
7 // The aggregate public key is:
8 //
9 // pk_agg = (a, sum(b_i))
10 //
11 // This is a valid Ring-LWE public key for the aggregate secret s_agg = sum(s_i)
12 // and aggregate error e_agg = sum(e_i). The aggregate error remains short
13 // because the sum of k independent short vectors has infinity norm bounded
14 // by k * max(||e_i||_inf), which stays well within the decryption threshold
15 // for moderate k.
16 //
17 // Security: the aggregate key is indistinguishable from a fresh Ring-LWE
18 // sample. Breaking it requires solving Ring-LWE, which reduces to SVP
19 // on ideal lattices.
20 //
21 // For HE64 (q=10000769, eta=1, n=64): aggregate noise ~ k*eta*sqrt(n) ~ 80
22 // for k=10 participants, vs decryption threshold q/4 ~ 2.5M. Massive headroom.
23 //
24 // Distributed decryption: each party computes d_i = s_i * u, the partial
25 // decryptions are summed, and the plaintext is recovered from v - d_agg.
26 // No party reveals its individual secret key.
27 28 package ring
29 30 import (
31 "crypto/rand"
32 "errors"
33 34 "golang.org/x/crypto/sha3"
35 )
36 37 // AggregateHEKeys combines multiple Ring-LWE public keys into a single
38 // aggregate key. All input keys must share the same public element A
39 // (generated from a common reference string or trusted setup).
40 //
41 // Returns a KEMPublicKey whose B component is the sum of all individual
42 // B components. This aggregate key can be used with standard HEEncrypt
43 // for multi-party computation.
44 func AggregateHEKeys(pks []*KEMPublicKey) (*KEMPublicKey, error) {
45 if len(pks) == 0 {
46 return nil, errors.New("keyagg: no public keys")
47 }
48 if len(pks) == 1 {
49 return pks[0], nil
50 }
51 52 // Verify all keys share the same A and parameters.
53 ref := pks[0]
54 for i := 1; i < len(pks); i++ {
55 if !Equal(ref.A, pks[i].A) {
56 return nil, errors.New("keyagg: public keys do not share the same A element")
57 }
58 if ref.P.Ring.N != pks[i].P.Ring.N || ref.P.Ring.Q != pks[i].P.Ring.Q {
59 return nil, errors.New("keyagg: incompatible ring parameters")
60 }
61 }
62 63 // Aggregate: B_agg = sum(B_i).
64 bAgg := ref.B.Clone()
65 for i := 1; i < len(pks); i++ {
66 bAgg = Add(bAgg, pks[i].B)
67 }
68 69 return &KEMPublicKey{
70 A: ref.A.Clone(),
71 B: bAgg,
72 P: ref.P,
73 }, nil
74 }
75 76 // PartialDecrypt computes a partial decryption of an HE ciphertext.
77 // Each participant computes d_i = s_i * u using their individual secret key.
78 // The result is a polynomial that must be combined with other partial
79 // decryptions to recover the plaintext.
80 func PartialDecrypt(sk *KEMSecretKey, ct *HECiphertext) *Poly {
81 uNTT := ct.U.Clone()
82 NTT(uNTT)
83 su := MulPointwise(sk.S, uNTT)
84 INTT(su)
85 return su
86 }
87 88 // CombinePartialDecryptions combines partial decryptions from all
89 // participants and recovers the plaintext bit.
90 //
91 // Each partial decryption d_i = s_i * u. The combination computes:
92 //
93 // d_agg = sum(d_i) = s_agg * u
94 // m = decode(v - d_agg) = decode(noise + m_encoded)
95 //
96 // The noise term is the sum of all individual error terms, which remains
97 // short for moderate participant counts.
98 func CombinePartialDecryptions(ct *HECiphertext, partials []*Poly) int {
99 if len(partials) == 0 {
100 return 0
101 }
102 103 // Sum all partial decryptions.
104 dAgg := partials[0].Clone()
105 for i := 1; i < len(partials); i++ {
106 dAgg = Add(dAgg, partials[i])
107 }
108 109 // Recover plaintext: v - d_agg.
110 noisy := Sub(ct.V, dAgg)
111 112 // BGV decoding: result mod 2, using centered representation.
113 q := ct.params.Ring.Q
114 c := noisy.Coeffs[0]
115 if c > q/2 {
116 c = q - c
117 }
118 return int(c % 2)
119 }
120 121 // GenerateSharedA generates a common public element A for key aggregation.
122 // All participants must use the same A when generating their individual keys.
123 // The seed should be a publicly agreed-upon value (common reference string).
124 func GenerateSharedA(kp KEMParams, seed []byte) *Poly {
125 // Use SHAKE256 as an XOF seeded from the common reference string.
126 // All participants with the same seed produce the identical A.
127 h := sha3.NewShake256()
128 h.Write([]byte("hamadryad-shared-a-v1"))
129 h.Write(seed)
130 a := UniformPolyFrom(kp.Ring, h)
131 NTT(a)
132 return a
133 }
134 135 // HEKeyGenWithA generates an HE key pair using a pre-specified A element.
136 // This is used for multi-party key aggregation where all participants
137 // share the same A from GenerateSharedA.
138 func HEKeyGenWithA(kp KEMParams, a *Poly) (*KEMPublicKey, *KEMSecretKey) {
139 p := kp.Ring
140 141 // s <- ternary secret.
142 s := TernaryPoly(p)
143 NTT(s)
144 145 // e <- small noise, scaled by 2 for BGV.
146 e := CBDPoly(p, kp.Eta1)
147 e = ScalarMul(e, 2)
148 NTT(e)
149 150 // b = a*s + 2*e.
151 b := MulPointwise(a, s)
152 b = Add(b, e)
153 154 // z <- implicit rejection value.
155 z := make([]byte, kp.SharedKeyLen)
156 if _, err := rand.Read(z); err != nil {
157 panic("keyagg: randomness source failed: " + err.Error())
158 }
159 160 pk := &KEMPublicKey{A: a.Clone(), B: b, P: kp}
161 sk := &KEMSecretKey{S: s, PK: pk, Z: z}
162 return pk, sk
163 }
164