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