fhe-study/bfv/src/lib.rs
bfv/src/lib.rsRaw
1//! Implementation of BFV https://eprint.iacr.org/2012/144.pdf
2#![allow(non_snake_case)]
3#![allow(non_upper_case_globals)]
4#![allow(non_camel_case_types)]
5#![allow(clippy::upper_case_acronyms)]
6#![allow(dead_code)] // TMP
7
8use anyhow::Result;
9use rand::Rng;
10use rand_distr::{Normal, Uniform};
11use std::ops;
12
13use arith::{Rq, R};
14
15// error deviation for the Gaussian(Normal) distribution
16// sigma=3.2 from: https://eprint.iacr.org/2022/162.pdf page 5
17const ERR_SIGMA: f64 = 3.2;
18
19#[derive(Clone, Debug)]
20pub struct SecretKey<const Q: u64, const N: usize>(Rq<Q, N>);
21
22#[derive(Clone, Debug)]
23pub struct PublicKey<const Q: u64, const N: usize>(Rq<Q, N>, Rq<Q, N>);
24
25/// Relinearization key
26#[derive(Clone, Debug)]
27pub struct RLK<const PQ: u64, const N: usize>(Rq<PQ, N>, Rq<PQ, N>);
28
29// RLWE ciphertext
30#[derive(Clone, Debug)]
31pub struct RLWE<const Q: u64, const N: usize>(Rq<Q, N>, Rq<Q, N>);
32
33impl<const Q: u64, const N: usize> RLWE<Q, N> {
34 fn add(lhs: Self, rhs: Self) -> Self {
35 RLWE::<Q, N>(lhs.0 + rhs.0, lhs.1 + rhs.1)
36 }
37 pub fn remodule<const P: u64>(&self) -> RLWE<P, N> {
38 let x = self.0.remodule::<P>();
39 let y = self.1.remodule::<P>();
40 RLWE::<P, N>(x, y)
41 }
42
43 fn tensor<const PQ: u64, const T: u64>(a: &Self, b: &Self) -> (Rq<Q, N>, Rq<Q, N>, Rq<Q, N>) {
44 // expand Q->PQ // TODO rm
45
46 // get the coefficients in Z, ie. interpret a,b \in R (instead of R_q)
47 let a0: R<N> = a.0.to_r();
48 let a1: R<N> = a.1.to_r();
49 let b0: R<N> = b.0.to_r();
50 let b1: R<N> = b.1.to_r();
51
52 // tensor (\in R) (2021-204 p.9)
53 // NOTE: here can use *, but at first versions want to make it explicit
54 // that we're using the naive mul. TODO use *.
55 use arith::ring::naive_mul;
56 let c0: Vec<i64> = naive_mul(&a0, &b0);
57 let c1_l: Vec<i64> = naive_mul(&a0, &b1);
58 let c1_r = naive_mul(&a1, &b0);
59 let c1: Vec<i64> = itertools::zip_eq(c1_l, c1_r).map(|(l, r)| l + r).collect();
60 let c2: Vec<i64> = naive_mul(&a1, &b1);
61
62 // scale down, then reduce module Q, so result is \in R_q
63 let c0: Rq<Q, N> = arith::ring::mul_div_round::<Q, N>(c0, T, Q);
64 let c1: Rq<Q, N> = arith::ring::mul_div_round::<Q, N>(c1, T, Q);
65 let c2: Rq<Q, N> = arith::ring::mul_div_round::<Q, N>(c2, T, Q);
66
67 (c0, c1, c2)
68 }
69 /// ciphertext multiplication
70 fn mul<const PQ: u64, const T: u64>(rlk: &RLK<PQ, N>, a: &Self, b: &Self) -> Self {
71 let (c0, c1, c2) = Self::tensor::<PQ, T>(a, b);
72 BFV::<Q, N, T>::relinearize_204::<PQ>(&rlk, &c0, &c1, &c2)
73 }
74}
75// naive mul in the ring Rq, reusing the ring::naive_mul and then applying mod(X^N +1)
76fn tmp_naive_mul<const Q: u64, const N: usize>(a: Rq<Q, N>, b: Rq<Q, N>) -> Rq<Q, N> {
77 Rq::<Q, N>::from_vec_i64(arith::ring::naive_mul(&a.to_r(), &b.to_r()))
78}
79
80impl<const Q: u64, const N: usize> ops::Add<RLWE<Q, N>> for RLWE<Q, N> {
81 type Output = Self;
82 fn add(self, rhs: Self) -> Self {
83 Self::add(self, rhs)
84 }
85}
86
87impl<const Q: u64, const N: usize, const T: u64> ops::Add<&Rq<T, N>> for &RLWE<Q, N> {
88 type Output = RLWE<Q, N>;
89 fn add(self, rhs: &Rq<T, N>) -> Self::Output {
90 BFV::<Q, N, T>::add_const(self, rhs)
91 }
92}
93
94pub struct BFV<const Q: u64, const N: usize, const T: u64> {}
95
96impl<const Q: u64, const N: usize, const T: u64> BFV<Q, N, T> {
97 const DELTA: u64 = Q / T; // floor
98
99 /// generate a new key pair (privK, pubK)
100 pub fn new_key(mut rng: impl Rng) -> Result<(SecretKey<Q, N>, PublicKey<Q, N>)> {
101 // WIP: review probabilities
102
103 // let Xi_key = Uniform::new(-1_f64, 1_f64);
104 let Xi_key = Uniform::new(0_u64, 2_u64);
105 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
106
107 // secret key
108 // let s = Rq::<Q, N>::rand_f64(&mut rng, Xi_key)?;
109 let s = Rq::<Q, N>::rand_u64(&mut rng, Xi_key)?;
110
111 // pk = (-a * s + e, a)
112 let a = Rq::<Q, N>::rand_u64(&mut rng, Uniform::new(0_u64, Q))?;
113 let e = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
114 let pk: PublicKey<Q, N> = PublicKey((&(-a) * &s) + e, a.clone());
115 Ok((SecretKey(s), pk))
116 }
117
118 pub fn encrypt(mut rng: impl Rng, pk: &PublicKey<Q, N>, m: &Rq<T, N>) -> Result<RLWE<Q, N>> {
119 let Xi_key = Uniform::new(-1_f64, 1_f64);
120 // let Xi_key = Uniform::new(0_u64, 2_u64);
121 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
122
123 let u = Rq::<Q, N>::rand_f64(&mut rng, Xi_key)?;
124 // let u = Rq::<Q, N>::rand_u64(&mut rng, Xi_key)?;
125 let e_1 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
126 let e_2 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
127
128 // migrate m's coeffs to the bigger modulus Q (from T)
129 let m = m.remodule::<Q>();
130 let c0 = &pk.0 * &u + e_1 + m * Self::DELTA;
131 let c1 = &pk.1 * &u + e_2;
132 Ok(RLWE::<Q, N>(c0, c1))
133 }
134
135 pub fn decrypt(sk: &SecretKey<Q, N>, c: &RLWE<Q, N>) -> Rq<T, N> {
136 let cs = c.0 + c.1 * sk.0; // done in mod q
137
138 // same but with naive_mul:
139 // let c1s = arith::ring::naive_mul(&c.1.to_r(), &sk.0.to_r());
140 // let c1s = Rq::<Q, N>::from_vec_i64(c1s);
141 // let cs = c.0 + c1s;
142
143 let r: Rq<Q, N> = cs.mul_div_round(T, Q);
144 r.remodule::<T>()
145 }
146
147 fn add_const(c: &RLWE<Q, N>, m: &Rq<T, N>) -> RLWE<Q, N> {
148 // assuming T<Q, move m from Zq<T> to Zq<Q>
149 let m = m.remodule::<Q>();
150 RLWE::<Q, N>(c.0 + m * Self::DELTA, c.1)
151 }
152 fn mul_const<const PQ: u64>(rlk: &RLK<PQ, N>, c: &RLWE<Q, N>, m: &Rq<T, N>) -> RLWE<Q, N> {
153 // assuming T<Q, move m from Zq<T> to Zq<Q>
154 let m = m.remodule::<Q>();
155
156 // encrypt m*Delta without noise, and then perform normal ciphertext multiplication
157 let md = RLWE::<Q, N>(m * Self::DELTA, Rq::zero());
158 RLWE::<Q, N>::mul::<PQ, T>(&rlk, &c, &md)
159 }
160
161 fn rlk_key<const PQ: u64>(mut rng: impl Rng, s: &SecretKey<Q, N>) -> Result<RLK<PQ, N>> {
162 // TODO review using Xi' instead of Xi
163 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
164 // let Xi_err = Normal::new(0_f64, 0.0)?;
165 let s = s.0.remodule::<PQ>();
166 let a = Rq::<PQ, N>::rand_u64(&mut rng, Uniform::new(0_u64, PQ))?;
167 let e = Rq::<PQ, N>::rand_f64(&mut rng, Xi_err)?;
168
169 let P = PQ / Q;
170
171 // let rlk: RLK<PQ, N> = RLK::<PQ, N>(-(&a * &s + e) + (s * s) * P, a.clone());
172 let rlk: RLK<PQ, N> = RLK::<PQ, N>(
173 -(tmp_naive_mul(a, s) + e) + tmp_naive_mul(s, s) * P,
174 a.clone(),
175 );
176
177 Ok(rlk)
178 }
179
180 fn relinearize<const PQ: u64>(
181 rlk: &RLK<PQ, N>,
182 c0: &Rq<Q, N>,
183 c1: &Rq<Q, N>,
184 c2: &Rq<Q, N>,
185 ) -> RLWE<Q, N> {
186 let P = PQ / Q;
187
188 let c2rlk0: Vec<f64> = (c2.to_r() * rlk.0.to_r())
189 .coeffs()
190 .iter()
191 .map(|e| (*e as f64 / P as f64).round())
192 .collect();
193
194 let c2rlk1: Vec<f64> = (c2.to_r() * rlk.1.to_r())
195 .coeffs()
196 .iter()
197 .map(|e| (*e as f64 / P as f64).round())
198 .collect();
199
200 let r0 = Rq::<Q, N>::from_vec_f64(c2rlk0);
201 let r1 = Rq::<Q, N>::from_vec_f64(c2rlk1);
202
203 let res = RLWE::<Q, N>(c0 + &r0, c1 + &r1);
204 res
205 }
206 fn relinearize_204<const PQ: u64>(
207 rlk: &RLK<PQ, N>,
208 c0: &Rq<Q, N>,
209 c1: &Rq<Q, N>,
210 c2: &Rq<Q, N>,
211 ) -> RLWE<Q, N> {
212 let P = PQ / Q;
213
214 // let c2rlk0: Rq<PQ, N> = c2.remodule::<PQ>() * rlk.0.remodule::<PQ>();
215 // let c2rlk1: Rq<PQ, N> = c2.remodule::<PQ>() * rlk.1.remodule::<PQ>();
216 // let r0: Rq<Q, N> = c2rlk0.mul_div_round(1, P).remodule::<Q>();
217 // let r1: Rq<Q, N> = c2rlk1.mul_div_round(1, P).remodule::<Q>();
218
219 use arith::ring::naive_mul;
220 let c2rlk0: Vec<i64> = naive_mul(&c2.to_r(), &rlk.0.to_r());
221 let c2rlk1: Vec<i64> = naive_mul(&c2.to_r(), &rlk.1.to_r());
222 let r0: Rq<Q, N> = arith::ring::mul_div_round::<Q, N>(c2rlk0, 1, P);
223 let r1: Rq<Q, N> = arith::ring::mul_div_round::<Q, N>(c2rlk1, 1, P);
224
225 let res = RLWE::<Q, N>(c0 + &r0, c1 + &r1);
226 res
227 }
228}
229
230#[cfg(test)]
231mod tests {
232 use anyhow::Result;
233 use rand::distributions::Uniform;
234
235 use super::*;
236
237 #[test]
238 fn test_encrypt_decrypt() -> Result<()> {
239 const Q: u64 = 2u64.pow(16) + 1;
240 const N: usize = 512;
241 const T: u64 = 32; // plaintext modulus
242 type S = BFV<Q, N, T>;
243
244 let mut rng = rand::thread_rng();
245
246 for _ in 0..100 {
247 let (sk, pk) = S::new_key(&mut rng)?;
248
249 let msg_dist = Uniform::new(0_u64, T);
250 let m = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
251
252 let c = S::encrypt(&mut rng, &pk, &m)?;
253 let m_recovered = S::decrypt(&sk, &c);
254
255 assert_eq!(m, m_recovered);
256 }
257
258 Ok(())
259 }
260
261 #[test]
262 fn test_addition() -> Result<()> {
263 const Q: u64 = 2u64.pow(16) + 1;
264 const N: usize = 128;
265 const T: u64 = 32; // plaintext modulus
266 type S = BFV<Q, N, T>;
267
268 let mut rng = rand::thread_rng();
269
270 for _ in 0..100 {
271 let (sk, pk) = S::new_key(&mut rng)?;
272
273 let msg_dist = Uniform::new(0_u64, T);
274 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
275 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
276
277 let c1 = S::encrypt(&mut rng, &pk, &m1)?;
278 let c2 = S::encrypt(&mut rng, &pk, &m2)?;
279
280 let c3 = c1 + c2;
281
282 let m3_recovered = S::decrypt(&sk, &c3);
283
284 assert_eq!(m1 + m2, m3_recovered);
285 }
286
287 Ok(())
288 }
289
290 #[test]
291 fn test_constant_add_mul() -> Result<()> {
292 const Q: u64 = 2u64.pow(16) + 1;
293 const N: usize = 16;
294 const T: u64 = 16; // plaintext modulus
295 type S = BFV<Q, N, T>;
296
297 let mut rng = rand::thread_rng();
298
299 let (sk, pk) = S::new_key(&mut rng)?;
300
301 let msg_dist = Uniform::new(0_u64, T);
302 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
303 let m2_const = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
304 let c1 = S::encrypt(&mut rng, &pk, &m1)?;
305
306 let c3_add = &c1 + &m2_const;
307
308 let m3_add_recovered = S::decrypt(&sk, &c3_add);
309 assert_eq!(m1 + m2_const, m3_add_recovered);
310
311 // test multiplication of a ciphertext by a constant
312 const P: u64 = Q * Q;
313 const PQ: u64 = P * Q;
314 let rlk = BFV::<Q, N, T>::rlk_key::<PQ>(&mut rng, &sk)?;
315
316 let c3_mul = S::mul_const(&rlk, &c1, &m2_const);
317
318 let m3_mul_recovered = S::decrypt(&sk, &c3_mul);
319 assert_eq!(
320 (m1.to_r() * m2_const.to_r()).to_rq::<T>().coeffs(),
321 m3_mul_recovered.coeffs()
322 );
323
324 Ok(())
325 }
326
327 // TMP WIP
328 #[test]
329 #[ignore]
330 fn test_params() -> Result<()> {
331 const Q: u64 = 2u64.pow(16) + 1; // q prime, and 2^q + 1 shape
332 const N: usize = 32;
333 const T: u64 = 8; // plaintext modulus
334
335 const P: u64 = Q * Q;
336 const PQ: u64 = P * Q;
337 const DELTA: u64 = Q / T; // floor
338
339 let mut rng = rand::thread_rng();
340
341 let Xi_key = Uniform::new(0_f64, 1_f64);
342 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
343
344 let s = Rq::<Q, N>::rand_f64(&mut rng, Xi_key)?;
345 let e = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
346 let u = Rq::<Q, N>::rand_f64(&mut rng, Xi_key)?;
347 let e_0 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
348 let e_1 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
349 let m = Rq::<Q, N>::rand_u64(&mut rng, Uniform::new(0_u64, T))?;
350
351 // v_fresh
352 let v: Rq<Q, N> = u * e + e_1 * s + e_0;
353
354 let q: f64 = Q as f64;
355 let t: f64 = T as f64;
356 let n: f64 = N as f64;
357 let delta: f64 = DELTA as f64;
358
359 // r_t(q)/t should be equal to q/t-Δ
360 assert_eq!(
361 // r_t(q)/t, where r_t(q)=q mod t
362 (q % t) / t,
363 // Δt/Q = q - r_t(Q)/Q, so r_t(Q)=q - Δt
364 (q / t) - delta
365 );
366 let rt: f64 = (q % t) / t;
367 dbg!(&rt);
368
369 dbg!(v.infinity_norm());
370 let bound: f64 = (q / (2_f64 * t)) - (rt / 2_f64);
371 dbg!(bound);
372 assert!((v.infinity_norm() as f64) < bound);
373 let max_v_infnorm = bound - 1.0;
374
375 // addition noise
376 let v_add: Rq<Q, N> = v + v + u * rt;
377 let v_add: Rq<Q, N> = v_add + v_add + u * rt;
378 assert!((v_add.infinity_norm() as f64) < bound);
379
380 // multiplication noise
381 let (_, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
382 let c = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m.remodule::<T>())?;
383 let b_key: f64 = 1_f64;
384 // ef: expansion factor
385 let ef: f64 = 2.0 * n.sqrt();
386 let bound: f64 = ((ef * t) / 2.0)
387 * ((2.0 * max_v_infnorm * max_v_infnorm) / q
388 + (4.0 + ef * b_key) * (max_v_infnorm + max_v_infnorm)
389 + rt * (ef * b_key + 5.0))
390 + (1.0 + ef * b_key + ef * ef * b_key * b_key) / 2.0;
391 dbg!(&bound);
392
393 let k: Vec<f64> = (c.0 + c.1 * s - m * delta - v)
394 .coeffs()
395 .iter()
396 .map(|e_i| e_i.0 as f64 / q)
397 .collect();
398 let k = Rq::<Q, N>::from_vec_f64(k);
399 let v_tensor_0 = (v * v)
400 .coeffs()
401 .iter()
402 .map(|e_i| (e_i.0 as f64 * t) / q)
403 .collect::<Vec<f64>>();
404 let v_tensor_0 = Rq::<Q, N>::from_vec_f64(v_tensor_0);
405 let v_tensor_1 = ((m * v) + (m * v))
406 .coeffs()
407 .iter()
408 .map(|e_i| (e_i.0 as f64 * t * delta) / q)
409 .collect::<Vec<f64>>();
410 let v_tensor_1 = Rq::<Q, N>::from_vec_f64(v_tensor_1);
411 let v_tensor_2: Rq<Q, N> = (v * k + v * k) * t;
412 let rm: f64 = (ef * t) / 2.0;
413 let rm: Rq<Q, N> = Rq::<Q, N>::from_vec_f64(vec![rm; N]);
414 let v_tensor_3: Rq<Q, N> = (m * k
415 + m * k
416 + rm
417 + Rq::from_vec_f64(
418 ((m * m) * DELTA)
419 .coeffs()
420 .iter()
421 .map(|e_i| e_i.0 as f64 / q)
422 .collect::<Vec<f64>>(),
423 ))
424 * rt;
425 let v_tensor = v_tensor_0 + v_tensor_1 + v_tensor_2 - v_tensor_3;
426
427 let v_r = (1.0 + ef * b_key + ef * ef * b_key * b_key) / 2.0;
428 let v_mult_norm = v_tensor.infinity_norm() as f64 + v_r;
429 dbg!(&v_mult_norm);
430 dbg!(&bound);
431 assert!(v_mult_norm < bound);
432
433 // let m1 = Rq::<T, N>::zero();
434 // let m2 = Rq::<T, N>::zero();
435 // let (_, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
436 // let c1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m1)?;
437 // let c2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m2)?;
438 // let (c_a, c_b, c_c) = RLWE::<Q, N>::tensor::<PQ, T>(&c1, &c2);
439 // dbg!(&c_a.infinity_norm());
440 // dbg!(&c_b.infinity_norm());
441 // dbg!(&c_c.infinity_norm());
442 // assert!((c_a.infinity_norm() as f64) < bound);
443 // assert!((c_b.infinity_norm() as f64) < bound);
444 // assert!((c_c.infinity_norm() as f64) < bound);
445 // WIP
446
447 Ok(())
448 }
449
450 #[test]
451 fn test_tensor() -> Result<()> {
452 const Q: u64 = 2u64.pow(16) + 1; // q prime, and 2^q + 1 shape
453 const N: usize = 16;
454 const T: u64 = 2; // plaintext modulus
455
456 // const P: u64 = Q;
457 const P: u64 = Q * Q;
458 const PQ: u64 = P * Q;
459
460 let mut rng = rand::thread_rng();
461
462 let msg_dist = Uniform::new(0_u64, T);
463 for _ in 0..1_000 {
464 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
465 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
466
467 test_tensor_opt::<Q, N, T, PQ>(&mut rng, m1, m2)?;
468 }
469
470 Ok(())
471 }
472 fn test_tensor_opt<const Q: u64, const N: usize, const T: u64, const PQ: u64>(
473 mut rng: impl Rng,
474 m1: Rq<T, N>,
475 m2: Rq<T, N>,
476 ) -> Result<()> {
477 let (sk, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
478
479 let c1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m1)?;
480 let c2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m2)?;
481
482 let (c_a, c_b, c_c) = RLWE::<Q, N>::tensor::<PQ, T>(&c1, &c2);
483 // let (c_a, c_b, c_c) = RLWE::<Q, N>::tensor_new::<PQ, T>(&c1, &c2);
484
485 // decrypt non-relinearized mul result
486 let m3: Rq<Q, N> = c_a + c_b * sk.0 + c_c * sk.0 * sk.0;
487 // let m3: Rq<Q, N> = c_a
488 // + Rq::<Q, N>::from_vec_i64(arith::ring::naive_mul(&c_b.to_r(), &sk.0.to_r()))
489 // + Rq::<Q, N>::from_vec_i64(arith::ring::naive_mul(
490 // &c_c.to_r(),
491 // &R::<N>::from_vec(arith::ring::naive_mul(&sk.0.to_r(), &sk.0.to_r())),
492 // ));
493 let m3: Rq<Q, N> = m3.mul_div_round(T, Q); // descale
494 let m3 = m3.remodule::<T>();
495
496 let naive = (m1.to_r() * m2.to_r()).to_rq::<T>();
497 assert_eq!(
498 m3.coeffs().to_vec(),
499 naive.coeffs().to_vec(),
500 "\n\nfor testing:\nlet m1 = Rq::<T, N>::from_vec_u64(vec!{:?});\nlet m2 = Rq::<T, N>::from_vec_u64(vec!{:?});\n",
501 m1.coeffs(),
502 m2.coeffs()
503 );
504
505 Ok(())
506 }
507
508 #[test]
509 fn test_mul_relin() -> Result<()> {
510 const Q: u64 = 2u64.pow(16) + 1;
511 const N: usize = 4;
512 const T: u64 = 2; // plaintext modulus
513 type S = BFV<Q, N, T>;
514
515 const P: u64 = Q * Q;
516 const PQ: u64 = P * Q;
517
518 let mut rng = rand::thread_rng();
519 let msg_dist = Uniform::new(0_u64, T);
520
521 for _ in 0..100 {
522 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
523 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
524
525 test_mul_relin_opt::<Q, N, T, PQ>(&mut rng, m1, m2)?;
526 }
527
528 Ok(())
529 }
530
531 fn test_mul_relin_opt<const Q: u64, const N: usize, const T: u64, const PQ: u64>(
532 mut rng: impl Rng,
533 m1: Rq<T, N>,
534 m2: Rq<T, N>,
535 ) -> Result<()> {
536 let (sk, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
537
538 let rlk = BFV::<Q, N, T>::rlk_key::<PQ>(&mut rng, &sk)?;
539
540 let c1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m1)?;
541 let c2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m2)?;
542
543 let c3 = RLWE::<Q, N>::mul::<PQ, T>(&rlk, &c1, &c2); // uses relinearize internally
544
545 let m3 = BFV::<Q, N, T>::decrypt(&sk, &c3);
546
547 let naive = (m1.to_r() * m2.to_r()).to_rq::<T>();
548 assert_eq!(
549 m3.coeffs().to_vec(),
550 naive.coeffs().to_vec(),
551 "\n\nfor testing:\nlet m1 = Rq::<T, N>::from_vec_u64(vec!{:?});\nlet m2 = Rq::<T, N>::from_vec_u64(vec!{:?});\n",
552 m1.coeffs(),
553 m2.coeffs()
554 );
555
556 Ok(())
557 }
558}