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::{anyhow, Result};
9use rand::Rng;
10use rand_distr::{Normal, Uniform};
11use std::ops;
12
13use arithmetic::{Rq, Zq, 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// const ERR_SIGMA: f64 = 0.0; // TODO WIP
19
20#[derive(Clone, Debug)]
21pub struct SecretKey<const Q: u64, const N: usize>(Rq<Q, N>);
22
23#[derive(Clone, Debug)]
24pub struct PublicKey<const Q: u64, const N: usize>(Rq<Q, N>, Rq<Q, N>);
25
26/// Relinearization key
27#[derive(Clone, Debug)]
28pub struct RLK<const PQ: u64, const N: usize>(Rq<PQ, N>, Rq<PQ, N>);
29
30// impl<const PQ: u64, const N: usize> RLK<Q, PQ, N> {
31// // const P: u64 = PQ / Q;
32//
33// // const PQ: u64 = P * Q;
34// }
35
36// RLWE ciphertext
37#[derive(Clone, Debug)]
38pub struct RLWE<const Q: u64, const N: usize>(Rq<Q, N>, Rq<Q, N>);
39
40impl<const Q: u64, const N: usize> RLWE<Q, N> {
41 fn add(lhs: Self, rhs: Self) -> Self {
42 RLWE::<Q, N>(lhs.0 + rhs.0, lhs.1 + rhs.1)
43 }
44 pub fn remodule<const P: u64>(&self) -> RLWE<P, N> {
45 let x = self.0.remodule::<P>();
46 let y = self.1.remodule::<P>();
47 RLWE::<P, N>(x, y)
48 }
49 fn tensor<const PQ: u64, const T: u64>(a: &Self, b: &Self) -> (Rq<Q, N>, Rq<Q, N>, Rq<Q, N>) {
50 // expand Q->PQ // TODO rm
51 // get the coefficients in Z, ie. interpret a,b \in R (instead of R_q)
52 let a0: R<N> = a.0.to_r();
53 let a1: R<N> = a.1.to_r();
54 let b0: R<N> = b.0.to_r();
55 let b1: R<N> = b.1.to_r();
56
57 // tensor (\in R)
58 use arithmetic::ring::naive_mul;
59 let c0: Vec<i64> = naive_mul(&a0, &b0);
60 let c1_l: Vec<i64> = naive_mul(&a0, &b1);
61 let c1_r = naive_mul(&a1, &b0);
62 let c1: Vec<i64> = itertools::zip_eq(c1_l, c1_r).map(|(l, r)| l + r).collect();
63 let c2: Vec<i64> = naive_mul(&a1, &b1);
64
65 // scale down, module Q, so result is \in R_q
66 let c0: Rq<Q, N> = arithmetic::ring::mul_div_round::<Q, N>(c0, T, Q);
67 let c1: Rq<Q, N> = arithmetic::ring::mul_div_round::<Q, N>(c1, T, Q);
68 let c2: Rq<Q, N> = arithmetic::ring::mul_div_round::<Q, N>(c2, T, Q);
69
70 (c0, c1, c2)
71 }
72 fn tensor_DBG<const PQ: u64, const T: u64>(
73 a: &Self,
74 b: &Self,
75 ) -> (Rq<Q, N>, Rq<Q, N>, Rq<Q, N>) {
76 // iacr 2021-204:
77 // expand Q->PQ
78 // let a: RLWE<PQ, N> = a.remodule::<PQ>();
79 // let b: RLWE<PQ, N> = b.remodule::<PQ>();
80
81 // tensor
82 let c0: Rq<Q, N> = a.0 * b.0; // NTT mul
83 let c1: Rq<Q, N> = a.0 * b.1 + a.1 * b.0; // NTT mul
84 let c2: Rq<Q, N> = a.1 * b.1; // NTT mul
85
86 // scale down
87 let c0: Rq<Q, N> = c0.mul_div_round(T, Q);
88 let c1: Rq<Q, N> = c1.mul_div_round(T, Q);
89 let c2: Rq<Q, N> = c2.mul_div_round(T, Q);
90
91 // expand^-1 PQ->Q
92 // let c0: Rq<Q, N> = c0.remodule::<Q>();
93 // let c1: Rq<Q, N> = c1.remodule::<Q>();
94 // let c2: Rq<Q, N> = c2.remodule::<Q>();
95
96 (c0, c1, c2)
97 }
98 /// ciphertext multiplication
99 fn mul<const PQ: u64, const T: u64>(rlk: &RLK<PQ, N>, a: &Self, b: &Self) -> Self {
100 let (c0, c1, c2) = Self::tensor::<PQ, T>(a, b);
101 BFV::<Q, N, T>::relinearize_204::<PQ>(&rlk, &c0, &c1, &c2)
102 }
103}
104// naive mul in the ring Rq, reusing the ring::naive_mul and then applying mod(X^N +1)
105fn tmp_naive_mul<const Q: u64, const N: usize>(a: Rq<Q, N>, b: Rq<Q, N>) -> Rq<Q, N> {
106 Rq::<Q, N>::from_vec_i64(arithmetic::ring::naive_mul(&a.to_r(), &b.to_r()))
107}
108
109impl<const Q: u64, const N: usize> ops::Add<RLWE<Q, N>> for RLWE<Q, N> {
110 type Output = Self;
111 fn add(self, rhs: Self) -> Self {
112 Self::add(self, rhs)
113 }
114}
115
116impl<const Q: u64, const N: usize, const T: u64> ops::Add<&Rq<T, N>> for &RLWE<Q, N> {
117 type Output = RLWE<Q, N>;
118 fn add(self, rhs: &Rq<T, N>) -> Self::Output {
119 BFV::<Q, N, T>::add_const(self, rhs)
120 }
121}
122impl<const Q: u64, const N: usize, const T: u64> ops::Mul<&Rq<T, N>> for &RLWE<Q, N> {
123 type Output = RLWE<Q, N>;
124 fn mul(self, rhs: &Rq<T, N>) -> Self::Output {
125 BFV::<Q, N, T>::mul_const(&self, rhs)
126 }
127}
128
129pub struct BFV<const Q: u64, const N: usize, const T: u64> {}
130
131impl<const Q: u64, const N: usize, const T: u64> BFV<Q, N, T> {
132 const DELTA: u64 = Q / T;
133
134 /// generate a new key pair (privK, pubK)
135 pub fn new_key(mut rng: impl Rng) -> Result<(SecretKey<Q, N>, PublicKey<Q, N>)> {
136 // WIP: review probabilities
137
138 // let Xi_key = Uniform::new(-1_f64, 1_f64);
139 let Xi_key = Uniform::new(0_u64, 2_u64);
140 // let Xi_key = Uniform::new(0_u64, 2_u64);
141 // use rand::distributions::Bernoulli;
142 // let Xi_key = Bernoulli::new(0.5)?;
143 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
144
145 // secret key
146 let s = Rq::<Q, N>::rand_u64(&mut rng, Xi_key)?;
147
148 #[cfg(test)] // sanity check
149 assert!(s.infinity_norm() <= 1, "{:?}", s.coeffs());
150
151 // pk = (-a * s + e, a)
152 let a = Rq::<Q, N>::rand_u64(&mut rng, Uniform::new(0_u64, Q))?;
153 let e = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
154 let pk: PublicKey<Q, N> = PublicKey((&(-a) * &s) + e, a.clone());
155 Ok((SecretKey(s), pk))
156 }
157
158 pub fn encrypt(mut rng: impl Rng, pk: &PublicKey<Q, N>, m: &Rq<T, N>) -> Result<RLWE<Q, N>> {
159 // let Xi_key = Uniform::new(-1_f64, 1_f64);
160 // let Xi_key = Uniform::new(0_f64, 2_f64);
161 let Xi_key = Uniform::new(0_u64, 2_u64);
162 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?;
163
164 let u = Rq::<Q, N>::rand_u64(&mut rng, Xi_key)?;
165 let e_1 = Rq::<Q, N>::rand_f64_abs(&mut rng, Xi_err)?;
166 let e_2 = Rq::<Q, N>::rand_f64_abs(&mut rng, Xi_err)?;
167
168 // println!("{:?}", &e_1.coeffs());
169 // println!("{:?}", &e_2.coeffs());
170
171 #[cfg(test)] // sanity check
172 assert!(u.infinity_norm() <= 1, "{:?}", u.coeffs());
173
174 // migrate m's coeffs to the bigger modulus Q (from T)
175 let m = m.remodule::<Q>();
176 #[cfg(test)]
177 {
178 // sanity check // TODO rm
179 let m_remod_naive =
180 Rq::<Q, N>::from_vec_u64(m.coeffs().iter().map(|m_i| m_i.0).collect());
181 assert_eq!(m_remod_naive, m);
182 }
183
184 // let c0 = &pk.0 * &u + e_1 + m * Self::DELTA;
185 let c0 = &pk.0 * &u + e_1 + m.mul_div_round(Q, T); // TODO use DELTA?
186 let c1 = &pk.1 * &u + e_2;
187 // let c0 = tmp_naive_mul(pk.0, u) + e_1 + m * Self::DELTA;
188 // let c0 = tmp_naive_mul(pk.0, u) + e_1 + m.mul_div_round(Q, T);
189 // let c1 = tmp_naive_mul(pk.1, u)
190 // // &pk.1 * &u
191 // + 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 = arithmetic::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(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 RLWE::<Q, N>(c.0 * m * Self::DELTA, c.1)
223 }
224
225 fn rlk_key<const PQ: u64>(mut rng: impl Rng, s: &SecretKey<Q, N>) -> Result<RLK<PQ, N>> {
226 let Xi_err = Normal::new(0_f64, ERR_SIGMA)?; // TODO review Xi' instead of Xi
227
228 let s = s.0.remodule::<PQ>();
229 let a = Rq::<PQ, N>::rand_u64(&mut rng, Uniform::new(0_u64, PQ))?;
230 let e = Rq::<PQ, N>::rand_f64(&mut rng, Xi_err)?;
231
232 // let rlk_1: Rq<PQ, N> = (&(-a) * &s) - e + (s * s) * P;
233 let P = PQ / Q;
234
235 // let rlk: RLK<PQ, N> = RLK::<PQ, N>((&(-a) * &s) - e + (s * s) * P, a.clone());
236 let rlk: RLK<PQ, N> = RLK::<PQ, N>(
237 -(tmp_naive_mul(a, s) + e) + tmp_naive_mul(s, s) * P,
238 a.clone(),
239 );
240 // let rlk: RLK<PQ, N> = RLK::<PQ, N>(-(&a * &s + e) + (s * s) * P, a.clone());
241
242 // let pq = P * Q;
243 // let a = Rq::<Q, N>::rand_u64(&mut rng, Uniform::new(0_u64, pq))?;
244 // let e = Rq::<Q, N>::rand_f64(&mut rng, Xi_err)?;
245 //
246 // let rlk_0: Rq<Q, N> = (&(-a) * &s) - e + (s * s) * P;
247 // let rlk_0 = rlk_0.remodule::<>();
248 // let rlk: RLK<Q, N> = RLK(rlk_0, a);
249 Ok(rlk)
250 }
251
252 fn relinearize<const PQ: u64>(
253 rlk: &RLK<PQ, N>,
254 c0: &Rq<Q, N>,
255 c1: &Rq<Q, N>,
256 c2: &Rq<Q, N>,
257 ) -> RLWE<Q, N> {
258 let P = PQ / Q;
259
260 // let c2 = c2.remodule::<PQ>();
261 // let c2 = c2.to_r();
262
263 let c2rlk0: Vec<f64> = (c2.to_r() * rlk.0.to_r())
264 .coeffs()
265 .iter()
266 .map(|e| (*e as f64 / P as f64).round())
267 .collect();
268
269 let c2rlk1: Vec<f64> = (c2.to_r() * rlk.1.to_r())
270 .coeffs()
271 .iter()
272 .map(|e| (*e as f64 / P as f64).round())
273 .collect();
274
275 let r0 = Rq::<Q, N>::from_vec_f64(c2rlk0);
276 let r1 = Rq::<Q, N>::from_vec_f64(c2rlk1);
277
278 let res = RLWE::<Q, N>(c0 + &r0, c1 + &r1);
279 res
280 }
281 fn relinearize_204<const PQ: u64>(
282 rlk: &RLK<PQ, N>,
283 c0: &Rq<Q, N>,
284 c1: &Rq<Q, N>,
285 c2: &Rq<Q, N>,
286 ) -> RLWE<Q, N> {
287 let P = PQ / Q;
288
289 // let c2 = c2.remodule::<PQ>();
290 // let c2 = c2.to_r();
291
292 // let c2rlk0: Vec<f64> = (c2.remodule::<PQ>() * rlk.0)
293 use arithmetic::ring::naive_mul;
294 let c2rlk0: Vec<i64> = naive_mul(&c2.to_r(), &rlk.0.to_r());
295 // .coeffs()
296 // .iter()
297 // .map(|e| (*e as f64 / P as f64).round())
298 // .collect();
299
300 let c2rlk1: Vec<i64> = naive_mul(&c2.to_r(), &rlk.1.to_r());
301 // .coeffs()
302 // .iter()
303 // .map(|e| (*e as f64 / P as f64).round())
304 // .collect();
305 //
306 let r0: Rq<Q, N> = arithmetic::ring::mul_div_round::<Q, N>(c2rlk0, 1, P);
307 let r1: Rq<Q, N> = arithmetic::ring::mul_div_round::<Q, N>(c2rlk1, 1, P);
308
309 // let r0 = Rq::<Q, N>::from_vec_f64(c2rlk0);
310 // let r1 = Rq::<Q, N>::from_vec_f64(c2rlk1);
311
312 let res = RLWE::<Q, N>(c0 + &r0, c1 + &r1);
313 res
314 }
315}
316
317#[cfg(test)]
318mod tests {
319 use anyhow::Result;
320 use rand::distributions::Uniform;
321
322 use super::*;
323
324 #[test]
325 fn test_encrypt_decrypt() -> Result<()> {
326 const Q: u64 = 2u64.pow(16) + 1;
327 const N: usize = 32;
328 const T: u64 = 4; // plaintext modulus
329 type S = BFV<Q, N, T>;
330
331 let mut rng = rand::thread_rng();
332
333 for _ in 0..1000 {
334 let (sk, pk) = S::new_key(&mut rng)?;
335
336 let msg_dist = Uniform::new(0_u64, T);
337 let m = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
338
339 let c = S::encrypt(&mut rng, &pk, &m)?;
340 let m_recovered = S::decrypt(&sk, &c);
341
342 assert_eq!(m, m_recovered);
343 }
344
345 Ok(())
346 }
347
348 #[test]
349 fn test_addition() -> Result<()> {
350 const Q: u64 = 2u64.pow(16) + 1;
351 // const N: usize = 32;
352 const N: usize = 4;
353 const T: u64 = 4; // plaintext modulus
354 type S = BFV<Q, N, T>;
355
356 let mut rng = rand::thread_rng();
357
358 let (sk, pk) = S::new_key(&mut rng)?;
359
360 let msg_dist = Uniform::new(0_u64, T);
361 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
362 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
363
364 let c1 = S::encrypt(&mut rng, &pk, &m1)?;
365 let c2 = S::encrypt(&mut rng, &pk, &m2)?;
366
367 let c3 = c1 + c2;
368
369 let m3_recovered = S::decrypt(&sk, &c3);
370
371 assert_eq!(m1 + m2, m3_recovered);
372
373 Ok(())
374 }
375
376 #[test]
377 fn test_constant_add() -> Result<()> {
378 const Q: u64 = 2u64.pow(16) + 1;
379 const N: usize = 32;
380 const T: u64 = 4; // plaintext modulus
381 type S = BFV<Q, N, T>;
382
383 let mut rng = rand::thread_rng();
384
385 let (sk, pk) = S::new_key(&mut rng)?;
386
387 let msg_dist = Uniform::new(0_u64, T);
388 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
389 let m2_const = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
390
391 let c1 = S::encrypt(&mut rng, &pk, &m1)?;
392
393 let c3_add = &c1 + &m2_const;
394 // let c3_mul = &c1 * &m2_const;
395
396 let m3_add_recovered = S::decrypt(&sk, &c3_add);
397 // let m3_mul_recovered = S::decrypt(&sk, &c3_mul);
398
399 assert_eq!(m1 + m2_const, m3_add_recovered);
400 //
401 // let mut mul_res = naive_poly_mul::<T>(&m1.coeffs().to_vec(), &m2_const.coeffs().to_vec());
402 // arithmetic::ring::modulus::<T, N>(&mut mul_res);
403 // dbg!(&mul_res);
404 // let mul_res_2 =
405 // naive_poly_mul_2::<T, N>(&m1.coeffs().to_vec(), &m2_const.coeffs().to_vec());
406 // assert_eq!(mul_res, mul_res_2);
407 // let mul_res = PR::<T, N>::from_vec(mul_res);
408 // assert_eq!(mul_res.coeffs(), m3_mul_recovered.coeffs());
409
410 Ok(())
411 }
412
413 #[test]
414 fn test_tensor() -> Result<()> {
415 const Q: u64 = 2u64.pow(16) + 1; // q prime, and 2^q + 1 shape
416 const N: usize = 8;
417 const T: u64 = 4; // plaintext modulus
418
419 // const P: u64 = Q;
420 const P: u64 = Q * Q;
421 // const P: u64 = 2_u64.pow(13) * Q + 1;
422 const PQ: u64 = P * Q;
423
424 let mut rng = rand::thread_rng();
425
426 let msg_dist = Uniform::new(0_u64, T);
427 for _ in 0..10_000 {
428 let m1 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
429 let m2 = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
430
431 test_tensor_opt::<Q, N, T, PQ>(&mut rng, m1, m2)?;
432 }
433
434 Ok(())
435 }
436 fn test_tensor_opt<const Q: u64, const N: usize, const T: u64, const PQ: u64>(
437 mut rng: impl Rng,
438 m1: Rq<T, N>,
439 m2: Rq<T, N>,
440 ) -> Result<()> {
441 let (sk, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
442
443 let c1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m1)?;
444 let c2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &m2)?;
445
446 let (c_a, c_b, c_c) = RLWE::<Q, N>::tensor::<PQ, T>(&c1, &c2);
447
448 // decrypt non-relinearized mul result
449 let m3: Rq<Q, N> = c_a + c_b * sk.0 + c_c * sk.0 * sk.0;
450 let m3: Rq<Q, N> = m3.mul_div_round(T, Q);
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);
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!(m3.coeffs().to_vec(), naive.coeffs().to_vec(),
547 "\n\nfor testing:\nlet m1 = Rq::<T, N>::from_vec_u64(vec!{:?});\nlet m2 = Rq::<T, N>::from_vec_u64(vec!{:?});\n",
548 m1.coeffs(),
549 m2.coeffs()
550 );
551
552 Ok(())
553 }
554
555 #[test]
556 fn test_naive_mul() -> Result<()> {
557 const Q: u64 = 2u64.pow(16) + 1; // prime, and 2^q + 1 shape
558 const N: usize = 4;
559 const T: u64 = 4; // plaintext modulus
560
561 let mut rng = rand::thread_rng();
562 let msg_dist = Uniform::new(0_u64, T);
563 // for _ in 0..10_000 {
564 for _ in 0..2 {
565 println!("---");
566 // let a = Rq::<Q, N>::rand_u64(&mut rng, msg_dist)?;
567 // let b = Rq::<Q, N>::rand_u64(&mut rng, msg_dist)?;
568 // let a = Rq::<Q, N>::from_vec_u64(vec![Q - 1, Q - 2, Q - 3, Q - 3]);
569 // let b = Rq::<Q, N>::from_vec_u64(vec![Q - 3, Q - 3, Q - 2, Q - 1]);
570 let a = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
571 let b = Rq::<T, N>::rand_u64(&mut rng, msg_dist)?;
572 dbg!(&a);
573 dbg!(&b);
574 let (_, pk) = BFV::<Q, N, T>::new_key(&mut rng)?;
575 let ciph1 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &a)?;
576 let ciph2 = BFV::<Q, N, T>::encrypt(&mut rng, &pk, &b)?;
577 let a = ciph1.0;
578 let b = ciph2.0;
579 dbg!(&a);
580 dbg!(&b);
581
582 let c0: Vec<i64> = arithmetic::ring::naive_mul(&a.to_r(), &b.to_r());
583 let c0 = Rq::<Q, N>::from_vec_i64(c0);
584 let c1 = tmp_naive_mul(a, b); // naive mul
585 let c2: Rq<Q, N> = a * b; // NTT mul
586
587 println!("{:?}", c0.coeffs());
588 println!("{:?}", c1.coeffs());
589 println!("{:?}", c2.coeffs());
590 assert_eq!(c0, c2);
591 assert_eq!(c1, c2);
592
593 // scale by Delta=Q/T
594 let a = a.mul_div_round(Q, T);
595 let b = b.mul_div_round(Q, T);
596 dbg!(&a);
597 dbg!(&b);
598
599 let c0: Vec<i64> = arithmetic::ring::naive_mul(&a.to_r(), &b.to_r());
600 let c0 = Rq::<Q, N>::from_vec_i64(c0);
601 let c1 = tmp_naive_mul(a, b); // naive mul
602 let c2: Rq<Q, N> = a * b; // NTT mul
603
604 println!("{:?}", c0.coeffs());
605 println!("{:?}", c1.coeffs());
606 println!("{:?}", c2.coeffs());
607 assert_eq!(c0, c2);
608 assert_eq!(c1, c2);
609
610 let c0 = c0.mul_div_round(T, Q);
611 let c1 = c1.mul_div_round(T, Q);
612 let c2 = c2.mul_div_round(T, Q);
613 println!("{:?}", c0.coeffs());
614 println!("{:?}", c1.coeffs());
615 println!("{:?}", c2.coeffs());
616 assert_eq!(c0, c2);
617 assert_eq!(c1, c2);
618
619 /*
620 // now same as before, but multiplying by T/Q
621 let c0: Vec<i64> = arithmetic::ring::naive_mul(&a.to_r(), &b.to_r());
622 let c0: Vec<f64> = c0
623 .iter()
624 .map(|e| ((T as f64 * *e as f64) / Q as f64).round())
625 .collect();
626 let c0 = Rq::<Q, N>::from_vec_f64(c0);
627 dbg!(&c0.coeffs());
628
629 let a = a.mul_div_round(T, Q);
630 let b = b.mul_div_round(T, Q);
631 println!("a{:?}", a.coeffs());
632 println!("b{:?}", b.coeffs());
633
634 let c4: Vec<i64> = arithmetic::ring::naive_mul(&a.to_r(), &b.to_r());
635 let c4 = Rq::<Q, N>::from_vec_i64(c4);
636 let c4 = c4.mul_div_round(T, Q);
637
638 let c1 = tmp_naive_mul(a, b); // naive mul
639 let c1 = c1.mul_div_round(T, Q);
640 let c2 = a * b; // NTT mul
641 let c2 = c2.mul_div_round(T, Q);
642
643 println!("{:?}", c0.coeffs());
644 println!("{:?}", c1.coeffs());
645 println!("{:?}", c2.coeffs());
646 println!("{:?}", c4.coeffs());
647 assert_eq!(c0, c2);
648 assert_eq!(c4, c2);
649 assert_eq!(c1, c2);
650 */
651 }
652
653 Ok(())
654 }
655}