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