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