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