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 encode_x_pow_si_with_emebedding_factor, fill_random_ternary_secret_with_hamming_weight,
45 generate_prime, mod_exponent, 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
67/// Common reference seed used for Interactive multi-party,
68///
69/// Seeds for public key shares and differents parts of server key shares are
70/// derived from common reference seed with different puncture rountines.
71///
72/// ## Punctures
73///
74/// Initial Seed:
75/// Puncture 1 -> Public key share seed
76/// Puncture 2 -> Main server key share seed
77/// Puncture 1 -> RGSW cuphertexts seed
78/// Puncture 2 -> Auto keys cipertexts seed
79/// Puncture 3 -> LWE ksk seed
80#[derive(Clone, PartialEq)]
81pub struct MultiPartyCrs<S> {
82 pub(super) seed: S,
83}
84
85impl MultiPartyCrs<[u8; 32]> {
86 pub(super) fn random() -> Self {
87 DefaultSecureRng::with_local_mut(|rng| {
88 let mut seed = [0u8; 32];
89 rng.fill_bytes(&mut seed);
90 Self { seed }
91 })
92 }
93}
94impl<S: Default + Copy> MultiPartyCrs<S> {
95 /// Seed to generate public key share
96 fn public_key_share_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
97 let mut prng = Rng::new_with_seed(self.seed);
98 puncture_p_rng(&mut prng, 1)
99 }
100
101 /// Main server key share seed
102 fn key_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
103 let mut prng = Rng::new_with_seed(self.seed);
104 puncture_p_rng(&mut prng, 2)
105 }
106
107 pub(super) fn rgsw_cts_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
108 let mut key_prng = Rng::new_with_seed(self.key_seed::<Rng>());
109 puncture_p_rng(&mut key_prng, 1)
110 }
111
112 pub(super) fn auto_keys_cts_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
113 let mut key_prng = Rng::new_with_seed(self.key_seed::<Rng>());
114 puncture_p_rng(&mut key_prng, 2)
115 }
116
117 pub(super) fn lwe_ksk_cts_seed_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
118 let mut key_prng = Rng::new_with_seed(self.key_seed::<Rng>());
119 puncture_p_rng(&mut key_prng, 3)
120 }
121}
122
123/// Common reference seed used for non-interactive multi-party.
124///
125/// Initial Seed
126/// Puncture 1 -> Key Seed
127/// Puncture 1 -> Rgsw ciphertext seed
128/// Puncture 2 -> auto keys seed
129/// Puncture 3 -> Lwe key switching key seed
130/// Puncture 2 -> user specific seed for u_j to s ksk
131/// Punture j+1 -> user j's seed
132#[derive(Clone)]
133pub struct NonInteractiveMultiPartyCrs<S> {
134 pub(super) seed: S,
135}
136
137impl<S: Default + Copy> NonInteractiveMultiPartyCrs<S> {
138 fn key_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
139 let mut p_rng = R::new_with_seed(self.seed);
140 puncture_p_rng(&mut p_rng, 1)
141 }
142
143 pub(crate) fn rgsw_cts_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
144 let mut p_rng = R::new_with_seed(self.key_seed::<R>());
145 puncture_p_rng(&mut p_rng, 1)
146 }
147
148 pub(crate) fn auto_keys_cts_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
149 let mut p_rng = R::new_with_seed(self.key_seed::<R>());
150 puncture_p_rng(&mut p_rng, 2)
151 }
152
153 pub(crate) fn lwe_ksk_cts_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
154 let mut p_rng = R::new_with_seed(self.key_seed::<R>());
155 puncture_p_rng(&mut p_rng, 3)
156 }
157
158 fn ui_to_s_ks_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
159 let mut p_rng = R::new_with_seed(self.seed);
160 puncture_p_rng(&mut p_rng, 2)
161 }
162
163 pub(crate) fn ui_to_s_ks_seed_for_user_i<R: NewWithSeed<Seed = S> + RandomFill<S>>(
164 &self,
165 user_i: usize,
166 ) -> S {
167 let ks_seed = self.ui_to_s_ks_seed::<R>();
168 let mut p_rng = R::new_with_seed(ks_seed);
169
170 puncture_p_rng(&mut p_rng, user_i + 1)
171 }
172}
173
174pub(crate) trait BooleanGates {
175 type Ciphertext: RowEntity;
176 type Key;
177
178 fn and_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
179 fn nand_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
180 fn or_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
181 fn nor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
182 fn xor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
183 fn xnor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
184 fn not_inplace(&mut self, c: &mut Self::Ciphertext);
185
186 fn and(
187 &mut self,
188 c0: &Self::Ciphertext,
189 c1: &Self::Ciphertext,
190 key: &Self::Key,
191 ) -> Self::Ciphertext;
192 fn nand(
193 &mut self,
194 c0: &Self::Ciphertext,
195 c1: &Self::Ciphertext,
196 key: &Self::Key,
197 ) -> Self::Ciphertext;
198 fn or(
199 &mut self,
200 c0: &Self::Ciphertext,
201 c1: &Self::Ciphertext,
202 key: &Self::Key,
203 ) -> Self::Ciphertext;
204 fn nor(
205 &mut self,
206 c0: &Self::Ciphertext,
207 c1: &Self::Ciphertext,
208 key: &Self::Key,
209 ) -> Self::Ciphertext;
210 fn xor(
211 &mut self,
212 c0: &Self::Ciphertext,
213 c1: &Self::Ciphertext,
214 key: &Self::Key,
215 ) -> Self::Ciphertext;
216 fn xnor(
217 &mut self,
218 c0: &Self::Ciphertext,
219 c1: &Self::Ciphertext,
220 key: &Self::Key,
221 ) -> Self::Ciphertext;
222 fn not(&mut self, c: &Self::Ciphertext) -> Self::Ciphertext;
223}
224
225struct ScratchMemory<M>
226where
227 M: Matrix,
228{
229 lwe_vector: M::R,
230 decomposition_matrix: M,
231}
232
233impl<M: MatrixEntity> ScratchMemory<M>
234where
235 M::R: RowEntity,
236{
237 fn new(parameters: &BoolParameters<M::MatElement>) -> Self {
238 // Vector to store LWE ciphertext with LWE dimesnion n
239 let lwe_vector = M::R::zeros(parameters.lwe_n().0 + 1);
240
241 // Matrix to store decomposed polynomials
242 // Max decompistion count + space for temporary RLWE
243 let d = std::cmp::max(
244 parameters.auto_decomposition_count().0,
245 std::cmp::max(
246 parameters.rlwe_rgsw_decomposition_count().0 .0,
247 parameters.rlwe_rgsw_decomposition_count().1 .0,
248 ),
249 ) + 2;
250 let decomposition_matrix = M::zeros(d, parameters.rlwe_n().0);
251
252 Self {
253 lwe_vector,
254 decomposition_matrix,
255 }
256 }
257}
258
259pub(super) trait BoolEncoding {
260 type Element;
261 fn true_el(&self) -> Self::Element;
262 fn false_el(&self) -> Self::Element;
263 fn qby4(&self) -> Self::Element;
264 fn decode(&self, m: Self::Element) -> bool;
265}
266
267impl<T> BoolEncoding for CiphertextModulus<T>
268where
269 CiphertextModulus<T>: Modulus<Element = T>,
270 T: PrimInt,
271{
272 type Element = T;
273
274 fn qby4(&self) -> Self::Element {
275 if self.is_native() {
276 T::one() << (CiphertextModulus::<T>::_bits() - 2)
277 } else {
278 self.q().unwrap() >> 2
279 }
280 }
281 /// Q/8
282 fn true_el(&self) -> Self::Element {
283 if self.is_native() {
284 T::one() << (CiphertextModulus::<T>::_bits() - 3)
285 } else {
286 self.q().unwrap() >> 3
287 }
288 }
289 /// -Q/8
290 fn false_el(&self) -> Self::Element {
291 self.largest_unsigned_value() - self.true_el() + T::one()
292 }
293 fn decode(&self, m: Self::Element) -> bool {
294 let qby8 = self.true_el();
295 let m = (((m + qby8).to_f64().unwrap() * 4.0f64) / self.q_as_f64().unwrap()).round()
296 as usize
297 % 4usize;
298
299 if m == 0 {
300 return false;
301 } else if m == 1 {
302 return true;
303 } else {
304 panic!("Incorrect bool decryption. Got m={m} but expected m to be 0 or 1")
305 }
306 }
307}
308
309impl<B> Encoder<bool, B::Element> for B
310where
311 B: BoolEncoding,
312{
313 fn encode(&self, v: bool) -> B::Element {
314 if v {
315 self.true_el()
316 } else {
317 self.false_el()
318 }
319 }
320}
321
322pub(super) struct BoolPbsInfo<M: Matrix, Ntt, RlweModOp, LweModOp> {
323 auto_decomposer: DefaultDecomposer<M::MatElement>,
324 rlwe_rgsw_decomposer: (
325 DefaultDecomposer<M::MatElement>,
326 DefaultDecomposer<M::MatElement>,
327 ),
328 lwe_decomposer: DefaultDecomposer<M::MatElement>,
329 g_k_dlog_map: Vec<usize>,
330 rlwe_nttop: Ntt,
331 rlwe_modop: RlweModOp,
332 lwe_modop: LweModOp,
333 embedding_factor: usize,
334 rlwe_qby4: M::MatElement,
335 rlwe_auto_maps: Vec<(Vec<usize>, Vec<bool>)>,
336 parameters: BoolParameters<M::MatElement>,
337}
338
339impl<M: Matrix, NttOp, RlweModOp, LweModOp> PbsInfo for BoolPbsInfo<M, NttOp, RlweModOp, LweModOp>
340where
341 M::MatElement: PrimInt
342 + WrappingSub
343 + NumInfo
344 + FromPrimitive
345 + From<bool>
346 + Display
347 + WrappingAdd
348 + Debug,
349 RlweModOp: ArithmeticOps<Element = M::MatElement> + ShoupMatrixFMA<M::R>,
350 LweModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
351 NttOp: Ntt<Element = M::MatElement>,
352{
353 type M = M;
354 type Modulus = CiphertextModulus<M::MatElement>;
355 type D = DefaultDecomposer<M::MatElement>;
356 type RlweModOp = RlweModOp;
357 type LweModOp = LweModOp;
358 type NttOp = NttOp;
359 fn rlwe_auto_map(&self, k: usize) -> &(Vec<usize>, Vec<bool>) {
360 &self.rlwe_auto_maps[k]
361 }
362 fn br_q(&self) -> usize {
363 *self.parameters.br_q()
364 }
365 fn lwe_decomposer(&self) -> &Self::D {
366 &self.lwe_decomposer
367 }
368 fn rlwe_rgsw_decomposer(&self) -> &(Self::D, Self::D) {
369 &self.rlwe_rgsw_decomposer
370 }
371 fn auto_decomposer(&self) -> &Self::D {
372 &self.auto_decomposer
373 }
374 fn embedding_factor(&self) -> usize {
375 self.embedding_factor
376 }
377 fn g(&self) -> isize {
378 self.parameters.g() as isize
379 }
380 fn w(&self) -> usize {
381 self.parameters.w()
382 }
383 fn g_k_dlog_map(&self) -> &[usize] {
384 &self.g_k_dlog_map
385 }
386 fn lwe_n(&self) -> usize {
387 self.parameters.lwe_n().0
388 }
389 fn lwe_q(&self) -> &Self::Modulus {
390 self.parameters.lwe_q()
391 }
392 fn rlwe_n(&self) -> usize {
393 self.parameters.rlwe_n().0
394 }
395 fn rlwe_q(&self) -> &Self::Modulus {
396 self.parameters.rlwe_q()
397 }
398 fn modop_lweq(&self) -> &Self::LweModOp {
399 &self.lwe_modop
400 }
401 fn modop_rlweq(&self) -> &Self::RlweModOp {
402 &self.rlwe_modop
403 }
404 fn nttop_rlweq(&self) -> &Self::NttOp {
405 &self.rlwe_nttop
406 }
407}
408
409pub(crate) struct BoolEvaluator<M, Ntt, RlweModOp, LweModOp, SKey>
410where
411 M: Matrix,
412{
413 pbs_info: BoolPbsInfo<M, Ntt, RlweModOp, LweModOp>,
414 scratch_memory: ScratchMemory<M>,
415 nand_test_vec: M::R,
416 and_test_vec: M::R,
417 or_test_vec: M::R,
418 nor_test_vec: M::R,
419 xor_test_vec: M::R,
420 xnor_test_vec: M::R,
421 /// Non-interactive u_i -> s key switch decomposer
422 ni_ui_to_s_ks_decomposer: Option<DefaultDecomposer<M::MatElement>>,
423 _phantom: PhantomData<SKey>,
424}
425
426impl<M: Matrix, NttOp, RlweModOp, LweModOp, Skey>
427 BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
428{
429 pub(crate) fn parameters(&self) -> &BoolParameters<M::MatElement> {
430 &self.pbs_info.parameters
431 }
432
433 pub(super) fn pbs_info(&self) -> &BoolPbsInfo<M, NttOp, RlweModOp, LweModOp> {
434 &self.pbs_info
435 }
436
437 pub(super) fn ni_ui_to_s_ks_decomposer(&self) -> &Option<DefaultDecomposer<M::MatElement>> {
438 &self.ni_ui_to_s_ks_decomposer
439 }
440}
441
442fn trim_rgsw_ct_matrix_from_rgrg_to_rlrg<
443 M: MatrixMut + MatrixEntity,
444 D: DoubleDecomposerParams<Count = DecompositionCount>,
445>(
446 rgsw_ct_in: M,
447 rgrg_params: D,
448 rlrg_params: D,
449) -> M
450where
451 M::R: RowMut,
452 M::MatElement: Copy,
453{
454 let (rgswrgsw_d_a, rgswrgsw_d_b) = (
455 rgrg_params.decomposition_count_a(),
456 rgrg_params.decomposition_count_b(),
457 );
458 let (rlrg_d_a, rlrg_d_b) = (
459 rlrg_params.decomposition_count_a(),
460 rlrg_params.decomposition_count_b(),
461 );
462 let rgsw_ct_rows_in = rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 * 2;
463 let rgsw_ct_rows_out = rlrg_d_a.0 * 2 + rlrg_d_b.0 * 2;
464 assert!(rgsw_ct_in.dimension().0 == rgsw_ct_rows_in);
465 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);
466 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);
467
468 let mut reduced_ct_i_out = M::zeros(rgsw_ct_rows_out, rgsw_ct_in.dimension().1);
469
470 // RLWE'(-sm) part A
471 izip!(
472 reduced_ct_i_out.iter_rows_mut().take(rlrg_d_a.0),
473 rgsw_ct_in
474 .iter_rows()
475 .skip(rgswrgsw_d_a.0 - rlrg_d_a.0)
476 .take(rlrg_d_a.0)
477 )
478 .for_each(|(to_ri, from_ri)| {
479 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
480 });
481
482 // RLWE'(-sm) part B
483 izip!(
484 reduced_ct_i_out
485 .iter_rows_mut()
486 .skip(rlrg_d_a.0)
487 .take(rlrg_d_a.0),
488 rgsw_ct_in
489 .iter_rows()
490 .skip(rgswrgsw_d_a.0 + (rgswrgsw_d_a.0 - rlrg_d_a.0))
491 .take(rlrg_d_a.0)
492 )
493 .for_each(|(to_ri, from_ri)| {
494 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
495 });
496
497 // RLWE'(m) Part A
498 izip!(
499 reduced_ct_i_out
500 .iter_rows_mut()
501 .skip(rlrg_d_a.0 * 2)
502 .take(rlrg_d_b.0),
503 rgsw_ct_in
504 .iter_rows()
505 .skip(rgswrgsw_d_a.0 * 2 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
506 .take(rlrg_d_b.0)
507 )
508 .for_each(|(to_ri, from_ri)| {
509 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
510 });
511
512 // RLWE'(m) Part B
513 izip!(
514 reduced_ct_i_out
515 .iter_rows_mut()
516 .skip(rlrg_d_a.0 * 2 + rlrg_d_b.0)
517 .take(rlrg_d_b.0),
518 rgsw_ct_in
519 .iter_rows()
520 .skip(rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
521 .take(rlrg_d_b.0)
522 )
523 .for_each(|(to_ri, from_ri)| {
524 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
525 });
526
527 reduced_ct_i_out
528}
529
530/// Assigns user with user_id segement of LWE secret indices for which they
531/// generate RGSW(X^{s[i]}) as the leader (i.e. for RLWExRGSW). If returned
532/// tuple is (start, end), user's segment is [start, end)
533pub(super) fn interactive_mult_party_user_id_lwe_segment(
534 user_id: usize,
535 total_users: usize,
536 lwe_n: usize,
537) -> (usize, usize) {
538 let per_user = (lwe_n as f64 / total_users as f64)
539 .ceil()
540 .to_usize()
541 .unwrap();
542 (
543 per_user * user_id,
544 std::cmp::min(per_user * (user_id + 1), lwe_n),
545 )
546}
547
548impl<M: Matrix, NttOp, RlweModOp, LweModOp, SKey> BoolEvaluator<M, NttOp, RlweModOp, LweModOp, SKey>
549where
550 M: MatrixEntity + MatrixMut,
551 M::MatElement: PrimInt
552 + Debug
553 + Display
554 + NumInfo
555 + FromPrimitive
556 + WrappingSub
557 + WrappingAdd
558 + SampleUniform
559 + From<bool>,
560 NttOp: Ntt<Element = M::MatElement>,
561 RlweModOp: ArithmeticOps<Element = M::MatElement>
562 + VectorOps<Element = M::MatElement>
563 + GetModulus<Element = M::MatElement, M = CiphertextModulus<M::MatElement>>
564 + ShoupMatrixFMA<M::R>,
565 LweModOp: ArithmeticOps<Element = M::MatElement>
566 + VectorOps<Element = M::MatElement>
567 + GetModulus<Element = M::MatElement, M = CiphertextModulus<M::MatElement>>,
568 M::R: TryConvertFrom1<[i32], CiphertextModulus<M::MatElement>> + RowEntity + Debug,
569 <M as Matrix>::R: RowMut,
570{
571 pub(super) fn new(parameters: BoolParameters<M::MatElement>) -> Self
572 where
573 RlweModOp: ModInit<M = CiphertextModulus<M::MatElement>>,
574 LweModOp: ModInit<M = CiphertextModulus<M::MatElement>>,
575 NttOp: NttInit<CiphertextModulus<M::MatElement>>,
576 {
577 //TODO(Jay): Run sanity checks for modulus values in parameters
578
579 // generates dlog map s.t. (+/-)g^{k} % q = a, for all a \in Z*_{q} and k \in
580 // [0, q/4). We store the dlog `k` at index `a`. This makes it easier to
581 // simply look up `k` at runtime as vec[a]. If a = g^{k} then dlog is
582 // stored as k. If a = -g^{k} then dlog is stored as k = q/4. This is done to
583 // differentiate sign.
584 let g = parameters.g();
585 let q = *parameters.br_q();
586 let mut g_k_dlog_map = vec![0usize; q];
587 for i in 0..q / 4 {
588 let v = mod_exponent(g as u64, i as u64, q as u64) as usize;
589 // g^i
590 g_k_dlog_map[v] = i;
591 // -(g^i)
592 g_k_dlog_map[q - v] = i + (q / 4);
593 }
594
595 let embedding_factor = (2 * parameters.rlwe_n().0) / q;
596
597 let rlwe_nttop = NttOp::new(parameters.rlwe_q(), parameters.rlwe_n().0);
598 let rlwe_modop = RlweModOp::new(*parameters.rlwe_q());
599 let lwe_modop = LweModOp::new(*parameters.lwe_q());
600
601 let q = *parameters.br_q();
602 let qby2 = q >> 1;
603 let qby8 = q >> 3;
604 // Q/8 (Q: rlwe_q)
605 let true_m_el = parameters.rlwe_q().true_el();
606 // -Q/8
607 let false_m_el = parameters.rlwe_q().false_el();
608 let (auto_map_index, auto_map_sign) = generate_auto_map(qby2, -(g as isize));
609
610 let init_test_vec = |partition_el: usize,
611 before_partition_el: M::MatElement,
612 after_partition_el: M::MatElement| {
613 let mut test_vec = M::R::zeros(qby2);
614 for i in 0..qby2 {
615 if i < partition_el {
616 test_vec.as_mut()[i] = before_partition_el;
617 } else {
618 test_vec.as_mut()[i] = after_partition_el;
619 }
620 }
621
622 // v(X) -> v(X^{-g})
623 let mut test_vec_autog = M::R::zeros(qby2);
624 izip!(
625 test_vec.as_ref().iter(),
626 auto_map_index.iter(),
627 auto_map_sign.iter()
628 )
629 .for_each(|(v, to_index, to_sign)| {
630 if !to_sign {
631 // negate
632 test_vec_autog.as_mut()[*to_index] = rlwe_modop.neg(v);
633 } else {
634 test_vec_autog.as_mut()[*to_index] = *v;
635 }
636 });
637
638 return test_vec_autog;
639 };
640
641 let nand_test_vec = init_test_vec(3 * qby8, true_m_el, false_m_el);
642 let and_test_vec = init_test_vec(3 * qby8, false_m_el, true_m_el);
643 let or_test_vec = init_test_vec(qby8, false_m_el, true_m_el);
644 let nor_test_vec = init_test_vec(qby8, true_m_el, false_m_el);
645 let xor_test_vec = init_test_vec(qby8, false_m_el, true_m_el);
646 let xnor_test_vec = init_test_vec(qby8, true_m_el, false_m_el);
647
648 // auto map indices and sign
649 // Auto maps are stored as [-g, g^{1}, g^{2}, ..., g^{w}]
650 let mut rlwe_auto_maps = vec![];
651 let ring_size = parameters.rlwe_n().0;
652 let g = parameters.g();
653 let br_q = parameters.br_q();
654 let auto_element_dlogs = parameters.auto_element_dlogs();
655 assert!(auto_element_dlogs[0] == 0);
656 for i in auto_element_dlogs.into_iter() {
657 let el = if i == 0 {
658 -(g as isize)
659 } else {
660 (g.pow(i as u32) % br_q) as isize
661 };
662 rlwe_auto_maps.push(generate_auto_map(ring_size, el))
663 }
664
665 let rlwe_qby4 = parameters.rlwe_q().qby4();
666
667 let scratch_memory = ScratchMemory::new(¶meters);
668
669 let ni_ui_to_s_ks_decomposer = if parameters.variant()
670 == &ParameterVariant::NonInteractiveMultiParty
671 {
672 Some(parameters
673 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>())
674 } else {
675 None
676 };
677
678 let pbs_info = BoolPbsInfo {
679 auto_decomposer: parameters.auto_decomposer(),
680 lwe_decomposer: parameters.lwe_decomposer(),
681 rlwe_rgsw_decomposer: parameters.rlwe_rgsw_decomposer(),
682 g_k_dlog_map,
683 embedding_factor,
684 lwe_modop,
685 rlwe_modop,
686 rlwe_nttop,
687 rlwe_qby4,
688 rlwe_auto_maps,
689 parameters: parameters,
690 };
691
692 BoolEvaluator {
693 pbs_info,
694 scratch_memory,
695 nand_test_vec,
696 and_test_vec,
697 or_test_vec,
698 nor_test_vec,
699 xnor_test_vec,
700 xor_test_vec,
701 ni_ui_to_s_ks_decomposer,
702 _phantom: PhantomData,
703 }
704 }
705
706 pub(crate) fn client_key(
707 &self,
708 ) -> ClientKey<<DefaultSecureRng as NewWithSeed>::Seed, M::MatElement> {
709 ClientKey::new(self.parameters().clone())
710 }
711
712 pub(super) fn single_party_server_key<K: SinglePartyClientKey<Element = i32>>(
713 &self,
714 client_key: &K,
715 ) -> SeededSinglePartyServerKey<M, BoolParameters<M::MatElement>, [u8; 32]> {
716 assert_eq!(self.parameters().variant(), &ParameterVariant::SingleParty);
717
718 DefaultSecureRng::with_local_mut(|rng| {
719 let mut main_seed = [0u8; 32];
720 rng.fill_bytes(&mut main_seed);
721
722 let mut main_prng = DefaultSecureRng::new_seeded(main_seed);
723
724 let rlwe_n = self.pbs_info.parameters.rlwe_n().0;
725 let sk_rlwe = client_key.sk_rlwe();
726 let sk_lwe = client_key.sk_lwe();
727
728 // generate auto keys
729 let mut auto_keys = HashMap::new();
730 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
731 let g = self.pbs_info.parameters.g();
732 let br_q = self.pbs_info.parameters.br_q();
733 let auto_els = self.pbs_info.parameters.auto_element_dlogs();
734 for i in auto_els.into_iter() {
735 let g_pow = if i == 0 {
736 -(g as isize)
737 } else {
738 (g.pow(i as u32) % br_q) as isize
739 };
740 let mut gk = M::zeros(self.pbs_info.auto_decomposer.decomposition_count(), rlwe_n);
741 galois_key_gen(
742 &mut gk,
743 &sk_rlwe,
744 g_pow,
745 &auto_gadget,
746 &self.pbs_info.rlwe_modop,
747 &self.pbs_info.rlwe_nttop,
748 &mut main_prng,
749 rng,
750 );
751 auto_keys.insert(i, gk);
752 }
753
754 // generate rgsw ciphertexts RGSW(si) where si is i^th LWE secret element
755 let ring_size = self.pbs_info.parameters.rlwe_n().0;
756 let rlwe_q = self.pbs_info.parameters.rlwe_q();
757 let (rlrg_d_a, rlrg_d_b) = (
758 self.pbs_info.rlwe_rgsw_decomposer.0.decomposition_count(),
759 self.pbs_info.rlwe_rgsw_decomposer.1.decomposition_count(),
760 );
761 let rlrg_gadget_a = self.pbs_info.rlwe_rgsw_decomposer.0.gadget_vector();
762 let rlrg_gadget_b = self.pbs_info.rlwe_rgsw_decomposer.1.gadget_vector();
763 let rgsw_cts = sk_lwe
764 .iter()
765 .map(|si| {
766 // X^{si}; assume |emebedding_factor * si| < N
767 let mut m = M::R::zeros(ring_size);
768 let si = (self.pbs_info.embedding_factor as i32) * si;
769 // dbg!(si);
770 if si < 0 {
771 // X^{-i} = X^{2N - i} = -X^{N-i}
772 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q.neg_one();
773 } else {
774 // X^{i}
775 m.as_mut()[si.abs() as usize] = M::MatElement::one();
776 }
777
778 let mut rgsw_si = M::zeros(rlrg_d_a * 2 + rlrg_d_b, ring_size);
779 secret_key_encrypt_rgsw(
780 &mut rgsw_si,
781 m.as_ref(),
782 &rlrg_gadget_a,
783 &rlrg_gadget_b,
784 &sk_rlwe,
785 &self.pbs_info.rlwe_modop,
786 &self.pbs_info.rlwe_nttop,
787 &mut main_prng,
788 rng,
789 );
790
791 rgsw_si
792 })
793 .collect_vec();
794
795 // LWE KSK from RLWE secret s -> LWE secret z
796 let d_lwe_gadget = self.pbs_info.lwe_decomposer.gadget_vector();
797 let mut lwe_ksk =
798 M::R::zeros(self.pbs_info.lwe_decomposer.decomposition_count() * ring_size);
799 lwe_ksk_keygen(
800 &sk_rlwe,
801 &sk_lwe,
802 &mut lwe_ksk,
803 &d_lwe_gadget,
804 &self.pbs_info.lwe_modop,
805 &mut main_prng,
806 rng,
807 );
808
809 SeededSinglePartyServerKey::from_raw(
810 auto_keys,
811 rgsw_cts,
812 lwe_ksk,
813 self.pbs_info.parameters.clone(),
814 main_seed,
815 )
816 })
817 }
818
819 pub(super) fn multi_party_server_key_share<K: InteractiveMultiPartyClientKey<Element = i32>>(
820 &self,
821 user_id: usize,
822 total_users: usize,
823 cr_seed: &MultiPartyCrs<[u8; 32]>,
824 collective_pk: &M,
825 client_key: &K,
826 ) -> CommonReferenceSeededMultiPartyServerKeyShare<
827 M,
828 BoolParameters<M::MatElement>,
829 MultiPartyCrs<[u8; 32]>,
830 > {
831 assert_eq!(self.parameters().variant(), &ParameterVariant::MultiParty);
832 assert!(user_id < total_users);
833
834 let sk_rlwe = client_key.sk_rlwe();
835 let sk_lwe = client_key.sk_lwe();
836
837 let g = self.pbs_info.parameters.g();
838 let ring_size = self.pbs_info.parameters.rlwe_n().0;
839 let rlwe_q = self.pbs_info.parameters.rlwe_q();
840 let lwe_q = self.pbs_info.parameters.lwe_q();
841
842 let rlweq_modop = &self.pbs_info.rlwe_modop;
843 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
844
845 // sanity check
846 assert!(sk_rlwe.len() == ring_size);
847 assert!(sk_lwe.len() == self.pbs_info.parameters.lwe_n().0);
848
849 // auto keys
850 let auto_keys = self._common_rountine_multi_party_auto_keys_share_gen(
851 cr_seed.auto_keys_cts_seed::<DefaultSecureRng>(),
852 &sk_rlwe,
853 );
854
855 // rgsw ciphertexts of lwe secret elements
856 let (self_leader_rgsws, not_self_leader_rgsws) = DefaultSecureRng::with_local_mut(|rng| {
857 let mut self_leader_rgsw = vec![];
858 let mut not_self_leader_rgsws = vec![];
859
860 let (segment_start, segment_end) = interactive_mult_party_user_id_lwe_segment(
861 user_id,
862 total_users,
863 self.pbs_info().lwe_n(),
864 );
865
866 // self LWE secret indices
867 {
868 // LWE secret indices for which user is the leader they need to send RGSW(m) for
869 // RLWE x RGSW multiplication
870 let rlrg_decomposer = self.pbs_info().rlwe_rgsw_decomposer();
871 let (rlrg_d_a, rlrg_d_b) = (
872 rlrg_decomposer.a().decomposition_count(),
873 rlrg_decomposer.b().decomposition_count(),
874 );
875 let (gadget_a, gadget_b) = (
876 rlrg_decomposer.a().gadget_vector(),
877 rlrg_decomposer.b().gadget_vector(),
878 );
879 for s_index in segment_start..segment_end {
880 let mut out_rgsw = M::zeros(rlrg_d_a * 2 + rlrg_d_b * 2, ring_size);
881 public_key_encrypt_rgsw(
882 &mut out_rgsw,
883 &encode_x_pow_si_with_emebedding_factor::<
884 M::R,
885 CiphertextModulus<M::MatElement>,
886 >(
887 sk_lwe[s_index],
888 self.pbs_info().embedding_factor(),
889 ring_size,
890 self.pbs_info().rlwe_q(),
891 )
892 .as_ref(),
893 collective_pk,
894 &gadget_a,
895 &gadget_b,
896 rlweq_modop,
897 rlweq_nttop,
898 rng,
899 );
900 self_leader_rgsw.push(out_rgsw);
901 }
902 }
903
904 // not self LWE secret indices
905 {
906 // LWE secret indices for which user isn't the leader, they need to send RGSW(m)
907 // for RGSW x RGSW multiplcation
908 let rgsw_rgsw_decomposer = self
909 .pbs_info
910 .parameters
911 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
912 let (rgrg_d_a, rgrg_d_b) = (
913 rgsw_rgsw_decomposer.a().decomposition_count(),
914 rgsw_rgsw_decomposer.b().decomposition_count(),
915 );
916 let (rgrg_gadget_a, rgrg_gadget_b) = (
917 rgsw_rgsw_decomposer.a().gadget_vector(),
918 rgsw_rgsw_decomposer.b().gadget_vector(),
919 );
920
921 for s_index in (0..segment_start).chain(segment_end..self.parameters().lwe_n().0) {
922 let mut out_rgsw = M::zeros(rgrg_d_a * 2 + rgrg_d_b * 2, ring_size);
923 public_key_encrypt_rgsw(
924 &mut out_rgsw,
925 &encode_x_pow_si_with_emebedding_factor::<
926 M::R,
927 CiphertextModulus<M::MatElement>,
928 >(
929 sk_lwe[s_index],
930 self.pbs_info().embedding_factor(),
931 ring_size,
932 self.pbs_info().rlwe_q(),
933 )
934 .as_ref(),
935 collective_pk,
936 &rgrg_gadget_a,
937 &rgrg_gadget_b,
938 rlweq_modop,
939 rlweq_nttop,
940 rng,
941 );
942
943 not_self_leader_rgsws.push(out_rgsw);
944 }
945 }
946
947 (self_leader_rgsw, not_self_leader_rgsws)
948 });
949
950 // LWE Ksk
951 let lwe_ksk = self._common_rountine_multi_party_lwe_ksk_share_gen(
952 cr_seed.lwe_ksk_cts_seed_seed::<DefaultSecureRng>(),
953 &sk_rlwe,
954 &sk_lwe,
955 );
956
957 CommonReferenceSeededMultiPartyServerKeyShare::new(
958 self_leader_rgsws,
959 not_self_leader_rgsws,
960 auto_keys,
961 lwe_ksk,
962 cr_seed.clone(),
963 self.pbs_info.parameters.clone(),
964 user_id,
965 )
966 }
967
968 pub(super) fn aggregate_multi_party_server_key_shares<S>(
969 &self,
970 shares: &[CommonReferenceSeededMultiPartyServerKeyShare<
971 M,
972 BoolParameters<M::MatElement>,
973 MultiPartyCrs<S>,
974 >],
975 ) -> SeededMultiPartyServerKey<M, MultiPartyCrs<S>, BoolParameters<M::MatElement>>
976 where
977 S: PartialEq + Clone,
978 M: Clone,
979 {
980 assert_eq!(self.parameters().variant(), &ParameterVariant::MultiParty);
981 assert!(shares.len() > 0);
982
983 let total_users = shares.len();
984
985 let parameters = shares[0].parameters().clone();
986 let cr_seed = shares[0].cr_seed();
987
988 let rlwe_n = parameters.rlwe_n().0;
989 let g = parameters.g() as isize;
990 let rlwe_q = parameters.rlwe_q();
991 let lwe_q = parameters.lwe_q();
992
993 // sanity checks
994 shares.iter().skip(1).for_each(|s| {
995 assert!(s.parameters() == ¶meters);
996 assert!(s.cr_seed() == cr_seed);
997 });
998
999 let rlweq_modop = &self.pbs_info.rlwe_modop;
1000 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1001
1002 // auto keys
1003 let mut auto_keys = HashMap::new();
1004 let auto_elements_dlog = parameters.auto_element_dlogs();
1005 for i in auto_elements_dlog.into_iter() {
1006 let mut key = M::zeros(parameters.auto_decomposition_count().0, rlwe_n);
1007
1008 shares.iter().for_each(|s| {
1009 let auto_key_share_i = s.auto_keys().get(&i).expect("Auto key {i} missing");
1010 assert!(
1011 auto_key_share_i.dimension()
1012 == (parameters.auto_decomposition_count().0, rlwe_n)
1013 );
1014 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
1015 |(partb_out, partb_share)| {
1016 rlweq_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
1017 },
1018 );
1019 });
1020
1021 auto_keys.insert(i, key);
1022 }
1023
1024 // rgsw ciphertext (most expensive part!)
1025 let rgsw_cts = {
1026 let rgsw_by_rgsw_decomposer =
1027 parameters.rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1028 let rlwe_x_rgsw_decomposer = self.pbs_info().rlwe_rgsw_decomposer();
1029 let rgsw_x_rgsw_dimension = (
1030 rgsw_by_rgsw_decomposer.a().decomposition_count() * 2
1031 + rgsw_by_rgsw_decomposer.b().decomposition_count() * 2,
1032 rlwe_n,
1033 );
1034 let rlwe_x_rgsw_dimension = (
1035 rlwe_x_rgsw_decomposer.a().decomposition_count() * 2
1036 + rlwe_x_rgsw_decomposer.b().decomposition_count() * 2,
1037 rlwe_n,
1038 );
1039 let mut rgsw_x_rgsw_scratch_mat = M::zeros(
1040 std::cmp::max(
1041 rgsw_by_rgsw_decomposer.a().decomposition_count(),
1042 rgsw_by_rgsw_decomposer.b().decomposition_count(),
1043 ) + rlwe_x_rgsw_dimension.0,
1044 rlwe_n,
1045 );
1046
1047 let shares_in_correct_order = (0..total_users)
1048 .map(|i| shares.iter().find(|s| s.user_id() == i).unwrap())
1049 .collect_vec();
1050
1051 let lwe_n = self.parameters().lwe_n().0;
1052 let (users_segments, users_segments_sizes): (Vec<(usize, usize)>, Vec<usize>) = (0
1053 ..total_users)
1054 .map(|(user_id)| {
1055 let (start_index, end_index) =
1056 interactive_mult_party_user_id_lwe_segment(user_id, total_users, lwe_n);
1057 ((start_index, end_index), end_index - start_index)
1058 })
1059 .unzip();
1060
1061 let mut rgsw_cts = Vec::with_capacity(lwe_n);
1062 users_segments
1063 .iter()
1064 .enumerate()
1065 .for_each(|(user_id, user_segment)| {
1066 let share = shares_in_correct_order[user_id];
1067 for secret_index in user_segment.0..user_segment.1 {
1068 let mut rgsw_i =
1069 share.self_leader_rgsws()[secret_index - user_segment.0].clone();
1070 // assert already exists in RGSW x RGSW rountine
1071 assert!(rgsw_i.dimension() == rlwe_x_rgsw_dimension);
1072
1073 // multiply leader's RGSW ct at `secret_index` with RGSW cts of other users
1074 // for lwe index `secret_index`
1075 (0..total_users)
1076 .filter(|i| i != &user_id)
1077 .for_each(|other_user_id| {
1078 let mut offset = 0;
1079 if other_user_id < user_id {
1080 offset = users_segments_sizes[other_user_id];
1081 }
1082
1083 let mut other_rgsw_i = shares_in_correct_order[other_user_id]
1084 .not_self_leader_rgsws()
1085 [secret_index.checked_sub(offset).unwrap()]
1086 .clone();
1087 // assert already exists in RGSW x RGSW rountine
1088 assert!(other_rgsw_i.dimension() == rgsw_x_rgsw_dimension);
1089
1090 // send to evaluation domain for RGSwxRGSW mul
1091 other_rgsw_i
1092 .iter_rows_mut()
1093 .for_each(|r| rlweq_nttop.forward(r.as_mut()));
1094
1095 rgsw_by_rgsw_inplace(
1096 &mut rgsw_i,
1097 rlwe_x_rgsw_decomposer.a().decomposition_count(),
1098 rlwe_x_rgsw_decomposer.b().decomposition_count(),
1099 &other_rgsw_i,
1100 &rgsw_by_rgsw_decomposer,
1101 &mut rgsw_x_rgsw_scratch_mat,
1102 rlweq_nttop,
1103 rlweq_modop,
1104 )
1105 });
1106
1107 rgsw_cts.push(rgsw_i);
1108 }
1109 });
1110
1111 rgsw_cts
1112 };
1113
1114 // LWE ksks
1115 let mut lwe_ksk = M::R::zeros(rlwe_n * parameters.lwe_decomposition_count().0);
1116 let lweq_modop = &self.pbs_info.lwe_modop;
1117 shares.iter().for_each(|si| {
1118 assert!(si.lwe_ksk().as_ref().len() == rlwe_n * parameters.lwe_decomposition_count().0);
1119 lweq_modop.elwise_add_mut(lwe_ksk.as_mut(), si.lwe_ksk().as_ref())
1120 });
1121
1122 SeededMultiPartyServerKey::new(rgsw_cts, auto_keys, lwe_ksk, cr_seed.clone(), parameters)
1123 }
1124
1125 pub(super) fn aggregate_non_interactive_multi_party_key_share(
1126 &self,
1127 cr_seed: &NonInteractiveMultiPartyCrs<[u8; 32]>,
1128 total_users: usize,
1129 key_shares: &[CommonReferenceSeededNonInteractiveMultiPartyServerKeyShare<
1130 M,
1131 NonInteractiveMultiPartyCrs<[u8; 32]>,
1132 >],
1133 ) -> SeededNonInteractiveMultiPartyServerKey<
1134 M,
1135 NonInteractiveMultiPartyCrs<[u8; 32]>,
1136 BoolParameters<M::MatElement>,
1137 >
1138 where
1139 M: Clone + Debug,
1140 {
1141 assert_eq!(
1142 self.parameters().variant(),
1143 &ParameterVariant::NonInteractiveMultiParty
1144 );
1145
1146 // sanity checks
1147 let key_order = {
1148 let existing_key_order = key_shares.iter().map(|s| s.user_index()).collect_vec();
1149
1150 // record the order s.t. key_order[i] stores the position of i^th
1151 // users key share in existing order
1152 let mut key_order = Vec::with_capacity(existing_key_order.len());
1153 (0..total_users).for_each(|i| {
1154 // find i
1155 let index = existing_key_order
1156 .iter()
1157 .position(|x| x == &i)
1158 .expect(&format!("Missing user {i}'s key!"));
1159 key_order.push(index);
1160 });
1161
1162 key_order
1163 };
1164
1165 let rlwe_modop = &self.pbs_info().rlwe_modop;
1166 let nttop = &self.pbs_info().rlwe_nttop;
1167 let ring_size = self.parameters().rlwe_n().0;
1168 let rlwe_q = self.parameters().rlwe_q();
1169 let lwe_modop = self.pbs_info().modop_lweq();
1170
1171 // genrate key switching key from u_i to s
1172 let ui_to_s_ksk_decomposition_count = self
1173 .parameters()
1174 .non_interactive_ui_to_s_key_switch_decomposition_count();
1175 let mut ui_to_s_ksks = key_shares
1176 .iter()
1177 .map(|share| {
1178 let mut useri_ui_to_s_ksk = share.ui_to_s_ksk().clone();
1179 assert!(
1180 useri_ui_to_s_ksk.dimension() == (ui_to_s_ksk_decomposition_count.0, ring_size)
1181 );
1182 key_shares
1183 .iter()
1184 .filter(|x| x.user_index() != share.user_index())
1185 .for_each(|(other_share)| {
1186 let op2 = other_share.ui_to_s_ksk_zero_encs_for_user_i(share.user_index());
1187 assert!(op2.dimension() == (ui_to_s_ksk_decomposition_count.0, ring_size));
1188 izip!(useri_ui_to_s_ksk.iter_rows_mut(), op2.iter_rows()).for_each(
1189 |(add_to, add_from)| {
1190 rlwe_modop.elwise_add_mut(add_to.as_mut(), add_from.as_ref())
1191 },
1192 );
1193 });
1194 useri_ui_to_s_ksk
1195 })
1196 .collect_vec();
1197
1198 let rgsw_cts = {
1199 let mut rgsw_prng =
1200 DefaultSecureRng::new_seeded(cr_seed.rgsw_cts_seed::<DefaultSecureRng>());
1201
1202 let rgsw_by_rgsw_decomposer = self
1203 .parameters()
1204 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1205
1206 // Generate RGSW Cts
1207 let rgsw_cts_all_users_eval = {
1208 // temporarily put ui_to_s in evaluation domain and sample a_i's for u_i to s
1209 // ksk for upcomong key switches
1210 ui_to_s_ksks.iter_mut().for_each(|ksk_i| {
1211 ksk_i
1212 .iter_rows_mut()
1213 .for_each(|r| nttop.forward(r.as_mut()))
1214 });
1215 let ui_to_s_ksks_part_a_eval = key_shares
1216 .iter()
1217 .map(|share| {
1218 let mut ksk_prng = DefaultSecureRng::new_seeded(
1219 cr_seed
1220 .ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(share.user_index()),
1221 );
1222 let mut ais = M::zeros(ui_to_s_ksk_decomposition_count.0, ring_size);
1223
1224 ais.iter_rows_mut().for_each(|r_ai| {
1225 RandomFillUniformInModulus::random_fill(
1226 &mut ksk_prng,
1227 rlwe_q,
1228 r_ai.as_mut(),
1229 );
1230
1231 nttop.forward(r_ai.as_mut())
1232 });
1233 ais
1234 })
1235 .collect_vec();
1236
1237 let max_rgrg_deocmposer = if rgsw_by_rgsw_decomposer.a().decomposition_count()
1238 > rgsw_by_rgsw_decomposer.b().decomposition_count()
1239 {
1240 rgsw_by_rgsw_decomposer.a()
1241 } else {
1242 rgsw_by_rgsw_decomposer.b()
1243 };
1244
1245 let ui_to_s_ksk_decomposer = self
1246 .parameters()
1247 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>(
1248 );
1249
1250 // Generate a_i*s + E = \sum_{j \in P} a_i*s_j + e for all rlwes in each
1251 // non-interactive rgsws. Then decompose and put decompositions in evaluation
1252 // for u_i -> s key switch.
1253 let decomp_ni_rgsws_part_1_acc = {
1254 let mut tmp_space = M::R::zeros(ring_size);
1255
1256 (0..self.parameters().lwe_n().0)
1257 .into_iter()
1258 .map(|lwe_index| {
1259 (0..max_rgrg_deocmposer.decomposition_count())
1260 .into_iter()
1261 .map(|d_index| {
1262 let mut sum = M::zeros(
1263 ui_to_s_ksk_decomposer.decomposition_count(),
1264 ring_size,
1265 );
1266
1267 // set temp_space to all zeros
1268 tmp_space.as_mut().fill(M::MatElement::zero());
1269
1270 // a_i*s + E
1271 key_shares.iter().for_each(|s| {
1272 rlwe_modop.elwise_add_mut(
1273 tmp_space.as_mut(),
1274 s.ni_rgsw_cts().1[lwe_index].get_row_slice(d_index),
1275 );
1276 });
1277
1278 tmp_space.as_ref().iter().enumerate().for_each(|(ri, el)| {
1279 ui_to_s_ksk_decomposer
1280 .decompose_iter(el)
1281 .enumerate()
1282 .for_each(|(row_j, d_el)| {
1283 (sum.as_mut()[row_j]).as_mut()[ri] = d_el;
1284 });
1285 });
1286
1287 sum.iter_rows_mut().for_each(|r| nttop.forward(r.as_mut()));
1288
1289 sum
1290 })
1291 .collect_vec()
1292 })
1293 .collect_vec()
1294 };
1295
1296 // Sample a_i's are used to generate non-interactive rgsw cts for all lwe
1297 // indices. Since a_i are just needed for key switches , decompose them
1298 // and put them in evaluation domain
1299 // Decomposition count used for RGSW ct in non-interactive key share gen equals
1300 // max of A and B decomposition required in RGSWxRGSW. This is because same
1301 // polynomials are used to generate RLWE'(m) and RLWE'(-sm)
1302 let decomp_ni_rgsw_neg_ais = {
1303 let mut tmp_space = M::R::zeros(ring_size);
1304 (0..self.parameters().lwe_n().0)
1305 .into_iter()
1306 .map(|_| {
1307 // FIXME(Jay): well well, ais are only required for key switching to
1308 // generate RLWE'(m) and RLWE'(m) itself
1309 // requires RLWE(\beta^i m) for i \in RGSWxRGSW
1310 // part B decomposition count. However, we still need to puncture prng
1311 // for ais corresponding to ignored limbs.
1312 // Probably it will be nice idea to
1313 // avoid decomposition after punturing for a_i's corresponding to
1314 // ignored limbs. Moreover, note that, for
1315 // RGSWxRGSW often times decompostion count for part A
1316 // > part B. Hence, it's very likely that we are doing
1317 // unecesary decompositions for ignored limbs all the time.
1318 (0..max_rgrg_deocmposer.decomposition_count())
1319 .map(|_| {
1320 RandomFillUniformInModulus::random_fill(
1321 &mut rgsw_prng,
1322 rlwe_q,
1323 tmp_space.as_mut(),
1324 );
1325
1326 // negate
1327 rlwe_modop.elwise_neg_mut(tmp_space.as_mut());
1328
1329 // decomposer a_i for ui -> s key switch
1330 let mut decomp_neg_ai = M::zeros(
1331 ui_to_s_ksk_decomposer.decomposition_count(),
1332 ring_size,
1333 );
1334 tmp_space.as_ref().iter().enumerate().for_each(
1335 |(index, el)| {
1336 ui_to_s_ksk_decomposer
1337 .decompose_iter(el)
1338 .enumerate()
1339 .for_each(|(row_j, d_el)| {
1340 (decomp_neg_ai.as_mut()[row_j]).as_mut()
1341 [index] = d_el;
1342 });
1343 },
1344 );
1345
1346 // put in evaluation domain
1347 decomp_neg_ai
1348 .iter_rows_mut()
1349 .for_each(|r| nttop.forward(r.as_mut()));
1350
1351 decomp_neg_ai
1352 })
1353 .collect_vec()
1354 })
1355 .collect_vec()
1356 };
1357
1358 // genrate RGSW cts
1359 let rgsw_cts_all_users_eval = izip!(
1360 key_shares.iter(),
1361 ui_to_s_ksks.iter(),
1362 ui_to_s_ksks_part_a_eval.iter()
1363 )
1364 .map(
1365 |(share, user_uitos_ksk_partb_eval, user_uitos_ksk_parta_eval)| {
1366 // RGSW_s(X^{s[i]})
1367 let rgsw_cts_user_i_eval = izip!(
1368 share.ni_rgsw_cts().0.iter(),
1369 decomp_ni_rgsw_neg_ais.iter(),
1370 decomp_ni_rgsws_part_1_acc.iter()
1371 )
1372 .map(
1373 |(
1374 m_encs_under_ui,
1375 decomposed_rgsw_i_neg_ais,
1376 decomposed_acc_rgsw_part1,
1377 )| {
1378 let d_a = rgsw_by_rgsw_decomposer.a().decomposition_count();
1379 let d_b = rgsw_by_rgsw_decomposer.b().decomposition_count();
1380 let max_d = std::cmp::max(d_a, d_b);
1381
1382 assert!(decomposed_rgsw_i_neg_ais.len() == max_d);
1383
1384 // To be RGSW(X^{s[i]}) = [RLWE'(-sm), RLWE'(m)]
1385 let mut rgsw_ct_eval = M::zeros(d_a * 2 + d_b * 2, ring_size);
1386 let (rlwe_dash_nsm, rlwe_dash_m) =
1387 rgsw_ct_eval.split_at_row_mut(d_a * 2);
1388
1389 let mut scratch_row = M::R::zeros(ring_size);
1390
1391 let mut m_encs_under_ui_eval = m_encs_under_ui.clone();
1392 m_encs_under_ui_eval
1393 .iter_rows_mut()
1394 .for_each(|r| nttop.forward(r.as_mut()));
1395
1396 // RLWE(-sm)
1397 {
1398 // Recall that we have RLWE(a_i * s + e). We key
1399 // switch RLWE(a_i * s + e) using ksk(u_i -> s) to
1400 // get RLWE(a_i*s*u_i + e*u_i).
1401 // Given (u_i * a_i + e + \beta m), we obtain
1402 // RLWE(-sm) = RLWE(a_i*s*u_i + e*u_i) + (0, (u_i *
1403 // a_i + e + \beta m))
1404 //
1405 // Again RLWE'(-sm) only cares for RLWE(\beta -sm)
1406 // with scaling factor \beta corresponding to most
1407 // signficant d_a limbs. Hence, we skip (d_max -
1408 // d_a) least signficant limbs
1409
1410 let (rlwe_dash_neg_sm_part_a, rlwe_dash_neg_sm_part_b) =
1411 rlwe_dash_nsm.split_at_mut(d_a);
1412
1413 izip!(
1414 rlwe_dash_neg_sm_part_a.iter_mut(),
1415 rlwe_dash_neg_sm_part_b.iter_mut(),
1416 decomposed_acc_rgsw_part1.iter().skip(max_d - d_a),
1417 m_encs_under_ui_eval.iter_rows().skip(max_d - d_a)
1418 )
1419 .for_each(
1420 |(rlwe_a, rlwe_b, decomp_ai_s, beta_m_enc_ui)| {
1421 // RLWE_s(a_i * s * u_i + u_i * e) = decomp<a_i * s + e>
1422 // * ksk(u_i
1423 // -> s)
1424 izip!(
1425 decomp_ai_s.iter_rows(),
1426 user_uitos_ksk_partb_eval.iter_rows(),
1427 user_uitos_ksk_parta_eval.iter_rows()
1428 )
1429 .for_each(
1430 |(a0, part_b, part_a)| {
1431 // rlwe_b += decomp<a_i * s + e>[i] * ksk
1432 // part_b[i]
1433 rlwe_modop.elwise_mul(
1434 scratch_row.as_mut(),
1435 a0.as_ref(),
1436 part_b.as_ref(),
1437 );
1438 rlwe_modop.elwise_add_mut(
1439 rlwe_b.as_mut(),
1440 scratch_row.as_ref(),
1441 );
1442
1443 // rlwe_a += decomp<a_i * s + e>[i] * ksk
1444 // part_a[i]
1445 rlwe_modop.elwise_mul(
1446 scratch_row.as_mut(),
1447 a0.as_ref(),
1448 part_a.as_ref(),
1449 );
1450 rlwe_modop.elwise_add_mut(
1451 rlwe_a.as_mut(),
1452 scratch_row.as_ref(),
1453 );
1454 },
1455 );
1456
1457 // RLWE_s(-sm) = RLWE_s(a_i * s * u_i + u_i
1458 // * e) + (0, a_i * u + e + m)
1459 rlwe_modop.elwise_add_mut(
1460 rlwe_a.as_mut(),
1461 beta_m_enc_ui.as_ref(),
1462 );
1463 },
1464 );
1465 }
1466
1467 // RLWE(m)
1468 {
1469 // Routine:
1470 // Let RLWE(-a_i * u_i) = (decomp<-a_i> \cdot ksk(u_i -> s)),
1471 // then RLWE(m) = RLWE(a'*s + e + m) = (a_i
1472 // * u_i + e + m, 0) + RLWE(-a_i * u_i)
1473 //
1474 // Since RLWE'(m) only cares for RLWE ciphertexts corresponding
1475 // to higher d_b limbs, we skip routine 1 for lower max(d_a,
1476 // d_b) - d_b limbs
1477 let (rlwe_dash_m_part_a, rlwe_dash_m_part_b) =
1478 rlwe_dash_m.split_at_mut(d_b);
1479
1480 izip!(
1481 rlwe_dash_m_part_a.iter_mut(),
1482 rlwe_dash_m_part_b.iter_mut(),
1483 decomposed_rgsw_i_neg_ais.iter().skip(max_d - d_b),
1484 m_encs_under_ui_eval.iter_rows().skip(max_d - d_b)
1485 )
1486 .for_each(
1487 |(rlwe_a, rlwe_b, decomp_neg_ai, beta_m_enc_ui)| {
1488 // RLWE_s(-a_i * ui) = decomp<-a_i> \cdot ksk(ui -> s)
1489 izip!(
1490 decomp_neg_ai.iter_rows(),
1491 user_uitos_ksk_partb_eval.iter_rows(),
1492 user_uitos_ksk_parta_eval.iter_rows()
1493 )
1494 .for_each(
1495 |(a0, part_b, part_a)| {
1496 // rlwe_b += decomp<a>[i] * ksk part_b[i]
1497 rlwe_modop.elwise_mul(
1498 scratch_row.as_mut(),
1499 a0.as_ref(),
1500 part_b.as_ref(),
1501 );
1502 rlwe_modop.elwise_add_mut(
1503 rlwe_b.as_mut(),
1504 scratch_row.as_ref(),
1505 );
1506
1507 // rlwe_a += decomp<a>[i] * ksk
1508 // part_a[i]
1509 rlwe_modop.elwise_mul(
1510 scratch_row.as_mut(),
1511 a0.as_ref(),
1512 part_a.as_ref(),
1513 );
1514 rlwe_modop.elwise_add_mut(
1515 rlwe_a.as_mut(),
1516 scratch_row.as_ref(),
1517 );
1518 },
1519 );
1520
1521 // RLWE_s(m) = (a_i * ui + e + \beta m, 0)
1522 // +
1523 // RLWE_s(-a_i * ui)
1524 rlwe_modop.elwise_add_mut(
1525 rlwe_b.as_mut(),
1526 beta_m_enc_ui.as_ref(),
1527 );
1528 },
1529 );
1530 }
1531
1532 rgsw_ct_eval
1533 },
1534 )
1535 .collect_vec();
1536 rgsw_cts_user_i_eval
1537 },
1538 )
1539 .collect_vec();
1540
1541 // put u_i -> s ksks back in coefficient domain
1542 ui_to_s_ksks.iter_mut().for_each(|ksk_i| {
1543 ksk_i
1544 .iter_rows_mut()
1545 .for_each(|r| nttop.backward(r.as_mut()))
1546 });
1547
1548 rgsw_cts_all_users_eval
1549 };
1550
1551 // RGSW x RGSW
1552 let lwe_n = self.parameters().lwe_n().0;
1553 let mut scratch_matrix = M::zeros(
1554 std::cmp::max(
1555 rgsw_by_rgsw_decomposer.a().decomposition_count(),
1556 rgsw_by_rgsw_decomposer.b().decomposition_count(),
1557 ) + (rgsw_by_rgsw_decomposer.a().decomposition_count() * 2
1558 + rgsw_by_rgsw_decomposer.b().decomposition_count() * 2),
1559 ring_size,
1560 );
1561 let rgsw_cts_untrimmed = (0..lwe_n).map(|s_index| {
1562 // copy over s_index^th rgsw ct of user 0. Use it to accumulate RGSW products of
1563 // all RGSW ciphertexts at s_index
1564 let mut rgsw_i = rgsw_cts_all_users_eval[0][s_index].clone();
1565 rgsw_i
1566 .iter_rows_mut()
1567 .for_each(|r| nttop.backward(r.as_mut()));
1568
1569 rgsw_cts_all_users_eval
1570 .iter()
1571 .skip(1)
1572 .for_each(|user_i_rgsws| {
1573 rgsw_by_rgsw_inplace(
1574 &mut rgsw_i,
1575 rgsw_by_rgsw_decomposer.a().decomposition_count(),
1576 rgsw_by_rgsw_decomposer.b().decomposition_count(),
1577 &user_i_rgsws[s_index],
1578 &rgsw_by_rgsw_decomposer,
1579 &mut scratch_matrix,
1580 nttop,
1581 rlwe_modop,
1582 );
1583 });
1584
1585 rgsw_i
1586 });
1587
1588 // After this point we don't require RGSW cts for RGSWxRGSW
1589 // multiplicaiton anymore. So we trim them to suit RLWExRGSW require for PBS
1590 let rgsw_cts = rgsw_cts_untrimmed
1591 .map(|rgsw_ct| {
1592 trim_rgsw_ct_matrix_from_rgrg_to_rlrg(
1593 rgsw_ct,
1594 self.parameters().rgsw_by_rgsw_decomposition_params(),
1595 self.parameters().rlwe_by_rgsw_decomposition_params(),
1596 )
1597 })
1598 .collect_vec();
1599 rgsw_cts
1600 };
1601
1602 // auto keys
1603 let auto_keys = {
1604 let mut auto_keys = HashMap::new();
1605 let auto_elements_dlog = self.parameters().auto_element_dlogs();
1606 for i in auto_elements_dlog.into_iter() {
1607 let mut key = M::zeros(self.parameters().auto_decomposition_count().0, ring_size);
1608
1609 key_shares.iter().for_each(|s| {
1610 let auto_key_share_i =
1611 s.auto_keys_share().get(&i).expect("Auto key {i} missing");
1612 assert!(
1613 auto_key_share_i.dimension()
1614 == (self.parameters().auto_decomposition_count().0, ring_size)
1615 );
1616 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
1617 |(partb_out, partb_share)| {
1618 rlwe_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
1619 },
1620 );
1621 });
1622
1623 auto_keys.insert(i, key);
1624 }
1625 auto_keys
1626 };
1627
1628 // LWE ksk
1629 let lwe_ksk = {
1630 let mut lwe_ksk =
1631 M::R::zeros(self.parameters().lwe_decomposition_count().0 * ring_size);
1632 key_shares.iter().for_each(|s| {
1633 assert!(
1634 s.lwe_ksk_share().as_ref().len()
1635 == self.parameters().lwe_decomposition_count().0 * ring_size
1636 );
1637 lwe_modop.elwise_add_mut(lwe_ksk.as_mut(), s.lwe_ksk_share().as_ref());
1638 });
1639 lwe_ksk
1640 };
1641
1642 SeededNonInteractiveMultiPartyServerKey::new(
1643 ui_to_s_ksks,
1644 key_order,
1645 rgsw_cts,
1646 auto_keys,
1647 lwe_ksk,
1648 cr_seed.clone(),
1649 self.parameters().clone(),
1650 )
1651 }
1652
1653 pub(super) fn non_interactive_multi_party_key_share<
1654 K: NonInteractiveMultiPartyClientKey<Element = i32>,
1655 >(
1656 &self,
1657 // TODO(Jay): Should get a common reference seed here and derive the rest.
1658 cr_seed: &NonInteractiveMultiPartyCrs<[u8; 32]>,
1659 self_index: usize,
1660 total_users: usize,
1661 client_key: &K,
1662 ) -> CommonReferenceSeededNonInteractiveMultiPartyServerKeyShare<
1663 M,
1664 NonInteractiveMultiPartyCrs<[u8; 32]>,
1665 > {
1666 assert_eq!(
1667 self.parameters().variant(),
1668 &ParameterVariant::NonInteractiveMultiParty
1669 );
1670
1671 // TODO: check whether parameters support `total_users`
1672 let nttop = self.pbs_info().nttop_rlweq();
1673 let rlwe_modop = self.pbs_info().modop_rlweq();
1674 let ring_size = self.pbs_info().rlwe_n();
1675 let rlwe_q = self.parameters().rlwe_q();
1676
1677 let sk_rlwe = client_key.sk_rlwe();
1678 let sk_u_rlwe = client_key.sk_u_rlwe();
1679 let sk_lwe = client_key.sk_lwe();
1680
1681 let (ui_to_s_ksk, zero_encs_for_others) = DefaultSecureRng::with_local_mut(|rng| {
1682 // ui_to_s_ksk
1683 let non_interactive_decomposer = self
1684 .parameters()
1685 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>(
1686 );
1687 let non_interactive_gadget_vec = non_interactive_decomposer.gadget_vector();
1688 let ui_to_s_ksk = {
1689 let mut p_rng = DefaultSecureRng::new_seeded(
1690 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(self_index),
1691 );
1692
1693 non_interactive_ksk_gen::<M, _, _, _, _, _>(
1694 &sk_rlwe,
1695 &sk_u_rlwe,
1696 &non_interactive_gadget_vec,
1697 &mut p_rng,
1698 rng,
1699 nttop,
1700 rlwe_modop,
1701 )
1702 };
1703
1704 // zero encryptions for others uj_to_s ksk
1705 let all_users_except_self = (0..total_users).filter(|x| *x != self_index);
1706 let zero_encs_for_others = all_users_except_self
1707 .map(|other_user_index| {
1708 let mut p_rng = DefaultSecureRng::new_seeded(
1709 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(other_user_index),
1710 );
1711 let zero_encs =
1712 non_interactive_ksk_zero_encryptions_for_other_party_i::<M, _, _, _, _, _>(
1713 &sk_rlwe,
1714 &non_interactive_gadget_vec,
1715 &mut p_rng,
1716 rng,
1717 nttop,
1718 rlwe_modop,
1719 );
1720 zero_encs
1721 })
1722 .collect_vec();
1723
1724 (ui_to_s_ksk, zero_encs_for_others)
1725 });
1726
1727 // Non-interactive RGSW cts = (a_i * u_j + e + \beta X^{s[i]}, a_i * s_j + e')
1728 let ni_rgsw_cts = DefaultSecureRng::with_local_mut(|rng| {
1729 let mut rgsw_cts_prng =
1730 DefaultSecureRng::new_seeded(cr_seed.rgsw_cts_seed::<DefaultSecureRng>());
1731 // generate non-interactive rgsw cts
1732 let rgsw_by_rgsw_decomposer = self
1733 .parameters()
1734 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1735
1736 let ni_rgrg_gadget_vec = {
1737 if rgsw_by_rgsw_decomposer.a().decomposition_count()
1738 > rgsw_by_rgsw_decomposer.b().decomposition_count()
1739 {
1740 rgsw_by_rgsw_decomposer.a().gadget_vector()
1741 } else {
1742 rgsw_by_rgsw_decomposer.b().gadget_vector()
1743 }
1744 };
1745 let ni_rgsw_cts: (Vec<M>, Vec<M>) = sk_lwe
1746 .iter()
1747 .map(|s_i| {
1748 // X^{s[i]}
1749 let mut m = M::R::zeros(ring_size);
1750 let s_i = s_i * (self.pbs_info().embedding_factor() as i32);
1751 if s_i < 0 {
1752 // X^{-s[i]} -> -X^{N+s[i]}
1753 m.as_mut()[ring_size - (s_i.abs() as usize)] = rlwe_q.neg_one();
1754 } else {
1755 m.as_mut()[s_i as usize] = M::MatElement::one();
1756 }
1757
1758 non_interactive_rgsw_ct::<M, _, _, _, _, _>(
1759 &sk_rlwe,
1760 &sk_u_rlwe,
1761 m.as_ref(),
1762 &ni_rgrg_gadget_vec,
1763 &mut rgsw_cts_prng,
1764 rng,
1765 nttop,
1766 rlwe_modop,
1767 )
1768 })
1769 .unzip();
1770 ni_rgsw_cts
1771 });
1772
1773 // Auto key share
1774 let auto_keys_share = {
1775 let auto_seed = cr_seed.auto_keys_cts_seed::<DefaultSecureRng>();
1776 self._common_rountine_multi_party_auto_keys_share_gen(auto_seed, &sk_rlwe)
1777 };
1778
1779 // Lwe Ksk share
1780 let lwe_ksk_share = {
1781 let lwe_ksk_seed = cr_seed.lwe_ksk_cts_seed::<DefaultSecureRng>();
1782 self._common_rountine_multi_party_lwe_ksk_share_gen(lwe_ksk_seed, &sk_rlwe, &sk_lwe)
1783 };
1784
1785 CommonReferenceSeededNonInteractiveMultiPartyServerKeyShare::new(
1786 ni_rgsw_cts,
1787 ui_to_s_ksk,
1788 zero_encs_for_others,
1789 auto_keys_share,
1790 lwe_ksk_share,
1791 self_index,
1792 cr_seed.clone(),
1793 )
1794 }
1795
1796 fn _common_rountine_multi_party_auto_keys_share_gen(
1797 &self,
1798 auto_seed: <DefaultSecureRng as NewWithSeed>::Seed,
1799 sk_rlwe: &[i32],
1800 ) -> HashMap<usize, M> {
1801 let g = self.pbs_info.parameters.g();
1802 let ring_size = self.pbs_info.parameters.rlwe_n().0;
1803 let br_q = self.pbs_info.parameters.br_q();
1804 let rlweq_modop = &self.pbs_info.rlwe_modop;
1805 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1806
1807 DefaultSecureRng::with_local_mut(|rng| {
1808 let mut p_rng = DefaultSecureRng::new_seeded(auto_seed);
1809
1810 let mut auto_keys = HashMap::new();
1811 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
1812 let auto_element_dlogs = self.pbs_info.parameters.auto_element_dlogs();
1813
1814 for i in auto_element_dlogs.into_iter() {
1815 let g_pow = if i == 0 {
1816 -(g as isize)
1817 } else {
1818 (g.pow(i as u32) % br_q) as isize
1819 };
1820
1821 let mut ksk_out = M::zeros(
1822 self.pbs_info.auto_decomposer.decomposition_count(),
1823 ring_size,
1824 );
1825 galois_key_gen(
1826 &mut ksk_out,
1827 sk_rlwe,
1828 g_pow,
1829 &auto_gadget,
1830 rlweq_modop,
1831 rlweq_nttop,
1832 &mut p_rng,
1833 rng,
1834 );
1835 auto_keys.insert(i, ksk_out);
1836 }
1837
1838 auto_keys
1839 })
1840 }
1841
1842 fn _common_rountine_multi_party_lwe_ksk_share_gen(
1843 &self,
1844 lwe_ksk_seed: <DefaultSecureRng as NewWithSeed>::Seed,
1845 sk_rlwe: &[i32],
1846 sk_lwe: &[i32],
1847 ) -> M::R {
1848 DefaultSecureRng::with_local_mut(|rng| {
1849 let mut p_rng = DefaultSecureRng::new_seeded(lwe_ksk_seed);
1850 let mut lwe_ksk = M::R::zeros(
1851 self.pbs_info.lwe_decomposer.decomposition_count() * self.parameters().rlwe_n().0,
1852 );
1853 let lwe_modop = &self.pbs_info.lwe_modop;
1854 let d_lwe_gadget_vec = self.pbs_info.lwe_decomposer.gadget_vector();
1855 lwe_ksk_keygen(
1856 sk_rlwe,
1857 sk_lwe,
1858 &mut lwe_ksk,
1859 &d_lwe_gadget_vec,
1860 lwe_modop,
1861 &mut p_rng,
1862 rng,
1863 );
1864 lwe_ksk
1865 })
1866 }
1867
1868 pub(super) fn multi_party_public_key_share<K: InteractiveMultiPartyClientKey<Element = i32>>(
1869 &self,
1870 cr_seed: &MultiPartyCrs<[u8; 32]>,
1871 client_key: &K,
1872 ) -> CommonReferenceSeededCollectivePublicKeyShare<
1873 <M as Matrix>::R,
1874 [u8; 32],
1875 BoolParameters<<M as Matrix>::MatElement>,
1876 > {
1877 DefaultSecureRng::with_local_mut(|rng| {
1878 let mut share_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0);
1879 let modop = &self.pbs_info.rlwe_modop;
1880 let nttop = &self.pbs_info.rlwe_nttop;
1881 let pk_seed = cr_seed.public_key_share_seed::<DefaultSecureRng>();
1882 let mut main_prng = DefaultSecureRng::new_seeded(pk_seed);
1883 public_key_share(
1884 &mut share_out,
1885 &client_key.sk_rlwe(),
1886 modop,
1887 nttop,
1888 &mut main_prng,
1889 rng,
1890 );
1891 CommonReferenceSeededCollectivePublicKeyShare::new(
1892 share_out,
1893 pk_seed,
1894 self.pbs_info.parameters.clone(),
1895 )
1896 })
1897 }
1898
1899 pub(super) fn multi_party_decryption_share<K: InteractiveMultiPartyClientKey<Element = i32>>(
1900 &self,
1901 lwe_ct: &M::R,
1902 client_key: &K,
1903 ) -> <M as Matrix>::MatElement {
1904 assert!(lwe_ct.as_ref().len() == self.pbs_info.parameters.rlwe_n().0 + 1);
1905 let modop = &self.pbs_info.rlwe_modop;
1906 let mut neg_s =
1907 M::R::try_convert_from(&client_key.sk_rlwe(), &self.pbs_info.parameters.rlwe_q());
1908 modop.elwise_neg_mut(neg_s.as_mut());
1909
1910 let mut neg_sa = M::MatElement::zero();
1911 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
1912 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
1913 });
1914
1915 let e = DefaultSecureRng::with_local_mut(|rng| {
1916 let mut e =
1917 RandomGaussianElementInModulus::random(rng, self.pbs_info.parameters.rlwe_q());
1918 e
1919 });
1920 let share = modop.add(&neg_sa, &e);
1921
1922 share
1923 }
1924
1925 pub(crate) fn multi_party_decrypt(&self, shares: &[M::MatElement], lwe_ct: &M::R) -> bool {
1926 let modop = &self.pbs_info.rlwe_modop;
1927 let mut sum_a = M::MatElement::zero();
1928 shares
1929 .iter()
1930 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i));
1931
1932 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
1933 self.pbs_info.parameters.rlwe_q().decode(encoded_m)
1934 }
1935
1936 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
1937 self.pk_encrypt_batched(pk, &vec![m]).remove(0)
1938 }
1939
1940 /// Encrypts a batch booleans as multiple LWE ciphertexts.
1941 ///
1942 /// For public key encryption we first encrypt `m` as a RLWE ciphertext and
1943 /// then sample extract LWE samples at required indices.
1944 ///
1945 /// - TODO(Jay:) Communication can be improved by not sample exctracting and
1946 /// instead just truncate degree 0 values (part Bs)
1947 pub(crate) fn pk_encrypt_batched(&self, pk: &M, m: &[bool]) -> Vec<M::R> {
1948 DefaultSecureRng::with_local_mut(|rng| {
1949 let ring_size = self.pbs_info.parameters.rlwe_n().0;
1950 assert!(
1951 m.len() <= ring_size,
1952 "Cannot batch encrypt > ring_size{ring_size} elements at once"
1953 );
1954
1955 let modop = &self.pbs_info.rlwe_modop;
1956 let nttop = &self.pbs_info.rlwe_nttop;
1957
1958 // RLWE(0)
1959 // sample ephemeral key u
1960 let mut u = vec![0i32; ring_size];
1961 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1962 let mut u = M::R::try_convert_from(&u, &self.pbs_info.parameters.rlwe_q());
1963 nttop.forward(u.as_mut());
1964
1965 let mut ua = M::R::zeros(ring_size);
1966 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1967 let mut ub = M::R::zeros(ring_size);
1968 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1969
1970 // a*u
1971 nttop.forward(ua.as_mut());
1972 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
1973 nttop.backward(ua.as_mut());
1974
1975 // b*u
1976 nttop.forward(ub.as_mut());
1977 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
1978 nttop.backward(ub.as_mut());
1979
1980 let mut rlwe = M::zeros(2, ring_size);
1981 // sample error
1982 rlwe.iter_rows_mut().for_each(|ri| {
1983 RandomFillGaussianInModulus::<[M::MatElement], CiphertextModulus<M::MatElement>>::random_fill(
1984 rng,
1985 &self.pbs_info.parameters.rlwe_q(),
1986 ri.as_mut(),
1987 );
1988 });
1989
1990 // a*u + e0
1991 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
1992 // b*u + e1
1993 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
1994
1995 //FIXME(Jay): Figure out a way to get Q/8 form modulus
1996 let mut m_vec = M::R::zeros(ring_size);
1997 izip!(m_vec.as_mut().iter_mut(), m.iter()).for_each(|(m_el, m_bool)| {
1998 if *m_bool {
1999 // Q/8
2000 *m_el = self.pbs_info.rlwe_q().true_el()
2001 } else {
2002 // -Q/8
2003 *m_el = self.pbs_info.rlwe_q().false_el()
2004 }
2005 });
2006
2007 // b*u + e1 + m
2008 modop.elwise_add_mut(rlwe.get_row_mut(1), m_vec.as_ref());
2009 // rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
2010
2011 // sample extract index required indices
2012 let samples = m.len();
2013 (0..samples)
2014 .into_iter()
2015 .map(|i| {
2016 let mut lwe_out = M::R::zeros(ring_size + 1);
2017 sample_extract(&mut lwe_out, &rlwe, modop, i);
2018 lwe_out
2019 })
2020 .collect_vec()
2021 })
2022 }
2023
2024 /// TODO(Jay): Fetch client key from thread local
2025 pub fn sk_encrypt<K: SinglePartyClientKey<Element = i32>>(
2026 &self,
2027 m: bool,
2028 client_key: &K,
2029 ) -> M::R {
2030 //FIXME(Jay): Figure out a way to get Q/8 form modulus
2031 let m = if m {
2032 // Q/8
2033 self.pbs_info.rlwe_q().true_el()
2034 } else {
2035 // -Q/8
2036 self.pbs_info.rlwe_q().false_el()
2037 };
2038
2039 DefaultSecureRng::with_local_mut(|rng| {
2040 let mut lwe_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0 + 1);
2041 encrypt_lwe(
2042 &mut lwe_out,
2043 &m,
2044 &client_key.sk_rlwe(),
2045 &self.pbs_info.rlwe_modop,
2046 rng,
2047 );
2048 lwe_out
2049 })
2050 }
2051
2052 pub fn sk_decrypt<K: SinglePartyClientKey<Element = i32>>(
2053 &self,
2054 lwe_ct: &M::R,
2055 client_key: &K,
2056 ) -> bool {
2057 let m = decrypt_lwe(lwe_ct, &client_key.sk_rlwe(), &self.pbs_info.rlwe_modop);
2058 self.pbs_info.rlwe_q().decode(m)
2059 }
2060}
2061
2062impl<M, NttOp, RlweModOp, LweModOp, Skey> BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
2063where
2064 M: MatrixMut + MatrixEntity,
2065 M::R: RowMut + RowEntity,
2066 M::MatElement: PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo,
2067 RlweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
2068 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
2069 NttOp: Ntt<Element = M::MatElement>,
2070{
2071 /// Returns c0 + c1 + Q/4
2072 fn _add_and_shift_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
2073 let modop = &self.pbs_info.rlwe_modop;
2074 modop.elwise_add_mut(c0.as_mut(), c1.as_ref());
2075 // +Q/4
2076 c0.as_mut()[0] = modop.add(&c0.as_ref()[0], &self.pbs_info.rlwe_qby4);
2077 }
2078
2079 /// Returns 2(c0 - c1) + Q/4
2080 fn _subtract_double_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
2081 let modop = &self.pbs_info.rlwe_modop;
2082 // c0 - c1
2083 modop.elwise_sub_mut(c0.as_mut(), c1.as_ref());
2084
2085 // double
2086 c0.as_mut().iter_mut().for_each(|v| *v = modop.add(v, v));
2087 }
2088}
2089
2090impl<M, NttOp, RlweModOp, LweModOp, Skey> BooleanGates
2091 for BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
2092where
2093 M: MatrixMut + MatrixEntity,
2094 M::R: RowMut + RowEntity + Clone,
2095 M::MatElement: PrimInt
2096 + FromPrimitive
2097 + One
2098 + Copy
2099 + Zero
2100 + Display
2101 + WrappingSub
2102 + NumInfo
2103 + From<bool>
2104 + WrappingAdd
2105 + Debug,
2106 RlweModOp: VectorOps<Element = M::MatElement>
2107 + ArithmeticOps<Element = M::MatElement>
2108 + ShoupMatrixFMA<M::R>,
2109 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
2110 NttOp: Ntt<Element = M::MatElement>,
2111 Skey: PbsKey<AutoKey = <Skey as PbsKey>::RgswCt, LweKskKey = M>,
2112 <Skey as PbsKey>::RgswCt: WithShoupRepr<M = M>,
2113{
2114 type Ciphertext = M::R;
2115 type Key = Skey;
2116
2117 fn nand_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2118 self._add_and_shift_lwe_cts(c0, c1);
2119
2120 // PBS
2121 pbs(
2122 &self.pbs_info,
2123 &self.nand_test_vec,
2124 c0,
2125 server_key,
2126 &mut self.scratch_memory.lwe_vector,
2127 &mut self.scratch_memory.decomposition_matrix,
2128 );
2129 }
2130
2131 fn and_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2132 self._add_and_shift_lwe_cts(c0, c1);
2133
2134 // PBS
2135 pbs(
2136 &self.pbs_info,
2137 &self.and_test_vec,
2138 c0,
2139 server_key,
2140 &mut self.scratch_memory.lwe_vector,
2141 &mut self.scratch_memory.decomposition_matrix,
2142 );
2143 }
2144
2145 fn or_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2146 self._add_and_shift_lwe_cts(c0, c1);
2147
2148 // PBS
2149 pbs(
2150 &self.pbs_info,
2151 &self.or_test_vec,
2152 c0,
2153 server_key,
2154 &mut self.scratch_memory.lwe_vector,
2155 &mut self.scratch_memory.decomposition_matrix,
2156 );
2157 }
2158
2159 fn nor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2160 self._add_and_shift_lwe_cts(c0, c1);
2161
2162 // PBS
2163 pbs(
2164 &self.pbs_info,
2165 &self.nor_test_vec,
2166 c0,
2167 server_key,
2168 &mut self.scratch_memory.lwe_vector,
2169 &mut self.scratch_memory.decomposition_matrix,
2170 )
2171 }
2172
2173 fn xor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2174 self._subtract_double_lwe_cts(c0, c1);
2175
2176 // PBS
2177 pbs(
2178 &self.pbs_info,
2179 &self.xor_test_vec,
2180 c0,
2181 server_key,
2182 &mut self.scratch_memory.lwe_vector,
2183 &mut self.scratch_memory.decomposition_matrix,
2184 );
2185 }
2186
2187 fn xnor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2188 self._subtract_double_lwe_cts(c0, c1);
2189
2190 // PBS
2191 pbs(
2192 &self.pbs_info,
2193 &self.xnor_test_vec,
2194 c0,
2195 server_key,
2196 &mut self.scratch_memory.lwe_vector,
2197 &mut self.scratch_memory.decomposition_matrix,
2198 );
2199 }
2200
2201 fn not_inplace(&mut self, c0: &mut M::R) {
2202 let modop = &self.pbs_info.rlwe_modop;
2203 c0.as_mut().iter_mut().for_each(|v| *v = modop.neg(v));
2204 }
2205
2206 fn and(
2207 &mut self,
2208 c0: &Self::Ciphertext,
2209 c1: &Self::Ciphertext,
2210 key: &Self::Key,
2211 ) -> Self::Ciphertext {
2212 let mut out = c0.clone();
2213 self.and_inplace(&mut out, c1, key);
2214 out
2215 }
2216
2217 fn nand(
2218 &mut self,
2219 c0: &Self::Ciphertext,
2220 c1: &Self::Ciphertext,
2221 key: &Self::Key,
2222 ) -> Self::Ciphertext {
2223 let mut out = c0.clone();
2224 self.nand_inplace(&mut out, c1, key);
2225 out
2226 }
2227
2228 fn or(
2229 &mut self,
2230 c0: &Self::Ciphertext,
2231 c1: &Self::Ciphertext,
2232 key: &Self::Key,
2233 ) -> Self::Ciphertext {
2234 let mut out = c0.clone();
2235 self.or_inplace(&mut out, c1, key);
2236 out
2237 }
2238
2239 fn nor(
2240 &mut self,
2241 c0: &Self::Ciphertext,
2242 c1: &Self::Ciphertext,
2243 key: &Self::Key,
2244 ) -> Self::Ciphertext {
2245 let mut out = c0.clone();
2246 self.nor_inplace(&mut out, c1, key);
2247 out
2248 }
2249
2250 fn xnor(
2251 &mut self,
2252 c0: &Self::Ciphertext,
2253 c1: &Self::Ciphertext,
2254 key: &Self::Key,
2255 ) -> Self::Ciphertext {
2256 let mut out = c0.clone();
2257 self.xnor_inplace(&mut out, c1, key);
2258 out
2259 }
2260
2261 fn xor(
2262 &mut self,
2263 c0: &Self::Ciphertext,
2264 c1: &Self::Ciphertext,
2265 key: &Self::Key,
2266 ) -> Self::Ciphertext {
2267 let mut out = c0.clone();
2268 self.xor_inplace(&mut out, c1, key);
2269 out
2270 }
2271
2272 fn not(&mut self, c: &Self::Ciphertext) -> Self::Ciphertext {
2273 let mut out = c.clone();
2274 self.not_inplace(&mut out);
2275 out
2276 }
2277}
2278
2279#[cfg(test)]
2280mod tests {
2281
2282 use rand::{thread_rng, Rng};
2283 use rand_distr::Uniform;
2284
2285 use crate::{
2286 backend::ModulusPowerOf2,
2287 bool::{
2288 keys::{
2289 NonInteractiveServerKeyEvaluationDomain, PublicKey,
2290 ShoupNonInteractiveServerKeyEvaluationDomain,
2291 },
2292 parameters::{
2293 MP_BOOL_PARAMS, NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS, SMALL_MP_BOOL_PARAMS,
2294 SP_TEST_BOOL_PARAMS,
2295 },
2296 },
2297 evaluator,
2298 ntt::NttBackendU64,
2299 parameters::OPTIMISED_SMALL_MP_BOOL_PARAMS,
2300 random::{RandomElementInModulus, DEFAULT_RNG},
2301 rgsw::{
2302 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
2303 tests::{_measure_noise_rgsw, _sk_encrypt_rlwe},
2304 RgswCiphertext, RgswCiphertextEvaluationDomain, SeededRgswCiphertext,
2305 SeededRlweCiphertext,
2306 },
2307 utils::{negacyclic_mul, tests::Stats},
2308 };
2309
2310 use super::*;
2311
2312 #[test]
2313 fn testtest() {
2314 let evaluator = BoolEvaluator::<
2315 Vec<Vec<u64>>,
2316 NttBackendU64,
2317 ModularOpsU64<CiphertextModulus<u64>>,
2318 ModulusPowerOf2<CiphertextModulus<u64>>,
2319 ShoupNonInteractiveServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2320 >::new(NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS);
2321 let mp_seed = NonInteractiveMultiPartyCrs { seed: [1u8; 32] };
2322
2323 let ring_size = evaluator.parameters().rlwe_n().0;
2324 let rlwe_q = evaluator.parameters().rlwe_q();
2325 let rlwe_modop = evaluator.pbs_info().modop_rlweq();
2326 let nttop = evaluator.pbs_info().nttop_rlweq();
2327
2328 let parties = 2;
2329
2330 let cks = (0..parties).map(|_| evaluator.client_key()).collect_vec();
2331
2332 let key_shares = (0..parties)
2333 .map(|i| evaluator.non_interactive_multi_party_key_share(&mp_seed, i, parties, &cks[i]))
2334 .collect_vec();
2335 // dbg!(key_shares[1].user_index);
2336
2337 let seeded_server_key = evaluator.aggregate_non_interactive_multi_party_key_share(
2338 &mp_seed,
2339 parties,
2340 &key_shares,
2341 );
2342 let server_key_evaluation_domain =
2343 NonInteractiveServerKeyEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
2344 &seeded_server_key,
2345 );
2346
2347 let mut ideal_rlwe = vec![0; ring_size];
2348 cks.iter().for_each(|k| {
2349 izip!(
2350 ideal_rlwe.iter_mut(),
2351 NonInteractiveMultiPartyClientKey::sk_rlwe(k).iter()
2352 )
2353 .for_each(|(a, b)| {
2354 *a = *a + b;
2355 });
2356 });
2357
2358 let mut ideal_lwe = vec![0; evaluator.parameters().lwe_n().0];
2359 cks.iter().for_each(|k| {
2360 izip!(
2361 ideal_lwe.iter_mut(),
2362 NonInteractiveMultiPartyClientKey::sk_lwe(k).iter()
2363 )
2364 .for_each(|(a, b)| {
2365 *a = *a + b;
2366 });
2367 });
2368
2369 let mut stats = Stats::new();
2370
2371 {
2372 let (rlrg_decomp_a, rlrg_decomp_b) = evaluator
2373 .parameters()
2374 .rlwe_rgsw_decomposer::<DefaultDecomposer<u64>>();
2375 let gadget_vec_a = rlrg_decomp_a.gadget_vector();
2376 let gadget_vec_b = rlrg_decomp_b.gadget_vector();
2377 let d_a = rlrg_decomp_a.decomposition_count();
2378 let d_b = rlrg_decomp_b.decomposition_count();
2379
2380 // s[X]
2381 let s_poly = Vec::<u64>::try_convert_from(ideal_rlwe.as_slice(), rlwe_q);
2382
2383 // -s[X]
2384 let mut neg_s_poly_eval = s_poly.clone();
2385 rlwe_modop.elwise_neg_mut(&mut neg_s_poly_eval);
2386 nttop.forward(neg_s_poly_eval.as_mut());
2387
2388 server_key_evaluation_domain
2389 .rgsw_cts()
2390 .iter()
2391 .enumerate()
2392 .for_each(|(s_index, ct)| {
2393 // X^{lwe_s[i]}
2394 let mut m = vec![0u64; ring_size];
2395 let s_i = ideal_lwe[s_index] * (evaluator.pbs_info().embedding_factor() as i32);
2396 if s_i < 0 {
2397 m[ring_size - (s_i.abs() as usize)] = rlwe_q.neg_one();
2398 } else {
2399 m[(s_i as usize)] = 1;
2400 }
2401
2402 let mut neg_sm = m.clone();
2403 nttop.forward(&mut neg_sm);
2404 rlwe_modop.elwise_mul_mut(&mut neg_sm, &neg_s_poly_eval);
2405 nttop.backward(&mut neg_sm);
2406
2407 // RLWE'(-sm)
2408 gadget_vec_a.iter().enumerate().for_each(|(index, beta)| {
2409 // RLWE(\beta -sm)
2410
2411 // \beta * -sX^[lwe_s[i]]
2412 let mut beta_neg_sm = neg_sm.clone();
2413 rlwe_modop.elwise_scalar_mul_mut(&mut beta_neg_sm, beta);
2414
2415 // extract RLWE(-sm \beta)
2416 let mut rlwe = vec![vec![0u64; ring_size]; 2];
2417 rlwe[0].copy_from_slice(&ct[index]);
2418 rlwe[1].copy_from_slice(&ct[index + d_a]);
2419 // send back to coefficient domain
2420 rlwe.iter_rows_mut()
2421 .for_each(|r| nttop.backward(r.as_mut_slice()));
2422
2423 // decrypt
2424 let mut m_out = vec![0u64; ring_size];
2425 decrypt_rlwe(&rlwe, &ideal_rlwe, &mut m_out, nttop, rlwe_modop); // println!("{:?}", &beta_neg_sm);
2426
2427 let mut diff = m_out;
2428 rlwe_modop.elwise_sub_mut(&mut diff, &beta_neg_sm);
2429
2430 stats.add_more(&Vec::<i64>::try_convert_from(&diff, rlwe_q));
2431 });
2432 });
2433 }
2434 println!("Stats: {}", stats.std_dev().abs().log2());
2435 }
2436
2437}