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