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