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