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, RandomGaussianElementInModulus,
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!(self.parameters().variant(), &ParameterVariant::MultiParty);
914 assert!(user_id < total_users);
915
916 let sk_rlwe = client_key.sk_rlwe();
917 let sk_lwe = client_key.sk_lwe();
918
919 let g = self.pbs_info.parameters.g();
920 let ring_size = self.pbs_info.parameters.rlwe_n().0;
921 let rlwe_q = self.pbs_info.parameters.rlwe_q();
922 let lwe_q = self.pbs_info.parameters.lwe_q();
923
924 let rlweq_modop = &self.pbs_info.rlwe_modop;
925 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
926
927 // sanity check
928 assert!(sk_rlwe.len() == ring_size);
929 assert!(sk_lwe.len() == self.pbs_info.parameters.lwe_n().0);
930
931 // auto keys
932 let auto_keys = self._common_rountine_multi_party_auto_keys_share_gen(
933 cr_seed.auto_keys_cts_seed::<DefaultSecureRng>(),
934 &sk_rlwe,
935 );
936
937 // rgsw ciphertexts of lwe secret elements
938 let (self_leader_rgsws, not_self_leader_rgsws) = DefaultSecureRng::with_local_mut(|rng| {
939 let mut self_leader_rgsw = vec![];
940 let mut not_self_leader_rgsws = vec![];
941
942 let (segment_start, segment_end) =
943 multi_party_user_id_lwe_segment(user_id, total_users, self.pbs_info().lwe_n());
944
945 // self LWE secret indices
946 {
947 // LWE secret indices for which user is the leader they need to send RGSW(m) for
948 // RLWE x RGSW multiplication
949 let rlrg_decomposer = self.pbs_info().rlwe_rgsw_decomposer();
950 let (rlrg_d_a, rlrg_d_b) = (
951 rlrg_decomposer.a().decomposition_count(),
952 rlrg_decomposer.b().decomposition_count(),
953 );
954 let (gadget_a, gadget_b) = (
955 rlrg_decomposer.a().gadget_vector(),
956 rlrg_decomposer.b().gadget_vector(),
957 );
958 for s_index in segment_start..segment_end {
959 let mut out_rgsw = M::zeros(rlrg_d_a.0 * 2 + rlrg_d_b.0 * 2, ring_size);
960 public_key_encrypt_rgsw(
961 &mut out_rgsw,
962 &encode_x_pow_si_with_emebedding_factor::<
963 M::R,
964 CiphertextModulus<M::MatElement>,
965 >(
966 sk_lwe[s_index],
967 self.pbs_info().embedding_factor(),
968 ring_size,
969 self.pbs_info().rlwe_q(),
970 )
971 .as_ref(),
972 collective_pk,
973 &gadget_a,
974 &gadget_b,
975 rlweq_modop,
976 rlweq_nttop,
977 rng,
978 );
979 self_leader_rgsw.push(out_rgsw);
980 }
981 }
982
983 // not self LWE secret indices
984 {
985 // LWE secret indices for which user isn't the leader, they need to send RGSW(m)
986 // for RGSW x RGSW multiplcation
987 let rgsw_rgsw_decomposer = self
988 .pbs_info
989 .parameters
990 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
991 let (rgrg_d_a, rgrg_d_b) = (
992 rgsw_rgsw_decomposer.a().decomposition_count(),
993 rgsw_rgsw_decomposer.b().decomposition_count(),
994 );
995 let (rgrg_gadget_a, rgrg_gadget_b) = (
996 rgsw_rgsw_decomposer.a().gadget_vector(),
997 rgsw_rgsw_decomposer.b().gadget_vector(),
998 );
999
1000 for s_index in (0..segment_start).chain(segment_end..self.parameters().lwe_n().0) {
1001 let mut out_rgsw = M::zeros(rgrg_d_a.0 * 2 + rgrg_d_b.0 * 2, ring_size);
1002 public_key_encrypt_rgsw(
1003 &mut out_rgsw,
1004 &encode_x_pow_si_with_emebedding_factor::<
1005 M::R,
1006 CiphertextModulus<M::MatElement>,
1007 >(
1008 sk_lwe[s_index],
1009 self.pbs_info().embedding_factor(),
1010 ring_size,
1011 self.pbs_info().rlwe_q(),
1012 )
1013 .as_ref(),
1014 collective_pk,
1015 &rgrg_gadget_a,
1016 &rgrg_gadget_b,
1017 rlweq_modop,
1018 rlweq_nttop,
1019 rng,
1020 );
1021
1022 not_self_leader_rgsws.push(out_rgsw);
1023 }
1024 }
1025
1026 (self_leader_rgsw, not_self_leader_rgsws)
1027 });
1028
1029 // LWE Ksk
1030 let lwe_ksk = self._common_rountine_multi_party_lwe_ksk_share_gen(
1031 cr_seed.lwe_ksk_cts_seed_seed::<DefaultSecureRng>(),
1032 &sk_rlwe,
1033 &sk_lwe,
1034 );
1035
1036 CommonReferenceSeededInteractiveMultiPartyServerKeyShare::new(
1037 self_leader_rgsws,
1038 not_self_leader_rgsws,
1039 auto_keys,
1040 lwe_ksk,
1041 cr_seed.clone(),
1042 self.pbs_info.parameters.clone(),
1043 user_id,
1044 )
1045 }
1046
1047 pub(super) fn aggregate_interactive_multi_party_server_key_shares<S>(
1048 &self,
1049 shares: &[CommonReferenceSeededInteractiveMultiPartyServerKeyShare<
1050 M,
1051 BoolParameters<M::MatElement>,
1052 InteractiveMultiPartyCrs<S>,
1053 >],
1054 ) -> SeededInteractiveMultiPartyServerKey<
1055 M,
1056 InteractiveMultiPartyCrs<S>,
1057 BoolParameters<M::MatElement>,
1058 >
1059 where
1060 S: PartialEq + Clone,
1061 M: Clone,
1062 {
1063 assert_eq!(self.parameters().variant(), &ParameterVariant::MultiParty);
1064 assert!(shares.len() > 0);
1065
1066 let total_users = shares.len();
1067
1068 let parameters = shares[0].parameters().clone();
1069 let cr_seed = shares[0].cr_seed();
1070
1071 let rlwe_n = parameters.rlwe_n().0;
1072
1073 // sanity checks
1074 shares.iter().skip(1).for_each(|s| {
1075 assert!(s.parameters() == ¶meters);
1076 assert!(s.cr_seed() == cr_seed);
1077 });
1078
1079 let rlweq_modop = &self.pbs_info.rlwe_modop;
1080 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1081
1082 // auto keys
1083 let mut auto_keys = HashMap::new();
1084 let auto_elements_dlog = parameters.auto_element_dlogs();
1085 for i in auto_elements_dlog.into_iter() {
1086 let mut key = M::zeros(parameters.auto_decomposition_count().0, rlwe_n);
1087
1088 shares.iter().for_each(|s| {
1089 let auto_key_share_i = s.auto_keys().get(&i).expect("Auto key {i} missing");
1090 assert!(
1091 auto_key_share_i.dimension()
1092 == (parameters.auto_decomposition_count().0, rlwe_n)
1093 );
1094 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
1095 |(partb_out, partb_share)| {
1096 rlweq_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
1097 },
1098 );
1099 });
1100
1101 auto_keys.insert(i, key);
1102 }
1103
1104 // rgsw ciphertext (most expensive part!)
1105 let rgsw_cts = {
1106 let rgsw_x_rgsw_decomposer =
1107 parameters.rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1108 let rlwe_x_rgsw_decomposer = self.pbs_info().rlwe_rgsw_decomposer();
1109 let rgsw_x_rgsw_dimension = (
1110 rgsw_x_rgsw_decomposer.a().decomposition_count().0 * 2
1111 + rgsw_x_rgsw_decomposer.b().decomposition_count().0 * 2,
1112 rlwe_n,
1113 );
1114 let rlwe_x_rgsw_dimension = (
1115 rlwe_x_rgsw_decomposer.a().decomposition_count().0 * 2
1116 + rlwe_x_rgsw_decomposer.b().decomposition_count().0 * 2,
1117 rlwe_n,
1118 );
1119
1120 let mut rgsw_x_rgsw_scratch = M::zeros(
1121 rgsw_x_rgsw_scratch_rows(rlwe_x_rgsw_decomposer, &rgsw_x_rgsw_decomposer),
1122 rlwe_n,
1123 );
1124
1125 let shares_in_correct_order = (0..total_users)
1126 .map(|i| shares.iter().find(|s| s.user_id() == i).unwrap())
1127 .collect_vec();
1128
1129 let lwe_n = self.parameters().lwe_n().0;
1130 let (users_segments, users_segments_sizes): (Vec<(usize, usize)>, Vec<usize>) = (0
1131 ..total_users)
1132 .map(|(user_id)| {
1133 let (start_index, end_index) =
1134 multi_party_user_id_lwe_segment(user_id, total_users, lwe_n);
1135 ((start_index, end_index), end_index - start_index)
1136 })
1137 .unzip();
1138
1139 let mut rgsw_cts = Vec::with_capacity(lwe_n);
1140 users_segments
1141 .iter()
1142 .enumerate()
1143 .for_each(|(user_id, user_segment)| {
1144 let share = shares_in_correct_order[user_id];
1145 for secret_index in user_segment.0..user_segment.1 {
1146 let mut rgsw_i =
1147 share.self_leader_rgsws()[secret_index - user_segment.0].clone();
1148 // assert already exists in RGSW x RGSW rountine
1149 assert!(rgsw_i.dimension() == rlwe_x_rgsw_dimension);
1150
1151 // multiply leader's RGSW ct at `secret_index` with RGSW cts of other users
1152 // for lwe index `secret_index`
1153 (0..total_users)
1154 .filter(|i| i != &user_id)
1155 .for_each(|other_user_id| {
1156 let mut offset = 0;
1157 if other_user_id < user_id {
1158 offset = users_segments_sizes[other_user_id];
1159 }
1160
1161 let mut other_rgsw_i = shares_in_correct_order[other_user_id]
1162 .not_self_leader_rgsws()
1163 [secret_index.checked_sub(offset).unwrap()]
1164 .clone();
1165 // assert already exists in RGSW x RGSW rountine
1166 assert!(other_rgsw_i.dimension() == rgsw_x_rgsw_dimension);
1167
1168 // send to evaluation domain for RGSwxRGSW mul
1169 other_rgsw_i
1170 .iter_rows_mut()
1171 .for_each(|r| rlweq_nttop.forward(r.as_mut()));
1172
1173 rgsw_by_rgsw_inplace(
1174 &mut RgswCiphertextMutRef::new(
1175 rgsw_i.as_mut(),
1176 rlwe_x_rgsw_decomposer.a().decomposition_count().0,
1177 rlwe_x_rgsw_decomposer.b().decomposition_count().0,
1178 ),
1179 &RgswCiphertextRef::new(
1180 other_rgsw_i.as_ref(),
1181 rgsw_x_rgsw_decomposer.a().decomposition_count().0,
1182 rgsw_x_rgsw_decomposer.b().decomposition_count().0,
1183 ),
1184 rlwe_x_rgsw_decomposer,
1185 &rgsw_x_rgsw_decomposer,
1186 &mut RuntimeScratchMutRef::new(rgsw_x_rgsw_scratch.as_mut()),
1187 rlweq_nttop,
1188 rlweq_modop,
1189 );
1190 });
1191
1192 rgsw_cts.push(rgsw_i);
1193 }
1194 });
1195
1196 rgsw_cts
1197 };
1198
1199 // LWE ksks
1200 let mut lwe_ksk = M::R::zeros(rlwe_n * parameters.lwe_decomposition_count().0);
1201 let lweq_modop = &self.pbs_info.lwe_modop;
1202 shares.iter().for_each(|si| {
1203 assert!(si.lwe_ksk().as_ref().len() == rlwe_n * parameters.lwe_decomposition_count().0);
1204 lweq_modop.elwise_add_mut(lwe_ksk.as_mut(), si.lwe_ksk().as_ref())
1205 });
1206
1207 SeededInteractiveMultiPartyServerKey::new(
1208 rgsw_cts,
1209 auto_keys,
1210 lwe_ksk,
1211 cr_seed.clone(),
1212 parameters,
1213 )
1214 }
1215
1216 pub(super) fn aggregate_non_interactive_multi_party_server_key_shares(
1217 &self,
1218 cr_seed: &NonInteractiveMultiPartyCrs<[u8; 32]>,
1219 key_shares: &[CommonReferenceSeededNonInteractiveMultiPartyServerKeyShare<
1220 M,
1221 BoolParameters<M::MatElement>,
1222 NonInteractiveMultiPartyCrs<[u8; 32]>,
1223 >],
1224 ) -> SeededNonInteractiveMultiPartyServerKey<
1225 M,
1226 NonInteractiveMultiPartyCrs<[u8; 32]>,
1227 BoolParameters<M::MatElement>,
1228 >
1229 where
1230 M: Clone + Debug,
1231 <M as Matrix>::R: RowMut + Clone,
1232 {
1233 assert_eq!(
1234 self.parameters().variant(),
1235 &ParameterVariant::NonInteractiveMultiParty
1236 );
1237
1238 let total_users = key_shares.len();
1239 let key_shares = (0..total_users)
1240 .map(|user_id| {
1241 // find share of user_id
1242 key_shares
1243 .iter()
1244 .find(|share| share.user_index() == user_id)
1245 .expect(&format!("Key Share for user_id={user_id} missing"))
1246 })
1247 .collect_vec();
1248
1249 // check parameters and cr seed are equal
1250 {
1251 key_shares.iter().for_each(|k| {
1252 assert!(k.parameters() == self.parameters());
1253 assert!(k.cr_seed() == cr_seed);
1254 });
1255 }
1256
1257 let rlwe_modop = &self.pbs_info().rlwe_modop;
1258 let nttop = &self.pbs_info().rlwe_nttop;
1259 let ring_size = self.parameters().rlwe_n().0;
1260 let rlwe_q = self.parameters().rlwe_q();
1261 let lwe_modop = self.pbs_info().modop_lweq();
1262
1263 // Generate Key switching key from u_j to s, where u_j user j's RLWE secret and
1264 // s is the ideal RLWE secret.
1265 //
1266 // User j gives [s_j * a_{i, j} + e + \beta^i u_j] where a_{i, j} is user j
1267 // specific publicly know polynomial sampled from user j's pseudo random seed
1268 // defined in the protocol.
1269 //
1270 // User k, k != j, gives [s_k * a_{i, j} + e].
1271 //
1272 // We set Ksk(u_j -> s) = [s_j * a_{i, j} + e + \beta^i u_j + \sum_{k \in P, k
1273 // != j} s_k * a_{i, j} + e]
1274 let ni_uj_to_s_decomposer = self
1275 .parameters()
1276 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>();
1277 let mut uj_to_s_ksks = key_shares
1278 .iter()
1279 .map(|share| {
1280 let mut useri_ui_to_s_ksk = share.ui_to_s_ksk().clone();
1281 assert!(
1282 useri_ui_to_s_ksk.dimension()
1283 == (ni_uj_to_s_decomposer.decomposition_count().0, ring_size)
1284 );
1285 key_shares
1286 .iter()
1287 .filter(|x| x.user_index() != share.user_index())
1288 .for_each(|other_share| {
1289 let op2 = other_share.ui_to_s_ksk_zero_encs_for_user_i(share.user_index());
1290 assert!(
1291 op2.dimension()
1292 == (ni_uj_to_s_decomposer.decomposition_count().0, ring_size)
1293 );
1294 izip!(useri_ui_to_s_ksk.iter_rows_mut(), op2.iter_rows()).for_each(
1295 |(add_to, add_from)| {
1296 rlwe_modop.elwise_add_mut(add_to.as_mut(), add_from.as_ref())
1297 },
1298 );
1299 });
1300 useri_ui_to_s_ksk
1301 })
1302 .collect_vec();
1303
1304 let rgsw_cts = {
1305 // Send u_j -> s ksk in evaluation domain and sample corresponding a's using
1306 // user j's ksk seed to prepare for upcoming key switches
1307 uj_to_s_ksks.iter_mut().for_each(|ksk_i| {
1308 ksk_i
1309 .iter_rows_mut()
1310 .for_each(|r| nttop.forward(r.as_mut()))
1311 });
1312 let uj_to_s_ksks_part_a_eval = key_shares
1313 .iter()
1314 .map(|share| {
1315 let mut ksk_prng = DefaultSecureRng::new_seeded(
1316 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(share.user_index()),
1317 );
1318 let mut ais =
1319 M::zeros(ni_uj_to_s_decomposer.decomposition_count().0, ring_size);
1320
1321 ais.iter_rows_mut().for_each(|r_ai| {
1322 RandomFillUniformInModulus::random_fill(
1323 &mut ksk_prng,
1324 rlwe_q,
1325 r_ai.as_mut(),
1326 );
1327
1328 nttop.forward(r_ai.as_mut())
1329 });
1330 ais
1331 })
1332 .collect_vec();
1333
1334 let rgsw_x_rgsw_decomposer = self
1335 .parameters()
1336 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1337 let rlwe_x_rgsw_decomposer = self
1338 .parameters()
1339 .rlwe_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1340
1341 let d_max = if rgsw_x_rgsw_decomposer.a().decomposition_count().0
1342 > rgsw_x_rgsw_decomposer.b().decomposition_count().0
1343 {
1344 rgsw_x_rgsw_decomposer.a().decomposition_count().0
1345 } else {
1346 rgsw_x_rgsw_decomposer.b().decomposition_count().0
1347 };
1348
1349 let mut scratch_rgsw_x_rgsw = M::zeros(
1350 rgsw_x_rgsw_scratch_rows(&rlwe_x_rgsw_decomposer, &rgsw_x_rgsw_decomposer),
1351 self.parameters().rlwe_n().0,
1352 );
1353
1354 // Recall that given u_j * a_{i, l} + e + \beta^i X^{s_j[l]} from user j
1355 //
1356 // We generate:
1357 //
1358 // - RLWE(-s \beta^i X^{s_j[l]}) = KS_{u_j -> s}(a_{i, l} * s + e) + (0 , u_j *
1359 // a_{i, l} + e + \beta^i X^{s_j[l]}), where KS_{u_j -> s}(a_{i, l} * s + e) =
1360 // RLWE_s(a_{i, l} * u_j)
1361 // - RLWE(\beta^i X^{s_j[l]}) = KS_{u_j -> s}(-a_{i,l}) + (u_j * a_{i, l} + e +
1362 // \beta^i X^{s_j[l]}, 0), where KS_{u_j -> s}(-a_{i,l}) = RLWE_s(-a_{i,l} *
1363 // u_j)
1364 //
1365 // a_{i, l} * s + e = \sum_{j \in P} a_{i, l} * s_{j} + e
1366 let user_segments = (0..total_users)
1367 .map(|user_id| {
1368 multi_party_user_id_lwe_segment(
1369 user_id,
1370 total_users,
1371 self.parameters().lwe_n().0,
1372 )
1373 })
1374 .collect_vec();
1375 // Note: Each user is assigned a contigous LWE segement and the LWE dimension is
1376 // split approximately uniformly across all users. Hence, concatenation of all
1377 // user specific lwe segments will give LWE dimension.
1378 let rgsw_cts = user_segments
1379 .into_iter()
1380 .enumerate()
1381 .flat_map(|(user_id, lwe_segment)| {
1382 (lwe_segment.0..lwe_segment.1)
1383 .into_iter()
1384 .map(|lwe_index| {
1385 // We sample d_b `-a_i`s to key switch and generate RLWE'(m). But before
1386 // we sampling we need to puncture a_prng d_max - d_b times to align
1387 // a_i's. After sampling we decompose `-a_i`s and send them to
1388 // evaluation domain for upcoming key switches.
1389 let mut a_prng = DefaultSecureRng::new_seeded(
1390 cr_seed.ni_rgsw_ct_seed_for_index::<DefaultSecureRng>(lwe_index),
1391 );
1392
1393 let mut scratch = M::R::zeros(self.parameters().rlwe_n().0);
1394 (0..d_max - rgsw_x_rgsw_decomposer.b().decomposition_count().0)
1395 .for_each(|_| {
1396 RandomFillUniformInModulus::random_fill(
1397 &mut a_prng,
1398 rlwe_q,
1399 scratch.as_mut(),
1400 );
1401 });
1402
1403 let decomp_neg_ais = (0..rgsw_x_rgsw_decomposer
1404 .b()
1405 .decomposition_count()
1406 .0)
1407 .map(|_| {
1408 RandomFillUniformInModulus::random_fill(
1409 &mut a_prng,
1410 rlwe_q,
1411 scratch.as_mut(),
1412 );
1413 rlwe_modop.elwise_neg_mut(scratch.as_mut());
1414
1415 let mut decomp_neg_ai = M::zeros(
1416 ni_uj_to_s_decomposer.decomposition_count().0,
1417 self.parameters().rlwe_n().0,
1418 );
1419 scratch.as_ref().iter().enumerate().for_each(|(index, el)| {
1420 ni_uj_to_s_decomposer
1421 .decompose_iter(el)
1422 .enumerate()
1423 .for_each(|(row_j, d_el)| {
1424 (decomp_neg_ai.as_mut()[row_j]).as_mut()[index] =
1425 d_el;
1426 });
1427 });
1428
1429 decomp_neg_ai
1430 .iter_rows_mut()
1431 .for_each(|ri| nttop.forward(ri.as_mut()));
1432
1433 decomp_neg_ai
1434 })
1435 .collect_vec();
1436
1437 // Aggregate zero encryptions to produce a_{i, l} * s + e =
1438 // \sum_{k in P} a_{i, l} * s_{k} + e where s is the ideal RLWE
1439 // secret. Aggregated a_{i, l} * s + e are key switched using
1440 // Ksk(u_j -> s) to produce RLWE_{s}(a_{i, l} * s) which are
1441 // then use to produce RLWE'(-sX^{s_{lwe}[l]}).
1442 // Hence, after aggregation we decompose a_{i, l} * s + e to
1443 // prepare for key switching
1444 let ni_rgsw_zero_encs = (0..rgsw_x_rgsw_decomposer
1445 .a()
1446 .decomposition_count()
1447 .0)
1448 .map(|i| {
1449 let mut sum = M::R::zeros(self.parameters().rlwe_n().0);
1450 key_shares.iter().for_each(|k| {
1451 let to_add_ref = k
1452 .ni_rgsw_zero_enc_for_lwe_index(lwe_index)
1453 .get_row_slice(i);
1454 assert!(to_add_ref.len() == self.parameters().rlwe_n().0);
1455 rlwe_modop.elwise_add_mut(sum.as_mut(), to_add_ref);
1456 });
1457
1458 // decompose
1459 let mut decomp_sum = M::zeros(
1460 ni_uj_to_s_decomposer.decomposition_count().0,
1461 self.parameters().rlwe_n().0,
1462 );
1463 sum.as_ref().iter().enumerate().for_each(|(index, el)| {
1464 ni_uj_to_s_decomposer
1465 .decompose_iter(el)
1466 .enumerate()
1467 .for_each(|(row_j, d_el)| {
1468 (decomp_sum.as_mut()[row_j]).as_mut()[index] = d_el;
1469 });
1470 });
1471
1472 decomp_sum
1473 .iter_rows_mut()
1474 .for_each(|r| nttop.forward(r.as_mut()));
1475
1476 decomp_sum
1477 })
1478 .collect_vec();
1479
1480 // Produce RGSW(X^{s_{j=user_id, lwe}[l]}) for the
1481 // leader, ie user's id = user_id.
1482 // Recall leader's RGSW ciphertext must be constructed
1483 // for RLWE x RGSW multiplication, and is then used
1484 // to accumulate, using RGSW x RGSW multiplication,
1485 // X^{s_{j != user_id, lwe}[l]} from other users.
1486 let mut rgsw_i = produce_rgsw_ciphertext_from_ni_rgsw(
1487 key_shares[user_id]
1488 .ni_rgsw_cts_for_self_leader_lwe_index(lwe_index),
1489 &ni_rgsw_zero_encs[rgsw_x_rgsw_decomposer
1490 .a()
1491 .decomposition_count()
1492 .0
1493 - rlwe_x_rgsw_decomposer.a().decomposition_count().0..],
1494 &decomp_neg_ais[rgsw_x_rgsw_decomposer
1495 .b()
1496 .decomposition_count()
1497 .0
1498 - rlwe_x_rgsw_decomposer.b().decomposition_count().0..],
1499 &rlwe_x_rgsw_decomposer,
1500 self.parameters(),
1501 (&uj_to_s_ksks[user_id], &uj_to_s_ksks_part_a_eval[user_id]),
1502 rlwe_modop,
1503 nttop,
1504 false,
1505 );
1506
1507 // RGSW for lwe_index of users that are not leader.
1508 //
1509 // Recall that for users that are not leader for the
1510 // lwe_index we require to produce RGSW ciphertext for
1511 // RGSW x RGSW product
1512 (0..total_users)
1513 .filter(|i| *i != user_id)
1514 .for_each(|other_user_id| {
1515 let mut other_rgsw_i = produce_rgsw_ciphertext_from_ni_rgsw(
1516 key_shares[other_user_id]
1517 .ni_rgsw_cts_for_self_not_leader_lwe_index(lwe_index),
1518 &ni_rgsw_zero_encs,
1519 &decomp_neg_ais,
1520 &rgsw_x_rgsw_decomposer,
1521 self.parameters(),
1522 (
1523 &uj_to_s_ksks[other_user_id],
1524 &uj_to_s_ksks_part_a_eval[other_user_id],
1525 ),
1526 rlwe_modop,
1527 nttop,
1528 true,
1529 );
1530
1531 rgsw_by_rgsw_inplace(
1532 &mut RgswCiphertextMutRef::new(
1533 rgsw_i.as_mut(),
1534 rlwe_x_rgsw_decomposer.a().decomposition_count().0,
1535 rlwe_x_rgsw_decomposer.b().decomposition_count().0,
1536 ),
1537 &RgswCiphertextRef::new(
1538 other_rgsw_i.as_ref(),
1539 rgsw_x_rgsw_decomposer.a().decomposition_count().0,
1540 rgsw_x_rgsw_decomposer.b().decomposition_count().0,
1541 ),
1542 &rlwe_x_rgsw_decomposer,
1543 &rgsw_x_rgsw_decomposer,
1544 &mut RuntimeScratchMutRef::new(
1545 scratch_rgsw_x_rgsw.as_mut(),
1546 ),
1547 nttop,
1548 rlwe_modop,
1549 )
1550 });
1551
1552 rgsw_i
1553 })
1554 .collect_vec()
1555 })
1556 .collect_vec();
1557
1558 // put u_j to s ksk in coefficient domain
1559 uj_to_s_ksks.iter_mut().for_each(|ksk_i| {
1560 ksk_i
1561 .iter_rows_mut()
1562 .for_each(|r| nttop.backward(r.as_mut()))
1563 });
1564
1565 rgsw_cts
1566 };
1567
1568 // auto keys
1569 let auto_keys = {
1570 let mut auto_keys = HashMap::new();
1571 let auto_elements_dlog = self.parameters().auto_element_dlogs();
1572 for i in auto_elements_dlog.into_iter() {
1573 let mut key = M::zeros(self.parameters().auto_decomposition_count().0, ring_size);
1574
1575 key_shares.iter().for_each(|s| {
1576 let auto_key_share_i =
1577 s.auto_keys_share().get(&i).expect("Auto key {i} missing");
1578 assert!(
1579 auto_key_share_i.dimension()
1580 == (self.parameters().auto_decomposition_count().0, ring_size)
1581 );
1582 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
1583 |(partb_out, partb_share)| {
1584 rlwe_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
1585 },
1586 );
1587 });
1588
1589 auto_keys.insert(i, key);
1590 }
1591 auto_keys
1592 };
1593
1594 // LWE ksk
1595 let lwe_ksk = {
1596 let mut lwe_ksk =
1597 M::R::zeros(self.parameters().lwe_decomposition_count().0 * ring_size);
1598 key_shares.iter().for_each(|s| {
1599 assert!(
1600 s.lwe_ksk_share().as_ref().len()
1601 == self.parameters().lwe_decomposition_count().0 * ring_size
1602 );
1603 lwe_modop.elwise_add_mut(lwe_ksk.as_mut(), s.lwe_ksk_share().as_ref());
1604 });
1605 lwe_ksk
1606 };
1607
1608 SeededNonInteractiveMultiPartyServerKey::new(
1609 uj_to_s_ksks,
1610 rgsw_cts,
1611 auto_keys,
1612 lwe_ksk,
1613 cr_seed.clone(),
1614 self.parameters().clone(),
1615 )
1616 }
1617
1618 pub(super) fn gen_non_interactive_multi_party_key_share<
1619 K: NonInteractiveMultiPartyClientKey<Element = i32>,
1620 >(
1621 &self,
1622 cr_seed: &NonInteractiveMultiPartyCrs<[u8; 32]>,
1623 self_index: usize,
1624 total_users: usize,
1625 client_key: &K,
1626 ) -> CommonReferenceSeededNonInteractiveMultiPartyServerKeyShare<
1627 M,
1628 BoolParameters<M::MatElement>,
1629 NonInteractiveMultiPartyCrs<[u8; 32]>,
1630 > {
1631 assert_eq!(
1632 self.parameters().variant(),
1633 &ParameterVariant::NonInteractiveMultiParty
1634 );
1635
1636 // TODO: check whether parameters support `total_users`
1637 let nttop = self.pbs_info().nttop_rlweq();
1638 let rlwe_modop = self.pbs_info().modop_rlweq();
1639 let ring_size = self.pbs_info().rlwe_n();
1640 let rlwe_q = self.parameters().rlwe_q();
1641
1642 let sk_rlwe = client_key.sk_rlwe();
1643 let sk_u_rlwe = client_key.sk_u_rlwe();
1644 let sk_lwe = client_key.sk_lwe();
1645
1646 let (ui_to_s_ksk, ksk_zero_encs_for_others) = DefaultSecureRng::with_local_mut(|rng| {
1647 // ui_to_s_ksk
1648 let non_interactive_decomposer = self
1649 .parameters()
1650 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>(
1651 );
1652 let non_interactive_gadget_vec = non_interactive_decomposer.gadget_vector();
1653 let ui_to_s_ksk = {
1654 let mut p_rng = DefaultSecureRng::new_seeded(
1655 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(self_index),
1656 );
1657
1658 non_interactive_ksk_gen::<M, _, _, _, _, _>(
1659 &sk_rlwe,
1660 &sk_u_rlwe,
1661 &non_interactive_gadget_vec,
1662 &mut p_rng,
1663 rng,
1664 nttop,
1665 rlwe_modop,
1666 )
1667 };
1668
1669 // zero encryptions for others uj_to_s ksk
1670 let all_users_except_self = (0..total_users).filter(|x| *x != self_index);
1671 let zero_encs_for_others = all_users_except_self
1672 .map(|other_user_index| {
1673 let mut p_rng = DefaultSecureRng::new_seeded(
1674 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(other_user_index),
1675 );
1676 let zero_encs =
1677 non_interactive_ksk_zero_encryptions_for_other_party_i::<M, _, _, _, _, _>(
1678 &sk_rlwe,
1679 &non_interactive_gadget_vec,
1680 &mut p_rng,
1681 rng,
1682 nttop,
1683 rlwe_modop,
1684 );
1685 zero_encs
1686 })
1687 .collect_vec();
1688
1689 (ui_to_s_ksk, zero_encs_for_others)
1690 });
1691
1692 // Non-interactive RGSW cts
1693 let (ni_rgsw_zero_encs, self_leader_ni_rgsw_cts, not_self_leader_rgsw_cts) = {
1694 let rgsw_x_rgsw_decomposer = self
1695 .parameters()
1696 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1697 let rlwe_x_rgsw_decomposer = self
1698 .parameters()
1699 .rlwe_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1700
1701 // We assume that d_{a/b} for RGSW x RGSW are always < d'_{a/b} for RLWE x RGSW
1702 assert!(
1703 rlwe_x_rgsw_decomposer.a().decomposition_count().0
1704 < rgsw_x_rgsw_decomposer.a().decomposition_count().0
1705 );
1706 assert!(
1707 rlwe_x_rgsw_decomposer.b().decomposition_count().0
1708 < rgsw_x_rgsw_decomposer.b().decomposition_count().0
1709 );
1710
1711 let sj_poly_eval = {
1712 let mut s = M::R::try_convert_from(&sk_rlwe, rlwe_q);
1713 nttop.forward(s.as_mut());
1714 s
1715 };
1716
1717 let d_rgsw_a = rgsw_x_rgsw_decomposer.a().decomposition_count().0;
1718 let d_rgsw_b = rgsw_x_rgsw_decomposer.b().decomposition_count().0;
1719 let d_max = std::cmp::max(d_rgsw_a, d_rgsw_b);
1720
1721 // Zero encyptions for each LWE index. We generate d_a zero encryptions for each
1722 // LWE index using a_{i, l} with i \in {d_max - d_a , d_max) and l = lwe_index
1723 let zero_encs = {
1724 (0..self.parameters().lwe_n().0)
1725 .map(|lwe_index| {
1726 let mut p_rng = DefaultSecureRng::new_seeded(
1727 cr_seed.ni_rgsw_ct_seed_for_index::<DefaultSecureRng>(lwe_index),
1728 );
1729
1730 let mut scratch = M::R::zeros(self.parameters().rlwe_n().0);
1731
1732 // puncture seeded prng d_max - d_a times
1733 (0..(d_max - d_rgsw_a)).into_iter().for_each(|_| {
1734 RandomFillUniformInModulus::random_fill(
1735 &mut p_rng,
1736 rlwe_q,
1737 scratch.as_mut(),
1738 );
1739 });
1740
1741 let mut zero_enc = M::zeros(d_rgsw_a, self.parameters().rlwe_n().0);
1742 zero_enc.iter_rows_mut().for_each(|out| {
1743 // sample a_i
1744 RandomFillUniformInModulus::random_fill(
1745 &mut p_rng,
1746 rlwe_q,
1747 out.as_mut(),
1748 );
1749
1750 // a_i * s_j
1751 nttop.forward(out.as_mut());
1752 rlwe_modop.elwise_mul_mut(out.as_mut(), sj_poly_eval.as_ref());
1753 nttop.backward(out.as_mut());
1754
1755 // a_j * s_j + e
1756 DefaultSecureRng::with_local_mut_mut(&mut |rng| {
1757 RandomFillGaussianInModulus::random_fill(
1758 rng,
1759 rlwe_q,
1760 scratch.as_mut(),
1761 );
1762 });
1763
1764 rlwe_modop.elwise_add_mut(out.as_mut(), scratch.as_ref());
1765 });
1766
1767 zero_enc
1768 })
1769 .collect_vec()
1770 };
1771
1772 let uj_poly_eval = {
1773 let mut u = M::R::try_convert_from(&sk_u_rlwe, rlwe_q);
1774 nttop.forward(u.as_mut());
1775 u
1776 };
1777
1778 // Generate non-interactive RGSW ciphertexts a_{i, l} u_j + e + \beta X^{s_j[l]}
1779 // for i \in (0, d_max]
1780 let (self_start_index, self_end_index) = multi_party_user_id_lwe_segment(
1781 self_index,
1782 total_users,
1783 self.parameters().lwe_n().0,
1784 );
1785
1786 // For LWE indices [self_start_index, self_end_index) user generates
1787 // non-interactive RGSW cts for RLWE x RGSW product. We refer to
1788 // such indices as where user is the leader. For the rest of
1789 // the indices user generates non-interactive RGWS cts for RGSW x
1790 // RGSW multiplication. We refer to such indices as where user is
1791 // not the leader.
1792 let self_leader_ni_rgsw_cts = {
1793 let max_rlwe_x_rgsw_decomposer =
1794 if rlwe_x_rgsw_decomposer.a().decomposition_count().0
1795 > rlwe_x_rgsw_decomposer.b().decomposition_count().0
1796 {
1797 rlwe_x_rgsw_decomposer.a()
1798 } else {
1799 rlwe_x_rgsw_decomposer.b()
1800 };
1801
1802 let gadget_vec = max_rlwe_x_rgsw_decomposer.gadget_vector();
1803
1804 (self_start_index..self_end_index)
1805 .map(|lwe_index| {
1806 let mut p_rng = DefaultSecureRng::new_seeded(
1807 cr_seed.ni_rgsw_ct_seed_for_index::<DefaultSecureRng>(lwe_index),
1808 );
1809
1810 // puncture p_rng d_max - d'_max time to align with `a_{i, l}`s used to
1811 // produce RGSW cts for RGSW x RGSW
1812 let mut scratch = M::R::zeros(self.parameters().rlwe_n().0);
1813 (0..(d_max - max_rlwe_x_rgsw_decomposer.decomposition_count().0))
1814 .into_iter()
1815 .for_each(|_| {
1816 RandomFillUniformInModulus::random_fill(
1817 &mut p_rng,
1818 rlwe_q,
1819 scratch.as_mut(),
1820 );
1821 });
1822
1823 let mut ni_rgsw_cts = M::zeros(
1824 max_rlwe_x_rgsw_decomposer.decomposition_count().0,
1825 self.parameters().rlwe_n().0,
1826 );
1827
1828 // X^{s_{j, lwe}[l]}
1829 let m_poly = encode_x_pow_si_with_emebedding_factor::<M::R, _>(
1830 sk_lwe[lwe_index],
1831 self.pbs_info().embedding_factor(),
1832 self.parameters().rlwe_n().0,
1833 rlwe_q,
1834 );
1835
1836 izip!(ni_rgsw_cts.iter_rows_mut(), gadget_vec.iter()).for_each(
1837 |(out, beta)| {
1838 // sample a_i
1839 RandomFillUniformInModulus::random_fill(
1840 &mut p_rng,
1841 rlwe_q,
1842 out.as_mut(),
1843 );
1844
1845 // u_j * a_i
1846 nttop.forward(out.as_mut());
1847 rlwe_modop.elwise_mul_mut(out.as_mut(), uj_poly_eval.as_ref());
1848 nttop.backward(out.as_mut());
1849
1850 // u_j + a_i + e
1851 DefaultSecureRng::with_local_mut_mut(&mut |rng| {
1852 RandomFillGaussianInModulus::random_fill(
1853 rng,
1854 rlwe_q,
1855 scratch.as_mut(),
1856 );
1857 });
1858 rlwe_modop.elwise_add_mut(out.as_mut(), scratch.as_ref());
1859
1860 // u_j + a_i + e + beta m
1861 rlwe_modop.elwise_scalar_mul(
1862 scratch.as_mut(),
1863 m_poly.as_ref(),
1864 beta,
1865 );
1866 rlwe_modop.elwise_add_mut(out.as_mut(), scratch.as_ref());
1867 },
1868 );
1869
1870 ni_rgsw_cts
1871 })
1872 .collect_vec()
1873 };
1874
1875 let not_self_leader_rgsw_cts = {
1876 let max_rgsw_x_rgsw_decomposer =
1877 if rgsw_x_rgsw_decomposer.a().decomposition_count().0
1878 > rgsw_x_rgsw_decomposer.b().decomposition_count().0
1879 {
1880 rgsw_x_rgsw_decomposer.a()
1881 } else {
1882 rgsw_x_rgsw_decomposer.b()
1883 };
1884 let gadget_vec = max_rgsw_x_rgsw_decomposer.gadget_vector();
1885
1886 ((0..self_start_index).chain(self_end_index..self.parameters().lwe_n().0))
1887 .map(|lwe_index| {
1888 let mut p_rng = DefaultSecureRng::new_seeded(
1889 cr_seed.ni_rgsw_ct_seed_for_index::<DefaultSecureRng>(lwe_index),
1890 );
1891 let mut ni_rgsw_cts = M::zeros(
1892 max_rgsw_x_rgsw_decomposer.decomposition_count().0,
1893 self.parameters().rlwe_n().0,
1894 );
1895 let mut scratch = M::R::zeros(self.parameters().rlwe_n().0);
1896
1897 // X^{s_{j, lwe}[l]}
1898 let m_poly = encode_x_pow_si_with_emebedding_factor::<M::R, _>(
1899 sk_lwe[lwe_index],
1900 self.pbs_info().embedding_factor(),
1901 self.parameters().rlwe_n().0,
1902 rlwe_q,
1903 );
1904
1905 izip!(ni_rgsw_cts.iter_rows_mut(), gadget_vec.iter()).for_each(
1906 |(out, beta)| {
1907 // sample a_i
1908 RandomFillUniformInModulus::random_fill(
1909 &mut p_rng,
1910 rlwe_q,
1911 out.as_mut(),
1912 );
1913
1914 // u_j * a_i
1915 nttop.forward(out.as_mut());
1916 rlwe_modop.elwise_mul_mut(out.as_mut(), uj_poly_eval.as_ref());
1917 nttop.backward(out.as_mut());
1918
1919 // u_j + a_i + e
1920 DefaultSecureRng::with_local_mut_mut(&mut |rng| {
1921 RandomFillGaussianInModulus::random_fill(
1922 rng,
1923 rlwe_q,
1924 scratch.as_mut(),
1925 );
1926 });
1927 rlwe_modop.elwise_add_mut(out.as_mut(), scratch.as_ref());
1928
1929 // u_j * a_i + e + beta m
1930 rlwe_modop.elwise_scalar_mul(
1931 scratch.as_mut(),
1932 m_poly.as_ref(),
1933 beta,
1934 );
1935 rlwe_modop.elwise_add_mut(out.as_mut(), scratch.as_ref());
1936 },
1937 );
1938
1939 ni_rgsw_cts
1940 })
1941 .collect_vec()
1942 };
1943
1944 (zero_encs, self_leader_ni_rgsw_cts, not_self_leader_rgsw_cts)
1945 };
1946
1947 // Auto key share
1948 let auto_keys_share = {
1949 let auto_seed = cr_seed.auto_keys_cts_seed::<DefaultSecureRng>();
1950 self._common_rountine_multi_party_auto_keys_share_gen(auto_seed, &sk_rlwe)
1951 };
1952
1953 // Lwe Ksk share
1954 let lwe_ksk_share = {
1955 let lwe_ksk_seed = cr_seed.lwe_ksk_cts_seed::<DefaultSecureRng>();
1956 self._common_rountine_multi_party_lwe_ksk_share_gen(lwe_ksk_seed, &sk_rlwe, &sk_lwe)
1957 };
1958
1959 CommonReferenceSeededNonInteractiveMultiPartyServerKeyShare::new(
1960 self_leader_ni_rgsw_cts,
1961 not_self_leader_rgsw_cts,
1962 ni_rgsw_zero_encs,
1963 ui_to_s_ksk,
1964 ksk_zero_encs_for_others,
1965 auto_keys_share,
1966 lwe_ksk_share,
1967 self_index,
1968 total_users,
1969 self.parameters().lwe_n().0,
1970 cr_seed.clone(),
1971 self.parameters().clone(),
1972 )
1973 }
1974
1975 fn _common_rountine_multi_party_auto_keys_share_gen(
1976 &self,
1977 auto_seed: <DefaultSecureRng as NewWithSeed>::Seed,
1978 sk_rlwe: &[i32],
1979 ) -> HashMap<usize, M> {
1980 let g = self.pbs_info.parameters.g();
1981 let ring_size = self.pbs_info.parameters.rlwe_n().0;
1982 let br_q = self.pbs_info.parameters.br_q();
1983 let rlweq_modop = &self.pbs_info.rlwe_modop;
1984 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1985
1986 DefaultSecureRng::with_local_mut(|rng| {
1987 let mut p_rng = DefaultSecureRng::new_seeded(auto_seed);
1988
1989 let mut auto_keys = HashMap::new();
1990 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
1991 let auto_element_dlogs = self.pbs_info.parameters.auto_element_dlogs();
1992
1993 for i in auto_element_dlogs.into_iter() {
1994 let g_pow = if i == 0 {
1995 -(g as isize)
1996 } else {
1997 (g.pow(i as u32) % br_q) as isize
1998 };
1999
2000 let mut ksk_out = M::zeros(
2001 self.pbs_info.auto_decomposer.decomposition_count().0,
2002 ring_size,
2003 );
2004 seeded_auto_key_gen(
2005 &mut ksk_out,
2006 sk_rlwe,
2007 g_pow,
2008 &auto_gadget,
2009 rlweq_modop,
2010 rlweq_nttop,
2011 &mut p_rng,
2012 rng,
2013 );
2014 auto_keys.insert(i, ksk_out);
2015 }
2016
2017 auto_keys
2018 })
2019 }
2020
2021 fn _common_rountine_multi_party_lwe_ksk_share_gen(
2022 &self,
2023 lwe_ksk_seed: <DefaultSecureRng as NewWithSeed>::Seed,
2024 sk_rlwe: &[i32],
2025 sk_lwe: &[i32],
2026 ) -> M::R {
2027 DefaultSecureRng::with_local_mut(|rng| {
2028 let mut p_rng = DefaultSecureRng::new_seeded(lwe_ksk_seed);
2029 let lwe_modop = &self.pbs_info.lwe_modop;
2030 let d_lwe_gadget_vec = self.pbs_info.lwe_decomposer.gadget_vector();
2031 seeded_lwe_ksk_keygen(
2032 sk_rlwe,
2033 sk_lwe,
2034 &d_lwe_gadget_vec,
2035 lwe_modop,
2036 &mut p_rng,
2037 rng,
2038 )
2039 })
2040 }
2041
2042 pub(super) fn multi_party_public_key_share<K: InteractiveMultiPartyClientKey<Element = i32>>(
2043 &self,
2044 cr_seed: &InteractiveMultiPartyCrs<[u8; 32]>,
2045 client_key: &K,
2046 ) -> CommonReferenceSeededCollectivePublicKeyShare<
2047 <M as Matrix>::R,
2048 [u8; 32],
2049 BoolParameters<<M as Matrix>::MatElement>,
2050 > {
2051 DefaultSecureRng::with_local_mut(|rng| {
2052 let mut share_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0);
2053 let modop = &self.pbs_info.rlwe_modop;
2054 let nttop = &self.pbs_info.rlwe_nttop;
2055 let pk_seed = cr_seed.public_key_share_seed::<DefaultSecureRng>();
2056 let mut main_prng = DefaultSecureRng::new_seeded(pk_seed);
2057 public_key_share(
2058 &mut share_out,
2059 &client_key.sk_rlwe(),
2060 modop,
2061 nttop,
2062 &mut main_prng,
2063 rng,
2064 );
2065 CommonReferenceSeededCollectivePublicKeyShare::new(
2066 share_out,
2067 pk_seed,
2068 self.pbs_info.parameters.clone(),
2069 )
2070 })
2071 }
2072
2073 pub fn sk_encrypt<K: SinglePartyClientKey<Element = i32>>(
2074 &self,
2075 m: bool,
2076 client_key: &K,
2077 ) -> M::R {
2078 //FIXME(Jay): Figure out a way to get Q/8 form modulus
2079 let m = if m {
2080 // Q/8
2081 self.pbs_info.rlwe_q().true_el()
2082 } else {
2083 // -Q/8
2084 self.pbs_info.rlwe_q().false_el()
2085 };
2086
2087 DefaultSecureRng::with_local_mut(|rng| {
2088 encrypt_lwe(&m, &client_key.sk_rlwe(), &self.pbs_info.rlwe_modop, rng)
2089 })
2090 }
2091
2092 pub fn sk_decrypt<K: SinglePartyClientKey<Element = i32>>(
2093 &self,
2094 lwe_ct: &M::R,
2095 client_key: &K,
2096 ) -> bool {
2097 let m = decrypt_lwe(lwe_ct, &client_key.sk_rlwe(), &self.pbs_info.rlwe_modop);
2098 self.pbs_info.rlwe_q().decode(m)
2099 }
2100}
2101
2102impl<M, NttOp, RlweModOp, LweModOp, Skey> BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
2103where
2104 M: MatrixMut + MatrixEntity,
2105 M::R: RowMut + RowEntity,
2106 M::MatElement: PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo,
2107 RlweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
2108 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
2109 NttOp: Ntt<Element = M::MatElement>,
2110{
2111 /// Returns c0 + c1 + Q/4
2112 fn _add_and_shift_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
2113 let modop = &self.pbs_info.rlwe_modop;
2114 modop.elwise_add_mut(c0.as_mut(), c1.as_ref());
2115 // +Q/4
2116 c0.as_mut()[0] = modop.add(&c0.as_ref()[0], &self.pbs_info.rlwe_qby4);
2117 }
2118
2119 /// Returns 2(c0 - c1) + Q/4
2120 fn _subtract_double_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
2121 let modop = &self.pbs_info.rlwe_modop;
2122 // c0 - c1
2123 modop.elwise_sub_mut(c0.as_mut(), c1.as_ref());
2124
2125 // double
2126 c0.as_mut().iter_mut().for_each(|v| *v = modop.add(v, v));
2127 }
2128}
2129
2130impl<M, NttOp, RlweModOp, LweModOp, Skey> BooleanGates
2131 for BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
2132where
2133 M: MatrixMut + MatrixEntity,
2134 M::R: RowMut + RowEntity + Clone,
2135 M::MatElement: PrimInt
2136 + FromPrimitive
2137 + One
2138 + Copy
2139 + Zero
2140 + Display
2141 + WrappingSub
2142 + NumInfo
2143 + From<bool>
2144 + WrappingAdd
2145 + Debug,
2146 RlweModOp: VectorOps<Element = M::MatElement>
2147 + ArithmeticOps<Element = M::MatElement>
2148 + ShoupMatrixFMA<M::R>,
2149 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
2150 NttOp: Ntt<Element = M::MatElement>,
2151 Skey: PbsKey<AutoKey = <Skey as PbsKey>::RgswCt, LweKskKey = M>,
2152 <Skey as PbsKey>::RgswCt: WithShoupRepr<M = M>,
2153{
2154 type Ciphertext = M::R;
2155 type Key = Skey;
2156
2157 fn nand_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2158 self._add_and_shift_lwe_cts(c0, c1);
2159
2160 // PBS
2161 pbs(
2162 &self.pbs_info,
2163 &self.nand_test_vec,
2164 c0,
2165 server_key,
2166 &mut self.scratch_memory.lwe_vector,
2167 &mut self.scratch_memory.decomposition_matrix,
2168 );
2169 }
2170
2171 fn and_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2172 self._add_and_shift_lwe_cts(c0, c1);
2173
2174 // PBS
2175 pbs(
2176 &self.pbs_info,
2177 &self.and_test_vec,
2178 c0,
2179 server_key,
2180 &mut self.scratch_memory.lwe_vector,
2181 &mut self.scratch_memory.decomposition_matrix,
2182 );
2183 }
2184
2185 fn or_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2186 self._add_and_shift_lwe_cts(c0, c1);
2187
2188 // PBS
2189 pbs(
2190 &self.pbs_info,
2191 &self.or_test_vec,
2192 c0,
2193 server_key,
2194 &mut self.scratch_memory.lwe_vector,
2195 &mut self.scratch_memory.decomposition_matrix,
2196 );
2197 }
2198
2199 fn nor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2200 self._add_and_shift_lwe_cts(c0, c1);
2201
2202 // PBS
2203 pbs(
2204 &self.pbs_info,
2205 &self.nor_test_vec,
2206 c0,
2207 server_key,
2208 &mut self.scratch_memory.lwe_vector,
2209 &mut self.scratch_memory.decomposition_matrix,
2210 )
2211 }
2212
2213 fn xor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2214 self._subtract_double_lwe_cts(c0, c1);
2215
2216 // PBS
2217 pbs(
2218 &self.pbs_info,
2219 &self.xor_test_vec,
2220 c0,
2221 server_key,
2222 &mut self.scratch_memory.lwe_vector,
2223 &mut self.scratch_memory.decomposition_matrix,
2224 );
2225 }
2226
2227 fn xnor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2228 self._subtract_double_lwe_cts(c0, c1);
2229
2230 // PBS
2231 pbs(
2232 &self.pbs_info,
2233 &self.xnor_test_vec,
2234 c0,
2235 server_key,
2236 &mut self.scratch_memory.lwe_vector,
2237 &mut self.scratch_memory.decomposition_matrix,
2238 );
2239 }
2240
2241 fn not_inplace(&self, c0: &mut M::R) {
2242 let modop = &self.pbs_info.rlwe_modop;
2243 c0.as_mut().iter_mut().for_each(|v| *v = modop.neg(v));
2244 }
2245
2246 fn and(
2247 &mut self,
2248 c0: &Self::Ciphertext,
2249 c1: &Self::Ciphertext,
2250 key: &Self::Key,
2251 ) -> Self::Ciphertext {
2252 let mut out = c0.clone();
2253 self.and_inplace(&mut out, c1, key);
2254 out
2255 }
2256
2257 fn nand(
2258 &mut self,
2259 c0: &Self::Ciphertext,
2260 c1: &Self::Ciphertext,
2261 key: &Self::Key,
2262 ) -> Self::Ciphertext {
2263 let mut out = c0.clone();
2264 self.nand_inplace(&mut out, c1, key);
2265 out
2266 }
2267
2268 fn or(
2269 &mut self,
2270 c0: &Self::Ciphertext,
2271 c1: &Self::Ciphertext,
2272 key: &Self::Key,
2273 ) -> Self::Ciphertext {
2274 let mut out = c0.clone();
2275 self.or_inplace(&mut out, c1, key);
2276 out
2277 }
2278
2279 fn nor(
2280 &mut self,
2281 c0: &Self::Ciphertext,
2282 c1: &Self::Ciphertext,
2283 key: &Self::Key,
2284 ) -> Self::Ciphertext {
2285 let mut out = c0.clone();
2286 self.nor_inplace(&mut out, c1, key);
2287 out
2288 }
2289
2290 fn xnor(
2291 &mut self,
2292 c0: &Self::Ciphertext,
2293 c1: &Self::Ciphertext,
2294 key: &Self::Key,
2295 ) -> Self::Ciphertext {
2296 let mut out = c0.clone();
2297 self.xnor_inplace(&mut out, c1, key);
2298 out
2299 }
2300
2301 fn xor(
2302 &mut self,
2303 c0: &Self::Ciphertext,
2304 c1: &Self::Ciphertext,
2305 key: &Self::Key,
2306 ) -> Self::Ciphertext {
2307 let mut out = c0.clone();
2308 self.xor_inplace(&mut out, c1, key);
2309 out
2310 }
2311
2312 fn not(&self, c: &Self::Ciphertext) -> Self::Ciphertext {
2313 let mut out = c.clone();
2314 self.not_inplace(&mut out);
2315 out
2316 }
2317}