1 package ring
2
3 import (
4 "crypto/rand"
5 "io"
6
7 "golang.org/x/crypto/sha3"
8 )
9
10 // Homomorphic evaluation on Ring-LWE ciphertexts.
11 //
12 // A ciphertext (u, v) encrypts message m under public key (a, b = a·s + e):
13 // u = a·r + e1
14 // v = b·r + e2 + encode(m)
15 //
16 // Decryption: decode(v - s·u) = m + noise
17 //
18 // The noise term grows with operations:
19 // - Addition: noise_add = noise1 + noise2 (linear growth)
20 // - Multiplication: noise_mul ≈ noise1·noise2 (quadratic growth)
21 //
22 // The noise budget determines how many operations can be performed before
23 // decryption fails. This is the "somewhat homomorphic" (SHE) regime.
24 //
25 // For the recognizer use case (searchable encryption), we need:
26 // - Homomorphic XOR (= addition mod 2 of encoded bits)
27 // - Homomorphic AND (= multiplication of encoded bits)
28 // - Bounded depth circuits (pattern matching has fixed depth)
29
30 // HEParams holds parameters for homomorphic evaluation.
31 type HEParams struct {
32 KEM KEMParams
33
34 // RelinKey is the relinearization key for converting degree-2
35 // ciphertexts back to degree-1 after multiplication.
36 // Generated from the secret key.
37 RelinKey *RelinearizationKey
38 }
39
40 // HECiphertext is an Ring-LWE ciphertext supporting homomorphic operations.
41 // It wraps KEMCiphertext with noise tracking.
42 type HECiphertext struct {
43 U *Poly // first component
44 V *Poly // second component
45
46 // NoiseEstimate tracks the estimated noise magnitude.
47 // When this exceeds q/4, decryption will fail.
48 NoiseEstimate float64
49
50 params KEMParams
51 }
52
53 // RelinearizationKey enables conversion of degree-2 ciphertexts
54 // (produced by multiplication) back to degree-1.
55 //
56 // It's an encryption of s² under the public key:
57 // rk[i] = (a_i, a_i·s + e_i + (s²)·base^i)
58 // where base is the decomposition base for noise management.
59 type RelinearizationKey struct {
60 A []*Poly // uniform components
61 B []*Poly // a·s + e + s²·base^i
62 L int // number of decomposition levels
63 }
64
65 // DefaultHEParams returns parameters tuned for homomorphic evaluation.
66 // Uses HE64 ring (n=64, q=10000769) with eta=1 for tight noise.
67 // Supports depth-1 multiplicative circuits (one AND gate per path).
68 func DefaultHEParams() KEMParams {
69 return KEMParams{
70 Ring: HE64(),
71 Eta1: 1,
72 Eta2: 1,
73 SharedKeyLen: 32,
74 }
75 }
76
77 // HEKeyGen generates keys for homomorphic evaluation.
78 // Uses BGV-structured keygen: b = a·s + 2·e (noise is even).
79 func HEKeyGen(kp KEMParams) (*KEMPublicKey, *KEMSecretKey, *RelinearizationKey) {
80 return HEKeyGenFrom(kp, rand.Reader)
81 }
82
83 // HEKeyGenFrom generates HE keys from the given randomness source.
84 func HEKeyGenFrom(kp KEMParams, rng io.Reader) (*KEMPublicKey, *KEMSecretKey, *RelinearizationKey) {
85 p := kp.Ring
86
87 // a ← uniform
88 a := UniformPolyFrom(p, rng)
89 NTT(a)
90
91 // s ← ternary secret (small norm)
92 s := TernaryPolyFrom(p, rng)
93 NTT(s)
94
95 // e ← small noise, scaled by 2 for BGV structure
96 e := CBDPolyFrom(p, kp.Eta1, rng)
97 e = ScalarMul(e, 2)
98 NTT(e)
99
100 // b = a·s + 2·e
101 b := MulPointwise(a, s)
102 b = Add(b, e)
103
104 // z ← implicit rejection value
105 z := make([]byte, kp.SharedKeyLen)
106 io.ReadFull(rng, z)
107
108 pk := &KEMPublicKey{A: a, B: b, P: kp}
109 sk := &KEMSecretKey{S: s, PK: pk, Z: z}
110 rlk := genRelinKey(sk, rng)
111 return pk, sk, rlk
112 }
113
114 // genRelinKey generates a relinearization key from the secret key.
115 // Uses base-decomposition to control noise growth.
116 func genRelinKey(sk *KEMSecretKey, rng io.Reader) *RelinearizationKey {
117 p := sk.PK.P.Ring
118 q := p.Q
119
120 // Decomposition base: choose base so that ceil(log_base(q)) levels
121 // keeps the added noise manageable. Base = 256 gives ~2 levels for q=12289.
122 base := uint32(256)
123 levels := 0
124 for v := q; v > 0; v /= base {
125 levels++
126 }
127
128 // s² in NTT form.
129 s2 := MulPointwise(sk.S, sk.S)
130
131 rlkA := make([]*Poly, levels)
132 rlkB := make([]*Poly, levels)
133
134 power := uint32(1) // base^i
135 for i := range levels {
136 // a_i ← uniform
137 ai := UniformPolyFrom(p, rng)
138 NTT(ai)
139
140 // e_i ← small noise, scaled by 2 for BGV structure
141 ei := CBDPolyFrom(p, sk.PK.P.Eta1, rng)
142 ei = ScalarMul(ei, 2)
143 NTT(ei)
144
145 // b_i = a_i·s + e_i + s²·base^i
146 bi := MulPointwise(ai, sk.S)
147 bi = Add(bi, ei)
148
149 // Add s²·power (in NTT form, scalar multiply is pointwise).
150 s2Scaled := ScalarMul(s2, power)
151 bi = Add(bi, s2Scaled)
152
153 rlkA[i] = ai
154 rlkB[i] = bi
155
156 power = mulMod(power, base, q)
157 }
158
159 return &RelinearizationKey{A: rlkA, B: rlkB, L: levels}
160 }
161
162 // HEEncrypt encrypts a single bit (0 or 1) for homomorphic evaluation.
163 //
164 // Uses BGV-style encoding with plaintext modulus t=2:
165 //
166 // Encrypt(m): u = a·r + 2·e1, v = b·r + 2·e2 + m
167 // Decrypt(ct): (v - s·u) mod 2 = m (when noise < q/2)
168 //
169 // All noise terms are even (multiplied by t=2), so the message m ∈ {0,1}
170 // sits in the least significant bit. Addition in the ciphertext domain
171 // corresponds to XOR in the plaintext domain. Multiplication corresponds
172 // to AND (product of bits mod 2 = AND).
173 func HEEncrypt(pk *KEMPublicKey, bit int) *HECiphertext {
174 return HEEncryptFrom(pk, bit, rand.Reader)
175 }
176
177 // HEEncryptFrom encrypts a bit using the given randomness source.
178 func HEEncryptFrom(pk *KEMPublicKey, bit int, rng io.Reader) *HECiphertext {
179 p := pk.P.Ring
180 q := p.Q
181
182 coins := make([]byte, 32)
183 io.ReadFull(rng, coins)
184
185 noiseRng := sha3.NewShake256()
186 noiseRng.Write(coins)
187
188 // r ← small (ternary for tighter noise)
189 r := TernaryPolyFrom(p, noiseRng)
190 NTT(r)
191
192 // e1, e2 ← small noise, then multiply by 2 (BGV encoding)
193 e1 := CBDPolyFrom(p, pk.P.Eta1, noiseRng)
194 e2 := CBDPolyFrom(p, pk.P.Eta2, noiseRng)
195 e1 = ScalarMul(e1, 2)
196 e2 = ScalarMul(e2, 2)
197
198 // u = a·r + 2·e1
199 u := MulPointwise(pk.A, r)
200 INTT(u)
201 u = Add(u, e1)
202
203 // v = b·r + 2·e2 + m
204 v := MulPointwise(pk.B, r)
205 INTT(v)
206 v = Add(v, e2)
207
208 if bit != 0 {
209 v.Coeffs[0] = addMod(v.Coeffs[0], 1, q)
210 }
211
212 return &HECiphertext{
213 U: u,
214 V: v,
215 NoiseEstimate: float64(pk.P.Eta1+pk.P.Eta2) * 4,
216 params: pk.P,
217 }
218 }
219
220 // HEDecrypt decrypts a homomorphic ciphertext to recover the bit.
221 // Computes (v - s·u) mod q, then takes result mod 2.
222 func HEDecrypt(sk *KEMSecretKey, ct *HECiphertext) int {
223 uNTT := ct.U.Clone()
224 NTT(uNTT)
225 su := MulPointwise(sk.S, uNTT)
226 INTT(su)
227
228 noisy := Sub(ct.V, su)
229
230 // The result is 2·(noise) + m mod q.
231 // Recover m = result mod 2, using centered representation.
232 q := ct.params.Ring.Q
233 c := noisy.Coeffs[0]
234
235 // Centered lift: if c > q/2, interpret as negative.
236 if c > q/2 {
237 c = q - c // |c|, but parity is preserved: q is odd, so q-c has same parity as q+c
238 }
239 return int(c % 2)
240 }
241
242 // HEAdd computes the homomorphic addition of two ciphertexts.
243 // Decrypts to XOR of the two plaintext bits (addition mod 2 of encoded values).
244 func HEAdd(a, b *HECiphertext) *HECiphertext {
245 return &HECiphertext{
246 U: Add(a.U, b.U),
247 V: Add(a.V, b.V),
248 NoiseEstimate: a.NoiseEstimate + b.NoiseEstimate,
249 params: a.params,
250 }
251 }
252
253 // HESub computes homomorphic subtraction.
254 func HESub(a, b *HECiphertext) *HECiphertext {
255 return &HECiphertext{
256 U: Sub(a.U, b.U),
257 V: Sub(a.V, b.V),
258 NoiseEstimate: a.NoiseEstimate + b.NoiseEstimate,
259 params: a.params,
260 }
261 }
262
263 // HEMul computes homomorphic multiplication of two ciphertexts.
264 // Requires a relinearization key to bring the result back to degree 1.
265 //
266 // In BGV with t=2, decryption gives v - s·u = 2·e + m (mod q).
267 // The tensor product of two such ciphertexts produces a degree-2
268 // ciphertext (c0, c1, c2) where:
269 //
270 // decrypt_deg2 = c0 - c1·s + c2·s²
271 // = (2·e_a + m_a)·(2·e_b + m_b)
272 // = 4·e_a·e_b + 2·(m_a·e_b + m_b·e_a) + m_a·m_b
273 // = 2·(stuff) + m_a·m_b (mod 2)
274 //
275 // The product preserves the BGV structure: noise is still even,
276 // message sits in the LSB. No BFV-style rescaling needed.
277 //
278 // Relinearization converts (c0, c1, c2) → (u', v') using the
279 // relinearization key (encryption of s²).
280 func HEMul(a, b *HECiphertext, rlk *RelinearizationKey) *HECiphertext {
281 p := a.params.Ring
282
283 // Tensor product components.
284 // For ciphertext (u, v), decryption is v - s·u.
285 // For the product: (v_a - s·u_a)(v_b - s·u_b)
286 // = v_a·v_b - s·(v_a·u_b + u_a·v_b) + s²·u_a·u_b
287 // = c0 - s·c1 + s²·c2
288 c0 := Mul(a.V, b.V) // constant term
289 c1a := Mul(a.V, b.U) // linear terms
290 c1b := Mul(a.U, b.V) //
291 c1 := Add(c1a, c1b) // c1 = v_a·u_b + u_a·v_b
292 c2 := Mul(a.U, b.U) // quadratic term
293
294 // Relinearize c2: replace s²·c2 with an equivalent degree-1 term
295 // using the RLK which encrypts s².
296 // RLK[i] = (a_i, b_i = a_i·s + 2·e_i + s²·base^i)
297 // So: sum(digit_i · b_i) = sum(digit_i · a_i)·s + 2·(noise) + s²·c2
298 // This gives us: v' = c0 + sum(digit_i · b_i), u' = c1 + sum(digit_i · a_i)
299 base := uint32(256)
300 relinU := New(p)
301 relinV := New(p)
302
303 if c2.isNTT {
304 INTT(c2)
305 }
306
307 for level := 0; level < rlk.L; level++ {
308 digit := New(p)
309 for j := range digit.Coeffs {
310 d := c2.Coeffs[j]
311 for k := 0; k < level; k++ {
312 d /= base
313 }
314 digit.Coeffs[j] = d % base
315 }
316
317 NTT(digit)
318
319 uPart := MulPointwise(digit, rlk.A[level])
320 vPart := MulPointwise(digit, rlk.B[level])
321 INTT(uPart)
322 INTT(vPart)
323
324 relinU = Add(relinU, uPart)
325 relinV = Add(relinV, vPart)
326 }
327
328 return &HECiphertext{
329 U: Add(c1, relinU),
330 V: Add(c0, relinV),
331 NoiseEstimate: a.NoiseEstimate * b.NoiseEstimate * 4,
332 params: a.params,
333 }
334 }
335
336 // HENot computes the homomorphic NOT (bit flip) of a ciphertext.
337 // NOT(x) = 1 - x. In BGV encoding: the constant term has the message in its LSB.
338 // Adding 1 to v flips the LSB. u stays the same (NOT doesn't change the s term).
339 func HENot(a *HECiphertext) *HECiphertext {
340 p := a.params.Ring
341
342 one := New(p)
343 one.Coeffs[0] = 1
344
345 // v' = 1 + v (flip LSB), u stays (noise unchanged by constant add)
346 // Actually NOT(x) = 1 XOR x = 1 + x mod 2, which in the ciphertext domain
347 // means: add encrypt(1) to the ciphertext. But we can do it cheaper:
348 // just add 1 to v's constant coefficient.
349 newV := a.V.Clone()
350 newV.Coeffs[0] = addMod(newV.Coeffs[0], 1, p.Q)
351
352 return &HECiphertext{
353 U: a.U.Clone(),
354 V: newV,
355 NoiseEstimate: a.NoiseEstimate,
356 params: a.params,
357 }
358 }
359
360 // HEXOR computes XOR via addition (same as HEAdd for binary plaintexts).
361 func HEXOR(a, b *HECiphertext) *HECiphertext {
362 return HEAdd(a, b)
363 }
364
365 // HEAND computes AND via multiplication.
366 func HEAND(a, b *HECiphertext, rlk *RelinearizationKey) *HECiphertext {
367 return HEMul(a, b, rlk)
368 }
369
370 // Rerandomize adds a fresh encryption of zero to break linkability.
371 // This is the key anti-malleability defense: same plaintext, new ciphertext.
372 func Rerandomize(pk *KEMPublicKey, ct *HECiphertext) *HECiphertext {
373 return RerandomizeFrom(pk, ct, rand.Reader)
374 }
375
376 // RerandomizeFrom uses the given randomness source.
377 func RerandomizeFrom(pk *KEMPublicKey, ct *HECiphertext, rng io.Reader) *HECiphertext {
378 // Encrypt zero and add to ciphertext.
379 zero := HEEncryptFrom(pk, 0, rng)
380 return HEAdd(ct, zero)
381 }
382