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::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, Decomposer, MatrixEntity, MatrixMut, ModInit, Ntt, NttInit,
19 RowEntity, RowMut, 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
36struct ServerKeyStats<T> {
37 brk_rgsw_cts: (Stats<T>, Stats<T>),
38 post_1_auto: Stats<T>,
39 post_lwe_key_switch: Stats<T>,
40}
41
42impl<T: PrimInt + FromPrimitive + Debug + Sum> ServerKeyStats<T>
43where
44 T: for<'a> Sum<&'a T>,
45{
46 fn new() -> Self {
47 ServerKeyStats {
48 brk_rgsw_cts: (Stats::default(), Stats::default()),
49 post_1_auto: Stats::default(),
50 post_lwe_key_switch: Stats::default(),
51 }
52 }
53
54 fn add_noise_brk_rgsw_cts_nsm(&mut self, noise: &[T]) {
55 self.brk_rgsw_cts.0.add_more(noise);
56 }
57
58 fn add_noise_brk_rgsw_cts_m(&mut self, noise: &[T]) {
59 self.brk_rgsw_cts.1.add_more(noise);
60 }
61
62 fn add_noise_post_1_auto(&mut self, noise: &[T]) {
63 self.post_1_auto.add_more(&noise);
64 }
65
66 fn add_noise_post_kwe_key_switch(&mut self, noise: &[T]) {
67 self.post_lwe_key_switch.add_more(&noise);
68 }
69}
70
71fn collect_server_key_stats<
72 M: MatrixEntity + MatrixMut,
73 D: Decomposer<Element = M::MatElement>,
74 NttOp: NttInit<CiphertextModulus<M::MatElement>> + Ntt<Element = M::MatElement>,
75 ModOp: VectorOps<Element = M::MatElement>
76 + ArithmeticOps<Element = M::MatElement>
77 + ModInit<M = CiphertextModulus<M::MatElement>>
78 + GetModulus<M = CiphertextModulus<M::MatElement>, Element = M::MatElement>,
79 S: CollectRuntimeServerKeyStats<M = M>,
80>(
81 parameters: BoolParameters<M::MatElement>,
82 client_keys: &[ClientKey],
83 server_key: &S,
84) -> ServerKeyStats<i64>
85where
86 M::R: RowMut + RowEntity + TryConvertFrom1<[i32], CiphertextModulus<M::MatElement>> + Clone,
87 M::MatElement: Copy + PrimInt + FromPrimitive + SampleUniform + Zero + Debug,
88{
89 let ideal_sk_rlwe = ideal_sk_rlwe(client_keys);
90 let ideal_sk_lwe = ideal_sk_lwe(client_keys);
91
92 let embedding_factor = (2 * parameters.rlwe_n().0) / parameters.br_q();
93 let rlwe_n = parameters.rlwe_n().0;
94 let rlwe_q = parameters.rlwe_q();
95 let lwe_q = parameters.lwe_q();
96 let rlwe_modop = ModOp::new(rlwe_q.clone());
97 let rlwe_nttop = NttOp::new(rlwe_q, rlwe_n);
98 let lwe_modop = ModOp::new(*parameters.lwe_q());
99
100 let rlwe_x_rgsw_decomposer = parameters.rlwe_rgsw_decomposer::<D>();
101 let (rlwe_x_rgsw_gadget_a, rlwe_x_rgsw_gadget_b) = (
102 rlwe_x_rgsw_decomposer.a().gadget_vector(),
103 rlwe_x_rgsw_decomposer.b().gadget_vector(),
104 );
105
106 let lwe_ks_decomposer = parameters.lwe_decomposer::<D>();
107
108 let mut server_key_stats = ServerKeyStats::new();
109
110 let mut rng = DefaultSecureRng::new();
111
112 // RGSW ciphertext noise
113 // Check noise in RGSW ciphertexts of ideal LWE secret elements
114 {
115 ideal_sk_lwe.iter().enumerate().for_each(|(s_index, s_i)| {
116 let rgsw_ct_i = server_key.rgsw_cts_lwe_si(s_index);
117
118 // X^{s[i]}
119 let m_si = encode_x_pow_si_with_emebedding_factor::<M::R, _>(
120 *s_i,
121 embedding_factor,
122 rlwe_n,
123 rlwe_q,
124 );
125
126 // RLWE'(-sm)
127 let mut neg_s_eval = M::R::try_convert_from(ideal_sk_rlwe.as_slice(), rlwe_q);
128 rlwe_modop.elwise_neg_mut(neg_s_eval.as_mut());
129 rlwe_nttop.forward(neg_s_eval.as_mut());
130
131 for j in 0..rlwe_x_rgsw_decomposer.a().decomposition_count() {
132 // RLWE(B^{j} * -s[X]*X^{s_lwe[i]})
133
134 // -s[X]*X^{s_lwe[i]}*B_j
135 let mut m_ideal = m_si.clone();
136 rlwe_nttop.forward(m_ideal.as_mut());
137 rlwe_modop.elwise_mul_mut(m_ideal.as_mut(), neg_s_eval.as_ref());
138 rlwe_nttop.backward(m_ideal.as_mut());
139 rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut(), &rlwe_x_rgsw_gadget_a[j]);
140
141 // RLWE(-s*X^{s_lwe[i]}*B_j)
142 let mut rlwe_ct = M::zeros(2, rlwe_n);
143 rlwe_ct
144 .get_row_mut(0)
145 .copy_from_slice(rgsw_ct_i.get_row_slice(j));
146 rlwe_ct.get_row_mut(1).copy_from_slice(
147 rgsw_ct_i.get_row_slice(j + rlwe_x_rgsw_decomposer.a().decomposition_count()),
148 );
149 // RGSW ciphertexts are in eval domain. We put RLWE ciphertexts back in
150 // coefficient domain
151 rlwe_ct
152 .iter_rows_mut()
153 .for_each(|r| rlwe_nttop.backward(r.as_mut()));
154
155 let mut m_back = M::R::zeros(rlwe_n);
156 decrypt_rlwe(
157 &rlwe_ct,
158 &ideal_sk_rlwe,
159 &mut m_back,
160 &rlwe_nttop,
161 &rlwe_modop,
162 );
163
164 // diff
165 rlwe_modop.elwise_sub_mut(m_back.as_mut(), m_ideal.as_ref());
166 server_key_stats.add_noise_brk_rgsw_cts_nsm(&Vec::<i64>::try_convert_from(
167 m_back.as_ref(),
168 rlwe_q,
169 ));
170 }
171
172 // RLWE'(m)
173 for j in 0..rlwe_x_rgsw_decomposer.b().decomposition_count() {
174 // RLWE(B^{j} * X^{s_lwe[i]})
175
176 // X^{s_lwe[i]}*B_j
177 let mut m_ideal = m_si.clone();
178 rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut(), &rlwe_x_rgsw_gadget_b[j]);
179
180 // RLWE(X^{s_lwe[i]}*B_j)
181 let mut rlwe_ct = M::zeros(2, rlwe_n);
182 rlwe_ct.get_row_mut(0).copy_from_slice(
183 rgsw_ct_i
184 .get_row_slice(j + (2 * rlwe_x_rgsw_decomposer.a().decomposition_count())),
185 );
186 rlwe_ct
187 .get_row_mut(1)
188 .copy_from_slice(rgsw_ct_i.get_row_slice(
189 j + (2 * rlwe_x_rgsw_decomposer.a().decomposition_count())
190 + rlwe_x_rgsw_decomposer.b().decomposition_count(),
191 ));
192 rlwe_ct
193 .iter_rows_mut()
194 .for_each(|r| rlwe_nttop.backward(r.as_mut()));
195
196 let mut m_back = M::R::zeros(rlwe_n);
197 decrypt_rlwe(
198 &rlwe_ct,
199 &ideal_sk_rlwe,
200 &mut m_back,
201 &rlwe_nttop,
202 &rlwe_modop,
203 );
204
205 // diff
206 rlwe_modop.elwise_sub_mut(m_back.as_mut(), m_ideal.as_ref());
207 server_key_stats.add_noise_brk_rgsw_cts_m(&Vec::<i64>::try_convert_from(
208 m_back.as_ref(),
209 rlwe_q,
210 ));
211 }
212 });
213 }
214
215 // Noise in ciphertext after 1 auto
216 // For each auto key g^k. Sample random polynomial m(X) and multiply with
217 // -s(X^{g^k}) using key corresponding to auto g^k. Then check the noise in
218 // resutling RLWE(m(X) * -s(X^{g^k}))
219 {
220 let neg_s = {
221 let mut s = M::R::try_convert_from(ideal_sk_rlwe.as_slice(), rlwe_q);
222 rlwe_modop.elwise_neg_mut(s.as_mut());
223 s
224 };
225 let g = parameters.g();
226 let br_q = parameters.br_q();
227 let g_dlogs = parameters.auto_element_dlogs();
228 let auto_decomposer = parameters.auto_decomposer::<D>();
229 let mut scratch_matrix = M::zeros(rlwe_auto_scratch_rows(&auto_decomposer), rlwe_n);
230 let mut scratch_matrix_ref = RuntimeScratchMutRef::new(scratch_matrix.as_mut());
231
232 g_dlogs.iter().for_each(|k| {
233 let g_pow_k = if *k == 0 {
234 -(g as isize)
235 } else {
236 (g.pow(*k as u32) % br_q) as isize
237 };
238
239 // Send s(X) -> s(X^{g^k})
240 let (auto_index_map, auto_sign_map) = crate::rgsw::generate_auto_map(rlwe_n, g_pow_k);
241 let mut neg_s_g_k = M::R::zeros(rlwe_n);
242 izip!(
243 neg_s.as_ref().iter(),
244 auto_index_map.iter(),
245 auto_sign_map.iter()
246 )
247 .for_each(|(el, to_index, to_sign)| {
248 if !to_sign {
249 neg_s_g_k.as_mut()[*to_index] = rlwe_modop.neg(el);
250 } else {
251 neg_s_g_k.as_mut()[*to_index] = *el;
252 }
253 });
254
255 let mut m = M::R::zeros(rlwe_n);
256 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut());
257
258 // We want -m(X^{g^k})s(X^{g^k}) after key switch
259 let want_m = {
260 let mut m_g_k_eval = M::R::zeros(rlwe_n);
261 // send m(X) -> m(X^{g^k})
262 izip!(
263 m.as_ref().iter(),
264 auto_index_map.iter(),
265 auto_sign_map.iter()
266 )
267 .for_each(|(el, to_index, to_sign)| {
268 if !to_sign {
269 m_g_k_eval.as_mut()[*to_index] = rlwe_modop.neg(el);
270 } else {
271 m_g_k_eval.as_mut()[*to_index] = *el;
272 }
273 });
274
275 rlwe_nttop.forward(m_g_k_eval.as_mut());
276 let mut s_g_k = neg_s_g_k.clone();
277 rlwe_nttop.forward(s_g_k.as_mut());
278 rlwe_modop.elwise_mul_mut(m_g_k_eval.as_mut(), s_g_k.as_ref());
279 rlwe_nttop.backward(m_g_k_eval.as_mut());
280 m_g_k_eval
281 };
282
283 // RLWE auto sends part A, A(X), of RLWE to A(X^{g^k}) and then multiplies it
284 // with -s(X^{g^k}) using auto key. Deliberately set RLWE = (0, m(X))
285 // (ie. m in part A) to get back RLWE(-m(X^{g^k})s(X^{g^k}))
286 let mut rlwe = M::zeros(2, rlwe_n);
287 rlwe.get_row_mut(0).copy_from_slice(m.as_ref());
288
289 rlwe_auto(
290 &mut RlweCiphertextMutRef::new(rlwe.as_mut()),
291 &RlweKskRef::new(
292 server_key.galois_key_for_auto(*k).as_ref(),
293 auto_decomposer.decomposition_count(),
294 ),
295 &mut scratch_matrix_ref,
296 &auto_index_map,
297 &auto_sign_map,
298 &rlwe_modop,
299 &rlwe_nttop,
300 &auto_decomposer,
301 false,
302 );
303
304 // decrypt RLWE(-m(X)s(X^{g^k]}))
305 let mut back_m = M::R::zeros(rlwe_n);
306 decrypt_rlwe(&rlwe, &ideal_sk_rlwe, &mut back_m, &rlwe_nttop, &rlwe_modop);
307
308 // check difference
309 let mut diff = back_m;
310 rlwe_modop.elwise_sub_mut(diff.as_mut(), want_m.as_ref());
311 server_key_stats
312 .add_noise_post_1_auto(&Vec::<i64>::try_convert_from(diff.as_ref(), rlwe_q));
313 });
314
315 // sample random m
316
317 // key switch
318 }
319
320 // LWE Key switch
321 // LWE key switches LWE_in = LWE_{Q_ks,N, s}(m) = (b, a_0, ... a_N) -> LWE_out =
322 // LWE_{Q_{ks}, n, z}(m) = (b', a'_0, ..., a'n)
323 // If LWE_in = (0, a = {a_0, ..., a_N}), then LWE_out = LWE(-a \cdot s_{rlwe})
324 for _ in 0..10 {
325 let mut lwe_in = M::R::zeros(rlwe_n + 1);
326 RandomFillUniformInModulus::random_fill(&mut rng, lwe_q, &mut lwe_in.as_mut()[1..]);
327
328 // Key switch
329 let mut lwe_out = M::R::zeros(parameters.lwe_n().0 + 1);
330 lwe_key_switch(
331 &mut lwe_out,
332 &lwe_in,
333 server_key.lwe_ksk(),
334 &lwe_modop,
335 &lwe_ks_decomposer,
336 );
337
338 // -a \cdot s
339 let mut want_m = M::MatElement::zero();
340 izip!(lwe_in.as_ref().iter().skip(1), ideal_sk_rlwe.iter()).for_each(|(a, b)| {
341 want_m = lwe_modop.add(
342 &want_m,
343 &lwe_modop.mul(a, &lwe_q.map_element_from_i64(*b as i64)),
344 );
345 });
346 want_m = lwe_modop.neg(&want_m);
347
348 // decrypt lwe out
349 let back_m = decrypt_lwe(&lwe_out, &ideal_sk_lwe, &lwe_modop);
350
351 let noise = lwe_modop.sub(&want_m, &back_m);
352 server_key_stats.add_noise_post_kwe_key_switch(&vec![lwe_q.map_element_to_i64(&noise)]);
353 }
354
355 server_key_stats
356 // Auto keys noise
357
358 // Ksk noise
359}
360
361#[cfg(test)]
362mod tests {
363 use itertools::Itertools;
364
365 use super::collect_server_key_stats;
366
367 #[test]
368 #[cfg(feature = "interactive_mp")]
369 fn qwerty() {
370 use crate::{
371 aggregate_public_key_shares, aggregate_server_key_shares,
372 bool::keys::ServerKeyEvaluationDomain,
373 evaluator::MultiPartyCrs,
374 gen_client_key, gen_mp_keys_phase1, gen_mp_keys_phase2,
375 parameters::{BoolParameters, CiphertextModulus},
376 random::DefaultSecureRng,
377 set_mp_seed, set_parameter_set,
378 utils::WithLocal,
379 BoolEvaluator, DefaultDecomposer, ModularOpsU64, Ntt, NttBackendU64,
380 };
381
382 set_parameter_set(crate::ParameterSelector::HighCommunicationButFast2Party);
383 set_mp_seed(MultiPartyCrs::random().seed);
384 let parties = 2;
385 let cks = (0..parties).map(|_| gen_client_key()).collect_vec();
386 let pk_shares = cks.iter().map(|k| gen_mp_keys_phase1(k)).collect_vec();
387 let pk = aggregate_public_key_shares(&pk_shares);
388 let server_key_shares = cks
389 .iter()
390 .enumerate()
391 .map(|(index, k)| gen_mp_keys_phase2(k, index, parties, &pk))
392 .collect_vec();
393 let seeded_server_key = aggregate_server_key_shares(&server_key_shares);
394 let server_key_eval =
395 ServerKeyEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
396 &seeded_server_key,
397 );
398
399 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
400 let server_key_stats = collect_server_key_stats::<
401 _,
402 DefaultDecomposer<u64>,
403 NttBackendU64,
404 ModularOpsU64<CiphertextModulus<u64>>,
405 _,
406 >(parameters, &cks, &server_key_eval);
407
408 println!(
409 "Rgsw nsm std log2 {}",
410 server_key_stats.brk_rgsw_cts.0.std_dev().abs().log2()
411 );
412 println!(
413 "Rgsw m std log2 {}",
414 server_key_stats.brk_rgsw_cts.1.std_dev().abs().log2()
415 );
416 println!(
417 "rlwe post 1 auto std log2 {}",
418 server_key_stats.post_1_auto.std_dev().abs().log2()
419 );
420 println!(
421 "key switching noise rlwe secret s to lwe secret z std log2 {}",
422 server_key_stats.post_lwe_key_switch.std_dev().abs().log2()
423 );
424 }
425
426 #[test]
427 #[cfg(feature = "non_interactive_mp")]
428 fn querty2() {
429 use crate::{
430 aggregate_server_key_shares, bool::keys::NonInteractiveServerKeyEvaluationDomain,
431 evaluator::NonInteractiveMultiPartyCrs, gen_client_key, gen_server_key_share,
432 parameters::CiphertextModulus, random::DefaultSecureRng, set_common_reference_seed,
433 set_parameter_set, utils::WithLocal, BoolEvaluator, DefaultDecomposer, ModularOpsU64,
434 NttBackendU64,
435 };
436
437 set_parameter_set(crate::ParameterSelector::NonInteractiveLTE2Party);
438 set_common_reference_seed(NonInteractiveMultiPartyCrs::random().seed);
439 let parties = 2;
440 let cks = (0..parties).map(|_| gen_client_key()).collect_vec();
441 let server_key_shares = cks
442 .iter()
443 .enumerate()
444 .map(|(user_id, k)| gen_server_key_share(user_id, parties, k))
445 .collect_vec();
446 let server_key = aggregate_server_key_shares(&server_key_shares);
447
448 let server_key_eval =
449 NonInteractiveServerKeyEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
450 &server_key,
451 );
452
453 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
454 let server_key_stats = collect_server_key_stats::<
455 _,
456 DefaultDecomposer<u64>,
457 NttBackendU64,
458 ModularOpsU64<CiphertextModulus<u64>>,
459 _,
460 >(parameters, &cks, &server_key_eval);
461
462 println!(
463 "Rgsw nsm std log2 {}",
464 server_key_stats.brk_rgsw_cts.0.std_dev().abs().log2()
465 );
466 println!(
467 "Rgsw m std log2 {}",
468 server_key_stats.brk_rgsw_cts.1.std_dev().abs().log2()
469 );
470 println!(
471 "rlwe post 1 auto std log2 {}",
472 server_key_stats.post_1_auto.std_dev().abs().log2()
473 );
474 println!(
475 "key switching noise rlwe secret s to lwe secret z std log2 {}",
476 server_key_stats.post_lwe_key_switch.std_dev().abs().log2()
477 );
478 }
479
480 #[test]
481 #[cfg(feature = "non_interactive_mp")]
482 fn enc_under_sk_and_key_switch() {
483 use rand::{thread_rng, Rng};
484
485 use crate::{
486 aggregate_server_key_shares,
487 bool::{keys::tests::ideal_sk_rlwe, ni_mp_api::NonInteractiveBatchedFheBools},
488 gen_client_key, gen_server_key_share,
489 rgsw::decrypt_rlwe,
490 set_common_reference_seed, set_parameter_set,
491 utils::{tests::Stats, TryConvertFrom1, WithLocal},
492 BoolEvaluator, Encoder, Encryptor, KeySwitchWithId, ModInit, ModularOpsU64,
493 NttBackendU64, NttInit, ParameterSelector, VectorOps,
494 };
495
496 set_parameter_set(ParameterSelector::NonInteractiveLTE2Party);
497 set_common_reference_seed([2; 32]);
498
499 let parties = 2;
500
501 let cks = (0..parties).map(|_| gen_client_key()).collect_vec();
502
503 let key_shares = cks
504 .iter()
505 .enumerate()
506 .map(|(user_index, ck)| gen_server_key_share(user_index, parties, ck))
507 .collect_vec();
508
509 let seeded_server_key = aggregate_server_key_shares(&key_shares);
510 seeded_server_key.set_server_key();
511
512 let parameters = BoolEvaluator::with_local(|e| e.parameters().clone());
513 let nttop = NttBackendU64::new(parameters.rlwe_q(), parameters.rlwe_n().0);
514 let rlwe_q_modop = ModularOpsU64::new(*parameters.rlwe_q());
515
516 let m = (0..parameters.rlwe_n().0)
517 .map(|_| thread_rng().gen_bool(0.5))
518 .collect_vec();
519 let ct: NonInteractiveBatchedFheBools<_> = cks[0].encrypt(m.as_slice());
520 let ct = ct.key_switch(0);
521
522 let ideal_rlwe_sk = ideal_sk_rlwe(&cks);
523
524 let message = m
525 .iter()
526 .map(|b| parameters.rlwe_q().encode(*b))
527 .collect_vec();
528
529 let mut m_out = vec![0u64; parameters.rlwe_n().0];
530 decrypt_rlwe(
531 &ct.data[0],
532 &ideal_rlwe_sk,
533 &mut m_out,
534 &nttop,
535 &rlwe_q_modop,
536 );
537
538 let mut diff = m_out;
539 rlwe_q_modop.elwise_sub_mut(diff.as_mut_slice(), message.as_ref());
540
541 let mut stats = Stats::new();
542 stats.add_more(&Vec::<i64>::try_convert_from(
543 diff.as_slice(),
544 parameters.rlwe_q(),
545 ));
546 println!("Noise std log2: {}", stats.std_dev().abs().log2());
547 }
548}