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