poulpy/core/src/test_fft64/grlwe.rs
core/src/test_fft64/grlwe.rsRaw
1#[cfg(test)]
2
3mod tests {
4 use base2k::{FFT64, Module, ScalarZnx, ScalarZnxAlloc, ScratchOwned, Stats, VecZnxOps, ZnxViewMut};
5 use sampling::source::Source;
6
7 use crate::{
8 elem::{FromProdBy, FromProdByScratchSpace, Infos, ProdBy, ProdByScratchSpace},
9 grlwe::GRLWECt,
10 keys::{SecretKey, SecretKeyDft},
11 rgsw::RGSWCt,
12 rlwe::{RLWECtDft, RLWEPt},
13 test_fft64::{grlwe::noise_grlwe_rlwe_product, rgsw::noise_rgsw_rlwe_product},
14 };
15
16 #[test]
17 fn encrypt_sk() {
18 let module: Module<FFT64> = Module::<FFT64>::new(2048);
19 let log_base2k: usize = 8;
20 let log_k_ct: usize = 54;
21 let rows: usize = 4;
22
23 let sigma: f64 = 3.2;
24 let bound: f64 = sigma * 6.0;
25
26 let mut ct: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_ct, rows);
27 let mut pt: RLWEPt<Vec<u8>> = RLWEPt::new(&module, log_base2k, log_k_ct);
28 let mut pt_scalar: ScalarZnx<Vec<u8>> = module.new_scalar_znx(1);
29
30 let mut source_xs: Source = Source::new([0u8; 32]);
31 let mut source_xe: Source = Source::new([0u8; 32]);
32 let mut source_xa: Source = Source::new([0u8; 32]);
33
34 pt_scalar.fill_ternary_hw(0, module.n(), &mut source_xs);
35
36 let mut scratch: ScratchOwned = ScratchOwned::new(
37 GRLWECt::encrypt_sk_scratch_space(&module, ct.size()) | RLWECtDft::decrypt_scratch_space(&module, ct.size()),
38 );
39
40 let mut sk: SecretKey<Vec<u8>> = SecretKey::new(&module);
41 sk.fill_ternary_prob(0.5, &mut source_xs);
42
43 let mut sk_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
44 sk_dft.dft(&module, &sk);
45
46 ct.encrypt_sk(
47 &module,
48 &pt_scalar,
49 &sk_dft,
50 &mut source_xa,
51 &mut source_xe,
52 sigma,
53 bound,
54 scratch.borrow(),
55 );
56
57 let mut ct_rlwe_dft: RLWECtDft<Vec<u8>, FFT64> = RLWECtDft::new(&module, log_base2k, log_k_ct);
58
59 (0..ct.rows()).for_each(|row_i| {
60 ct.get_row(&module, row_i, &mut ct_rlwe_dft);
61 ct_rlwe_dft.decrypt(&module, &mut pt, &sk_dft, scratch.borrow());
62 module.vec_znx_sub_scalar_inplace(&mut pt, 0, row_i, &pt_scalar, 0);
63 let std_pt: f64 = pt.data.std(0, log_base2k) * (log_k_ct as f64).exp2();
64 assert!((sigma - std_pt).abs() <= 0.2, "{} {}", sigma, std_pt);
65 });
66
67 module.free();
68 }
69
70 #[test]
71 fn from_prod_by_grlwe() {
72 let module: Module<FFT64> = Module::<FFT64>::new(2048);
73 let log_base2k: usize = 12;
74 let log_k_grlwe: usize = 60;
75 let rows: usize = (log_k_grlwe + log_base2k - 1) / log_base2k;
76
77 let sigma: f64 = 3.2;
78 let bound: f64 = sigma * 6.0;
79
80 let mut ct_grlwe_s0s1: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
81 let mut ct_grlwe_s1s2: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
82 let mut ct_grlwe_s0s2: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
83
84 let mut source_xs: Source = Source::new([0u8; 32]);
85 let mut source_xe: Source = Source::new([0u8; 32]);
86 let mut source_xa: Source = Source::new([0u8; 32]);
87
88 let mut scratch: ScratchOwned = ScratchOwned::new(
89 GRLWECt::encrypt_sk_scratch_space(&module, ct_grlwe_s0s1.size())
90 | RLWECtDft::decrypt_scratch_space(&module, ct_grlwe_s0s2.size())
91 | GRLWECt::from_prod_by_grlwe_scratch_space(
92 &module,
93 ct_grlwe_s0s2.size(),
94 ct_grlwe_s0s1.size(),
95 ct_grlwe_s1s2.size(),
96 ),
97 );
98
99 let mut sk0: SecretKey<Vec<u8>> = SecretKey::new(&module);
100 sk0.fill_ternary_prob(0.5, &mut source_xs);
101
102 let mut sk0_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
103 sk0_dft.dft(&module, &sk0);
104
105 let mut sk1: SecretKey<Vec<u8>> = SecretKey::new(&module);
106 sk1.fill_ternary_prob(0.5, &mut source_xs);
107
108 let mut sk1_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
109 sk1_dft.dft(&module, &sk1);
110
111 let mut sk2: SecretKey<Vec<u8>> = SecretKey::new(&module);
112 sk2.fill_ternary_prob(0.5, &mut source_xs);
113
114 let mut sk2_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
115 sk2_dft.dft(&module, &sk2);
116
117 // GRLWE_{s1}(s0) = s0 -> s1
118 ct_grlwe_s0s1.encrypt_sk(
119 &module,
120 &sk0.data,
121 &sk1_dft,
122 &mut source_xa,
123 &mut source_xe,
124 sigma,
125 bound,
126 scratch.borrow(),
127 );
128
129 // GRLWE_{s2}(s1) -> s1 -> s2
130 ct_grlwe_s1s2.encrypt_sk(
131 &module,
132 &sk1.data,
133 &sk2_dft,
134 &mut source_xa,
135 &mut source_xe,
136 sigma,
137 bound,
138 scratch.borrow(),
139 );
140
141 // GRLWE_{s1}(s0) (x) GRLWE_{s2}(s1) = GRLWE_{s2}(s0)
142 ct_grlwe_s0s2.from_prod_by_grlwe(&module, &ct_grlwe_s0s1, &ct_grlwe_s1s2, scratch.borrow());
143
144 let mut ct_rlwe_dft_s0s2: RLWECtDft<Vec<u8>, FFT64> = RLWECtDft::new(&module, log_base2k, log_k_grlwe);
145 let mut pt: RLWEPt<Vec<u8>> = RLWEPt::new(&module, log_base2k, log_k_grlwe);
146
147 (0..ct_grlwe_s0s2.rows()).for_each(|row_i| {
148 ct_grlwe_s0s2.get_row(&module, row_i, &mut ct_rlwe_dft_s0s2);
149 ct_rlwe_dft_s0s2.decrypt(&module, &mut pt, &sk2_dft, scratch.borrow());
150 module.vec_znx_sub_scalar_inplace(&mut pt, 0, row_i, &sk0, 0);
151
152 let noise_have: f64 = pt.data.std(0, log_base2k).log2();
153 let noise_want: f64 = noise_grlwe_rlwe_product(
154 module.n() as f64,
155 log_base2k,
156 0.5,
157 0.5,
158 0f64,
159 sigma * sigma,
160 0f64,
161 log_k_grlwe,
162 log_k_grlwe,
163 );
164
165 assert!(
166 (noise_have - noise_want).abs() <= 0.1,
167 "{} {}",
168 noise_have,
169 noise_want
170 );
171 });
172
173 module.free();
174 }
175
176 #[test]
177 fn prod_by_grlwe() {
178 let module: Module<FFT64> = Module::<FFT64>::new(2048);
179 let log_base2k: usize = 12;
180 let log_k_grlwe: usize = 60;
181 let rows: usize = (log_k_grlwe + log_base2k - 1) / log_base2k;
182
183 let sigma: f64 = 3.2;
184 let bound: f64 = sigma * 6.0;
185
186 let mut ct_grlwe_s0s1: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
187 let mut ct_grlwe_s1s2: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
188
189 let mut source_xs: Source = Source::new([0u8; 32]);
190 let mut source_xe: Source = Source::new([0u8; 32]);
191 let mut source_xa: Source = Source::new([0u8; 32]);
192
193 let mut scratch: ScratchOwned = ScratchOwned::new(
194 GRLWECt::encrypt_sk_scratch_space(&module, ct_grlwe_s0s1.size())
195 | RLWECtDft::decrypt_scratch_space(&module, ct_grlwe_s0s1.size())
196 | GRLWECt::prod_by_grlwe_scratch_space(&module, ct_grlwe_s0s1.size(), ct_grlwe_s1s2.size()),
197 );
198
199 let mut sk0: SecretKey<Vec<u8>> = SecretKey::new(&module);
200 sk0.fill_ternary_prob(0.5, &mut source_xs);
201
202 let mut sk0_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
203 sk0_dft.dft(&module, &sk0);
204
205 let mut sk1: SecretKey<Vec<u8>> = SecretKey::new(&module);
206 sk1.fill_ternary_prob(0.5, &mut source_xs);
207
208 let mut sk1_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
209 sk1_dft.dft(&module, &sk1);
210
211 let mut sk2: SecretKey<Vec<u8>> = SecretKey::new(&module);
212 sk2.fill_ternary_prob(0.5, &mut source_xs);
213
214 let mut sk2_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
215 sk2_dft.dft(&module, &sk2);
216
217 // GRLWE_{s1}(s0) = s0 -> s1
218 ct_grlwe_s0s1.encrypt_sk(
219 &module,
220 &sk0.data,
221 &sk1_dft,
222 &mut source_xa,
223 &mut source_xe,
224 sigma,
225 bound,
226 scratch.borrow(),
227 );
228
229 // GRLWE_{s2}(s1) -> s1 -> s2
230 ct_grlwe_s1s2.encrypt_sk(
231 &module,
232 &sk1.data,
233 &sk2_dft,
234 &mut source_xa,
235 &mut source_xe,
236 sigma,
237 bound,
238 scratch.borrow(),
239 );
240
241 // GRLWE_{s1}(s0) (x) GRLWE_{s2}(s1) = GRLWE_{s2}(s0)
242 ct_grlwe_s0s1.prod_by_grlwe(&module, &ct_grlwe_s1s2, scratch.borrow());
243
244 let ct_grlwe_s0s2: GRLWECt<Vec<u8>, FFT64> = ct_grlwe_s0s1;
245
246 let mut ct_rlwe_dft_s0s2: RLWECtDft<Vec<u8>, FFT64> = RLWECtDft::new(&module, log_base2k, log_k_grlwe);
247 let mut pt: RLWEPt<Vec<u8>> = RLWEPt::new(&module, log_base2k, log_k_grlwe);
248
249 (0..ct_grlwe_s0s2.rows()).for_each(|row_i| {
250 ct_grlwe_s0s2.get_row(&module, row_i, &mut ct_rlwe_dft_s0s2);
251 ct_rlwe_dft_s0s2.decrypt(&module, &mut pt, &sk2_dft, scratch.borrow());
252 module.vec_znx_sub_scalar_inplace(&mut pt, 0, row_i, &sk0, 0);
253
254 let noise_have: f64 = pt.data.std(0, log_base2k).log2();
255 let noise_want: f64 = noise_grlwe_rlwe_product(
256 module.n() as f64,
257 log_base2k,
258 0.5,
259 0.5,
260 0f64,
261 sigma * sigma,
262 0f64,
263 log_k_grlwe,
264 log_k_grlwe,
265 );
266
267 assert!(
268 (noise_have - noise_want).abs() <= 0.1,
269 "{} {}",
270 noise_have,
271 noise_want
272 );
273 });
274
275 module.free();
276 }
277
278 #[test]
279 fn from_prod_by_rgsw() {
280 let module: Module<FFT64> = Module::<FFT64>::new(2048);
281 let log_base2k: usize = 12;
282 let log_k_grlwe: usize = 60;
283 let rows: usize = (log_k_grlwe + log_base2k - 1) / log_base2k;
284
285 let sigma: f64 = 3.2;
286 let bound: f64 = sigma * 6.0;
287
288 let mut ct_grlwe_in: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
289 let mut ct_grlwe_out: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
290 let mut ct_rgsw: RGSWCt<Vec<u8>, FFT64> = RGSWCt::new(&module, log_base2k, log_k_grlwe, rows);
291
292 let mut pt_rgsw: ScalarZnx<Vec<u8>> = module.new_scalar_znx(1);
293 let mut pt_grlwe: ScalarZnx<Vec<u8>> = module.new_scalar_znx(1);
294
295 let mut source_xs: Source = Source::new([0u8; 32]);
296 let mut source_xe: Source = Source::new([0u8; 32]);
297 let mut source_xa: Source = Source::new([0u8; 32]);
298
299 let mut scratch: ScratchOwned = ScratchOwned::new(
300 GRLWECt::encrypt_sk_scratch_space(&module, ct_grlwe_in.size())
301 | RLWECtDft::decrypt_scratch_space(&module, ct_grlwe_out.size())
302 | GRLWECt::from_prod_by_rgsw_scratch_space(
303 &module,
304 ct_grlwe_out.size(),
305 ct_grlwe_in.size(),
306 ct_rgsw.size(),
307 )
308 | RGSWCt::encrypt_sk_scratch_space(&module, ct_rgsw.size()),
309 );
310
311 let k: usize = 1;
312
313 pt_rgsw.raw_mut()[k] = 1; // X^{k}
314
315 pt_grlwe.fill_ternary_prob(0, 0.5, &mut source_xs);
316
317 let mut sk: SecretKey<Vec<u8>> = SecretKey::new(&module);
318 sk.fill_ternary_prob(0.5, &mut source_xs);
319
320 let mut sk_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
321 sk_dft.dft(&module, &sk);
322
323 // GRLWE_{s1}(s0) = s0 -> s1
324 ct_grlwe_in.encrypt_sk(
325 &module,
326 &pt_grlwe,
327 &sk_dft,
328 &mut source_xa,
329 &mut source_xe,
330 sigma,
331 bound,
332 scratch.borrow(),
333 );
334
335 ct_rgsw.encrypt_sk(
336 &module,
337 &pt_rgsw,
338 &sk_dft,
339 &mut source_xa,
340 &mut source_xe,
341 sigma,
342 bound,
343 scratch.borrow(),
344 );
345
346 // GRLWE_(m) (x) RGSW_(X^k) = GRLWE_(m * X^k)
347 ct_grlwe_out.from_prod_by_rgsw(&module, &ct_grlwe_in, &ct_rgsw, scratch.borrow());
348
349 let mut ct_rlwe_dft_s0s2: RLWECtDft<Vec<u8>, FFT64> = RLWECtDft::new(&module, log_base2k, log_k_grlwe);
350 let mut pt: RLWEPt<Vec<u8>> = RLWEPt::new(&module, log_base2k, log_k_grlwe);
351
352 module.vec_znx_rotate_inplace(k as i64, &mut pt_grlwe, 0);
353
354 (0..ct_grlwe_out.rows()).for_each(|row_i| {
355 ct_grlwe_out.get_row(&module, row_i, &mut ct_rlwe_dft_s0s2);
356 ct_rlwe_dft_s0s2.decrypt(&module, &mut pt, &sk_dft, scratch.borrow());
357 module.vec_znx_sub_scalar_inplace(&mut pt, 0, row_i, &pt_grlwe, 0);
358
359 let noise_have: f64 = pt.data.std(0, log_base2k).log2();
360
361 let var_gct_err_lhs: f64 = sigma * sigma;
362 let var_gct_err_rhs: f64 = 0f64;
363
364 let var_msg: f64 = 1f64 / module.n() as f64; // X^{k}
365 let var_a0_err: f64 = sigma * sigma;
366 let var_a1_err: f64 = 1f64 / 12f64;
367
368 let noise_want: f64 = noise_rgsw_rlwe_product(
369 module.n() as f64,
370 log_base2k,
371 0.5,
372 var_msg,
373 var_a0_err,
374 var_a1_err,
375 var_gct_err_lhs,
376 var_gct_err_rhs,
377 log_k_grlwe,
378 log_k_grlwe,
379 );
380
381 assert!(
382 (noise_have - noise_want).abs() <= 0.1,
383 "{} {}",
384 noise_have,
385 noise_want
386 );
387 });
388
389 module.free();
390 }
391
392 #[test]
393 fn prod_by_rgsw() {
394 let module: Module<FFT64> = Module::<FFT64>::new(2048);
395 let log_base2k: usize = 12;
396 let log_k_grlwe: usize = 60;
397 let rows: usize = (log_k_grlwe + log_base2k - 1) / log_base2k;
398
399 let sigma: f64 = 3.2;
400 let bound: f64 = sigma * 6.0;
401
402 let mut ct_grlwe: GRLWECt<Vec<u8>, FFT64> = GRLWECt::new(&module, log_base2k, log_k_grlwe, rows);
403 let mut ct_rgsw: RGSWCt<Vec<u8>, FFT64> = RGSWCt::new(&module, log_base2k, log_k_grlwe, rows);
404
405 let mut pt_rgsw: ScalarZnx<Vec<u8>> = module.new_scalar_znx(1);
406 let mut pt_grlwe: ScalarZnx<Vec<u8>> = module.new_scalar_znx(1);
407
408 let mut source_xs: Source = Source::new([0u8; 32]);
409 let mut source_xe: Source = Source::new([0u8; 32]);
410 let mut source_xa: Source = Source::new([0u8; 32]);
411
412 let mut scratch: ScratchOwned = ScratchOwned::new(
413 GRLWECt::encrypt_sk_scratch_space(&module, ct_grlwe.size())
414 | RLWECtDft::decrypt_scratch_space(&module, ct_grlwe.size())
415 | GRLWECt::prod_by_rgsw_scratch_space(&module, ct_grlwe.size(), ct_rgsw.size())
416 | RGSWCt::encrypt_sk_scratch_space(&module, ct_rgsw.size()),
417 );
418
419 let k: usize = 1;
420
421 pt_rgsw.raw_mut()[k] = 1; // X^{k}
422
423 pt_grlwe.fill_ternary_prob(0, 0.5, &mut source_xs);
424
425 let mut sk: SecretKey<Vec<u8>> = SecretKey::new(&module);
426 sk.fill_ternary_prob(0.5, &mut source_xs);
427
428 let mut sk_dft: SecretKeyDft<Vec<u8>, FFT64> = SecretKeyDft::new(&module);
429 sk_dft.dft(&module, &sk);
430
431 // GRLWE_{s1}(s0) = s0 -> s1
432 ct_grlwe.encrypt_sk(
433 &module,
434 &pt_grlwe,
435 &sk_dft,
436 &mut source_xa,
437 &mut source_xe,
438 sigma,
439 bound,
440 scratch.borrow(),
441 );
442
443 ct_rgsw.encrypt_sk(
444 &module,
445 &pt_rgsw,
446 &sk_dft,
447 &mut source_xa,
448 &mut source_xe,
449 sigma,
450 bound,
451 scratch.borrow(),
452 );
453
454 // GRLWE_(m) (x) RGSW_(X^k) = GRLWE_(m * X^k)
455 ct_grlwe.prod_by_rgsw(&module, &ct_rgsw, scratch.borrow());
456
457 let mut ct_rlwe_dft_s0s2: RLWECtDft<Vec<u8>, FFT64> = RLWECtDft::new(&module, log_base2k, log_k_grlwe);
458 let mut pt: RLWEPt<Vec<u8>> = RLWEPt::new(&module, log_base2k, log_k_grlwe);
459
460 module.vec_znx_rotate_inplace(k as i64, &mut pt_grlwe, 0);
461
462 (0..ct_grlwe.rows()).for_each(|row_i| {
463 ct_grlwe.get_row(&module, row_i, &mut ct_rlwe_dft_s0s2);
464 ct_rlwe_dft_s0s2.decrypt(&module, &mut pt, &sk_dft, scratch.borrow());
465 module.vec_znx_sub_scalar_inplace(&mut pt, 0, row_i, &pt_grlwe, 0);
466
467 let noise_have: f64 = pt.data.std(0, log_base2k).log2();
468
469 let var_gct_err_lhs: f64 = sigma * sigma;
470 let var_gct_err_rhs: f64 = 0f64;
471
472 let var_msg: f64 = 1f64 / module.n() as f64; // X^{k}
473 let var_a0_err: f64 = sigma * sigma;
474 let var_a1_err: f64 = 1f64 / 12f64;
475
476 let noise_want: f64 = noise_rgsw_rlwe_product(
477 module.n() as f64,
478 log_base2k,
479 0.5,
480 var_msg,
481 var_a0_err,
482 var_a1_err,
483 var_gct_err_lhs,
484 var_gct_err_rhs,
485 log_k_grlwe,
486 log_k_grlwe,
487 );
488
489 assert!(
490 (noise_have - noise_want).abs() <= 0.1,
491 "{} {}",
492 noise_have,
493 noise_want
494 );
495 });
496
497 module.free();
498 }
499}
500
501#[allow(dead_code)]
502pub(crate) fn noise_grlwe_rlwe_product(
503 n: f64,
504 log_base2k: usize,
505 var_xs: f64,
506 var_msg: f64,
507 var_a_err: f64,
508 var_gct_err_lhs: f64,
509 var_gct_err_rhs: f64,
510 a_logq: usize,
511 b_logq: usize,
512) -> f64 {
513 let a_logq: usize = a_logq.min(b_logq);
514 let a_cols: usize = (a_logq + log_base2k - 1) / log_base2k;
515
516 let b_scale = 2.0f64.powi(b_logq as i32);
517 let a_scale: f64 = 2.0f64.powi((b_logq - a_logq) as i32);
518
519 let base: f64 = (1 << (log_base2k)) as f64;
520 let var_base: f64 = base * base / 12f64;
521
522 // lhs = a_cols * n * (var_base * var_gct_err_lhs + var_e_a * var_msg * p^2)
523 // rhs = a_cols * n * var_base * var_gct_err_rhs * var_xs
524 let mut noise: f64 = (a_cols as f64) * n * var_base * (var_gct_err_lhs + var_xs * var_gct_err_rhs);
525 noise += var_msg * var_a_err * a_scale * a_scale * n;
526 noise = noise.sqrt();
527 noise /= b_scale;
528 noise.log2().min(-1.0) // max noise is [-2^{-1}, 2^{-1}]
529}