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 mut s = Rq::<Q, N>::rand_u64(&mut rng, Xi_key)?;
110 // since s is going to be multiplied by other Rq elements, already
111 // compute its NTT
112 s.compute_evals();
113
114 // pk = (-a * s + e, a)
115 let a = Rq::<Q, N>::rand_u64(&mut rng, Uniform::new(0_u64, Q))?;
116 let e = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
117 let pk: PublicKey<Q, N> = PublicKey((&(-a) * &s) + e, a.clone());
118 Ok((SecretKey(s), pk))
119 }
120
121 pub fn encrypt(mut rng: impl Rng, pk: &PublicKey<Q, N>, m: &Rq<T, N>) -> Result<RLWE<Q, N>> {
122 let Xi_key = Uniform::new(-1_f64, 1_f64);
123 // let Xi_key = Uniform::new(0_u64, 2_u64);
124 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
125
126 let u = Rq::<Q, N>::rand_f64(&mut rng, Xi_key)?;
127 // let u = Rq::<Q, N>::rand_u64(&mut rng, Xi_key)?;
128 let e_1 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
129 let e_2 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
130
131 // migrate m's coeffs to the bigger modulus Q (from T)
132 let m = m.remodule::<Q>();
133 let c0 = &pk.0 * &u + e_1 + m * Self::DELTA;
134 let c1 = &pk.1 * &u + e_2;
135 Ok(RLWE::<Q, N>(c0, c1))
136 }
137
138 pub fn decrypt(sk: &SecretKey<Q, N>, c: &RLWE<Q, N>) -> Rq<T, N> {
139 let cs = c.0 + c.1 * sk.0; // done in mod q
140
141 // same but with naive_mul:
142 // let c1s = arith::ring::naive_mul(&c.1.to_r(), &sk.0.to_r());
143 // let c1s = Rq::<Q, N>::from_vec_i64(c1s);
144 // let cs = c.0 + c1s;
145
146 let r: Rq<Q, N> = cs.mul_div_round(T, Q);
147 r.remodule::<T>()
148 }
149
150 fn add_const(c: &RLWE<Q, N>, m: &Rq<T, N>) -> RLWE<Q, N> {
151 // assuming T<Q, move m from Zq<T> to Zq<Q>
152 let m = m.remodule::<Q>();
153 RLWE::<Q, N>(c.0 + m * Self::DELTA, c.1)
154 }
155 fn mul_const<const PQ: u64>(rlk: &RLK<PQ, N>, c: &RLWE<Q, N>, m: &Rq<T, N>) -> RLWE<Q, N> {
156 // assuming T<Q, move m from Zq<T> to Zq<Q>
157 let m = m.remodule::<Q>();
158
159 // encrypt m*Delta without noise, and then perform normal ciphertext multiplication
160 let md = RLWE::<Q, N>(m * Self::DELTA, Rq::zero());
161 RLWE::<Q, N>::mul::<PQ, T>(&rlk, &c, &md)
162 }
163
164 fn rlk_key<const PQ: u64>(mut rng: impl Rng, s: &SecretKey<Q, N>) -> Result<RLK<PQ, N>> {
165 // TODO review using Xi' instead of Xi
166 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
167 // let Xi_err = Normal::new(0_f64, 0.0)?;
168 let s = s.0.remodule::<PQ>();
169 let a = Rq::<PQ, N>::rand_u64(&mut rng, Uniform::new(0_u64, PQ))?;
170 let e = Rq::<PQ, N>::rand_f64(&mut rng, Xi_err)?;
171
172 let P = PQ / Q;
173
174 // let rlk: RLK<PQ, N> = RLK::<PQ, N>(-(&a * &s + e) + (s * s) * P, a.clone());
175 let rlk: RLK<PQ, N> = RLK::<PQ, N>(
176 -(tmp_naive_mul(a, s) + e) + tmp_naive_mul(s, s) * P,
177 a.clone(),
178 );
179
180 Ok(rlk)
181 }
182
183 fn relinearize<const PQ: u64>(
184 rlk: &RLK<PQ, N>,
185 c0: &Rq<Q, N>,
186 c1: &Rq<Q, N>,
187 c2: &Rq<Q, N>,
188 ) -> RLWE<Q, N> {
189 let P = PQ / Q;
190
191 let c2rlk0: Vec<f64> = (c2.to_r() * rlk.0.to_r())
192 .coeffs()
193 .iter()
194 .map(|e| (*e as f64 / P as f64).round())
195 .collect();
196
197 let c2rlk1: Vec<f64> = (c2.to_r() * rlk.1.to_r())
198 .coeffs()
199 .iter()
200 .map(|e| (*e as f64 / P as f64).round())
201 .collect();
202
203 let r0 = Rq::<Q, N>::from_vec_f64(c2rlk0);
204 let r1 = Rq::<Q, N>::from_vec_f64(c2rlk1);
205
206 let res = RLWE::<Q, N>(c0 + &r0, c1 + &r1);
207 res
208 }
209 fn relinearize_204<const PQ: u64>(
210 rlk: &RLK<PQ, N>,
211 c0: &Rq<Q, N>,
212 c1: &Rq<Q, N>,
213 c2: &Rq<Q, N>,
214 ) -> RLWE<Q, N> {
215 let P = PQ / Q;
216
217 // let c2rlk0: Rq<PQ, N> = c2.remodule::<PQ>() * rlk.0.remodule::<PQ>();
218 // let c2rlk1: Rq<PQ, N> = c2.remodule::<PQ>() * rlk.1.remodule::<PQ>();
219 // let r0: Rq<Q, N> = c2rlk0.mul_div_round(1, P).remodule::<Q>();
220 // let r1: Rq<Q, N> = c2rlk1.mul_div_round(1, P).remodule::<Q>();
221
222 use arith::ring::naive_mul;
223 let c2rlk0: Vec<i64> = naive_mul(&c2.to_r(), &rlk.0.to_r());
224 let c2rlk1: Vec<i64> = naive_mul(&c2.to_r(), &rlk.1.to_r());
225 let r0: Rq<Q, N> = arith::ring::mul_div_round::<Q, N>(c2rlk0, 1, P);
226 let r1: Rq<Q, N> = arith::ring::mul_div_round::<Q, N>(c2rlk1, 1, P);
227
228 let res = RLWE::<Q, N>(c0 + &r0, c1 + &r1);
229 res
230 }
231}
232
233#[cfg(test)]
234mod tests {
235 use anyhow::Result;
236 use rand::distributions::Uniform;
237
238 use super::*;
239
240 #[test]
241 fn test_encrypt_decrypt() -> Result<()> {
242 const Q: u64 = 2u64.pow(16) + 1;
243 const N: usize = 512;
244 const T: u64 = 32; // plaintext modulus
245 type S = BFV<Q, N, T>;
246
247 let mut rng = rand::thread_rng();
248
249 for _ in 0..100 {
250 let (sk, pk) = S::new_key(&mut rng)?;
251
252 let msg_dist = Uniform::new(0_u64, T);
253 let m = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
254
255 let c = S::encrypt(&mut rng, &pk, &m)?;
256 let m_recovered = S::decrypt(&sk, &c);
257
258 assert_eq!(m, m_recovered);
259 }
260
261 Ok(())
262 }
263
264 #[test]
265 fn test_addition() -> Result<()> {
266 const Q: u64 = 2u64.pow(16) + 1;
267 const N: usize = 128;
268 const T: u64 = 32; // plaintext modulus
269 type S = BFV<Q, N, T>;
270
271 let mut rng = rand::thread_rng();
272
273 for _ in 0..100 {
274 let (sk, pk) = S::new_key(&mut rng)?;
275
276 let msg_dist = Uniform::new(0_u64, T);
277 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
278 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
279
280 let c1 = S::encrypt(&mut rng, &pk, &m1)?;
281 let c2 = S::encrypt(&mut rng, &pk, &m2)?;
282
283 let c3 = c1 + c2;
284
285 let m3_recovered = S::decrypt(&sk, &c3);
286
287 assert_eq!(m1 + m2, m3_recovered);
288 }
289
290 Ok(())
291 }
292
293 #[test]
294 fn test_constant_add_mul() -> Result<()> {
295 const Q: u64 = 2u64.pow(16) + 1;
296 const N: usize = 16;
297 const T: u64 = 16; // plaintext modulus
298 type S = BFV<Q, N, T>;
299
300 let mut rng = rand::thread_rng();
301
302 let (sk, pk) = S::new_key(&mut rng)?;
303
304 let msg_dist = Uniform::new(0_u64, T);
305 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
306 let m2_const = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
307 let c1 = S::encrypt(&mut rng, &pk, &m1)?;
308
309 let c3_add = &c1 + &m2_const;
310
311 let m3_add_recovered = S::decrypt(&sk, &c3_add);
312 assert_eq!(m1 + m2_const, m3_add_recovered);
313
314 // test multiplication of a ciphertext by a constant
315 const P: u64 = Q * Q;
316 const PQ: u64 = P * Q;
317 let rlk = BFV::<Q, N, T>::rlk_key::<PQ>(&mut rng, &sk)?;
318
319 let c3_mul = S::mul_const(&rlk, &c1, &m2_const);
320
321 let m3_mul_recovered = S::decrypt(&sk, &c3_mul);
322 assert_eq!(
323 (m1.to_r() * m2_const.to_r()).to_rq::<T>().coeffs(),
324 m3_mul_recovered.coeffs()
325 );
326
327 Ok(())
328 }
329
330 // TMP WIP
331 #[test]
332 #[ignore]
333 fn test_params() -> Result<()> {
334 const Q: u64 = 2u64.pow(16) + 1; // q prime, and 2^q + 1 shape
335 const N: usize = 32;
336 const T: u64 = 8; // plaintext modulus
337
338 const P: u64 = Q * Q;
339 const PQ: u64 = P * Q;
340 const DELTA: u64 = Q / T; // floor
341
342 let mut rng = rand::thread_rng();
343
344 let Xi_key = Uniform::new(0_f64, 1_f64);
345 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
346
347 let s = Rq::<Q, N>::rand_f64(&mut rng, Xi_key)?;
348 let e = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
349 let u = Rq::<Q, N>::rand_f64(&mut rng, Xi_key)?;
350 let e_0 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
351 let e_1 = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
352 let m = Rq::<Q, N>::rand_u64(&mut rng, Uniform::new(0_u64, T))?;
353
354 // v_fresh
355 let v: Rq<Q, N> = u * e + e_1 * s + e_0;
356
357 let q: f64 = Q as f64;
358 let t: f64 = T as f64;
359 let n: f64 = N as f64;
360 let delta: f64 = DELTA as f64;
361
362 // r_t(q)/t should be equal to q/t-Δ
363 assert_eq!(
364 // r_t(q)/t, where r_t(q)=q mod t
365 (q % t) / t,
366 // Δt/Q = q - r_t(Q)/Q, so r_t(Q)=q - Δt
367 (q / t) - delta
368 );
369 let rt: f64 = (q % t) / t;
370 dbg!(&rt);
371
372 dbg!(v.infinity_norm());
373 let bound: f64 = (q / (2_f64 * t)) - (rt / 2_f64);
374 dbg!(bound);
375 assert!((v.infinity_norm() as f64) < bound);
376 let max_v_infnorm = bound - 1.0;
377
378 // addition noise
379 let v_add: Rq<Q, N> = v + v + u * rt;
380 let v_add: Rq<Q, N> = v_add + v_add + u * rt;
381 assert!((v_add.infinity_norm() as f64) < bound);
382
383 // multiplication noise
384 let (_, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
385 let c = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m.remodule::<T>())?;
386 let b_key: f64 = 1_f64;
387 // ef: expansion factor
388 let ef: f64 = 2.0 * n.sqrt();
389 let bound: f64 = ((ef * t) / 2.0)
390 * ((2.0 * max_v_infnorm * max_v_infnorm) / q
391 + (4.0 + ef * b_key) * (max_v_infnorm + max_v_infnorm)
392 + rt * (ef * b_key + 5.0))
393 + (1.0 + ef * b_key + ef * ef * b_key * b_key) / 2.0;
394 dbg!(&bound);
395
396 let k: Vec<f64> = (c.0 + c.1 * s - m * delta - v)
397 .coeffs()
398 .iter()
399 .map(|e_i| e_i.0 as f64 / q)
400 .collect();
401 let k = Rq::<Q, N>::from_vec_f64(k);
402 let v_tensor_0 = (v * v)
403 .coeffs()
404 .iter()
405 .map(|e_i| (e_i.0 as f64 * t) / q)
406 .collect::<Vec<f64>>();
407 let v_tensor_0 = Rq::<Q, N>::from_vec_f64(v_tensor_0);
408 let v_tensor_1 = ((m * v) + (m * v))
409 .coeffs()
410 .iter()
411 .map(|e_i| (e_i.0 as f64 * t * delta) / q)
412 .collect::<Vec<f64>>();
413 let v_tensor_1 = Rq::<Q, N>::from_vec_f64(v_tensor_1);
414 let v_tensor_2: Rq<Q, N> = (v * k + v * k) * t;
415 let rm: f64 = (ef * t) / 2.0;
416 let rm: Rq<Q, N> = Rq::<Q, N>::from_vec_f64(vec![rm; N]);
417 let v_tensor_3: Rq<Q, N> = (m * k
418 + m * k
419 + rm
420 + Rq::from_vec_f64(
421 ((m * m) * DELTA)
422 .coeffs()
423 .iter()
424 .map(|e_i| e_i.0 as f64 / q)
425 .collect::<Vec<f64>>(),
426 ))
427 * rt;
428 let v_tensor = v_tensor_0 + v_tensor_1 + v_tensor_2 - v_tensor_3;
429
430 let v_r = (1.0 + ef * b_key + ef * ef * b_key * b_key) / 2.0;
431 let v_mult_norm = v_tensor.infinity_norm() as f64 + v_r;
432 dbg!(&v_mult_norm);
433 dbg!(&bound);
434 assert!(v_mult_norm < bound);
435
436 // let m1 = Rq::<T, N>::zero();
437 // let m2 = Rq::<T, N>::zero();
438 // let (_, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
439 // let c1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m1)?;
440 // let c2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m2)?;
441 // let (c_a, c_b, c_c) = RLWE::<Q, N>::tensor::<PQ, T>(&c1, &c2);
442 // dbg!(&c_a.infinity_norm());
443 // dbg!(&c_b.infinity_norm());
444 // dbg!(&c_c.infinity_norm());
445 // assert!((c_a.infinity_norm() as f64) < bound);
446 // assert!((c_b.infinity_norm() as f64) < bound);
447 // assert!((c_c.infinity_norm() as f64) < bound);
448 // WIP
449
450 Ok(())
451 }
452
453 #[test]
454 fn test_tensor() -> Result<()> {
455 const Q: u64 = 2u64.pow(16) + 1; // q prime, and 2^q + 1 shape
456 const N: usize = 16;
457 const T: u64 = 2; // plaintext modulus
458
459 // const P: u64 = Q;
460 const P: u64 = Q * Q;
461 const PQ: u64 = P * Q;
462
463 let mut rng = rand::thread_rng();
464
465 let msg_dist = Uniform::new(0_u64, T);
466 for _ in 0..1_000 {
467 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
468 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
469
470 test_tensor_opt::<Q, N, T, PQ>(&mut rng, m1, m2)?;
471 }
472
473 Ok(())
474 }
475 fn test_tensor_opt<const Q: u64, const N: usize, const T: u64, const PQ: u64>(
476 mut rng: impl Rng,
477 m1: Rq<T, N>,
478 m2: Rq<T, N>,
479 ) -> Result<()> {
480 let (sk, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
481
482 let c1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m1)?;
483 let c2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m2)?;
484
485 let (c_a, c_b, c_c) = RLWE::<Q, N>::tensor::<PQ, T>(&c1, &c2);
486 // let (c_a, c_b, c_c) = RLWE::<Q, N>::tensor_new::<PQ, T>(&c1, &c2);
487
488 // decrypt non-relinearized mul result
489 let m3: Rq<Q, N> = c_a + c_b * sk.0 + c_c * sk.0 * sk.0;
490 // let m3: Rq<Q, N> = c_a
491 // + Rq::<Q, N>::from_vec_i64(arith::ring::naive_mul(&c_b.to_r(), &sk.0.to_r()))
492 // + Rq::<Q, N>::from_vec_i64(arith::ring::naive_mul(
493 // &c_c.to_r(),
494 // &R::<N>::from_vec(arith::ring::naive_mul(&sk.0.to_r(), &sk.0.to_r())),
495 // ));
496 let m3: Rq<Q, N> = m3.mul_div_round(T, Q); // descale
497 let m3 = m3.remodule::<T>();
498
499 let naive = (m1.to_r() * m2.to_r()).to_rq::<T>();
500 assert_eq!(
501 m3.coeffs().to_vec(),
502 naive.coeffs().to_vec(),
503 "\n\nfor testing:\nlet m1 = Rq::<T, N>::from_vec_u64(vec!{:?});\nlet m2 = Rq::<T, N>::from_vec_u64(vec!{:?});\n",
504 m1.coeffs(),
505 m2.coeffs()
506 );
507
508 Ok(())
509 }
510
511 #[test]
512 fn test_mul_relin() -> Result<()> {
513 const Q: u64 = 2u64.pow(16) + 1;
514 const N: usize = 16;
515 const T: u64 = 2; // plaintext modulus
516 type S = BFV<Q, N, T>;
517
518 const P: u64 = Q * Q;
519 const PQ: u64 = P * Q;
520
521 let mut rng = rand::thread_rng();
522 let msg_dist = Uniform::new(0_u64, T);
523
524 for _ in 0..1_000 {
525 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
526 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
527
528 test_mul_relin_opt::<Q, N, T, PQ>(&mut rng, m1, m2)?;
529 }
530
531 Ok(())
532 }
533
534 fn test_mul_relin_opt<const Q: u64, const N: usize, const T: u64, const PQ: u64>(
535 mut rng: impl Rng,
536 m1: Rq<T, N>,
537 m2: Rq<T, N>,
538 ) -> Result<()> {
539 let (sk, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
540
541 let rlk = BFV::<Q, N, T>::rlk_key::<PQ>(&mut rng, &sk)?;
542
543 let c1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m1)?;
544 let c2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m2)?;
545
546 let c3 = RLWE::<Q, N>::mul::<PQ, T>(&rlk, &c1, &c2); // uses relinearize internally
547
548 let m3 = BFV::<Q, N, T>::decrypt(&sk, &c3);
549
550 let naive = (m1.to_r() * m2.to_r()).to_rq::<T>();
551 assert_eq!(
552 m3.coeffs().to_vec(),
553 naive.coeffs().to_vec(),
554 "\n\nfor testing:\nlet m1 = Rq::<T, N>::from_vec_u64(vec!{:?});\nlet m2 = Rq::<T, N>::from_vec_u64(vec!{:?});\n",
555 m1.coeffs(),
556 m2.coeffs()
557 );
558
559 Ok(())
560 }
561}