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