phantom-zone/src/bool/evaluator.rs
src/bool/evaluator.rsRaw
1use std::{
2 cell::RefCell,
3 collections::HashMap,
4 fmt::{Debug, Display},
5 marker::PhantomData,
6};
7
8use itertools::{izip, partition, Itertools};
9use num_traits::{FromPrimitive, Num, One, PrimInt, ToPrimitive, WrappingSub, Zero};
10
11use crate::{
12 backend::{ArithmeticOps, ModInit, ModularOpsU64, VectorOps},
13 decomposer::{Decomposer, DefaultDecomposer, NumInfo},
14 lwe::{decrypt_lwe, encrypt_lwe, lwe_key_switch, lwe_ksk_keygen, measure_noise_lwe, LweSecret},
15 multi_party::public_key_share,
16 ntt::{self, Ntt, NttBackendU64, NttInit},
17 random::{DefaultSecureRng, NewWithSeed, RandomGaussianDist, RandomUniformDist},
18 rgsw::{
19 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, public_key_encrypt_rgsw,
20 rgsw_by_rgsw_inplace, rlwe_by_rgsw, secret_key_encrypt_rgsw, IsTrivial, RlweCiphertext,
21 RlweSecret,
22 },
23 utils::{
24 fill_random_ternary_secret_with_hamming_weight, generate_prime, mod_exponent,
25 TryConvertFrom, WithLocal,
26 },
27 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut, Secret,
28};
29
30use super::parameters::{self, BoolParameters};
31
32// thread_local! {
33// pub(crate) static CLIENT_KEY: RefCell<ClientKey> =
34// RefCell::new(ClientKey::random()); }
35
36trait PbsKey {
37 type M: Matrix;
38
39 /// RGSW ciphertext of LWE secret elements
40 fn rgsw_ct_lwe_si(&self, si: usize) -> &Self::M;
41 /// Key for automorphism
42 fn galois_key_for_auto(&self, k: isize) -> &Self::M;
43 /// LWE ksk to key switch from RLWE secret to LWE secret
44 fn lwe_ksk(&self) -> &Self::M;
45}
46
47trait PbsParameters {
48 type Element;
49 type D: Decomposer<Element = Self::Element>;
50 fn rlwe_q(&self) -> Self::Element;
51 fn lwe_q(&self) -> Self::Element;
52 fn br_q(&self) -> usize;
53 fn d_rgsw(&self) -> usize;
54 fn d_lwe(&self) -> usize;
55 fn rlwe_n(&self) -> usize;
56 fn lwe_n(&self) -> usize;
57 /// Embedding fator for ring X^{q}+1 inside
58 fn embedding_factor(&self) -> usize;
59 /// generator g
60 fn g(&self) -> isize;
61 fn decomoposer_lwe(&self) -> &Self::D;
62 fn decomoposer_rlwe(&self) -> &Self::D;
63
64 /// Maps a \in Z^*_{q} to discrete log k, with generator g (i.e. g^k =
65 /// a). Returned vector is of size q that stores dlog of a at `vec[a]`.
66 /// For any a, if k is s.t. a = g^{k}, then k is expressed as k. If k is s.t
67 /// a = -g^{k}, then k is expressed as k=k+q/2
68 fn g_k_dlog_map(&self) -> &[usize];
69 fn rlwe_auto_map(&self, k: isize) -> &(Vec<usize>, Vec<bool>);
70}
71
72#[derive(Clone)]
73struct ClientKey {
74 sk_rlwe: RlweSecret,
75 sk_lwe: LweSecret,
76}
77
78impl ClientKey {
79 fn random() -> Self {
80 let sk_rlwe = RlweSecret::random(0, 0);
81 let sk_lwe = LweSecret::random(0, 0);
82 Self { sk_rlwe, sk_lwe }
83 }
84}
85
86// impl WithLocal for ClientKey {
87// fn with_local<F, R>(func: F) -> R
88// where
89// F: Fn(&Self) -> R,
90// {
91// CLIENT_KEY.with_borrow(|client_key| func(client_key))
92// }
93
94// fn with_local_mut<F, R>(func: F) -> R
95// where
96// F: Fn(&mut Self) -> R,
97// {
98// CLIENT_KEY.with_borrow_mut(|client_key| func(client_key))
99// }
100// }
101
102// fn set_client_key(key: &ClientKey) {
103// ClientKey::with_local_mut(|k| *k = key.clone())
104// }
105
106struct MultiPartyDecryptionShare<E> {
107 share: E,
108}
109
110struct CommonReferenceSeededCollectivePublicKeyShare<R, S, P> {
111 share: R,
112 cr_seed: S,
113 parameters: P,
114}
115
116struct PublicKey<M, R, O> {
117 key: M,
118 _phantom: PhantomData<(R, O)>,
119}
120
121impl<
122 M: MatrixMut + MatrixEntity,
123 Rng: NewWithSeed + RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
124 ModOp: VectorOps<Element = M::MatElement> + ModInit<Element = M::MatElement>,
125 >
126 From<
127 &[CommonReferenceSeededCollectivePublicKeyShare<
128 M::R,
129 Rng::Seed,
130 BoolParameters<M::MatElement>,
131 >],
132 > for PublicKey<M, Rng, ModOp>
133where
134 <M as Matrix>::R: RowMut,
135 Rng::Seed: Copy + PartialEq,
136 M::MatElement: PartialEq + Copy,
137{
138 fn from(
139 value: &[CommonReferenceSeededCollectivePublicKeyShare<
140 M::R,
141 Rng::Seed,
142 BoolParameters<M::MatElement>,
143 >],
144 ) -> Self {
145 assert!(value.len() > 0);
146
147 let parameters = &value[0].parameters;
148 let mut key = M::zeros(2, parameters.rlwe_n().0);
149
150 // sample A
151 let seed = value[0].cr_seed;
152 let mut main_rng = Rng::new_with_seed(seed);
153 RandomUniformDist::random_fill(&mut main_rng, ¶meters.rlwe_q().0, key.get_row_mut(0));
154
155 // Sum all Bs
156 let rlweq_modop = ModOp::new(parameters.rlwe_q().0);
157 value.iter().for_each(|share_i| {
158 assert!(share_i.cr_seed == seed);
159 assert!(&share_i.parameters == parameters);
160
161 rlweq_modop.elwise_add_mut(key.get_row_mut(1), share_i.share.as_ref());
162 });
163
164 PublicKey {
165 key,
166 _phantom: PhantomData,
167 }
168 }
169}
170
171struct CommonReferenceSeededMultiPartyServerKeyShare<M: Matrix, P, S> {
172 rgsw_cts: Vec<M>,
173 auto_keys: HashMap<isize, M>,
174 lwe_ksk: M::R,
175 /// Common reference seed
176 cr_seed: S,
177 parameters: P,
178}
179struct SeededMultiPartyServerKey<M: Matrix, S, P> {
180 rgsw_cts: Vec<M>,
181 auto_keys: HashMap<isize, M>,
182 lwe_ksk: M::R,
183 cr_seed: S,
184 parameters: P,
185}
186
187fn aggregate_multi_party_server_key_shares<
188 M: MatrixMut + MatrixEntity,
189 S: Copy + PartialEq,
190 D: Decomposer<Element = M::MatElement>,
191 ModOp: VectorOps<Element = M::MatElement> + ModInit<Element = M::MatElement>,
192 NttOp: Ntt<Element = M::MatElement> + NttInit<Element = M::MatElement>,
193>(
194 shares: &[CommonReferenceSeededMultiPartyServerKeyShare<M, BoolParameters<M::MatElement>, S>],
195 d_rgsw_decomposer: &D,
196) -> SeededMultiPartyServerKey<M, S, BoolParameters<M::MatElement>>
197where
198 <M as Matrix>::R: RowMut + RowEntity,
199 M::MatElement: Copy + PartialEq + Zero,
200 M: Clone,
201{
202 assert!(shares.len() > 0);
203 let parameters = shares[0].parameters.clone();
204 let cr_seed = shares[0].cr_seed;
205
206 let rlwe_n = parameters.rlwe_n().0;
207 let g = parameters.g() as isize;
208 let rlwe_q = parameters.rlwe_q().0;
209 let lwe_q = parameters.lwe_q().0;
210
211 // sanity checks
212 shares.iter().skip(1).for_each(|s| {
213 assert!(s.parameters == parameters);
214 assert!(s.cr_seed == cr_seed);
215 });
216
217 let rlweq_modop = ModOp::new(rlwe_q);
218 let rlweq_nttop = NttOp::new(rlwe_q, rlwe_n);
219
220 // auto keys
221 let mut auto_keys = HashMap::new();
222 for i in [g, -g] {
223 let mut key = M::zeros(parameters.auto_decomposition_count().0, rlwe_n);
224
225 shares.iter().for_each(|s| {
226 let auto_key_share_i = s.auto_keys.get(&i).expect("Auto key {i} missing");
227 assert!(
228 auto_key_share_i.dimension() == (parameters.auto_decomposition_count().0, rlwe_n)
229 );
230 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
231 |(partb_out, partb_share)| {
232 rlweq_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
233 },
234 );
235 });
236
237 auto_keys.insert(i, key);
238 }
239
240 // rgsw ciphertext (most expensive part!)
241 let lwe_n = parameters.lwe_n().0;
242 let mut scratch_d_plus_rgsw_by_ring = M::zeros(d_rgsw + (d_rgsw * 4), rlwe_n);
243
244 let mut tmp_rgsw = M::zeros(d_rgsw * 2 * 2, rlwe_n);
245 let rgsw_cts = (0..lwe_n)
246 .into_iter()
247 .map(|index| {
248 // copy over rgsw ciphertext for index^th secret element from first share and
249 // treat it as accumulating rgsw ciphertext
250 let mut rgsw_i = shares[0].rgsw_cts[index].clone();
251
252 shares.iter().skip(1).for_each(|si| {
253 // copy over si's RGSW[index] ciphertext and send to evaluation domain
254 izip!(tmp_rgsw.iter_rows_mut(), si.rgsw_cts[index].iter_rows()).for_each(
255 |(to_ri, from_ri)| {
256 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
257 rlweq_nttop.forward(to_ri.as_mut())
258 },
259 );
260
261 rgsw_by_rgsw_inplace(
262 &mut rgsw_i,
263 &tmp_rgsw,
264 d_rgsw_decomposer,
265 &mut scratch_d_plus_rgsw_by_ring,
266 &rlweq_nttop,
267 &rlweq_modop,
268 );
269 });
270
271 rgsw_i
272 })
273 .collect_vec();
274
275 // LWE ksks
276 let mut lwe_ksk = M::R::zeros(rlwe_n * parameters.lwe_decomposition_count().0);
277 let lweq_modop = ModOp::new(lwe_q);
278 shares.iter().for_each(|si| {
279 assert!(si.lwe_ksk.as_ref().len() == rlwe_n * parameters.lwe_decomposition_count().0);
280 lweq_modop.elwise_add_mut(lwe_ksk.as_mut(), si.lwe_ksk.as_ref())
281 });
282
283 SeededMultiPartyServerKey {
284 rgsw_cts,
285 auto_keys,
286 lwe_ksk,
287 cr_seed,
288 parameters: parameters,
289 }
290}
291
292/// Seeded single party server key
293struct SeededServerKey<M: Matrix, P, S> {
294 /// Rgsw cts of LWE secret elements
295 pub(crate) rgsw_cts: Vec<M>,
296 /// Auto keys
297 pub(crate) auto_keys: HashMap<isize, M>,
298 /// LWE ksk to key switching LWE ciphertext from RLWE secret to LWE secret
299 pub(crate) lwe_ksk: M::R,
300 /// Parameters
301 pub(crate) parameters: P,
302 /// Main seed
303 pub(crate) seed: S,
304}
305
306impl<M: Matrix, S> SeededServerKey<M, BoolParameters<M::MatElement>, S> {
307 pub(crate) fn from_raw(
308 auto_keys: HashMap<isize, M>,
309 rgsw_cts: Vec<M>,
310 lwe_ksk: M::R,
311 parameters: BoolParameters<M::MatElement>,
312 seed: S,
313 ) -> Self {
314 // sanity checks
315 auto_keys.iter().for_each(|v| {
316 assert!(
317 v.1.dimension()
318 == (
319 parameters.auto_decomposition_count().0,
320 parameters.rlwe_n().0
321 )
322 )
323 });
324
325 let (part_a_d, part_b_d) = parameters.rlwe_rgsw_decomposition_count();
326 rgsw_cts.iter().for_each(|v| {
327 assert!(v.dimension() == (part_a_d.0 * 2 + part_b_d.0, parameters.rlwe_n().0))
328 });
329 assert!(
330 lwe_ksk.as_ref().len()
331 == (parameters.lwe_decomposition_count().0 * parameters.rlwe_n().0)
332 );
333
334 SeededServerKey {
335 rgsw_cts,
336 auto_keys,
337 lwe_ksk,
338 parameters,
339 seed,
340 }
341 }
342}
343
344/// Server key in evaluation domain
345struct ServerKeyEvaluationDomain<M, R, N> {
346 /// Rgsw cts of LWE secret elements
347 rgsw_cts: Vec<M>,
348 /// Galois keys
349 galois_keys: HashMap<isize, M>,
350 /// LWE ksk to key switching LWE ciphertext from RLWE secret to LWE secret
351 lwe_ksk: M,
352 _phanton: PhantomData<(R, N)>,
353}
354
355impl<
356 M: MatrixMut + MatrixEntity,
357 R: RandomUniformDist<[M::MatElement], Parameters = M::MatElement> + NewWithSeed,
358 N: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement>,
359 > From<&SeededServerKey<M, BoolParameters<M::MatElement>, R::Seed>>
360 for ServerKeyEvaluationDomain<M, R, N>
361where
362 <M as Matrix>::R: RowMut,
363 M::MatElement: Copy,
364 R::Seed: Clone,
365{
366 fn from(value: &SeededServerKey<M, BoolParameters<M::MatElement>, R::Seed>) -> Self {
367 let mut main_prng = R::new_with_seed(value.seed.clone());
368 let parameters = &value.parameters;
369 let g = parameters.g() as isize;
370 let ring_size = value.parameters.rlwe_n().0;
371 let lwe_n = value.parameters.lwe_n().0;
372 let rlwe_q = value.parameters.rlwe_q().0;
373 let lwq_q = value.parameters.lwe_q().0;
374
375 let nttop = N::new(rlwe_q, ring_size);
376
377 // galois keys
378 let mut auto_keys = HashMap::new();
379 let auto_decomp_count = parameters.auto_decomposition_count().0;
380 for i in [g, -g] {
381 let seeded_auto_key = value.auto_keys.get(&i).unwrap();
382 assert!(seeded_auto_key.dimension() == (auto_decomp_count, ring_size));
383
384 let mut data = M::zeros(auto_decomp_count * 2, ring_size);
385
386 // sample RLWE'_A(-s(X^k))
387 data.iter_rows_mut().take(auto_decomp_count).for_each(|ri| {
388 RandomUniformDist::random_fill(&mut main_prng, &rlwe_q, ri.as_mut())
389 });
390
391 // copy over RLWE'B_(-s(X^k))
392 izip!(
393 data.iter_rows_mut().skip(auto_decomp_count),
394 seeded_auto_key.iter_rows()
395 )
396 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
397
398 // Send to Evaluation domain
399 data.iter_rows_mut()
400 .for_each(|ri| nttop.forward(ri.as_mut()));
401
402 auto_keys.insert(i, data);
403 }
404
405 // RGSW ciphertexts
406 let (rlrg_a_decomp, rlrg_b_decomp) = parameters.rlwe_rgsw_decomposition_count();
407 let rgsw_cts = value
408 .rgsw_cts
409 .iter()
410 .map(|seeded_rgsw_si| {
411 assert!(
412 seeded_rgsw_si.dimension()
413 == (rlrg_a_decomp.0 * 2 + rlrg_b_decomp.0, ring_size)
414 );
415
416 let mut data = M::zeros(rlrg_a_decomp.0 * 2 + rlrg_b_decomp.0 * 2, ring_size);
417
418 // copy over RLWE'(-sm)
419 izip!(
420 data.iter_rows_mut().take(rlrg_a_decomp.0 * 2),
421 seeded_rgsw_si.iter_rows().take(rlrg_a_decomp.0 * 2)
422 )
423 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
424
425 // sample RLWE'_A(m)
426 data.iter_rows_mut()
427 .skip(rlrg_a_decomp.0 * 2)
428 .take(rlrg_b_decomp.0)
429 .for_each(|ri| {
430 RandomUniformDist::random_fill(&mut main_prng, &rlwe_q, ri.as_mut())
431 });
432
433 // copy over RLWE'_B(m)
434 izip!(
435 data.iter_rows_mut()
436 .skip(rlrg_a_decomp.0 * 2 + rlrg_b_decomp.0),
437 seeded_rgsw_si.iter_rows().skip(rlrg_a_decomp.0 * 2)
438 )
439 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
440
441 // send polynomials to evaluation domain
442 data.iter_rows_mut()
443 .for_each(|ri| nttop.forward(ri.as_mut()));
444
445 data
446 })
447 .collect_vec();
448
449 // LWE ksk
450 let lwe_ksk = {
451 let d = parameters.lwe_decomposition_count().0;
452 assert!(value.lwe_ksk.as_ref().len() == d * ring_size);
453
454 let mut data = M::zeros(d * ring_size, lwe_n + 1);
455 izip!(data.iter_rows_mut(), value.lwe_ksk.as_ref().iter()).for_each(|(lwe_i, bi)| {
456 RandomUniformDist::random_fill(&mut main_prng, &lwq_q, &mut lwe_i.as_mut()[1..]);
457 lwe_i.as_mut()[0] = *bi;
458 });
459
460 data
461 };
462
463 ServerKeyEvaluationDomain {
464 rgsw_cts,
465 galois_keys: auto_keys,
466 lwe_ksk,
467 _phanton: PhantomData,
468 }
469 }
470}
471
472impl<
473 M: MatrixMut + MatrixEntity,
474 Rng: NewWithSeed,
475 N: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement>,
476 > From<&SeededMultiPartyServerKey<M, Rng::Seed, BoolParameters<M::MatElement>>>
477 for ServerKeyEvaluationDomain<M, Rng, N>
478where
479 <M as Matrix>::R: RowMut,
480 Rng::Seed: Copy,
481 Rng: RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
482 M::MatElement: Copy,
483{
484 fn from(
485 value: &SeededMultiPartyServerKey<M, Rng::Seed, BoolParameters<M::MatElement>>,
486 ) -> Self {
487 let g = value.parameters.g() as isize;
488 let rlwe_n = value.parameters.rlwe_n().0;
489 let lwe_n = value.parameters.lwe_n().0;
490 let rlwe_q = value.parameters.rlwe_q().0;
491 let lwe_q = value.parameters.lwe_q().0;
492
493 let mut main_prng = Rng::new_with_seed(value.cr_seed);
494
495 let rlwe_nttop = N::new(rlwe_q, rlwe_n);
496
497 // auto keys
498 let mut auto_keys = HashMap::new();
499 let auto_d_count = value.parameters.auto_decomposition_count().0;
500 for i in [g, -g] {
501 let mut key = M::zeros(auto_d_count * 2, rlwe_n);
502
503 // sample a
504 key.iter_rows_mut().take(auto_d_count).for_each(|ri| {
505 RandomUniformDist::random_fill(&mut main_prng, &rlwe_q, ri.as_mut())
506 });
507
508 let key_part_b = value.auto_keys.get(&i).unwrap();
509 assert!(key_part_b.dimension() == (auto_d_count, rlwe_n));
510 izip!(
511 key.iter_rows_mut().skip(auto_d_count),
512 key_part_b.iter_rows()
513 )
514 .for_each(|(to_ri, from_ri)| {
515 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
516 });
517
518 // send to evaluation domain
519 key.iter_rows_mut()
520 .for_each(|ri| rlwe_nttop.forward(ri.as_mut()));
521
522 auto_keys.insert(i, key);
523 }
524
525 // rgsw cts
526 let (rlrg_d_a, rlrg_d_b) = value.parameters.rlwe_rgsw_decomposition_count();
527 let rgsw_ct_rows = rlrg_d_a.0 * 2 + rlrg_d_b.0 * 2;
528 let rgsw_cts = value
529 .rgsw_cts
530 .iter()
531 .map(|ct_i| {
532 assert!(ct_i.dimension() == (rgsw_ct_rows, rlwe_n));
533 let mut eval_ct_i = M::zeros(rgsw_ct_rows, rlwe_n);
534
535 izip!(eval_ct_i.iter_rows_mut(), ct_i.iter_rows()).for_each(|(to_ri, from_ri)| {
536 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
537 rlwe_nttop.forward(to_ri.as_mut());
538 });
539
540 eval_ct_i
541 })
542 .collect_vec();
543
544 // lwe ksk
545 let d_lwe = value.parameters.lwe_decomposition_count().0;
546 let mut lwe_ksk = M::zeros(rlwe_n * d_lwe, lwe_n + 1);
547 izip!(lwe_ksk.iter_rows_mut(), value.lwe_ksk.as_ref().iter()).for_each(|(lwe_i, bi)| {
548 RandomUniformDist::random_fill(&mut main_prng, &lwe_q, &mut lwe_i.as_mut()[1..]);
549 lwe_i.as_mut()[0] = *bi;
550 });
551
552 ServerKeyEvaluationDomain {
553 rgsw_cts,
554 galois_keys: auto_keys,
555 lwe_ksk,
556 _phanton: PhantomData,
557 }
558 }
559}
560
561//FIXME(Jay): Figure out a way for BoolEvaluator to have access to ServerKey
562// via a pointer and implement PbsKey for BoolEvaluator instead of ServerKey
563// directly
564impl<M: Matrix, R, N> PbsKey for ServerKeyEvaluationDomain<M, R, N> {
565 type M = M;
566 fn galois_key_for_auto(&self, k: isize) -> &Self::M {
567 self.galois_keys.get(&k).unwrap()
568 }
569 fn rgsw_ct_lwe_si(&self, si: usize) -> &Self::M {
570 &self.rgsw_cts[si]
571 }
572
573 fn lwe_ksk(&self) -> &Self::M {
574 &self.lwe_ksk
575 }
576}
577
578struct BoolEvaluator<M, E, Ntt, ModOp>
579where
580 M: Matrix,
581{
582 parameters: BoolParameters<E>,
583 decomposer_rlwe: DefaultDecomposer<E>,
584 decomposer_lwe: DefaultDecomposer<E>,
585 g_k_dlog_map: Vec<usize>,
586 rlwe_nttop: Ntt,
587 rlwe_modop: ModOp,
588 lwe_modop: ModOp,
589 embedding_factor: usize,
590 nand_test_vec: M::R,
591 rlweq_by8: M::MatElement,
592 rlwe_qby4: M::MatElement,
593 rlwe_auto_maps: Vec<(Vec<usize>, Vec<bool>)>,
594 _phantom: PhantomData<M>,
595}
596
597impl<M, NttOp, ModOp> BoolEvaluator<M, M::MatElement, NttOp, ModOp>
598where
599 NttOp: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement>,
600 ModOp: ModInit<Element = M::MatElement>
601 + ArithmeticOps<Element = M::MatElement>
602 + VectorOps<Element = M::MatElement>,
603 M::MatElement: PrimInt + Debug + Display + NumInfo + FromPrimitive + WrappingSub,
604 M: MatrixEntity + MatrixMut,
605 M::R: TryConvertFrom<[i32], Parameters = M::MatElement> + RowEntity + Debug,
606 M: TryConvertFrom<[i32], Parameters = M::MatElement>,
607 <M as Matrix>::R: RowMut,
608 DefaultSecureRng: RandomGaussianDist<[M::MatElement], Parameters = M::MatElement>
609 + RandomGaussianDist<M::MatElement, Parameters = M::MatElement>
610 + RandomUniformDist<[M::MatElement], Parameters = M::MatElement>
611 + NewWithSeed,
612{
613 fn new(parameters: BoolParameters<M::MatElement>) -> Self {
614 //TODO(Jay): Run sanity checks for modulus values in parameters
615 assert!(parameters.br_q.is_power_of_two());
616
617 let decomposer_rlwe =
618 DefaultDecomposer::new(parameters.rlwe_q, parameters.logb_rgsw, parameters.d_rgsw);
619 let decomposer_lwe =
620 DefaultDecomposer::new(parameters.lwe_q, parameters.logb_lwe, parameters.d_lwe);
621
622 // generatr dlog map s.t. g^{k} % q = a, for all a \in Z*_{q}
623 let g = parameters.g;
624 let q = parameters.br_q;
625 let mut g_k_dlog_map = vec![0usize; q];
626 for i in 0..q / 2 {
627 let v = mod_exponent(g as u64, i as u64, q as u64) as usize;
628 // g^i
629 g_k_dlog_map[v] = i;
630 // -(g^i)
631 g_k_dlog_map[q - v] = i + (q / 2);
632 }
633
634 let embedding_factor = (2 * parameters.rlwe_n) / q;
635
636 let rlwe_nttop = NttOp::new(parameters.rlwe_q, parameters.rlwe_n);
637 let rlwe_modop = ModInit::new(parameters.rlwe_q);
638 let lwe_modop = ModInit::new(parameters.lwe_q);
639
640 // set test vectors
641 let el_one = M::MatElement::one();
642 let nand_map = |index: usize, qby8: usize| {
643 if index < (3 * qby8) {
644 true
645 } else {
646 false
647 }
648 };
649
650 let q = parameters.br_q;
651 let qby2 = q >> 1;
652 let qby8 = q >> 3;
653 let mut nand_test_vec = M::R::zeros(qby2);
654 // Q/8 (Q: rlwe_q)
655 let rlwe_qby8 =
656 M::MatElement::from_f64((parameters.rlwe_q.to_f64().unwrap() / 8.0).round()).unwrap();
657 let true_m_el = rlwe_qby8;
658 // -Q/8
659 let false_m_el = parameters.rlwe_q - rlwe_qby8;
660 for i in 0..qby2 {
661 let v = nand_map(i, qby8);
662 if v {
663 nand_test_vec.as_mut()[i] = true_m_el;
664 } else {
665 nand_test_vec.as_mut()[i] = false_m_el;
666 }
667 }
668 // // Rotate and negate by q/8
669 // let mut tmp = M::R::zeros(qby2);
670 // tmp.as_mut()[..qby2 - qby8].copy_from_slice(&nand_test_vec.as_ref()[qby8..]);
671 // tmp.as_mut()[qby2 - qby8..].copy_from_slice(&nand_test_vec.as_ref()[..qby8]);
672 // tmp.as_mut()[qby2 - qby8..].iter_mut().for_each(|v| {
673 // *v = parameters.rlwe_q - *v;
674 // });
675 // let nand_test_vec = tmp;
676
677 // v(X) -> v(X^{-g})
678 let (auto_map_index, auto_map_sign) = generate_auto_map(qby2, -(g as isize));
679 let mut nand_test_vec_autog = M::R::zeros(qby2);
680 izip!(
681 nand_test_vec.as_ref().iter(),
682 auto_map_index.iter(),
683 auto_map_sign.iter()
684 )
685 .for_each(|(v, to_index, to_sign)| {
686 if !to_sign {
687 // negate
688 nand_test_vec_autog.as_mut()[*to_index] = parameters.rlwe_q - *v;
689 } else {
690 nand_test_vec_autog.as_mut()[*to_index] = *v;
691 }
692 });
693
694 // auto map indices and sign
695 let mut rlwe_auto_maps = vec![];
696 let ring_size = parameters.rlwe_n;
697 let g = parameters.g as isize;
698 for i in [g, -g] {
699 rlwe_auto_maps.push(generate_auto_map(ring_size, i))
700 }
701
702 let rlwe_qby4 =
703 M::MatElement::from_f64((parameters.rlwe_q.to_f64().unwrap() / 4.0).round()).unwrap();
704
705 BoolEvaluator {
706 parameters: parameters,
707 decomposer_lwe,
708 decomposer_rlwe,
709 g_k_dlog_map,
710 embedding_factor,
711 lwe_modop,
712 rlwe_modop,
713 rlwe_nttop,
714 nand_test_vec: nand_test_vec_autog,
715 rlweq_by8: rlwe_qby8,
716 rlwe_qby4: rlwe_qby4,
717 rlwe_auto_maps,
718
719 _phantom: PhantomData,
720 }
721 }
722
723 fn client_key(&self) -> ClientKey {
724 let sk_lwe = LweSecret::random(self.parameters.lwe_n >> 1, self.parameters.lwe_n);
725 let sk_rlwe = RlweSecret::random(self.parameters.rlwe_n >> 1, self.parameters.rlwe_n);
726 ClientKey { sk_rlwe, sk_lwe }
727 }
728
729 fn server_key(
730 &self,
731 client_key: &ClientKey,
732 ) -> SeededServerKey<M, BoolParameters<M::MatElement>, [u8; 32]> {
733 DefaultSecureRng::with_local_mut(|rng| {
734 let mut main_seed = [0u8; 32];
735 rng.fill_bytes(&mut main_seed);
736
737 let mut main_prng = DefaultSecureRng::new_seeded(main_seed);
738
739 let sk_rlwe = &client_key.sk_rlwe;
740 let sk_lwe = &client_key.sk_lwe;
741
742 let d_rgsw_gadget_vec = self.decomposer_rlwe.gadget_vector();
743
744 // generate auto keys -g, g
745 let mut auto_keys = HashMap::new();
746 let g = self.parameters.g as isize;
747 for i in [g, -g] {
748 let mut gk = M::zeros(self.parameters.d_rgsw, self.parameters.rlwe_n);
749 galois_key_gen(
750 &mut gk,
751 sk_rlwe.values(),
752 i,
753 &d_rgsw_gadget_vec,
754 &self.rlwe_modop,
755 &self.rlwe_nttop,
756 &mut main_prng,
757 rng,
758 );
759 auto_keys.insert(i, gk);
760 }
761
762 // generate rgsw ciphertexts RGSW(si) where si is i^th LWE secret element
763 let ring_size = self.parameters.rlwe_n;
764 let rlwe_q = self.parameters.rlwe_q;
765 let rgsw_cts = sk_lwe
766 .values()
767 .iter()
768 .map(|si| {
769 // X^{si}; assume |emebedding_factor * si| < N
770 let mut m = M::R::zeros(ring_size);
771 let si = (self.embedding_factor as i32) * si;
772 // dbg!(si);
773 if si < 0 {
774 // X^{-i} = X^{2N - i} = -X^{N-i}
775 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q - M::MatElement::one();
776 } else {
777 // X^{i}
778 m.as_mut()[si.abs() as usize] = M::MatElement::one();
779 }
780
781 let mut rgsw_si = M::zeros(self.parameters.d_rgsw * 3, ring_size);
782 secret_key_encrypt_rgsw(
783 &mut rgsw_si,
784 m.as_ref(),
785 &d_rgsw_gadget_vec,
786 sk_rlwe.values(),
787 &self.rlwe_modop,
788 &self.rlwe_nttop,
789 &mut main_prng,
790 rng,
791 );
792
793 rgsw_si
794 })
795 .collect_vec();
796
797 // LWE KSK from RLWE secret s -> LWE secret z
798 let d_lwe_gadget = self.decomposer_lwe.gadget_vector();
799
800 let mut lwe_ksk = M::R::zeros(self.parameters.d_lwe * ring_size);
801 lwe_ksk_keygen(
802 &sk_rlwe.values(),
803 &sk_lwe.values(),
804 &mut lwe_ksk,
805 &d_lwe_gadget,
806 &self.lwe_modop,
807 &mut main_prng,
808 rng,
809 );
810
811 SeededServerKey::from_raw(
812 auto_keys,
813 rgsw_cts,
814 lwe_ksk,
815 self.parameters.clone(),
816 main_seed,
817 )
818 })
819 }
820
821 fn multi_party_sever_key_share(
822 &self,
823 cr_seed: [u8; 32],
824 collective_pk: &M,
825 client_key: &ClientKey,
826 ) -> CommonReferenceSeededMultiPartyServerKeyShare<M, BoolParameters<M::MatElement>, [u8; 32]>
827 {
828 DefaultSecureRng::with_local_mut(|rng| {
829 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
830
831 let sk_rlwe = &client_key.sk_rlwe;
832 let sk_lwe = &client_key.sk_lwe;
833
834 let g = self.parameters.g as isize;
835 let ring_size = self.parameters.rlwe_n;
836 let d_rgsw = self.parameters.d_rgsw;
837 let d_lwe = self.parameters.d_lwe;
838 let rlwe_q = self.parameters.rlwe_q;
839 let lwe_q = self.parameters.lwe_q;
840
841 let d_rgsw_gadget_vec = self.decomposer_rlwe.gadget_vector();
842
843 let rlweq_modop = ModOp::new(rlwe_q);
844 let rlweq_nttop = NttOp::new(rlwe_q, ring_size);
845
846 // sanity check
847 assert!(sk_rlwe.values().len() == ring_size);
848 assert!(sk_lwe.values().len() == self.parameters.lwe_n);
849
850 // auto keys
851 let mut auto_keys = HashMap::new();
852 for i in [g, -g] {
853 let mut ksk_out = M::zeros(d_rgsw, ring_size);
854 galois_key_gen(
855 &mut ksk_out,
856 sk_rlwe.values(),
857 i,
858 &d_rgsw_gadget_vec,
859 &rlweq_modop,
860 &rlweq_nttop,
861 &mut main_prng,
862 rng,
863 );
864 auto_keys.insert(i, ksk_out);
865 }
866
867 // rgsw ciphertexts of lwe secret elements
868 let rgsw_cts = sk_lwe
869 .values()
870 .iter()
871 .map(|si| {
872 let mut m = M::R::zeros(ring_size);
873 //TODO(Jay): It will be nice to have a function that returns polynomial
874 // (monomial infact!) corresponding to secret element embedded in ring X^{2N+1}.
875 // Save lots of mistakes where one forgest to emebed si in bigger ring.
876 let si = *si * (self.embedding_factor as i32);
877 if si < 0 {
878 // X^{-si} = X^{2N-si} = -X^{N-si}, assuming abs(si) < N
879 // (which it is given si is secret element)
880 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q - M::MatElement::one();
881 } else {
882 m.as_mut()[si as usize] = M::MatElement::one();
883 }
884
885 // public key RGSW encryption has no part that can be seeded, unlike secret key
886 // RGSW encryption where RLWE'_A(m) is seeded
887 let mut out_rgsw = M::zeros(d_rgsw * 4, ring_size);
888 public_key_encrypt_rgsw(
889 &mut out_rgsw,
890 &m.as_ref(),
891 collective_pk,
892 &d_rgsw_gadget_vec,
893 &rlweq_modop,
894 &rlweq_nttop,
895 rng,
896 );
897
898 out_rgsw
899 })
900 .collect_vec();
901
902 // LWE ksk
903 let mut lwe_ksk = M::R::zeros(d_lwe * ring_size);
904 let lwe_modop = ModOp::new(lwe_q);
905 let d_lwe_gadget_vec = self.decomposer_lwe.gadget_vector();
906 lwe_ksk_keygen(
907 sk_rlwe.values(),
908 sk_lwe.values(),
909 &mut lwe_ksk,
910 &d_lwe_gadget_vec,
911 &lwe_modop,
912 &mut main_prng,
913 rng,
914 );
915
916 CommonReferenceSeededMultiPartyServerKeyShare {
917 auto_keys,
918 rgsw_cts,
919 lwe_ksk,
920 cr_seed,
921 parameters: self.parameters.clone(),
922 }
923 })
924 }
925
926 fn multi_party_public_key_share(
927 &self,
928 cr_seed: [u8; 32],
929 client_key: &ClientKey,
930 ) -> CommonReferenceSeededCollectivePublicKeyShare<
931 <M as Matrix>::R,
932 [u8; 32],
933 BoolParameters<<M as Matrix>::MatElement>,
934 > {
935 DefaultSecureRng::with_local_mut(|rng| {
936 let mut share_out = M::R::zeros(self.parameters.rlwe_n);
937 let modop = ModOp::new(self.parameters.rlwe_q);
938 let nttop = NttOp::new(self.parameters.rlwe_q, self.parameters.rlwe_n);
939 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
940 public_key_share(
941 &mut share_out,
942 client_key.sk_rlwe.values(),
943 &modop,
944 &nttop,
945 &mut main_prng,
946 rng,
947 );
948
949 CommonReferenceSeededCollectivePublicKeyShare {
950 share: share_out,
951 cr_seed: cr_seed,
952 parameters: self.parameters.clone(),
953 }
954 })
955 }
956
957 fn multi_party_decryption_share(
958 &self,
959 lwe_ct: &M::R,
960 client_key: &ClientKey,
961 ) -> MultiPartyDecryptionShare<<M as Matrix>::MatElement> {
962 assert!(lwe_ct.as_ref().len() == self.parameters.rlwe_n + 1);
963 let modop = &self.rlwe_modop;
964 let mut neg_s =
965 M::R::try_convert_from(client_key.sk_rlwe.values(), &self.parameters.rlwe_q);
966 modop.elwise_neg_mut(neg_s.as_mut());
967
968 let mut neg_sa = M::MatElement::zero();
969 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
970 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
971 });
972
973 let e = DefaultSecureRng::with_local_mut(|rng| {
974 let mut e = M::MatElement::zero();
975 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, &mut e);
976 e
977 });
978 let share = modop.add(&neg_sa, &e);
979
980 MultiPartyDecryptionShare { share }
981 }
982
983 pub(crate) fn multi_party_decrypt(
984 &self,
985 shares: &[MultiPartyDecryptionShare<M::MatElement>],
986 lwe_ct: &M::R,
987 ) -> bool {
988 let modop = &self.rlwe_modop;
989 let mut sum_a = M::MatElement::zero();
990 shares
991 .iter()
992 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i.share));
993
994 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
995
996 let m = (((encoded_m + self.rlweq_by8).to_f64().unwrap() * 4f64)
997 / self.parameters.rlwe_q.to_f64().unwrap())
998 .round() as usize
999 % 4usize;
1000
1001 if m == 0 {
1002 return false;
1003 } else if m == 1 {
1004 return true;
1005 } else {
1006 panic!("Bool decryption failure. Expected m to be either 1 or 0, but m={m} ");
1007 }
1008 }
1009
1010 /// First encrypt as RLWE(m) with m as constant polynomial and extract it as
1011 /// LWE ciphertext
1012 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
1013 DefaultSecureRng::with_local_mut(|rng| {
1014 let modop = &self.rlwe_modop;
1015 let nttop = &self.rlwe_nttop;
1016
1017 // RLWE(0)
1018 // sample ephemeral key u
1019 let ring_size = self.parameters.rlwe_n;
1020 let mut u = vec![0i32; ring_size];
1021 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1022 let mut u = M::R::try_convert_from(&u, &self.parameters.rlwe_q);
1023 nttop.forward(u.as_mut());
1024
1025 let mut ua = M::R::zeros(ring_size);
1026 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1027 let mut ub = M::R::zeros(ring_size);
1028 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1029
1030 // a*u
1031 nttop.forward(ua.as_mut());
1032 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
1033 nttop.backward(ua.as_mut());
1034
1035 // b*u
1036 nttop.forward(ub.as_mut());
1037 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
1038 nttop.backward(ub.as_mut());
1039
1040 let mut rlwe = M::zeros(2, ring_size);
1041 // sample error
1042 rlwe.iter_rows_mut().for_each(|ri| {
1043 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, ri.as_mut());
1044 });
1045
1046 // a*u + e0
1047 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
1048 // b*u + e1
1049 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
1050
1051 let m = if m {
1052 // Q/8
1053 self.rlweq_by8
1054 } else {
1055 // -Q/8
1056 self.parameters.rlwe_q - self.rlweq_by8
1057 };
1058
1059 // b*u + e1 + m, where m is constant polynomial
1060 rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
1061
1062 // sample extract index 0
1063 let mut lwe_out = M::R::zeros(ring_size + 1);
1064 sample_extract(&mut lwe_out, &rlwe, modop, 0);
1065
1066 lwe_out
1067 })
1068 }
1069
1070 /// TODO(Jay): Fetch client key from thread local
1071 pub fn sk_encrypt(&self, m: bool, client_key: &ClientKey) -> M::R {
1072 let m = if m {
1073 // Q/8
1074 self.rlweq_by8
1075 } else {
1076 // -Q/8
1077 self.parameters.rlwe_q - self.rlweq_by8
1078 };
1079
1080 DefaultSecureRng::with_local_mut(|rng| {
1081 let mut lwe_out = M::R::zeros(self.parameters.rlwe_n + 1);
1082 encrypt_lwe(
1083 &mut lwe_out,
1084 &m,
1085 client_key.sk_rlwe.values(),
1086 &self.rlwe_modop,
1087 rng,
1088 );
1089 lwe_out
1090 })
1091 }
1092
1093 pub fn sk_decrypt(&self, lwe_ct: &M::R, client_key: &ClientKey) -> bool {
1094 let m = decrypt_lwe(lwe_ct, client_key.sk_rlwe.values(), &self.rlwe_modop);
1095 let m = {
1096 // m + q/8 => {0,q/4 1}
1097 (((m + self.rlweq_by8).to_f64().unwrap() * 4.0)
1098 / self.parameters.rlwe_q.to_f64().unwrap())
1099 .round()
1100 .to_usize()
1101 .unwrap()
1102 % 4
1103 };
1104
1105 if m == 0 {
1106 false
1107 } else if m == 1 {
1108 true
1109 } else {
1110 panic!("Incorrect bool decryption. Got m={m} but expected m to be 0 or 1")
1111 }
1112 }
1113
1114 // TODO(Jay): scratch spaces must be thread local. Don't pass them as arguments
1115 pub fn nand(
1116 &self,
1117 c0: &M::R,
1118 c1: &M::R,
1119 server_key: &ServerKeyEvaluationDomain<M, DefaultSecureRng, NttOp>,
1120 scratch_lwen_plus1: &mut M::R,
1121 scratch_matrix_dplus2_ring: &mut M,
1122 ) -> M::R {
1123 // ClientKey::with_local(|ck| {
1124 // let c0_noise = measure_noise_lwe(
1125 // c0,
1126 // ck.sk_rlwe.values(),
1127 // &self.rlwe_modop,
1128 // &(self.rlwe_q() - self.rlweq_by8),
1129 // );
1130 // let c1_noise =
1131 // measure_noise_lwe(c1, ck.sk_rlwe.values(), &self.rlwe_modop,
1132 // &(self.rlweq_by8)); println!(
1133 // "c0 noise: {c0_noise}; c1 noise:
1134 // {c1_noise}"
1135 // );
1136 // });
1137
1138 let mut c_out = M::R::zeros(c0.as_ref().len());
1139 let modop = &self.rlwe_modop;
1140 izip!(
1141 c_out.as_mut().iter_mut(),
1142 c0.as_ref().iter(),
1143 c1.as_ref().iter()
1144 )
1145 .for_each(|(o, i0, i1)| {
1146 *o = modop.add(i0, i1);
1147 });
1148 // +Q/8
1149 c_out.as_mut()[0] = modop.add(&c_out.as_ref()[0], &self.rlwe_qby4);
1150
1151 // ClientKey::with_local(|ck| {
1152 // let noise = measure_noise_lwe(
1153 // &c_out,
1154 // ck.sk_rlwe.values(),
1155 // &self.rlwe_modop,
1156 // &(self.rlweq_by8),
1157 // );
1158 // println!("cout_noise: {noise}");
1159 // });
1160
1161 // PBS
1162 pbs(
1163 self,
1164 &self.nand_test_vec,
1165 &mut c_out,
1166 scratch_lwen_plus1,
1167 scratch_matrix_dplus2_ring,
1168 &self.lwe_modop,
1169 &self.rlwe_modop,
1170 &self.rlwe_nttop,
1171 server_key,
1172 );
1173
1174 c_out
1175 }
1176}
1177
1178impl<M: Matrix, NttOp, ModOp> PbsParameters for BoolEvaluator<M, M::MatElement, NttOp, ModOp>
1179where
1180 M::MatElement: PrimInt + WrappingSub + Debug,
1181{
1182 type Element = M::MatElement;
1183 type D = DefaultDecomposer<M::MatElement>;
1184 fn rlwe_auto_map(&self, k: isize) -> &(Vec<usize>, Vec<bool>) {
1185 let g = self.parameters.g as isize;
1186 if k == g {
1187 &self.rlwe_auto_maps[0]
1188 } else if k == -g {
1189 &self.rlwe_auto_maps[1]
1190 } else {
1191 panic!("RLWE auto map only supports k in [-g, g], but got k={k}");
1192 }
1193 }
1194
1195 fn br_q(&self) -> usize {
1196 self.parameters.br_q
1197 }
1198 fn d_lwe(&self) -> usize {
1199 self.parameters.d_lwe
1200 }
1201 fn d_rgsw(&self) -> usize {
1202 self.parameters.d_rgsw
1203 }
1204 fn decomoposer_lwe(&self) -> &Self::D {
1205 &self.decomposer_lwe
1206 }
1207 fn decomoposer_rlwe(&self) -> &Self::D {
1208 &self.decomposer_rlwe
1209 }
1210 fn embedding_factor(&self) -> usize {
1211 self.embedding_factor
1212 }
1213 fn g(&self) -> isize {
1214 self.parameters.g as isize
1215 }
1216 fn g_k_dlog_map(&self) -> &[usize] {
1217 &self.g_k_dlog_map
1218 }
1219 fn lwe_n(&self) -> usize {
1220 self.parameters.lwe_n
1221 }
1222 fn lwe_q(&self) -> Self::Element {
1223 self.parameters.lwe_q
1224 }
1225 fn rlwe_n(&self) -> usize {
1226 self.parameters.rlwe_n
1227 }
1228 fn rlwe_q(&self) -> Self::Element {
1229 self.parameters.rlwe_q
1230 }
1231}
1232
1233/// LMKCY+ Blind rotation
1234///
1235/// gk_to_si: [-g^0, -g^1, .., -g^{q/2-1}, g^0, ..., g^{q/2-1}]
1236fn blind_rotation<
1237 MT: IsTrivial + MatrixMut,
1238 Mmut: MatrixMut<MatElement = MT::MatElement> + Matrix,
1239 D: Decomposer<Element = MT::MatElement>,
1240 NttOp: Ntt<Element = MT::MatElement>,
1241 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
1242 K: PbsKey<M = Mmut>,
1243 P: PbsParameters<Element = MT::MatElement>,
1244>(
1245 trivial_rlwe_test_poly: &mut MT,
1246 scratch_matrix_dplus2_ring: &mut Mmut,
1247 g: isize,
1248 w: usize,
1249 q: usize,
1250 gk_to_si: &[Vec<usize>],
1251 decomposer: &D,
1252 ntt_op: &NttOp,
1253 mod_op: &ModOp,
1254 parameters: &P,
1255 pbs_key: &K,
1256) where
1257 <Mmut as Matrix>::R: RowMut,
1258 Mmut::MatElement: Copy + Zero,
1259 <MT as Matrix>::R: RowMut,
1260{
1261 let q_by_2 = q / 2;
1262
1263 // -(g^k)
1264 for i in (1..q_by_2).rev() {
1265 gk_to_si[q_by_2 + i].iter().for_each(|s_index| {
1266 rlwe_by_rgsw(
1267 trivial_rlwe_test_poly,
1268 pbs_key.rgsw_ct_lwe_si(*s_index),
1269 scratch_matrix_dplus2_ring,
1270 decomposer,
1271 ntt_op,
1272 mod_op,
1273 );
1274 });
1275
1276 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1277 galois_auto(
1278 trivial_rlwe_test_poly,
1279 pbs_key.galois_key_for_auto(g),
1280 scratch_matrix_dplus2_ring,
1281 &auto_map_index,
1282 &auto_map_sign,
1283 mod_op,
1284 ntt_op,
1285 decomposer,
1286 );
1287 }
1288
1289 // -(g^0)
1290 gk_to_si[q_by_2].iter().for_each(|s_index| {
1291 rlwe_by_rgsw(
1292 trivial_rlwe_test_poly,
1293 pbs_key.rgsw_ct_lwe_si(*s_index),
1294 scratch_matrix_dplus2_ring,
1295 decomposer,
1296 ntt_op,
1297 mod_op,
1298 );
1299 });
1300 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(-g);
1301 galois_auto(
1302 trivial_rlwe_test_poly,
1303 pbs_key.galois_key_for_auto(-g),
1304 scratch_matrix_dplus2_ring,
1305 &auto_map_index,
1306 &auto_map_sign,
1307 mod_op,
1308 ntt_op,
1309 decomposer,
1310 );
1311
1312 // +(g^k)
1313 for i in (1..q_by_2).rev() {
1314 gk_to_si[i].iter().for_each(|s_index| {
1315 rlwe_by_rgsw(
1316 trivial_rlwe_test_poly,
1317 pbs_key.rgsw_ct_lwe_si(*s_index),
1318 scratch_matrix_dplus2_ring,
1319 decomposer,
1320 ntt_op,
1321 mod_op,
1322 );
1323 });
1324
1325 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1326 galois_auto(
1327 trivial_rlwe_test_poly,
1328 pbs_key.galois_key_for_auto(g),
1329 scratch_matrix_dplus2_ring,
1330 &auto_map_index,
1331 &auto_map_sign,
1332 mod_op,
1333 ntt_op,
1334 decomposer,
1335 );
1336 }
1337
1338 // +(g^0)
1339 gk_to_si[0].iter().for_each(|s_index| {
1340 rlwe_by_rgsw(
1341 trivial_rlwe_test_poly,
1342 pbs_key.rgsw_ct_lwe_si(gk_to_si[q_by_2][*s_index]),
1343 scratch_matrix_dplus2_ring,
1344 decomposer,
1345 ntt_op,
1346 mod_op,
1347 );
1348 });
1349}
1350
1351/// - Mod down
1352/// - key switching
1353/// - mod down
1354/// - blind rotate
1355fn pbs<
1356 M: Matrix + MatrixMut + MatrixEntity,
1357 P: PbsParameters<Element = M::MatElement>,
1358 NttOp: Ntt<Element = M::MatElement>,
1359 ModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
1360 K: PbsKey<M = M>,
1361>(
1362 parameters: &P,
1363 test_vec: &M::R,
1364 lwe_in: &mut M::R,
1365 scratch_lwen_plus1: &mut M::R,
1366 scratch_matrix_dplus2_ring: &mut M,
1367 modop_lweq: &ModOp,
1368 modop_rlweq: &ModOp,
1369 nttop_rlweq: &NttOp,
1370 pbs_key: &K,
1371) where
1372 <M as Matrix>::R: RowMut,
1373 M::MatElement: PrimInt + ToPrimitive + FromPrimitive + One + Copy + Zero + Display,
1374{
1375 let rlwe_q = parameters.rlwe_q();
1376 let lwe_q = parameters.lwe_q();
1377 let br_q = parameters.br_q();
1378 let rlwe_qf64 = rlwe_q.to_f64().unwrap();
1379 let lwe_qf64 = lwe_q.to_f64().unwrap();
1380 let br_qf64 = br_q.to_f64().unwrap();
1381 let rlwe_n = parameters.rlwe_n();
1382
1383 PBSTracer::with_local_mut(|t| {
1384 let out = lwe_in
1385 .as_ref()
1386 .iter()
1387 .map(|v| v.to_u64().unwrap())
1388 .collect_vec();
1389 t.ct_rlwe_q_mod = out;
1390 });
1391
1392 // moddown Q -> Q_ks
1393 lwe_in.as_mut().iter_mut().for_each(|v| {
1394 *v =
1395 M::MatElement::from_f64(((v.to_f64().unwrap() * lwe_qf64) / rlwe_qf64).round()).unwrap()
1396 });
1397
1398 PBSTracer::with_local_mut(|t| {
1399 let out = lwe_in
1400 .as_ref()
1401 .iter()
1402 .map(|v| v.to_u64().unwrap())
1403 .collect_vec();
1404 t.ct_lwe_q_mod = out;
1405 });
1406
1407 // key switch RLWE secret to LWE secret
1408 scratch_lwen_plus1.as_mut().fill(M::MatElement::zero());
1409 lwe_key_switch(
1410 scratch_lwen_plus1,
1411 lwe_in,
1412 pbs_key.lwe_ksk(),
1413 modop_lweq,
1414 parameters.decomoposer_lwe(),
1415 );
1416
1417 PBSTracer::with_local_mut(|t| {
1418 let out = scratch_lwen_plus1
1419 .as_ref()
1420 .iter()
1421 .map(|v| v.to_u64().unwrap())
1422 .collect_vec();
1423 t.ct_lwe_q_mod_after_ksk = out;
1424 });
1425
1426 // odd mowdown Q_ks -> q
1427 let g_k_dlog_map = parameters.g_k_dlog_map();
1428 let mut g_k_si = vec![vec![]; br_q];
1429 scratch_lwen_plus1
1430 .as_ref()
1431 .iter()
1432 .skip(1)
1433 .enumerate()
1434 .for_each(|(index, v)| {
1435 let odd_v = mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64);
1436 let k = g_k_dlog_map[odd_v];
1437 g_k_si[k].push(index);
1438 });
1439
1440 PBSTracer::with_local_mut(|t| {
1441 let out = scratch_lwen_plus1
1442 .as_ref()
1443 .iter()
1444 .map(|v| mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64) as u64)
1445 .collect_vec();
1446 t.ct_br_q_mod = out;
1447 });
1448
1449 // handle b and set trivial test RLWE
1450 let g = parameters.g() as usize;
1451 let g_times_b = (g * mod_switch_odd(
1452 scratch_lwen_plus1.as_ref()[0].to_f64().unwrap(),
1453 lwe_qf64,
1454 br_qf64,
1455 )) % (br_q);
1456 // v = (v(X) * X^{g*b}) mod X^{q/2}+1
1457 let br_qby2 = br_q / 2;
1458 let mut gb_monomial_sign = true;
1459 let mut gb_monomial_exp = g_times_b;
1460 // X^{g*b} mod X^{q/2}+1
1461 if gb_monomial_exp > br_qby2 {
1462 gb_monomial_exp -= br_qby2;
1463 gb_monomial_sign = false
1464 }
1465 // monomial mul
1466 let mut trivial_rlwe_test_poly = RlweCiphertext::<_, DefaultSecureRng> {
1467 data: M::zeros(2, rlwe_n),
1468 is_trivial: true,
1469 _phatom: PhantomData,
1470 };
1471 if parameters.embedding_factor() == 1 {
1472 monomial_mul(
1473 test_vec.as_ref(),
1474 trivial_rlwe_test_poly.get_row_mut(1).as_mut(),
1475 gb_monomial_exp,
1476 gb_monomial_sign,
1477 br_qby2,
1478 modop_rlweq,
1479 );
1480 } else {
1481 // use lwe_in to store the `t = v(X) * X^{g*2} mod X^{q/2}+1` temporarily. This
1482 // works because q/2 <= N (where N is lwe_in LWE dimension) always.
1483 monomial_mul(
1484 test_vec.as_ref(),
1485 &mut lwe_in.as_mut()[..br_qby2],
1486 gb_monomial_exp,
1487 gb_monomial_sign,
1488 br_qby2,
1489 modop_rlweq,
1490 );
1491
1492 // emebed poly `t` in ring X^{q/2}+1 inside the bigger ring X^{N}+1
1493 let embed_factor = parameters.embedding_factor();
1494 let partb_trivial_rlwe = trivial_rlwe_test_poly.get_row_mut(1);
1495 lwe_in.as_ref()[..br_qby2]
1496 .iter()
1497 .enumerate()
1498 .for_each(|(index, v)| {
1499 partb_trivial_rlwe[embed_factor * index] = *v;
1500 });
1501 }
1502
1503 // blind rotate
1504 blind_rotation(
1505 &mut trivial_rlwe_test_poly,
1506 scratch_matrix_dplus2_ring,
1507 parameters.g(),
1508 1,
1509 br_q,
1510 &g_k_si,
1511 parameters.decomoposer_rlwe(),
1512 nttop_rlweq,
1513 modop_rlweq,
1514 parameters,
1515 pbs_key,
1516 );
1517
1518 // ClientKey::with_local(|ck| {
1519 // let ring_size = parameters.rlwe_n();
1520 // let mut rlwe_ct = vec![vec![0u64; ring_size]; 2];
1521 // izip!(
1522 // rlwe_ct[0].iter_mut(),
1523 // trivial_rlwe_test_poly.0.get_row_slice(0)
1524 // )
1525 // .for_each(|(t, f)| {
1526 // *t = f.to_u64().unwrap();
1527 // });
1528 // izip!(
1529 // rlwe_ct[1].iter_mut(),
1530 // trivial_rlwe_test_poly.0.get_row_slice(1)
1531 // )
1532 // .for_each(|(t, f)| {
1533 // *t = f.to_u64().unwrap();
1534 // });
1535 // let mut m_out = vec![vec![0u64; ring_size]];
1536 // let modop = ModularOpsU64::new(rlwe_q.to_u64().unwrap());
1537 // let nttop = NttBackendU64::new(rlwe_q.to_u64().unwrap(), ring_size);
1538 // decrypt_rlwe(&rlwe_ct, ck.sk_rlwe.values(), &mut m_out, &nttop, &modop);
1539
1540 // println!("RLWE post PBS message: {:?}", m_out[0]);
1541 // });
1542
1543 // sample extract
1544 sample_extract(lwe_in, &trivial_rlwe_test_poly, modop_rlweq, 0);
1545}
1546
1547fn mod_switch_odd(v: f64, from_q: f64, to_q: f64) -> usize {
1548 let odd_v = (((v * to_q) / (from_q)).floor()).to_usize().unwrap();
1549 //TODO(Jay): check correctness of this
1550 odd_v + ((odd_v & 1) ^ 1)
1551}
1552
1553// TODO(Jay): Add tests for sample extract
1554fn sample_extract<M: Matrix + MatrixMut, ModOp: ArithmeticOps<Element = M::MatElement>>(
1555 lwe_out: &mut M::R,
1556 rlwe_in: &M,
1557 mod_op: &ModOp,
1558 index: usize,
1559) where
1560 <M as Matrix>::R: RowMut,
1561 M::MatElement: Copy,
1562{
1563 let ring_size = rlwe_in.dimension().1;
1564
1565 // index..=0
1566 let to = &mut lwe_out.as_mut()[1..];
1567 let from = rlwe_in.get_row_slice(0);
1568 for i in 0..index + 1 {
1569 to[i] = from[index - i];
1570 }
1571
1572 // -(N..index)
1573 for i in index + 1..ring_size {
1574 to[i] = mod_op.neg(&from[ring_size + index - i]);
1575 }
1576
1577 // set b
1578 lwe_out.as_mut()[0] = *rlwe_in.get(1, index);
1579}
1580
1581/// TODO(Jay): Write tests for monomial mul
1582fn monomial_mul<El, ModOp: ArithmeticOps<Element = El>>(
1583 p_in: &[El],
1584 p_out: &mut [El],
1585 mon_exp: usize,
1586 mon_sign: bool,
1587 ring_size: usize,
1588 mod_op: &ModOp,
1589) where
1590 El: Copy,
1591{
1592 debug_assert!(p_in.as_ref().len() == ring_size);
1593 debug_assert!(p_in.as_ref().len() == p_out.as_ref().len());
1594 debug_assert!(mon_exp < ring_size);
1595
1596 p_in.as_ref().iter().enumerate().for_each(|(index, v)| {
1597 let mut to_index = index + mon_exp;
1598 let mut to_sign = mon_sign;
1599 if to_index >= ring_size {
1600 to_index = to_index - ring_size;
1601 to_sign = !to_sign;
1602 }
1603
1604 if !to_sign {
1605 p_out.as_mut()[to_index] = mod_op.neg(v);
1606 } else {
1607 p_out.as_mut()[to_index] = *v;
1608 }
1609 });
1610}
1611
1612thread_local! {
1613 static PBS_TRACER: RefCell<PBSTracer<Vec<Vec<u64>>>> = RefCell::new(PBSTracer::default());
1614}
1615
1616#[derive(Default)]
1617struct PBSTracer<M>
1618where
1619 M: Matrix + Default,
1620{
1621 pub(crate) ct_rlwe_q_mod: M::R,
1622 pub(crate) ct_lwe_q_mod: M::R,
1623 pub(crate) ct_lwe_q_mod_after_ksk: M::R,
1624 pub(crate) ct_br_q_mod: Vec<u64>,
1625}
1626
1627impl PBSTracer<Vec<Vec<u64>>> {
1628 fn trace(&self, parameters: &BoolParameters<u64>, sk_lwe: &[i32], sk_rlwe: &[i32]) {
1629 assert!(parameters.rlwe_n == sk_rlwe.len());
1630 assert!(parameters.lwe_n == sk_lwe.len());
1631
1632 let modop_rlweq = ModularOpsU64::new(parameters.rlwe_q as u64);
1633 // noise after mod down Q -> Q_ks
1634 let m_back0 = decrypt_lwe(&self.ct_rlwe_q_mod, sk_rlwe, &modop_rlweq);
1635
1636 let modop_lweq = ModularOpsU64::new(parameters.lwe_q as u64);
1637 // noise after mod down Q -> Q_ks
1638 let m_back1 = decrypt_lwe(&self.ct_lwe_q_mod, sk_rlwe, &modop_lweq);
1639 // noise after key switch from RLWE -> LWE
1640 let m_back2 = decrypt_lwe(&self.ct_lwe_q_mod_after_ksk, sk_lwe, &modop_lweq);
1641
1642 // noise after mod down odd from Q_ks -> q
1643 let modop_br_q = ModularOpsU64::new(parameters.br_q as u64);
1644 let m_back3 = decrypt_lwe(&self.ct_br_q_mod, sk_lwe, &modop_br_q);
1645
1646 println!(
1647 "
1648 M initial mod Q: {m_back0},
1649 M after mod down Q -> Q_ks: {m_back1},
1650 M after key switch from RLWE -> LWE: {m_back2},
1651 M after mod dwon Q_ks -> q: {m_back3}
1652 "
1653 );
1654 }
1655}
1656
1657impl WithLocal for PBSTracer<Vec<Vec<u64>>> {
1658 fn with_local<F, R>(func: F) -> R
1659 where
1660 F: Fn(&Self) -> R,
1661 {
1662 PBS_TRACER.with_borrow(|t| func(t))
1663 }
1664
1665 fn with_local_mut<F, R>(func: F) -> R
1666 where
1667 F: Fn(&mut Self) -> R,
1668 {
1669 PBS_TRACER.with_borrow_mut(|t| func(t))
1670 }
1671}
1672
1673#[cfg(test)]
1674mod tests {
1675 use std::iter::Sum;
1676
1677 use rand::{thread_rng, Rng};
1678 use rand_distr::Uniform;
1679
1680 use crate::{
1681 backend::ModularOpsU64,
1682 bool,
1683 ntt::NttBackendU64,
1684 random::DEFAULT_RNG,
1685 rgsw::{
1686 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
1687 tests::{_measure_noise_rgsw, _secret_encrypt_rlwe},
1688 RgswCiphertext, RgswCiphertextEvaluationDomain, SeededRgswCiphertext,
1689 SeededRlweCiphertext,
1690 },
1691 utils::negacyclic_mul,
1692 };
1693
1694 use self::parameters::{MP_BOOL_PARAMS, SP_BOOL_PARAMS};
1695
1696 use super::*;
1697
1698 // #[test]
1699 // fn trial() {
1700 // dbg!(generate_prime(28, 1 << 11, 1 << 28));
1701 // }
1702
1703 #[test]
1704 fn bool_encrypt_decrypt_works() {
1705 // let prime = generate_prime(32, 2 * 1024, 1 << 32);
1706 // dbg!(prime);
1707 let bool_evaluator =
1708 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1709 let client_key = bool_evaluator.client_key();
1710 // let sever_key = bool_evaluator.server_key(&client_key);
1711
1712 let mut m = true;
1713 for _ in 0..1000 {
1714 let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
1715 let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
1716 assert_eq!(m, m_back);
1717 m = !m;
1718 }
1719 }
1720
1721 #[test]
1722 fn bool_nand() {
1723 DefaultSecureRng::with_local_mut(|r| {
1724 let rng = DefaultSecureRng::new_seeded([19u8; 32]);
1725 *r = rng;
1726 });
1727
1728 let bool_evaluator =
1729 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1730
1731 // println!("{:?}", bool_evaluator.nand_test_vec);
1732 let client_key = bool_evaluator.client_key();
1733 let seeded_server_key = bool_evaluator.server_key(&client_key);
1734 let server_key_eval_domain =
1735 ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1736 &seeded_server_key,
1737 );
1738
1739 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
1740 let mut scratch_matrix_dplus2_ring = vec![
1741 vec![0u64; bool_evaluator.parameters.rlwe_n];
1742 bool_evaluator.parameters.d_rgsw + 2
1743 ];
1744
1745 let mut m0 = false;
1746 let mut m1 = true;
1747 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
1748 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
1749
1750 for _ in 0..1000 {
1751 let ct_back = bool_evaluator.nand(
1752 &ct0,
1753 &ct1,
1754 &server_key_eval_domain,
1755 &mut scratch_lwen_plus1,
1756 &mut scratch_matrix_dplus2_ring,
1757 );
1758
1759 let m_out = !(m0 && m1);
1760
1761 // Trace and measure PBS noise
1762 {
1763 let noise0 = {
1764 let ideal = if m0 {
1765 bool_evaluator.rlweq_by8
1766 } else {
1767 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1768 };
1769 let n = measure_noise_lwe(
1770 &ct0,
1771 client_key.sk_rlwe.values(),
1772 &bool_evaluator.rlwe_modop,
1773 &ideal,
1774 );
1775 let v = decrypt_lwe(
1776 &ct0,
1777 client_key.sk_rlwe.values(),
1778 &bool_evaluator.rlwe_modop,
1779 );
1780 (n, v)
1781 };
1782 let noise1 = {
1783 let ideal = if m1 {
1784 bool_evaluator.rlweq_by8
1785 } else {
1786 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1787 };
1788 let n = measure_noise_lwe(
1789 &ct1,
1790 client_key.sk_rlwe.values(),
1791 &bool_evaluator.rlwe_modop,
1792 &ideal,
1793 );
1794 let v = decrypt_lwe(
1795 &ct1,
1796 client_key.sk_rlwe.values(),
1797 &bool_evaluator.rlwe_modop,
1798 );
1799 (n, v)
1800 };
1801
1802 // Trace PBS
1803 PBSTracer::with_local(|t| {
1804 t.trace(
1805 &SP_BOOL_PARAMS,
1806 &client_key.sk_lwe.values(),
1807 client_key.sk_rlwe.values(),
1808 )
1809 });
1810
1811 // Calculate noise in ciphertext post PBS
1812 let noise_out = {
1813 let ideal = if m_out {
1814 bool_evaluator.rlweq_by8
1815 } else {
1816 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1817 };
1818 let n = measure_noise_lwe(
1819 &ct_back,
1820 client_key.sk_rlwe.values(),
1821 &bool_evaluator.rlwe_modop,
1822 &ideal,
1823 );
1824 let v = decrypt_lwe(
1825 &ct_back,
1826 client_key.sk_rlwe.values(),
1827 &bool_evaluator.rlwe_modop,
1828 );
1829 (n, v)
1830 };
1831 dbg!(m0, m1, m_out);
1832 println!(
1833 "ct0 (noise, message): {:?} \n ct1 (noise, message): {:?} \n PBS (noise, message): {:?}", noise0, noise1, noise_out
1834 );
1835 }
1836 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
1837 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
1838 println!("----------");
1839
1840 m1 = m0;
1841 m0 = m_out;
1842
1843 ct1 = ct0;
1844 ct0 = ct_back;
1845 }
1846 }
1847
1848 #[test]
1849 fn multi_party_encryption_decryption() {
1850 let bool_evaluator =
1851 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
1852
1853 let no_of_parties = 500;
1854 let parties = (0..no_of_parties)
1855 .map(|_| bool_evaluator.client_key())
1856 .collect_vec();
1857
1858 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
1859 parties.iter().for_each(|k| {
1860 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
1861 *ideal_i = *ideal_i + s_i;
1862 });
1863 });
1864
1865 println!("{:?}", &ideal_rlwe_sk);
1866
1867 let mut m = true;
1868 for i in 0..100 {
1869 let pk_cr_seed = [0u8; 32];
1870
1871 let public_key_share = parties
1872 .iter()
1873 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1874 .collect_vec();
1875
1876 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
1877 public_key_share.as_slice(),
1878 );
1879 let lwe_ct = bool_evaluator.pk_encrypt(&collective_pk.key, m);
1880
1881 let decryption_shares = parties
1882 .iter()
1883 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct, k))
1884 .collect_vec();
1885
1886 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
1887
1888 {
1889 let ideal_m = if m {
1890 bool_evaluator.rlweq_by8
1891 } else {
1892 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
1893 };
1894 let noise = measure_noise_lwe(
1895 &lwe_ct,
1896 &ideal_rlwe_sk,
1897 &bool_evaluator.rlwe_modop,
1898 &ideal_m,
1899 );
1900 println!("Noise: {noise}");
1901 }
1902
1903 assert_eq!(m_back, m);
1904 m = !m;
1905 }
1906 }
1907
1908 #[test]
1909 fn ms() {
1910 let logbig_q = 50;
1911 let logsmall_q = 20;
1912 let big_q = 1 << logbig_q;
1913 let small_q = 1 << logsmall_q;
1914 let lwe_n = 493;
1915
1916 let no_of_parties = 10;
1917 let parties_lwe_sk = (0..no_of_parties)
1918 .map(|_| LweSecret::random(lwe_n >> 1, lwe_n))
1919 .collect_vec();
1920
1921 // Ideal secrets
1922 let mut ideal_lwe_sk = vec![0i32; lwe_n];
1923 parties_lwe_sk.iter().for_each(|k| {
1924 izip!(ideal_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1925 *ideal_i = *ideal_i + s_i;
1926 });
1927 });
1928
1929 let mut rng = DefaultSecureRng::new();
1930
1931 let logp = 3;
1932 let modop_bigq = ModularOpsU64::new(big_q);
1933 let modop_smallq = ModularOpsU64::new(small_q);
1934
1935 for i in 0..100 {
1936 let m = thread_rng().sample(Uniform::new(0u64, (1u64 << logp)));
1937 let bigq_m = m << (logbig_q - logp);
1938 let smallq_m = m << (logsmall_q - logp);
1939
1940 // encrypt
1941 let mut lwe_ct = vec![0u64; lwe_n + 1];
1942 encrypt_lwe(&mut lwe_ct, &bigq_m, &ideal_lwe_sk, &modop_bigq, &mut rng);
1943
1944 let noise = measure_noise_lwe(&lwe_ct, &ideal_lwe_sk, &modop_bigq, &bigq_m);
1945 println!("Noise Before: {noise}");
1946
1947 // mod switch
1948 let lwe_ct_ms = lwe_ct
1949 .iter()
1950 .map(|v| (((*v as f64) * small_q as f64) / (big_q as f64)).round() as u64)
1951 .collect_vec();
1952
1953 let noise = measure_noise_lwe(&lwe_ct_ms, &ideal_lwe_sk, &modop_smallq, &smallq_m);
1954 println!("Noise After: {noise}");
1955 }
1956 }
1957
1958 #[test]
1959 fn multi_party_lwe_keyswitch() {
1960 let lwe_logq = 18;
1961 let lwe_q = 1 << lwe_logq;
1962 let d_lwe = 1;
1963 let logb_lwe = 6;
1964 let lweq_modop = ModularOpsU64::new(lwe_q);
1965
1966 let decomposer = DefaultDecomposer::new(lwe_q, logb_lwe, d_lwe);
1967 let lwe_gadgect_vec = decomposer.gadget_vector();
1968 let logp = 2;
1969
1970 let from_lwe_n = 2048;
1971 let to_lwe_n = 500;
1972
1973 let no_of_parties = 10;
1974 let parties_from_lwe_sk = (0..no_of_parties)
1975 .map(|_| LweSecret::random(from_lwe_n >> 1, from_lwe_n))
1976 .collect_vec();
1977 let parties_to_lwe_sk = (0..no_of_parties)
1978 .map(|_| LweSecret::random(to_lwe_n >> 1, to_lwe_n))
1979 .collect_vec();
1980
1981 // Ideal secrets
1982 let mut ideal_from_lwe_sk = vec![0i32; from_lwe_n];
1983 parties_from_lwe_sk.iter().for_each(|k| {
1984 izip!(ideal_from_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1985 *ideal_i = *ideal_i + s_i;
1986 });
1987 });
1988 let mut ideal_to_lwe_sk = vec![0i32; to_lwe_n];
1989 parties_to_lwe_sk.iter().for_each(|k| {
1990 izip!(ideal_to_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1991 *ideal_i = *ideal_i + s_i;
1992 });
1993 });
1994
1995 // Generate Lwe KSK share
1996 let mut rng = DefaultSecureRng::new();
1997 let mut ksk_seed = [0u8; 32];
1998 rng.fill_bytes(&mut ksk_seed);
1999 let lwe_ksk_shares = izip!(parties_from_lwe_sk.iter(), parties_to_lwe_sk.iter())
2000 .map(|(from_sk, to_sk)| {
2001 let mut ksk_out = vec![0u64; from_lwe_n * d_lwe];
2002 let mut p_rng = DefaultSecureRng::new_seeded(ksk_seed);
2003 lwe_ksk_keygen(
2004 from_sk.values(),
2005 to_sk.values(),
2006 &mut ksk_out,
2007 &lwe_gadgect_vec,
2008 &lweq_modop,
2009 &mut p_rng,
2010 &mut rng,
2011 );
2012 ksk_out
2013 })
2014 .collect_vec();
2015
2016 // Create collective LWE ksk
2017 let mut sum_partb = vec![0u64; d_lwe * from_lwe_n];
2018 lwe_ksk_shares.iter().for_each(|share| {
2019 lweq_modop.elwise_add_mut(sum_partb.as_mut_slice(), share.as_slice())
2020 });
2021 let mut lwe_ksk = vec![vec![0u64; to_lwe_n + 1]; d_lwe * from_lwe_n];
2022 let mut p_rng = DefaultSecureRng::new_seeded(ksk_seed);
2023 izip!(lwe_ksk.iter_mut(), sum_partb.iter()).for_each(|(lwe_i, part_bi)| {
2024 RandomUniformDist::random_fill(&mut p_rng, &lwe_q, &mut lwe_i.as_mut_slice()[1..]);
2025 lwe_i[0] = *part_bi;
2026 });
2027
2028 for i in 0..128 {
2029 println!("############## ITERATION {i} ##############");
2030
2031 // Encrypt m
2032 let m = 1;
2033 let mut lwe_ct = vec![0u64; from_lwe_n + 1];
2034 encrypt_lwe(&mut lwe_ct, &m, &ideal_from_lwe_sk, &lweq_modop, &mut rng);
2035
2036 let noise = measure_noise_lwe(&lwe_ct, &ideal_from_lwe_sk, &lweq_modop, &m);
2037 println!("Noise before key switch: {noise}");
2038
2039 // Key switch
2040 let lwe_ct_key_switched = {
2041 let mut lwe_ct_key_switched = vec![0u64; to_lwe_n + 1];
2042 lwe_key_switch(
2043 &mut lwe_ct_key_switched,
2044 &lwe_ct,
2045 &lwe_ksk,
2046 &lweq_modop,
2047 &decomposer,
2048 );
2049 lwe_ct_key_switched
2050 };
2051
2052 let noise = measure_noise_lwe(&lwe_ct_key_switched, &ideal_to_lwe_sk, &lweq_modop, &m);
2053 println!("Noise after key switch: {noise}");
2054 }
2055 }
2056
2057 fn _collecitve_public_key_gen(rlwe_q: u64, parties_rlwe_sk: &[RlweSecret]) -> Vec<Vec<u64>> {
2058 let ring_size = parties_rlwe_sk[0].values.len();
2059 assert!(ring_size.is_power_of_two());
2060 let mut rng = DefaultSecureRng::new();
2061 let nttop = NttBackendU64::new(rlwe_q, ring_size);
2062 let modop = ModularOpsU64::new(rlwe_q);
2063
2064 // Generate Pk shares
2065 let pk_seed = [0u8; 32];
2066 let pk_shares = parties_rlwe_sk.iter().map(|sk| {
2067 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2068 let mut share_out = vec![0u64; ring_size];
2069 public_key_share(
2070 &mut share_out,
2071 sk.values(),
2072 &modop,
2073 &nttop,
2074 &mut p_rng,
2075 &mut rng,
2076 );
2077 share_out
2078 });
2079
2080 let mut pk_part_b = vec![0u64; ring_size];
2081 pk_shares.for_each(|share| modop.elwise_add_mut(&mut pk_part_b, &share));
2082 let mut pk_part_a = vec![0u64; ring_size];
2083 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2084 RandomUniformDist::random_fill(&mut p_rng, &rlwe_q, pk_part_a.as_mut_slice());
2085
2086 vec![pk_part_a, pk_part_b]
2087 }
2088
2089 fn _multi_party_all_keygen(
2090 bool_evaluator: &BoolEvaluator<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>,
2091 no_of_parties: usize,
2092 ) -> (
2093 Vec<ClientKey>,
2094 PublicKey<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>,
2095 Vec<
2096 CommonReferenceSeededMultiPartyServerKeyShare<
2097 Vec<Vec<u64>>,
2098 BoolParameters<u64>,
2099 [u8; 32],
2100 >,
2101 >,
2102 SeededMultiPartyServerKey<Vec<Vec<u64>>, [u8; 32], BoolParameters<u64>>,
2103 ServerKeyEvaluationDomain<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>,
2104 ClientKey,
2105 ) {
2106 let parties = (0..no_of_parties)
2107 .map(|_| bool_evaluator.client_key())
2108 .collect_vec();
2109
2110 // Collective public key
2111 let pk_cr_seed = [0u8; 32];
2112 let public_key_share = parties
2113 .iter()
2114 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2115 .collect_vec();
2116 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2117 public_key_share.as_slice(),
2118 );
2119
2120 // Server key
2121 let pbs_cr_seed = [1u8; 32];
2122 let server_key_shares = parties
2123 .iter()
2124 .map(|k| bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k))
2125 .collect_vec();
2126 let seeded_server_key =
2127 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
2128 &server_key_shares,
2129 &bool_evaluator.decomposer_rlwe,
2130 );
2131 let server_key_eval = ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2132 &seeded_server_key,
2133 );
2134
2135 // construct ideal rlwe sk for meauring noise
2136 let ideal_client_key = {
2137 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
2138 parties.iter().for_each(|k| {
2139 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
2140 *ideal_i = *ideal_i + s_i;
2141 });
2142 });
2143 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
2144 parties.iter().for_each(|k| {
2145 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
2146 *ideal_i = *ideal_i + s_i;
2147 });
2148 });
2149
2150 ClientKey {
2151 sk_lwe: LweSecret {
2152 values: ideal_lwe_sk,
2153 },
2154 sk_rlwe: RlweSecret {
2155 values: ideal_rlwe_sk,
2156 },
2157 }
2158 };
2159
2160 (
2161 parties,
2162 collective_pk,
2163 server_key_shares,
2164 seeded_server_key,
2165 server_key_eval,
2166 ideal_client_key,
2167 )
2168 }
2169
2170 #[test]
2171 fn mp_key_correcntess() {
2172 let bool_evaluator =
2173 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2174
2175 let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2176 _multi_party_all_keygen(&bool_evaluator, 20);
2177
2178 let lwe_q = bool_evaluator.parameters.lwe_q;
2179 let rlwe_q = bool_evaluator.parameters.rlwe_q;
2180 let d_rgsw = bool_evaluator.parameters.d_rgsw;
2181 let lwe_logq = bool_evaluator.parameters.lwe_logq;
2182 let lwe_n = bool_evaluator.parameters.lwe_n;
2183 let rlwe_n = bool_evaluator.parameters.rlwe_n;
2184 let lwe_modop = &bool_evaluator.lwe_modop;
2185 let rlwe_nttop = &bool_evaluator.rlwe_nttop;
2186 let rlwe_modop = &bool_evaluator.rlwe_modop;
2187 let rlwe_decomposer = &bool_evaluator.decomposer_rlwe;
2188
2189 // test LWE ksk from RLWE -> LWE
2190 if false {
2191 let logp = 2;
2192 let mut rng = DefaultSecureRng::new();
2193
2194 let m = 1;
2195 let encoded_m = m << (lwe_logq - logp);
2196
2197 // Encrypt
2198 let mut lwe_ct = vec![0u64; rlwe_n + 1];
2199 encrypt_lwe(
2200 &mut lwe_ct,
2201 &encoded_m,
2202 ideal_client_key.sk_rlwe.values(),
2203 lwe_modop,
2204 &mut rng,
2205 );
2206
2207 // key switch
2208 let lwe_decomposer = &bool_evaluator.decomposer_lwe;
2209 let mut lwe_out = vec![0u64; lwe_n + 1];
2210 lwe_key_switch(
2211 &mut lwe_out,
2212 &lwe_ct,
2213 &server_key_eval.lwe_ksk,
2214 lwe_modop,
2215 lwe_decomposer,
2216 );
2217
2218 let encoded_m_back = decrypt_lwe(&lwe_out, ideal_client_key.sk_lwe.values(), lwe_modop);
2219 let m_back =
2220 ((encoded_m_back as f64 * (1 << logp) as f64) / (lwe_q as f64)).round() as u64;
2221 dbg!(m_back, m);
2222
2223 let noise = measure_noise_lwe(
2224 &lwe_out,
2225 ideal_client_key.sk_lwe.values(),
2226 lwe_modop,
2227 &encoded_m,
2228 );
2229
2230 println!("Noise: {noise}");
2231 }
2232
2233 // Measure noise in RGSW ciphertexts of ideal LWE secrets
2234 if true {
2235 let gadget_vec = rlwe_decomposer.gadget_vector();
2236 for i in 0..20 {
2237 // measure noise in RGSW(s[i])
2238 let si =
2239 ideal_client_key.sk_lwe.values[i] * (bool_evaluator.embedding_factor as i32);
2240 let mut si_poly = vec![0u64; rlwe_n];
2241 if si < 0 {
2242 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2243 } else {
2244 si_poly[(si.abs() as usize)] = 1;
2245 }
2246
2247 let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
2248 rgsw_si
2249 .iter_mut()
2250 .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
2251
2252 println!("####### Noise in RGSW(X^s_{i}) #######");
2253 _measure_noise_rgsw(
2254 &rgsw_si,
2255 &si_poly,
2256 ideal_client_key.sk_rlwe.values(),
2257 &gadget_vec,
2258 rlwe_q,
2259 );
2260 println!("####### ##################### #######");
2261 }
2262 }
2263
2264 // measure noise grwoth in RLWExRGSW
2265 if true {
2266 let mut rng = DefaultSecureRng::new();
2267 let mut carry_m = vec![0u64; rlwe_n];
2268 RandomUniformDist::random_fill(&mut rng, &rlwe_q, carry_m.as_mut_slice());
2269
2270 // RGSW(carrym)
2271 let trivial_rlwect = vec![vec![0u64; rlwe_n], carry_m.clone()];
2272 let mut rlwe_ct = RlweCiphertext::<_, DefaultSecureRng>::new_trivial(trivial_rlwect);
2273
2274 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
2275 let mul_mod =
2276 |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
2277
2278 for i in 0..bool_evaluator.parameters.lwe_n {
2279 rlwe_by_rgsw(
2280 &mut rlwe_ct,
2281 server_key_eval.rgsw_ct_lwe_si(i),
2282 &mut scratch_matrix_dplus2_ring,
2283 rlwe_decomposer,
2284 rlwe_nttop,
2285 rlwe_modop,
2286 );
2287
2288 // carry_m[X] * s_i[X]
2289 let si =
2290 ideal_client_key.sk_lwe.values[i] * (bool_evaluator.embedding_factor as i32);
2291 let mut si_poly = vec![0u64; rlwe_n];
2292 if si < 0 {
2293 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2294 } else {
2295 si_poly[(si.abs() as usize)] = 1;
2296 }
2297 carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod, rlwe_q);
2298
2299 let noise = measure_noise(
2300 &rlwe_ct,
2301 &carry_m,
2302 rlwe_nttop,
2303 rlwe_modop,
2304 ideal_client_key.sk_rlwe.values(),
2305 );
2306 println!("Noise RLWE(carry_m) accumulating {i}^th secret monomial: {noise}");
2307 }
2308 }
2309
2310 // Check galois keys
2311 if false {
2312 let g = bool_evaluator.g() as isize;
2313 let mut rng = DefaultSecureRng::new();
2314 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
2315 for i in [g, -g] {
2316 let mut m = vec![0u64; rlwe_n];
2317 RandomUniformDist::random_fill(&mut rng, &rlwe_q, m.as_mut_slice());
2318 let mut rlwe_ct = {
2319 let mut data = vec![vec![0u64; rlwe_n]; 2];
2320 public_key_encrypt_rlwe(
2321 &mut data,
2322 &collective_pk.key,
2323 &m,
2324 rlwe_modop,
2325 rlwe_nttop,
2326 &mut rng,
2327 );
2328 RlweCiphertext::<_, DefaultSecureRng>::new_trivial(data, false)
2329 };
2330
2331 let auto_key = server_key_eval.galois_key_for_auto(i);
2332 let (auto_map_index, auto_map_sign) = generate_auto_map(rlwe_n, i);
2333 galois_auto(
2334 &mut rlwe_ct,
2335 auto_key,
2336 &mut scratch_matrix_dplus2_ring,
2337 &auto_map_index,
2338 &auto_map_sign,
2339 rlwe_modop,
2340 rlwe_nttop,
2341 rlwe_decomposer,
2342 );
2343
2344 // send m(X) -> m(X^i)
2345 let mut m_k = vec![0u64; rlwe_n];
2346 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
2347 |(mi, to_index, to_sign)| {
2348 if !to_sign {
2349 m_k[*to_index] = rlwe_q - *mi;
2350 } else {
2351 m_k[*to_index] = *mi;
2352 }
2353 },
2354 );
2355
2356 // measure noise
2357 let noise = measure_noise(
2358 &rlwe_ct,
2359 &m_k,
2360 rlwe_nttop,
2361 rlwe_modop,
2362 ideal_client_key.sk_rlwe.values(),
2363 );
2364
2365 println!("Noise after auto k={i}: {noise}");
2366 }
2367 }
2368 }
2369
2370 #[test]
2371 fn multi_party_nand() {
2372 let bool_evaluator =
2373 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2374
2375 let (parties, collective_pk, _, _, server_key_eval, ideal_client_key) =
2376 _multi_party_all_keygen(&bool_evaluator, 50);
2377
2378 // PBS
2379 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
2380 let mut scratch_matrix_dplus2_ring = vec![
2381 vec![0u64; bool_evaluator.parameters.rlwe_n];
2382 bool_evaluator.parameters.d_rgsw + 2
2383 ];
2384
2385 let mut m0 = true;
2386 let mut m1 = false;
2387
2388 let mut lwe0 = bool_evaluator.pk_encrypt(&collective_pk.key, m0);
2389 let mut lwe1 = bool_evaluator.pk_encrypt(&collective_pk.key, m1);
2390
2391 for _ in 0..2000 {
2392 let lwe_out = bool_evaluator.nand(
2393 &lwe0,
2394 &lwe1,
2395 &server_key_eval,
2396 &mut scratch_lwen_plus1,
2397 &mut scratch_matrix_dplus2_ring,
2398 );
2399
2400 let m_expected = !(m0 & m1);
2401
2402 // measure noise
2403 {
2404 let noise0 = {
2405 let ideal = if m0 {
2406 bool_evaluator.rlweq_by8
2407 } else {
2408 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
2409 };
2410 let n = measure_noise_lwe(
2411 &lwe0,
2412 ideal_client_key.sk_rlwe.values(),
2413 &bool_evaluator.rlwe_modop,
2414 &ideal,
2415 );
2416 let v = decrypt_lwe(
2417 &lwe0,
2418 ideal_client_key.sk_rlwe.values(),
2419 &bool_evaluator.rlwe_modop,
2420 );
2421 (n, v)
2422 };
2423 let noise1 = {
2424 let ideal = if m1 {
2425 bool_evaluator.rlweq_by8
2426 } else {
2427 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
2428 };
2429 let n = measure_noise_lwe(
2430 &lwe1,
2431 ideal_client_key.sk_rlwe.values(),
2432 &bool_evaluator.rlwe_modop,
2433 &ideal,
2434 );
2435 let v = decrypt_lwe(
2436 &lwe1,
2437 ideal_client_key.sk_rlwe.values(),
2438 &bool_evaluator.rlwe_modop,
2439 );
2440 (n, v)
2441 };
2442
2443 // Trace PBS
2444 PBSTracer::with_local(|t| {
2445 t.trace(
2446 &MP_BOOL_PARAMS,
2447 &ideal_client_key.sk_lwe.values(),
2448 &ideal_client_key.sk_rlwe.values(),
2449 )
2450 });
2451
2452 let noise_out = {
2453 let ideal_m = if m_expected {
2454 bool_evaluator.rlweq_by8
2455 } else {
2456 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
2457 };
2458 let n = measure_noise_lwe(
2459 &lwe_out,
2460 ideal_client_key.sk_rlwe.values(),
2461 &bool_evaluator.rlwe_modop,
2462 &ideal_m,
2463 );
2464 let v = decrypt_lwe(
2465 &lwe_out,
2466 ideal_client_key.sk_rlwe.values(),
2467 &bool_evaluator.rlwe_modop,
2468 );
2469 (n, v)
2470 };
2471 dbg!(m0, m1, m_expected);
2472 println!(
2473 "ct0 (noise, message): {:?} \n ct1 (noise, message): {:?} \n PBS (noise, message): {:?}", noise0, noise1, noise_out
2474 );
2475 }
2476
2477 // multi-party decrypt
2478 let decryption_shares = parties
2479 .iter()
2480 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_out, k))
2481 .collect_vec();
2482 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
2483
2484 // let m_back = bool_evaluator.sk_decrypt(&lwe_out, &ideal_client_key);
2485
2486 assert!(m_expected == m_back, "Expected {m_expected}, got {m_back}");
2487 m1 = m0;
2488 m0 = m_expected;
2489
2490 lwe1 = lwe0;
2491 lwe0 = lwe_out;
2492 }
2493 }
2494
2495 struct Stats<T> {
2496 samples: Vec<T>,
2497 }
2498
2499 impl<T: PrimInt + FromPrimitive + Debug> Stats<T>
2500 where
2501 // T: for<'a> Sum<&'a T>,
2502 T: for<'a> std::iter::Sum<&'a T> + std::iter::Sum<T>,
2503 {
2504 fn mean(&self) -> f64 {
2505 self.samples.iter().sum::<T>().to_f64().unwrap() / (self.samples.len() as f64)
2506 }
2507
2508 fn std_dev(&self) -> f64 {
2509 let mean = self.mean();
2510
2511 // diff
2512 let diff_sq = self
2513 .samples
2514 .iter()
2515 .map(|v| {
2516 let t = v.to_f64().unwrap() - mean;
2517 t * t
2518 })
2519 .into_iter()
2520 .sum::<f64>();
2521
2522 (diff_sq / (self.samples.len() as f64)).sqrt()
2523 }
2524
2525 fn add_more(&mut self, values: &[T]) {
2526 self.samples.extend(values.iter());
2527 }
2528 }
2529
2530 #[test]
2531 fn tester() {
2532 // pub(super) const TEST_MP_BOOL_PARAMS: BoolParameters<u64> =
2533 // BoolParameters::<u64> { rlwe_q: 1152921504606830593,
2534 // rlwe_logq: 60,
2535 // lwe_q: 1 << 20,
2536 // lwe_logq: 20,
2537 // br_q: 1 << 11,
2538 // rlwe_n: 1 << 11,
2539 // lwe_n: 500,
2540 // d_rgsw: 4,
2541 // logb_rgsw: 12,
2542 // d_lwe: 5,
2543 // logb_lwe: 4,
2544 // g: 5,
2545 // w: 1,
2546 // };
2547
2548 let bool_evaluator =
2549 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2550
2551 // let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2552 // _multi_party_all_keygen(&bool_evaluator, 20);
2553 let no_of_parties = 2;
2554 let lwe_q = bool_evaluator.parameters.lwe_q;
2555 let rlwe_q = bool_evaluator.parameters.rlwe_q;
2556 let d_rgsw = bool_evaluator.parameters.d_rgsw;
2557 let lwe_logq = bool_evaluator.parameters.lwe_logq;
2558 let lwe_n = bool_evaluator.parameters.lwe_n;
2559 let rlwe_n = bool_evaluator.parameters.rlwe_n;
2560 let lwe_modop = &bool_evaluator.lwe_modop;
2561 let rlwe_nttop = &bool_evaluator.rlwe_nttop;
2562 let rlwe_modop = &bool_evaluator.rlwe_modop;
2563 let rlwe_decomposer = &bool_evaluator.decomposer_rlwe;
2564 let rlwe_gadget_vector = rlwe_decomposer.gadget_vector();
2565
2566 let parties = (0..no_of_parties)
2567 .map(|_| bool_evaluator.client_key())
2568 .collect_vec();
2569
2570 let ideal_client_key = {
2571 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
2572 parties.iter().for_each(|k| {
2573 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
2574 *ideal_i = *ideal_i + s_i;
2575 });
2576 });
2577 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
2578 parties.iter().for_each(|k| {
2579 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
2580 *ideal_i = *ideal_i + s_i;
2581 });
2582 });
2583
2584 ClientKey {
2585 sk_lwe: LweSecret {
2586 values: ideal_lwe_sk,
2587 },
2588 sk_rlwe: RlweSecret {
2589 values: ideal_rlwe_sk,
2590 },
2591 }
2592 };
2593
2594 // check noise in freshly encrypted RLWE ciphertext (ie var_fresh)
2595 if false {
2596 let mut rng = DefaultSecureRng::new();
2597 let mut check = Stats { samples: vec![] };
2598 for _ in 0..10 {
2599 // generate a new collective public key
2600 let mut pk_cr_seed = [0u8; 32];
2601 rng.fill_bytes(&mut pk_cr_seed);
2602 let public_key_share = parties
2603 .iter()
2604 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2605 .collect_vec();
2606 let collective_pk =
2607 PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2608 public_key_share.as_slice(),
2609 );
2610
2611 let m = vec![0u64; rlwe_n];
2612 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2613 public_key_encrypt_rlwe(
2614 &mut rlwe_ct,
2615 &collective_pk.key,
2616 &m,
2617 rlwe_modop,
2618 rlwe_nttop,
2619 &mut rng,
2620 );
2621
2622 let mut m_back = vec![0u64; rlwe_n];
2623 decrypt_rlwe(
2624 &rlwe_ct,
2625 ideal_client_key.sk_rlwe.values(),
2626 &mut m_back,
2627 rlwe_nttop,
2628 rlwe_modop,
2629 );
2630
2631 rlwe_modop.elwise_sub_mut(m_back.as_mut_slice(), m.as_slice());
2632
2633 check.add_more(Vec::<i64>::try_convert_from(&m_back, &rlwe_q).as_slice());
2634 }
2635
2636 println!("Public key Std: {}", check.std_dev().abs().log2());
2637 }
2638
2639 if true {
2640 // Generate server key shares
2641 let mut rng = DefaultSecureRng::new();
2642 let mut pk_cr_seed = [0u8; 32];
2643 rng.fill_bytes(&mut pk_cr_seed);
2644 let public_key_share = parties
2645 .iter()
2646 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2647 .collect_vec();
2648 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2649 public_key_share.as_slice(),
2650 );
2651 let pbs_cr_seed = [0u8; 32];
2652 rng.fill_bytes(&mut pk_cr_seed);
2653 let server_key_shares = parties
2654 .iter()
2655 .map(|k| {
2656 bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k)
2657 })
2658 .collect_vec();
2659
2660 let seeded_server_key =
2661 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
2662 &server_key_shares,
2663 rlwe_decomposer,
2664 );
2665
2666 // Check noise in RGSW ciphertexts of ideal LWE secret elements
2667 if true {
2668 let mut check = Stats { samples: vec![] };
2669 izip!(
2670 ideal_client_key.sk_lwe.values.iter(),
2671 seeded_server_key.rgsw_cts.iter()
2672 )
2673 .for_each(|(s_i, rgsw_ct_i)| {
2674 // X^{s[i]}
2675 let mut m_si = vec![0u64; rlwe_n];
2676 let s_i = *s_i * (bool_evaluator.embedding_factor as i32);
2677 if s_i < 0 {
2678 m_si[rlwe_n - (s_i.abs() as usize)] = rlwe_q - 1;
2679 } else {
2680 m_si[s_i as usize] = 1;
2681 }
2682
2683 _measure_noise_rgsw(
2684 &rgsw_ct_i,
2685 &m_si,
2686 ideal_client_key.sk_rlwe.values(),
2687 &rlwe_gadget_vector,
2688 rlwe_q,
2689 );
2690
2691 // RLWE(-sm)
2692 let mut neg_s_eval =
2693 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe.values(), &rlwe_q);
2694 rlwe_modop.elwise_neg_mut(&mut neg_s_eval);
2695 rlwe_nttop.forward(&mut neg_s_eval);
2696 for j in 0..rlwe_decomposer.decomposition_count() {
2697 // -s[X]*X^{s_lwe[i]}*B_j
2698 let mut m_ideal = m_si.clone();
2699 rlwe_nttop.forward(m_ideal.as_mut_slice());
2700 rlwe_modop.elwise_mul_mut(m_ideal.as_mut_slice(), neg_s_eval.as_slice());
2701 rlwe_nttop.backward(m_ideal.as_mut_slice());
2702 rlwe_modop
2703 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_gadget_vector[j]);
2704
2705 // RLWE(-s*X^{s_lwe[i]}*B_j)
2706 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2707 rlwe_ct[0].copy_from_slice(&rgsw_ct_i[j]);
2708 rlwe_ct[1]
2709 .copy_from_slice(&rgsw_ct_i[j + rlwe_decomposer.decomposition_count()]);
2710
2711 let mut m_back = vec![0u64; rlwe_n];
2712 decrypt_rlwe(
2713 &rlwe_ct,
2714 ideal_client_key.sk_rlwe.values(),
2715 &mut m_back,
2716 rlwe_nttop,
2717 rlwe_modop,
2718 );
2719
2720 // diff
2721 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2722 check.add_more(&Vec::<i64>::try_convert_from(&m_back, &rlwe_q));
2723 }
2724
2725 // RLWE'(m)
2726 for j in 0..rlwe_decomposer.decomposition_count() {
2727 // X^{s_lwe[i]}*B_j
2728 let mut m_ideal = m_si.clone();
2729 rlwe_modop
2730 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_gadget_vector[j]);
2731
2732 // RLWE(X^{s_lwe[i]}*B_j)
2733 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2734 rlwe_ct[0].copy_from_slice(
2735 &rgsw_ct_i[j + (2 * rlwe_decomposer.decomposition_count())],
2736 );
2737 rlwe_ct[1].copy_from_slice(
2738 &rgsw_ct_i[j + (3 * rlwe_decomposer.decomposition_count())],
2739 );
2740
2741 let mut m_back = vec![0u64; rlwe_n];
2742 decrypt_rlwe(
2743 &rlwe_ct,
2744 ideal_client_key.sk_rlwe.values(),
2745 &mut m_back,
2746 rlwe_nttop,
2747 rlwe_modop,
2748 );
2749
2750 // diff
2751 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2752 check.add_more(&Vec::<i64>::try_convert_from(&m_back, &rlwe_q));
2753 }
2754 });
2755 println!(
2756 "RGSW Std: {} {} ;; max={}",
2757 check.mean(),
2758 check.std_dev().abs().log2(),
2759 check.samples.iter().max().unwrap()
2760 );
2761 }
2762
2763 // check noise in RLWE x RGSW(X^{s_i}) where RGSW is accunulated RGSW ciphertext
2764 if false {
2765 let mut check = Stats { samples: vec![] };
2766 // server key in Evaluation domain
2767 let server_key_eval_domain =
2768 ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2769 &seeded_server_key,
2770 );
2771 izip!(
2772 ideal_client_key.sk_lwe.values(),
2773 seeded_server_key.rgsw_cts.iter()
2774 )
2775 .for_each(|(s_i, rgsw_ct_i)| {
2776 let mut rgsw_ct_i = rgsw_ct_i.clone();
2777 rgsw_ct_i
2778 .iter_mut()
2779 .for_each(|ri| rlwe_nttop.forward(ri.as_mut()));
2780
2781 let mut m = vec![0u64; rlwe_n];
2782 RandomUniformDist::random_fill(&mut rng, &rlwe_q, m.as_mut_slice());
2783 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2784 public_key_encrypt_rlwe(
2785 &mut rlwe_ct,
2786 &collective_pk.key,
2787 &m,
2788 rlwe_modop,
2789 rlwe_nttop,
2790 &mut rng,
2791 );
2792
2793 // RLWE(m*X^{s[i]}) = RLWE(m) x RGSW(X^{s[i]})
2794 let mut rlwe_after = RlweCiphertext::<_, DefaultSecureRng>::new_trivial(vec![
2795 vec![0u64; rlwe_n],
2796 m.clone(),
2797 ]);
2798 // let mut rlwe_after =
2799 // RlweCiphertext::<_, DefaultSecureRng>::from_raw(rlwe_ct.clone(), false);
2800 let mut scratch =
2801 vec![vec![0u64; rlwe_n]; rlwe_decomposer.decomposition_count() + 2];
2802 rlwe_by_rgsw(
2803 &mut rlwe_after,
2804 &rgsw_ct_i,
2805 &mut scratch,
2806 rlwe_decomposer,
2807 rlwe_nttop,
2808 rlwe_modop,
2809 );
2810
2811 // m1 = X^{s[i]}
2812 let mut m1 = vec![0u64; rlwe_n];
2813 let s_i = *s_i * (bool_evaluator.embedding_factor as i32);
2814 if s_i < 0 {
2815 m1[rlwe_n - (s_i.abs() as usize)] = rlwe_q - 1;
2816 } else {
2817 m1[s_i as usize] = 1;
2818 }
2819
2820 // (m+e) * m1
2821 let mut m_plus_e_times_m1 = m.clone();
2822 // decrypt_rlwe(
2823 // &rlwe_ct,
2824 // ideal_client_key.sk_rlwe.values(),
2825 // &mut m_plus_e_times_m1,
2826 // rlwe_nttop,
2827 // rlwe_modop,
2828 // );
2829 rlwe_nttop.forward(m_plus_e_times_m1.as_mut_slice());
2830 rlwe_nttop.forward(m1.as_mut_slice());
2831 rlwe_modop.elwise_mul_mut(m_plus_e_times_m1.as_mut_slice(), m1.as_slice());
2832 rlwe_nttop.backward(m_plus_e_times_m1.as_mut_slice());
2833
2834 // Resulting RLWE ciphertext will equal: (m0m1 + em1) + e_{rlsw x rgsw}.
2835 // Hence, resulting rlwe ciphertext will have error em1 + e_{rlwe x rgsw}.
2836 // Here we're only concerned with e_{rlwe x rgsw}, that is noise caused due to
2837 // RLWExRGSW. Also note, in practice m1 is a monomial, for ex, X^{s_{i}}, for
2838 // some i and var(em1) = var(e).
2839 let mut m_plus_e_times_m1_more_e = vec![0u64; rlwe_n];
2840 decrypt_rlwe(
2841 &rlwe_after,
2842 ideal_client_key.sk_rlwe.values(),
2843 &mut m_plus_e_times_m1_more_e,
2844 rlwe_nttop,
2845 rlwe_modop,
2846 );
2847
2848 // diff
2849 rlwe_modop.elwise_sub_mut(
2850 m_plus_e_times_m1_more_e.as_mut_slice(),
2851 m_plus_e_times_m1.as_slice(),
2852 );
2853
2854 let noise = measure_noise(
2855 &rlwe_after,
2856 &m_plus_e_times_m1,
2857 rlwe_nttop,
2858 rlwe_modop,
2859 ideal_client_key.sk_rlwe.values(),
2860 );
2861 print!("NOISE: {}", noise);
2862
2863 check.add_more(&Vec::<i64>::try_convert_from(
2864 &m_plus_e_times_m1_more_e,
2865 &rlwe_q,
2866 ));
2867 });
2868 println!(
2869 "RLWE x RGSW, where RGSW has noise var_brk, std: {} {}",
2870 check.std_dev(),
2871 check.std_dev().abs().log2()
2872 )
2873 }
2874 }
2875
2876 // Check noise in fresh RGSW ciphertexts, ie X^{s_j[i]}, must equal noise in
2877 // fresh RLWE ciphertext
2878 if true {}
2879 // test LWE ksk from RLWE -> LWE
2880 // if false {
2881 // let logp = 2;
2882 // let mut rng = DefaultSecureRng::new();
2883
2884 // let m = 1;
2885 // let encoded_m = m << (lwe_logq - logp);
2886
2887 // // Encrypt
2888 // let mut lwe_ct = vec![0u64; rlwe_n + 1];
2889 // encrypt_lwe(
2890 // &mut lwe_ct,
2891 // &encoded_m,
2892 // ideal_client_key.sk_rlwe.values(),
2893 // lwe_modop,
2894 // &mut rng,
2895 // );
2896
2897 // // key switch
2898 // let lwe_decomposer = &bool_evaluator.decomposer_lwe;
2899 // let mut lwe_out = vec![0u64; lwe_n + 1];
2900 // lwe_key_switch(
2901 // &mut lwe_out,
2902 // &lwe_ct,
2903 // &server_key_eval.lwe_ksk,
2904 // lwe_modop,
2905 // lwe_decomposer,
2906 // );
2907
2908 // let encoded_m_back = decrypt_lwe(&lwe_out,
2909 // ideal_client_key.sk_lwe.values(), lwe_modop); let m_back
2910 // = ((encoded_m_back as f64 * (1 << logp) as f64) /
2911 // (lwe_q as f64)).round() as u64; dbg!(m_back, m);
2912
2913 // let noise = measure_noise_lwe(
2914 // &lwe_out,
2915 // ideal_client_key.sk_lwe.values(),
2916 // lwe_modop,
2917 // &encoded_m,
2918 // );
2919
2920 // println!("Noise: {noise}");
2921 // }
2922
2923 // Measure noise in RGSW ciphertexts of ideal LWE secrets
2924 // if true {
2925 // let gadget_vec = gadget_vector(
2926 // bool_evaluator.parameters.rlwe_logq,
2927 // bool_evaluator.parameters.logb_rgsw,
2928 // bool_evaluator.parameters.d_rgsw,
2929 // );
2930
2931 // for i in 0..20 {
2932 // // measure noise in RGSW(s[i])
2933 // let si =
2934 // ideal_client_key.sk_lwe.values[i] *
2935 // (bool_evaluator.embedding_factor as i32); let mut
2936 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
2937 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2938 // } else {
2939 // si_poly[(si.abs() as usize)] = 1;
2940 // }
2941
2942 // let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
2943 // rgsw_si
2944 // .iter_mut()
2945 // .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
2946
2947 // println!("####### Noise in RGSW(X^s_{i}) #######");
2948 // _measure_noise_rgsw(
2949 // &rgsw_si,
2950 // &si_poly,
2951 // ideal_client_key.sk_rlwe.values(),
2952 // &gadget_vec,
2953 // rlwe_q,
2954 // );
2955 // println!("####### ##################### #######");
2956 // }
2957 // }
2958
2959 // // measure noise grwoth in RLWExRGSW
2960 // if true {
2961 // let mut rng = DefaultSecureRng::new();
2962 // let mut carry_m = vec![0u64; rlwe_n];
2963 // RandomUniformDist::random_fill(&mut rng, &rlwe_q,
2964 // carry_m.as_mut_slice());
2965
2966 // // RGSW(carrym)
2967 // let trivial_rlwect = vec![vec![0u64; rlwe_n], carry_m.clone()];
2968 // let mut rlwe_ct = RlweCiphertext::<_,
2969 // DefaultSecureRng>::from_raw(trivial_rlwect, true);
2970
2971 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
2972 // d_rgsw + 2]; let mul_mod =
2973 // |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
2974
2975 // for i in 0..bool_evaluator.parameters.lwe_n {
2976 // rlwe_by_rgsw(
2977 // &mut rlwe_ct,
2978 // server_key_eval.rgsw_ct_lwe_si(i),
2979 // &mut scratch_matrix_dplus2_ring,
2980 // rlwe_decomposer,
2981 // rlwe_nttop,
2982 // rlwe_modop,
2983 // );
2984
2985 // // carry_m[X] * s_i[X]
2986 // let si =
2987 // ideal_client_key.sk_lwe.values[i] *
2988 // (bool_evaluator.embedding_factor as i32); let mut
2989 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
2990 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2991 // } else {
2992 // si_poly[(si.abs() as usize)] = 1;
2993 // }
2994 // carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod,
2995 // rlwe_q);
2996
2997 // let noise = measure_noise(
2998 // &rlwe_ct,
2999 // &carry_m,
3000 // rlwe_nttop,
3001 // rlwe_modop,
3002 // ideal_client_key.sk_rlwe.values(),
3003 // );
3004 // println!("Noise RLWE(carry_m) accumulating {i}^th secret
3005 // monomial: {noise}"); }
3006 // }
3007
3008 // // Check galois keys
3009 // if false {
3010 // let g = bool_evaluator.g() as isize;
3011 // let mut rng = DefaultSecureRng::new();
3012 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
3013 // d_rgsw + 2]; for i in [g, -g] {
3014 // let mut m = vec![0u64; rlwe_n];
3015 // RandomUniformDist::random_fill(&mut rng, &rlwe_q,
3016 // m.as_mut_slice()); let mut rlwe_ct = {
3017 // let mut data = vec![vec![0u64; rlwe_n]; 2];
3018 // public_key_encrypt_rlwe(
3019 // &mut data,
3020 // &collective_pk.key,
3021 // &m,
3022 // rlwe_modop,
3023 // rlwe_nttop,
3024 // &mut rng,
3025 // );
3026 // RlweCiphertext::<_, DefaultSecureRng>::from_raw(data,
3027 // false) };
3028
3029 // let auto_key = server_key_eval.galois_key_for_auto(i);
3030 // let (auto_map_index, auto_map_sign) =
3031 // generate_auto_map(rlwe_n, i); galois_auto(
3032 // &mut rlwe_ct,
3033 // auto_key,
3034 // &mut scratch_matrix_dplus2_ring,
3035 // &auto_map_index,
3036 // &auto_map_sign,
3037 // rlwe_modop,
3038 // rlwe_nttop,
3039 // rlwe_decomposer,
3040 // );
3041
3042 // // send m(X) -> m(X^i)
3043 // let mut m_k = vec![0u64; rlwe_n];
3044 // izip!(m.iter(), auto_map_index.iter(),
3045 // auto_map_sign.iter()).for_each( |(mi, to_index, to_sign)|
3046 // { if !to_sign {
3047 // m_k[*to_index] = rlwe_q - *mi;
3048 // } else {
3049 // m_k[*to_index] = *mi;
3050 // }
3051 // },
3052 // );
3053
3054 // // measure noise
3055 // let noise = measure_noise(
3056 // &rlwe_ct,
3057 // &m_k,
3058 // rlwe_nttop,
3059 // rlwe_modop,
3060 // ideal_client_key.sk_rlwe.values(),
3061 // );
3062
3063 // println!("Noise after auto k={i}: {noise}");
3064 // }
3065 // }
3066 }
3067
3068 fn test_2() {
3069 let bool_evaluator =
3070 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
3071 }
3072}