phantom-zone/src/bool/print_noise.rs
src/bool/print_noise.rsRaw
1use std::{fmt::Debug, iter::Sum};
2
3use itertools::izip;
4use num_traits::{FromPrimitive, PrimInt, Zero};
5use rand_distr::uniform::SampleUniform;
6
7use crate::{
8 backend::{GetModulus, Modulus},
9 decomposer::{Decomposer, NumInfo, RlweDecomposer},
10 lwe::{decrypt_lwe, lwe_key_switch},
11 parameters::{BoolParameters, CiphertextModulus},
12 random::{DefaultSecureRng, RandomFillUniformInModulus},
13 rgsw::{
14 decrypt_rlwe, rlwe_auto, rlwe_auto_scratch_rows, RlweCiphertextMutRef, RlweKskRef,
15 RuntimeScratchMutRef,
16 },
17 utils::{encode_x_pow_si_with_emebedding_factor, tests::Stats, TryConvertFrom1},
18 ArithmeticOps, ClientKey, MatrixEntity, MatrixMut, ModInit, Ntt, NttInit, RowEntity, RowMut,
19 VectorOps,
20};
21
22use super::keys::tests::{ideal_sk_lwe, ideal_sk_rlwe};
23
24pub(crate) trait CollectRuntimeServerKeyStats {
25 type M;
26 /// RGSW ciphertext X^{s[s_index]} in evaluation domain where `s` the LWE
27 /// secret
28 fn rgsw_cts_lwe_si(&self, s_index: usize) -> &Self::M;
29 /// Auto key in evaluation domain for automorphism g^k. For auto key for
30 /// automorphism corresponding to -g, set k = 0
31 fn galois_key_for_auto(&self, k: usize) -> &Self::M;
32 /// LWE key switching key
33 fn lwe_ksk(&self) -> &Self::M;
34}
35
36#[derive(Default)]
37struct ServerKeyStats<T> {
38 /// Distribution of noise in RGSW ciphertexts
39 ///
40 /// We collect statistics for RLWE'(-sm) separately from RLWE'(m) because
41 /// non-interactive protocol differents between the two. Although we expect
42 /// the distribution of noise in both to be the same.
43 brk_rgsw_cts: (Stats<T>, Stats<T>),
44 /// Distribtion of noise added to RLWE ciphertext after automorphism using
45 /// Server auto keys.
46 post_1_auto: Stats<T>,
47 /// Distribution of noise added in LWE key switching from LWE_{q, s} to
48 /// LWE_{q, z} where `z` is ideal LWE secret and `s` is ideal RLWE secret
49 /// using Server's LWE key switching key.
50 post_lwe_key_switch: Stats<T>,
51}
52
53impl<T: PrimInt + FromPrimitive + Debug + Sum> ServerKeyStats<T>
54where
55 T: for<'a> Sum<&'a T>,
56{
57 fn new() -> Self {
58 ServerKeyStats {
59 brk_rgsw_cts: (Stats::default(), Stats::default()),
60 post_1_auto: Stats::default(),
61 post_lwe_key_switch: Stats::default(),
62 }
63 }
64
65 fn add_noise_brk_rgsw_cts_nsm(&mut self, noise: &[T]) {
66 self.brk_rgsw_cts.0.add_many_samples(noise);
67 }
68
69 fn add_noise_brk_rgsw_cts_m(&mut self, noise: &[T]) {
70 self.brk_rgsw_cts.1.add_many_samples(noise);
71 }
72
73 fn add_noise_post_1_auto(&mut self, noise: &[T]) {
74 self.post_1_auto.add_many_samples(&noise);
75 }
76
77 fn add_noise_post_kwe_key_switch(&mut self, noise: &[T]) {
78 self.post_lwe_key_switch.add_many_samples(&noise);
79 }
80
81 fn merge_in(&mut self, other: &Self) {
82 self.brk_rgsw_cts.0.merge_in(&other.brk_rgsw_cts.0);
83 self.brk_rgsw_cts.1.merge_in(&other.brk_rgsw_cts.1);
84
85 self.post_1_auto.merge_in(&other.post_1_auto);
86 self.post_lwe_key_switch
87 .merge_in(&other.post_lwe_key_switch);
88 }
89}
90
91fn collect_server_key_stats<
92 M: MatrixEntity + MatrixMut,
93 D: Decomposer<Element = M::MatElement>,
94 NttOp: NttInit<CiphertextModulus<M::MatElement>> + Ntt<Element = M::MatElement>,
95 ModOp: VectorOps<Element = M::MatElement>
96 + ArithmeticOps<Element = M::MatElement>
97 + ModInit<M = CiphertextModulus<M::MatElement>>
98 + GetModulus<M = CiphertextModulus<M::MatElement>, Element = M::MatElement>,
99 S: CollectRuntimeServerKeyStats<M = M>,
100>(
101 parameters: BoolParameters<M::MatElement>,
102 client_keys: &[ClientKey],
103 server_key: &S,
104) -> ServerKeyStats<i64>
105where
106 M::R: RowMut + RowEntity + TryConvertFrom1<[i32], CiphertextModulus<M::MatElement>> + Clone,
107 M::MatElement: Copy + PrimInt + FromPrimitive + SampleUniform + Zero + Debug + NumInfo,
108{
109 let ideal_sk_rlwe = ideal_sk_rlwe(client_keys);
110 let ideal_sk_lwe = ideal_sk_lwe(client_keys);
111
112 let embedding_factor = (2 * parameters.rlwe_n().0) / parameters.br_q();
113 let rlwe_n = parameters.rlwe_n().0;
114 let rlwe_q = parameters.rlwe_q();
115 let lwe_q = parameters.lwe_q();
116 let rlwe_modop = ModOp::new(rlwe_q.clone());
117 let rlwe_nttop = NttOp::new(rlwe_q, rlwe_n);
118 let lwe_modop = ModOp::new(*parameters.lwe_q());
119
120 let rlwe_x_rgsw_decomposer = parameters.rlwe_rgsw_decomposer::<D>();
121 let (rlwe_x_rgsw_gadget_a, rlwe_x_rgsw_gadget_b) = (
122 rlwe_x_rgsw_decomposer.a().gadget_vector(),
123 rlwe_x_rgsw_decomposer.b().gadget_vector(),
124 );
125
126 let lwe_ks_decomposer = parameters.lwe_decomposer::<D>();
127
128 let mut server_key_stats = ServerKeyStats::new();
129
130 let mut rng = DefaultSecureRng::new();
131
132 // RGSW ciphertext noise
133 // Check noise in RGSW ciphertexts of ideal LWE secret elements
134 {
135 ideal_sk_lwe.iter().enumerate().for_each(|(s_index, s_i)| {
136 let rgsw_ct_i = server_key.rgsw_cts_lwe_si(s_index);
137
138 // X^{s[i]}
139 let m_si = encode_x_pow_si_with_emebedding_factor::<M::R, _>(
140 *s_i,
141 embedding_factor,
142 rlwe_n,
143 rlwe_q,
144 );
145
146 // RLWE'(-sm)
147 let mut neg_s_eval = M::R::try_convert_from(ideal_sk_rlwe.as_slice(), rlwe_q);
148 rlwe_modop.elwise_neg_mut(neg_s_eval.as_mut());
149 rlwe_nttop.forward(neg_s_eval.as_mut());
150
151 for j in 0..rlwe_x_rgsw_decomposer.a().decomposition_count().0 {
152 // RLWE(B^{j} * -s[X]*X^{s_lwe[i]})
153
154 // -s[X]*X^{s_lwe[i]}*B_j
155 let mut m_ideal = m_si.clone();
156 rlwe_nttop.forward(m_ideal.as_mut());
157 rlwe_modop.elwise_mul_mut(m_ideal.as_mut(), neg_s_eval.as_ref());
158 rlwe_nttop.backward(m_ideal.as_mut());
159 rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut(), &rlwe_x_rgsw_gadget_a[j]);
160
161 // RLWE(-s*X^{s_lwe[i]}*B_j)
162 let mut rlwe_ct = M::zeros(2, rlwe_n);
163 rlwe_ct
164 .get_row_mut(0)
165 .copy_from_slice(rgsw_ct_i.get_row_slice(j));
166 rlwe_ct.get_row_mut(1).copy_from_slice(
167 rgsw_ct_i.get_row_slice(j + rlwe_x_rgsw_decomposer.a().decomposition_count().0),
168 );
169 // RGSW ciphertexts are in eval domain. We put RLWE ciphertexts back in
170 // coefficient domain
171 rlwe_ct
172 .iter_rows_mut()
173 .for_each(|r| rlwe_nttop.backward(r.as_mut()));
174
175 let mut m_back = M::R::zeros(rlwe_n);
176 decrypt_rlwe(
177 &rlwe_ct,
178 &ideal_sk_rlwe,
179 &mut m_back,
180 &rlwe_nttop,
181 &rlwe_modop,
182 );
183
184 // diff
185 rlwe_modop.elwise_sub_mut(m_back.as_mut(), m_ideal.as_ref());
186 server_key_stats.add_noise_brk_rgsw_cts_nsm(&Vec::<i64>::try_convert_from(
187 m_back.as_ref(),
188 rlwe_q,
189 ));
190 }
191
192 // RLWE'(m)
193 for j in 0..rlwe_x_rgsw_decomposer.b().decomposition_count().0 {
194 // RLWE(B^{j} * X^{s_lwe[i]})
195
196 // X^{s_lwe[i]}*B_j
197 let mut m_ideal = m_si.clone();
198 rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut(), &rlwe_x_rgsw_gadget_b[j]);
199
200 // RLWE(X^{s_lwe[i]}*B_j)
201 let mut rlwe_ct = M::zeros(2, rlwe_n);
202 rlwe_ct.get_row_mut(0).copy_from_slice(
203 rgsw_ct_i.get_row_slice(
204 j + (2 * rlwe_x_rgsw_decomposer.a().decomposition_count().0),
205 ),
206 );
207 rlwe_ct
208 .get_row_mut(1)
209 .copy_from_slice(rgsw_ct_i.get_row_slice(
210 j + (2 * rlwe_x_rgsw_decomposer.a().decomposition_count().0)
211 + rlwe_x_rgsw_decomposer.b().decomposition_count().0,
212 ));
213 rlwe_ct
214 .iter_rows_mut()
215 .for_each(|r| rlwe_nttop.backward(r.as_mut()));
216
217 let mut m_back = M::R::zeros(rlwe_n);
218 decrypt_rlwe(
219 &rlwe_ct,
220 &ideal_sk_rlwe,
221 &mut m_back,
222 &rlwe_nttop,
223 &rlwe_modop,
224 );
225
226 // diff
227 rlwe_modop.elwise_sub_mut(m_back.as_mut(), m_ideal.as_ref());
228 server_key_stats.add_noise_brk_rgsw_cts_m(&Vec::<i64>::try_convert_from(
229 m_back.as_ref(),
230 rlwe_q,
231 ));
232 }
233 });
234 }
235
236 // Noise in ciphertext after 1 auto
237 // For each auto key g^k. Sample random polynomial m(X) and multiply with
238 // -s(X^{g^k}) using key corresponding to auto g^k. Then check the noise in
239 // resutling RLWE(m(X) * -s(X^{g^k}))
240 {
241 let neg_s = {
242 let mut s = M::R::try_convert_from(ideal_sk_rlwe.as_slice(), rlwe_q);
243 rlwe_modop.elwise_neg_mut(s.as_mut());
244 s
245 };
246 let g = parameters.g();
247 let br_q = parameters.br_q();
248 let g_dlogs = parameters.auto_element_dlogs();
249 let auto_decomposer = parameters.auto_decomposer::<D>();
250 let mut scratch_matrix = M::zeros(rlwe_auto_scratch_rows(&auto_decomposer), rlwe_n);
251 let mut scratch_matrix_ref = RuntimeScratchMutRef::new(scratch_matrix.as_mut());
252
253 g_dlogs.iter().for_each(|k| {
254 let g_pow_k = if *k == 0 {
255 -(g as isize)
256 } else {
257 (g.pow(*k as u32) % br_q) as isize
258 };
259
260 // Send s(X) -> s(X^{g^k})
261 let (auto_index_map, auto_sign_map) = crate::rgsw::generate_auto_map(rlwe_n, g_pow_k);
262 let mut neg_s_g_k = M::R::zeros(rlwe_n);
263 izip!(
264 neg_s.as_ref().iter(),
265 auto_index_map.iter(),
266 auto_sign_map.iter()
267 )
268 .for_each(|(el, to_index, to_sign)| {
269 if !to_sign {
270 neg_s_g_k.as_mut()[*to_index] = rlwe_modop.neg(el);
271 } else {
272 neg_s_g_k.as_mut()[*to_index] = *el;
273 }
274 });
275
276 let mut m = M::R::zeros(rlwe_n);
277 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut());
278
279 // We want -m(X^{g^k})s(X^{g^k}) after key switch
280 let want_m = {
281 let mut m_g_k_eval = M::R::zeros(rlwe_n);
282 // send m(X) -> m(X^{g^k})
283 izip!(
284 m.as_ref().iter(),
285 auto_index_map.iter(),
286 auto_sign_map.iter()
287 )
288 .for_each(|(el, to_index, to_sign)| {
289 if !to_sign {
290 m_g_k_eval.as_mut()[*to_index] = rlwe_modop.neg(el);
291 } else {
292 m_g_k_eval.as_mut()[*to_index] = *el;
293 }
294 });
295
296 rlwe_nttop.forward(m_g_k_eval.as_mut());
297 let mut s_g_k = neg_s_g_k.clone();
298 rlwe_nttop.forward(s_g_k.as_mut());
299 rlwe_modop.elwise_mul_mut(m_g_k_eval.as_mut(), s_g_k.as_ref());
300 rlwe_nttop.backward(m_g_k_eval.as_mut());
301 m_g_k_eval
302 };
303
304 // RLWE auto sends part A, A(X), of RLWE to A(X^{g^k}) and then multiplies it
305 // with -s(X^{g^k}) using auto key. Deliberately set RLWE = (0, m(X))
306 // (ie. m in part A) to get back RLWE(-m(X^{g^k})s(X^{g^k}))
307 let mut rlwe = M::zeros(2, rlwe_n);
308 rlwe.get_row_mut(0).copy_from_slice(m.as_ref());
309
310 rlwe_auto(
311 &mut RlweCiphertextMutRef::new(rlwe.as_mut()),
312 &RlweKskRef::new(
313 server_key.galois_key_for_auto(*k).as_ref(),
314 auto_decomposer.decomposition_count().0,
315 ),
316 &mut scratch_matrix_ref,
317 &auto_index_map,
318 &auto_sign_map,
319 &rlwe_modop,
320 &rlwe_nttop,
321 &auto_decomposer,
322 false,
323 );
324
325 // decrypt RLWE(-m(X)s(X^{g^k]}))
326 let mut back_m = M::R::zeros(rlwe_n);
327 decrypt_rlwe(&rlwe, &ideal_sk_rlwe, &mut back_m, &rlwe_nttop, &rlwe_modop);
328
329 // check difference
330 let mut diff = back_m;
331 rlwe_modop.elwise_sub_mut(diff.as_mut(), want_m.as_ref());
332 server_key_stats
333 .add_noise_post_1_auto(&Vec::<i64>::try_convert_from(diff.as_ref(), rlwe_q));
334 });
335
336 // sample random m
337
338 // key switch
339 }
340
341 // LWE Key switch
342 // LWE key switches LWE_in = LWE_{Q_ks,N, s}(m) = (b, a_0, ... a_N) -> LWE_out =
343 // LWE_{Q_{ks}, n, z}(m) = (b', a'_0, ..., a'n)
344 // If LWE_in = (0, a = {a_0, ..., a_N}), then LWE_out = LWE(-a \cdot s_{rlwe})
345 for _ in 0..100 {
346 let mut lwe_in = M::R::zeros(rlwe_n + 1);
347 RandomFillUniformInModulus::random_fill(&mut rng, lwe_q, &mut lwe_in.as_mut()[1..]);
348
349 // Key switch
350 let mut lwe_out = M::R::zeros(parameters.lwe_n().0 + 1);
351 lwe_key_switch(
352 &mut lwe_out,
353 &lwe_in,
354 server_key.lwe_ksk(),
355 &lwe_modop,
356 &lwe_ks_decomposer,
357 );
358
359 // -a \cdot s
360 let mut want_m = M::MatElement::zero();
361 izip!(lwe_in.as_ref().iter().skip(1), ideal_sk_rlwe.iter()).for_each(|(a, b)| {
362 want_m = lwe_modop.add(
363 &want_m,
364 &lwe_modop.mul(a, &lwe_q.map_element_from_i64(*b as i64)),
365 );
366 });
367 want_m = lwe_modop.neg(&want_m);
368
369 // decrypt lwe out
370 let back_m = decrypt_lwe(&lwe_out, &ideal_sk_lwe, &lwe_modop);
371
372 let noise = lwe_modop.sub(&want_m, &back_m);
373 server_key_stats.add_noise_post_kwe_key_switch(&vec![lwe_q.map_element_to_i64(&noise)]);
374 }
375
376 server_key_stats
377 // Auto keys noise
378
379 // Ksk noise
380}
381
382#[cfg(test)]
383mod tests {
384 use itertools::Itertools;
385
386 #[test]
387 #[cfg(feature = "interactive_mp")]
388 fn interactive_key_noise() {
389 use crate::{
390 aggregate_public_key_shares, aggregate_server_key_shares,
391 bool::{
392 evaluator::InteractiveMultiPartyCrs,
393 keys::{key_size::KeySize, ServerKeyEvaluationDomain},
394 },
395 gen_client_key, gen_mp_keys_phase2, interactive_multi_party_round1_share,
396 parameters::CiphertextModulus,
397 random::DefaultSecureRng,
398 set_common_reference_seed, set_parameter_set,
399 utils::WithLocal,
400 BoolEvaluator, DefaultDecomposer, ModularOpsU64, NttBackendU64,
401 };
402
403 use super::*;
404
405 set_parameter_set(crate::ParameterSelector::InteractiveLTE8Party);
406 set_common_reference_seed(InteractiveMultiPartyCrs::random().seed);
407 let parties = 8;
408
409 let mut server_key_stats = ServerKeyStats::default();
410 let mut server_key_share_size = 0usize;
411
412 for i in 0..2 {
413 let cks = (0..parties).map(|_| gen_client_key()).collect_vec();
414 let pk_shares = cks
415 .iter()
416 .map(|k| interactive_multi_party_round1_share(k))
417 .collect_vec();
418
419 let pk = aggregate_public_key_shares(&pk_shares);
420 let server_key_shares = cks
421 .iter()
422 .enumerate()
423 .map(|(index, k)| gen_mp_keys_phase2(k, index, parties, &pk))
424 .collect_vec();
425
426 // In 0th iteration measure server key size
427 if i == 0 {
428 // Server key share size of user with last id may not equal server key share
429 // sizes of other users if LWE dimension does not divides number of parties.
430 server_key_share_size = std::cmp::max(
431 server_key_shares.first().unwrap().size(),
432 server_key_shares.last().unwrap().size(),
433 );
434 }
435
436 // println!("Size: {}", server_key_shares[0].size());
437 let seeded_server_key = aggregate_server_key_shares(&server_key_shares);
438 let server_key_eval =
439 ServerKeyEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
440 &seeded_server_key,
441 );
442
443 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
444 server_key_stats.merge_in(&collect_server_key_stats::<
445 _,
446 DefaultDecomposer<u64>,
447 NttBackendU64,
448 ModularOpsU64<CiphertextModulus<u64>>,
449 _,
450 >(parameters, &cks, &server_key_eval));
451 }
452
453 println!(
454 "Common reference seeded server key share key size: {} Bits",
455 server_key_share_size
456 );
457
458 println!(
459 "Rgsw nsm std log2 {}",
460 server_key_stats.brk_rgsw_cts.0.std_dev().log2()
461 );
462 println!(
463 "Rgsw m std log2 {}",
464 server_key_stats.brk_rgsw_cts.1.std_dev().log2()
465 );
466 println!(
467 "rlwe post 1 auto std log2 {}",
468 server_key_stats.post_1_auto.std_dev().log2()
469 );
470 println!(
471 "key switching noise rlwe secret s to lwe secret z std log2 {}",
472 server_key_stats.post_lwe_key_switch.std_dev().log2()
473 );
474 }
475
476 const K: usize = 10;
477
478 #[test]
479 #[cfg(feature = "interactive_mp")]
480 fn interactive_mp_bool_gates() {
481 use rand::{thread_rng, RngCore};
482
483 use crate::{
484 aggregate_public_key_shares, aggregate_server_key_shares,
485 backend::Modulus,
486 bool::{
487 keys::{
488 tests::{ideal_sk_rlwe, measure_noise_lwe},
489 ServerKeyEvaluationDomain,
490 },
491 print_noise::collect_server_key_stats,
492 },
493 gen_client_key, gen_mp_keys_phase2, interactive_multi_party_round1_share,
494 parameters::CiphertextModulus,
495 random::DefaultSecureRng,
496 set_common_reference_seed, set_parameter_set,
497 utils::{tests::Stats, Global, WithLocal},
498 BoolEvaluator, BooleanGates, DefaultDecomposer, Encoder, Encryptor, ModInit,
499 ModularOpsU64, MultiPartyDecryptor, NttBackendU64, ParameterSelector, RuntimeServerKey,
500 };
501
502 set_parameter_set(ParameterSelector::InteractiveLTE8Party);
503
504 let mut seed = [0u8; 32];
505 thread_rng().fill_bytes(&mut seed);
506 set_common_reference_seed(seed);
507
508 let no_of_parties = 8;
509
510 let cks = (0..no_of_parties).map(|_| gen_client_key()).collect_vec();
511
512 // round 1
513 let pk_shares = cks
514 .iter()
515 .map(|k| interactive_multi_party_round1_share(k))
516 .collect_vec();
517
518 let pk = aggregate_public_key_shares(&pk_shares);
519
520 // round 2
521 let server_key_shares = cks
522 .iter()
523 .enumerate()
524 .map(|(user_id, k)| gen_mp_keys_phase2(k, user_id, no_of_parties, &pk))
525 .collect_vec();
526
527 let server_key = aggregate_server_key_shares(&server_key_shares);
528 server_key.set_server_key();
529
530 let mut m0 = false;
531 let mut m1 = true;
532
533 let mut ct0 = pk.encrypt(&m0);
534 let mut ct1 = pk.encrypt(&m1);
535
536 let ideal_sk_rlwe = ideal_sk_rlwe(&cks);
537 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
538 let rlwe_modop = ModularOpsU64::new(*parameters.rlwe_q());
539
540 let mut stats = Stats::new();
541
542 for _ in 0..K {
543 // let now = std::time::Instant::now();
544 let ct_out =
545 BoolEvaluator::with_local_mut(|e| e.xor(&ct0, &ct1, RuntimeServerKey::global()));
546 // println!("Time: {:?}", now.elapsed());
547
548 let m_expected = m0 ^ m1;
549
550 let decryption_shares = cks
551 .iter()
552 .map(|k| k.gen_decryption_share(&ct_out))
553 .collect_vec();
554 let m_out = cks[0].aggregate_decryption_shares(&ct_out, &decryption_shares);
555
556 assert!(m_out == m_expected, "Expected {m_expected}, got {m_out}");
557
558 {
559 let noise = measure_noise_lwe(
560 &ct_out,
561 parameters.rlwe_q().encode(m_expected),
562 &ideal_sk_rlwe,
563 &rlwe_modop,
564 );
565 stats.add_sample(parameters.rlwe_q().map_element_to_i64(&noise));
566 }
567
568 m1 = m0;
569 m0 = m_expected;
570
571 ct1 = ct0;
572 ct0 = ct_out;
573 }
574
575 let server_key_stats = collect_server_key_stats::<
576 _,
577 DefaultDecomposer<u64>,
578 NttBackendU64,
579 ModularOpsU64<CiphertextModulus<u64>>,
580 _,
581 >(
582 parameters,
583 &cks,
584 &ServerKeyEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(&server_key),
585 );
586
587 println!("## Bootstrapping Statistics ##");
588 println!("Bootstrapped ciphertext noise std_dev: {}", stats.std_dev());
589
590 println!("## Key Statistics ##");
591 println!(
592 "Rgsw nsm std_dev {}",
593 server_key_stats.brk_rgsw_cts.0.std_dev()
594 );
595 println!(
596 "Rgsw m std_dev {}",
597 server_key_stats.brk_rgsw_cts.1.std_dev()
598 );
599 println!(
600 "rlwe post 1 auto std_dev {}",
601 server_key_stats.post_1_auto.std_dev()
602 );
603 println!(
604 "key switching noise rlwe secret s to lwe secret z std_dev {}",
605 server_key_stats.post_lwe_key_switch.std_dev()
606 );
607 println!();
608 }
609
610 #[test]
611 #[cfg(feature = "non_interactive_mp")]
612 fn non_interactive_mp_bool_gates() {
613 use rand::{thread_rng, RngCore};
614
615 use crate::{
616 aggregate_server_key_shares,
617 backend::Modulus,
618 bool::{
619 keys::{
620 tests::{ideal_sk_rlwe, measure_noise_lwe},
621 NonInteractiveServerKeyEvaluationDomain,
622 },
623 print_noise::collect_server_key_stats,
624 NonInteractiveBatchedFheBools,
625 },
626 gen_client_key, gen_server_key_share,
627 parameters::CiphertextModulus,
628 random::DefaultSecureRng,
629 set_common_reference_seed, set_parameter_set,
630 utils::{tests::Stats, Global, WithLocal},
631 BoolEvaluator, BooleanGates, DefaultDecomposer, Encoder, Encryptor, KeySwitchWithId,
632 ModInit, ModularOpsU64, MultiPartyDecryptor, NttBackendU64, ParameterSelector,
633 RuntimeServerKey,
634 };
635
636 set_parameter_set(ParameterSelector::NonInteractiveLTE8Party);
637 let mut seed = [0u8; 32];
638 thread_rng().fill_bytes(&mut seed);
639 set_common_reference_seed(seed);
640
641 let parties = 8;
642
643 let cks = (0..parties).map(|_| gen_client_key()).collect_vec();
644
645 let server_key_shares = cks
646 .iter()
647 .enumerate()
648 .map(|(user_index, ck)| gen_server_key_share(user_index, parties, ck))
649 .collect_vec();
650
651 let seeded_server_key = aggregate_server_key_shares(&server_key_shares);
652 seeded_server_key.set_server_key();
653
654 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
655 let rlwe_modop = ModularOpsU64::new(*parameters.rlwe_q());
656
657 let ideal_sk_rlwe = ideal_sk_rlwe(&cks);
658
659 let mut m0 = false;
660 let mut m1 = true;
661
662 let mut ct0 = {
663 let ct: NonInteractiveBatchedFheBools<_> = cks[0].encrypt(vec![m0].as_slice());
664 let ct = ct.key_switch(0);
665 ct.extract(0)
666 };
667 let mut ct1 = {
668 let ct: NonInteractiveBatchedFheBools<_> = cks[1].encrypt(vec![m1].as_slice());
669 let ct = ct.key_switch(1);
670 ct.extract(0)
671 };
672
673 let mut stats = Stats::new();
674
675 for _ in 0..K {
676 // let now = std::time::Instant::now();
677 let ct_out =
678 BoolEvaluator::with_local_mut(|e| e.xor(&ct0, &ct1, RuntimeServerKey::global()));
679 // println!("Time: {:?}", now.elapsed());
680
681 let decryption_shares = cks
682 .iter()
683 .map(|k| k.gen_decryption_share(&ct_out))
684 .collect_vec();
685 let m_out = cks[0].aggregate_decryption_shares(&ct_out, &decryption_shares);
686
687 let m_expected = m0 ^ m1;
688
689 {
690 let noise = measure_noise_lwe(
691 &ct_out,
692 parameters.rlwe_q().encode(m_expected),
693 &ideal_sk_rlwe,
694 &rlwe_modop,
695 );
696 stats.add_sample(parameters.rlwe_q().map_element_to_i64(&noise));
697 }
698
699 assert!(m_out == m_expected, "Expected {m_expected} but got {m_out}");
700
701 m1 = m0;
702 m0 = m_out;
703
704 ct1 = ct0;
705 ct0 = ct_out;
706 }
707
708 // server key statistics
709 let server_key_stats = collect_server_key_stats::<
710 _,
711 DefaultDecomposer<u64>,
712 NttBackendU64,
713 ModularOpsU64<CiphertextModulus<u64>>,
714 _,
715 >(
716 parameters,
717 &cks,
718 &NonInteractiveServerKeyEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
719 &seeded_server_key,
720 ),
721 );
722
723 println!("## Bootstrapping Statistics ##");
724 println!("Bootstrapped ciphertext noise std_dev: {}", stats.std_dev());
725
726 println!("## Key Statistics ##");
727 println!(
728 "Rgsw nsm std_dev {}",
729 server_key_stats.brk_rgsw_cts.0.std_dev()
730 );
731 println!(
732 "Rgsw m std_dev {}",
733 server_key_stats.brk_rgsw_cts.1.std_dev()
734 );
735 println!(
736 "rlwe post 1 auto std_dev {}",
737 server_key_stats.post_1_auto.std_dev()
738 );
739 println!(
740 "key switching noise rlwe secret s to lwe secret z std_dev {}",
741 server_key_stats.post_lwe_key_switch.std_dev()
742 );
743 println!();
744 }
745
746 #[test]
747 #[cfg(feature = "non_interactive_mp")]
748 fn non_interactive_key_noise() {
749 use crate::{
750 aggregate_server_key_shares,
751 bool::{
752 evaluator::NonInteractiveMultiPartyCrs,
753 keys::{key_size::KeySize, NonInteractiveServerKeyEvaluationDomain},
754 },
755 decomposer::DefaultDecomposer,
756 gen_client_key, gen_server_key_share,
757 parameters::CiphertextModulus,
758 random::DefaultSecureRng,
759 set_common_reference_seed, set_parameter_set,
760 utils::WithLocal,
761 BoolEvaluator, ModularOpsU64, NttBackendU64,
762 };
763
764 use super::*;
765
766 set_parameter_set(crate::ParameterSelector::NonInteractiveLTE8Party);
767 set_common_reference_seed(NonInteractiveMultiPartyCrs::random().seed);
768 let parties = 8;
769
770 let mut server_key_stats = ServerKeyStats::default();
771 let mut server_key_share_size = 0;
772 for i in 0..2 {
773 let cks = (0..parties).map(|_| gen_client_key()).collect_vec();
774 let server_key_shares = cks
775 .iter()
776 .enumerate()
777 .map(|(user_id, k)| gen_server_key_share(user_id, parties, k))
778 .collect_vec();
779
780 // Collect server key size in the 0th iteration
781 if i == 0 {
782 // Server key share size may differ for user with last id from
783 // the share size of other users if the LWE dimension `n` is not
784 // divisible by no. of parties.
785 server_key_share_size = std::cmp::max(
786 server_key_shares.first().unwrap().size(),
787 server_key_shares.last().unwrap().size(),
788 );
789 }
790
791 let server_key = aggregate_server_key_shares(&server_key_shares);
792
793 let server_key_eval = NonInteractiveServerKeyEvaluationDomain::<
794 _,
795 _,
796 DefaultSecureRng,
797 NttBackendU64,
798 >::from(&server_key);
799
800 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
801 server_key_stats.merge_in(&collect_server_key_stats::<
802 _,
803 DefaultDecomposer<u64>,
804 NttBackendU64,
805 ModularOpsU64<CiphertextModulus<u64>>,
806 _,
807 >(parameters, &cks, &server_key_eval));
808 }
809
810 println!(
811 "Common reference seeded server key share key size: {} Bits",
812 server_key_share_size
813 );
814 println!(
815 "Rgsw nsm std log2 {}",
816 server_key_stats.brk_rgsw_cts.0.std_dev().abs().log2()
817 );
818 println!(
819 "Rgsw m std log2 {}",
820 server_key_stats.brk_rgsw_cts.1.std_dev().abs().log2()
821 );
822 println!(
823 "rlwe post 1 auto std log2 {}",
824 server_key_stats.post_1_auto.std_dev().abs().log2()
825 );
826 println!(
827 "key switching noise rlwe secret s to lwe secret z std log2 {}",
828 server_key_stats.post_lwe_key_switch.std_dev().abs().log2()
829 );
830 }
831
832 #[test]
833 #[cfg(feature = "non_interactive_mp")]
834 fn enc_under_sk_and_key_switch() {
835 use rand::{thread_rng, Rng};
836
837 use crate::{
838 aggregate_server_key_shares,
839 bool::{keys::tests::ideal_sk_rlwe, ni_mp_api::NonInteractiveBatchedFheBools},
840 gen_client_key, gen_server_key_share,
841 rgsw::decrypt_rlwe,
842 set_common_reference_seed, set_parameter_set,
843 utils::{tests::Stats, TryConvertFrom1, WithLocal},
844 BoolEvaluator, Encoder, Encryptor, KeySwitchWithId, ModInit, ModularOpsU64,
845 NttBackendU64, NttInit, ParameterSelector, VectorOps,
846 };
847
848 set_parameter_set(ParameterSelector::NonInteractiveLTE2Party);
849 set_common_reference_seed([2; 32]);
850
851 let parties = 2;
852
853 let cks = (0..parties).map(|_| gen_client_key()).collect_vec();
854
855 let key_shares = cks
856 .iter()
857 .enumerate()
858 .map(|(user_index, ck)| gen_server_key_share(user_index, parties, ck))
859 .collect_vec();
860
861 let seeded_server_key = aggregate_server_key_shares(&key_shares);
862 seeded_server_key.set_server_key();
863
864 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
865 let nttop = NttBackendU64::new(parameters.rlwe_q(), parameters.rlwe_n().0);
866 let rlwe_q_modop = ModularOpsU64::new(*parameters.rlwe_q());
867
868 let m = (0..parameters.rlwe_n().0)
869 .map(|_| thread_rng().gen_bool(0.5))
870 .collect_vec();
871 let ct: NonInteractiveBatchedFheBools<_> = cks[0].encrypt(m.as_slice());
872 let ct = ct.key_switch(0);
873
874 let ideal_rlwe_sk = ideal_sk_rlwe(&cks);
875
876 let message = m
877 .iter()
878 .map(|b| parameters.rlwe_q().encode(*b))
879 .collect_vec();
880
881 let mut m_out = vec![0u64; parameters.rlwe_n().0];
882 decrypt_rlwe(
883 &ct.data[0],
884 &ideal_rlwe_sk,
885 &mut m_out,
886 &nttop,
887 &rlwe_q_modop,
888 );
889
890 let mut diff = m_out;
891 rlwe_q_modop.elwise_sub_mut(diff.as_mut_slice(), message.as_ref());
892
893 let mut stats = Stats::new();
894 stats.add_many_samples(&Vec::<i64>::try_convert_from(
895 diff.as_slice(),
896 parameters.rlwe_q(),
897 ));
898 println!("Noise std log2: {}", stats.std_dev().abs().log2());
899 }
900
901 #[test]
902 fn mod_switch_noise() {
903 // Experiment to check mod switch noise using different secret dist in
904 // multi-party setting
905
906 use itertools::izip;
907 use num_traits::ToPrimitive;
908
909 use crate::{
910 backend::{Modulus, ModulusPowerOf2},
911 parameters::SecretKeyDistribution,
912 random::{DefaultSecureRng, RandomFillGaussian, RandomFillUniformInModulus},
913 utils::{fill_random_ternary_secret_with_hamming_weight, tests::Stats},
914 ArithmeticOps, ModInit,
915 };
916
917 fn mod_switch(v: u64, q_from: u64, q_to: u64) -> f64 {
918 (v as f64) * (q_to as f64) / q_from as f64
919 }
920
921 fn mod_switch_round(v: u64, q_from: u64, q_to: u64) -> u64 {
922 mod_switch(v, q_from, q_to).round().to_u64().unwrap()
923 }
924
925 fn mod_switch_odd(v: u64, q_from: u64, q_to: u64) -> u64 {
926 let odd_v = mod_switch(v, q_from, q_to).floor().to_u64().unwrap();
927 odd_v + ((odd_v & 1) ^ 1)
928 }
929
930 fn sample_secret(n: usize, dist: &SecretKeyDistribution) -> Vec<i32> {
931 let mut s = vec![0i32; n];
932 let mut rng = DefaultSecureRng::new();
933
934 match dist {
935 SecretKeyDistribution::ErrorDistribution => {
936 RandomFillGaussian::random_fill(&mut rng, s.as_mut_slice());
937 }
938 SecretKeyDistribution::TernaryDistribution => {
939 fill_random_ternary_secret_with_hamming_weight(&mut s, n >> 1, &mut rng);
940 }
941 }
942
943 s
944 }
945
946 let parties = 2;
947 let q_from = 1 << 40;
948 let q_to = 1 << 20;
949 let n = 480;
950 let lweq_in_modop = ModulusPowerOf2::new(q_from);
951 let lweq_out_modop = ModulusPowerOf2::new(q_to);
952 let secret_dist = SecretKeyDistribution::ErrorDistribution;
953
954 let mut stats_ms_noise = Stats::new();
955 let mut stats_ms_rounding_err = Stats::new();
956
957 for _ in 0..1000000 {
958 let mut rng = DefaultSecureRng::new();
959
960 // sample secrets
961
962 let s = {
963 let mut s = vec![0i32; n];
964 for _ in 0..parties {
965 let temp = sample_secret(n, &secret_dist);
966 izip!(s.iter_mut(), temp.iter()).for_each(|(si, ti)| {
967 *si = *si + *ti;
968 });
969 }
970 s
971 };
972
973 let m = 10;
974
975 // LWE encryption without noise
976 let mut lwe_in = vec![0u64; n + 1];
977 {
978 RandomFillUniformInModulus::random_fill(&mut rng, &q_from, &mut lwe_in[1..]);
979 let mut b = m;
980 izip!(lwe_in.iter().skip(1), s.iter()).for_each(|(ai, si)| {
981 b = lweq_in_modop.add(
982 &b,
983 &lweq_in_modop.mul(ai, &q_from.map_element_from_i64(*si as i64)),
984 );
985 });
986 lwe_in[0] = b;
987 }
988
989 // Mod switch
990 let lwe_out = lwe_in
991 .iter()
992 .map(|v| {
993 // mod_switch_round(*v, q_from, q_to)
994 mod_switch_odd(*v, q_from, q_to)
995 })
996 .collect_vec();
997
998 let rounding_errors = izip!(lwe_out.iter(), lwe_in.iter())
999 .map(|(v_out, v_in)| {
1000 let r_i = mod_switch(*v_in, q_from, q_to) - (*v_out as f64);
1001 r_i
1002 })
1003 .collect_vec();
1004 stats_ms_rounding_err.add_many_samples(&rounding_errors);
1005
1006 // LWE decrypt and calculate ms noise
1007 let mut m_back = 0;
1008 izip!(lwe_out.iter().skip(1), s.iter()).for_each(|(ai, si)| {
1009 m_back = lweq_out_modop.add(
1010 &m_back,
1011 &lweq_out_modop.mul(ai, &q_from.map_element_from_i64(*si as i64)),
1012 );
1013 });
1014 m_back = lweq_out_modop.sub(&lwe_out[0], &m_back);
1015 let noise = lweq_out_modop.sub(&m_back, &m);
1016 stats_ms_noise.add_many_samples(&vec![q_to.map_element_to_i64(&noise)]);
1017 }
1018
1019 println!("ms noise variance: {}", stats_ms_noise.variance());
1020 println!("ms rounding errors mean: {}", stats_ms_rounding_err.mean());
1021 println!(
1022 "ms rounding errors variance: {}",
1023 stats_ms_rounding_err.variance()
1024 );
1025 }
1026}