phantom-zone/src/bool/evaluator.rs
src/bool/evaluator.rsRaw
1use std::{
2 borrow::BorrowMut,
3 cell::{OnceCell, RefCell},
4 clone,
5 collections::HashMap,
6 fmt::{Debug, Display},
7 iter::Once,
8 marker::PhantomData,
9 ops::Shr,
10 sync::OnceLock,
11 usize,
12};
13
14use itertools::{izip, partition, Itertools};
15use num_traits::{FromPrimitive, Num, One, Pow, PrimInt, ToPrimitive, WrappingSub, Zero};
16use rand::Rng;
17use rand_distr::uniform::SampleUniform;
18
19use crate::{
20 backend::{
21 ArithmeticOps, GetModulus, ModInit, ModularOpsU64, Modulus, ShoupMatrixFMA, VectorOps,
22 },
23 decomposer::{Decomposer, DefaultDecomposer, NumInfo, RlweDecomposer},
24 lwe::{decrypt_lwe, encrypt_lwe, lwe_key_switch, lwe_ksk_keygen, measure_noise_lwe, LweSecret},
25 multi_party::{
26 non_interactive_ksk_gen, non_interactive_ksk_zero_encryptions_for_other_party_i,
27 non_interactive_rgsw_ct, public_key_share,
28 },
29 ntt::{self, Ntt, NttBackendU64, NttInit},
30 pbs::{pbs, sample_extract, PbsInfo, PbsKey, WithShoupRepr},
31 random::{
32 DefaultSecureRng, NewWithSeed, RandomFill, RandomFillGaussianInModulus,
33 RandomFillUniformInModulus, RandomGaussianElementInModulus,
34 },
35 rgsw::{
36 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, public_key_encrypt_rgsw,
37 rgsw_by_rgsw_inplace, rlwe_by_rgsw, secret_key_encrypt_rgsw, IsTrivial, RgswCiphertext,
38 RlweCiphertext, RlweSecret,
39 },
40 utils::{
41 fill_random_ternary_secret_with_hamming_weight, generate_prime, mod_exponent, Global,
42 TryConvertFrom1, WithLocal,
43 },
44 Decryptor, Encryptor, Matrix, MatrixEntity, MatrixMut, MultiPartyDecryptor, Row, RowEntity,
45 RowMut, Secret,
46};
47
48use super::{
49 parameters::{BoolParameters, CiphertextModulus},
50 ClientKey, CommonReferenceSeededCollectivePublicKeyShare,
51 CommonReferenceSeededMultiPartyServerKeyShare, DecompositionCount, DecompostionLogBase,
52 DoubleDecomposerParams, SeededMultiPartyServerKey, SeededNonInteractiveMultiPartyServerKey,
53 SeededSinglePartyServerKey, ServerKeyEvaluationDomain, ShoupServerKeyEvaluationDomain,
54 ThrowMeAwayKey,
55};
56
57pub struct NonInteractiveMultiPartyServerKeyShare<M: Matrix, S> {
58 /// (ak*si + e + \beta ui, ak*si + e)
59 ni_rgsw_cts: (Vec<M>, Vec<M>),
60 ui_to_s_ksk: M,
61 others_ksk_zero_encs: Vec<M>,
62
63 auto_keys_share: HashMap<usize, M>,
64 lwe_ksk_share: M::R,
65
66 user_index: usize,
67 cr_seed: S,
68}
69
70impl<M: Matrix, S> NonInteractiveMultiPartyServerKeyShare<M, S> {
71 fn ui_to_s_ksk_zero_encs_for_user_i(&self, user_i: usize) -> &M {
72 assert!(user_i != self.user_index);
73 if user_i < self.user_index {
74 &self.others_ksk_zero_encs[user_i]
75 } else {
76 &self.others_ksk_zero_encs[user_i - 1]
77 }
78 }
79}
80
81pub struct MultiPartyCrs<S> {
82 pub(super) seed: S,
83}
84
85fn puncture_p_rng<S: Default + Copy, R: RandomFill<S>>(p_rng: &mut R, times: usize) -> S {
86 let mut out = S::default();
87 for _ in 0..times {
88 RandomFill::<S>::random_fill(p_rng, &mut out);
89 }
90 return out;
91}
92
93/// Common reference seed used for non-interactive multi-party.
94///
95/// Initial Seed
96/// Puncture 1 -> Key Seed
97/// Puncture 1 -> Rgsw ciphertext seed
98/// Puncture 2 -> auto keys seed
99/// Puncture 3 -> Lwe key switching key seed
100/// Puncture 2 -> user specific seed for u_j to s ksk
101/// Punture j+1 -> user j's seed
102#[derive(Clone)]
103pub struct NonInteractiveMultiPartyCrs<S> {
104 pub(super) seed: S,
105}
106
107// impl<S: Clone> Clone for NonInteractiveMultiPartyCrs<S> where S: Clone {}
108// impl<S: Copy> Copy for NonInteractiveMultiPartyCrs<S> where S: Copy {}
109
110impl<S: Default + Copy> NonInteractiveMultiPartyCrs<S> {
111 fn key_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
112 let mut p_rng = R::new_with_seed(self.seed);
113 puncture_p_rng(&mut p_rng, 1)
114 }
115
116 pub(crate) fn rgsw_cts_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
117 let key_seed = self.key_seed::<R>();
118 let mut p_rng = R::new_with_seed(key_seed);
119 puncture_p_rng(&mut p_rng, 1)
120 }
121
122 pub(crate) fn auto_keys_cts_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
123 let key_seed = self.key_seed::<R>();
124 let mut p_rng = R::new_with_seed(key_seed);
125 puncture_p_rng(&mut p_rng, 2)
126 }
127
128 pub(crate) fn lwe_ksk_cts_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
129 let key_seed = self.key_seed::<R>();
130 let mut p_rng = R::new_with_seed(key_seed);
131 puncture_p_rng(&mut p_rng, 3)
132 }
133
134 fn ui_to_s_ks_seed<R: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
135 let mut p_rng = R::new_with_seed(self.seed);
136 puncture_p_rng(&mut p_rng, 2)
137 }
138
139 pub(crate) fn ui_to_s_ks_seed_for_user_i<R: NewWithSeed<Seed = S> + RandomFill<S>>(
140 &self,
141 user_i: usize,
142 ) -> S {
143 let ks_seed = self.ui_to_s_ks_seed::<R>();
144 let mut p_rng = R::new_with_seed(ks_seed);
145
146 puncture_p_rng(&mut p_rng, user_i + 1)
147 }
148}
149
150impl<S: Default + Copy> MultiPartyCrs<S> {
151 /// Seed to generate public key share using MultiPartyCrs as the main seed.
152 ///
153 /// Public key seed equals the 1st seed extracted from PRNG Seeded with
154 /// MiltiPartyCrs's seed.
155 pub(super) fn public_key_share_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
156 let mut prng = Rng::new_with_seed(self.seed);
157
158 let mut seed = S::default();
159 RandomFill::<S>::random_fill(&mut prng, &mut seed);
160 seed
161 }
162
163 /// Seed to generate server key share using MultiPartyCrs as the main seed.
164 ///
165 /// Server key seed equals the 2nd seed extracted from PRNG Seeded with
166 /// MiltiPartyCrs's seed.
167 pub(super) fn server_key_share_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
168 let mut prng = Rng::new_with_seed(self.seed);
169
170 let mut seed = S::default();
171 RandomFill::<S>::random_fill(&mut prng, &mut seed);
172 RandomFill::<S>::random_fill(&mut prng, &mut seed);
173 seed
174 }
175}
176
177pub(crate) trait BooleanGates {
178 type Ciphertext: RowEntity;
179 type Key;
180
181 fn and_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
182 fn nand_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
183 fn or_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
184 fn nor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
185 fn xor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
186 fn xnor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
187 fn not_inplace(&mut self, c: &mut Self::Ciphertext);
188
189 fn and(
190 &mut self,
191 c0: &Self::Ciphertext,
192 c1: &Self::Ciphertext,
193 key: &Self::Key,
194 ) -> Self::Ciphertext;
195 fn nand(
196 &mut self,
197 c0: &Self::Ciphertext,
198 c1: &Self::Ciphertext,
199 key: &Self::Key,
200 ) -> Self::Ciphertext;
201 fn or(
202 &mut self,
203 c0: &Self::Ciphertext,
204 c1: &Self::Ciphertext,
205 key: &Self::Key,
206 ) -> Self::Ciphertext;
207 fn nor(
208 &mut self,
209 c0: &Self::Ciphertext,
210 c1: &Self::Ciphertext,
211 key: &Self::Key,
212 ) -> Self::Ciphertext;
213 fn xor(
214 &mut self,
215 c0: &Self::Ciphertext,
216 c1: &Self::Ciphertext,
217 key: &Self::Key,
218 ) -> Self::Ciphertext;
219 fn xnor(
220 &mut self,
221 c0: &Self::Ciphertext,
222 c1: &Self::Ciphertext,
223 key: &Self::Key,
224 ) -> Self::Ciphertext;
225 fn not(&mut self, c: &Self::Ciphertext) -> Self::Ciphertext;
226}
227
228struct ScratchMemory<M>
229where
230 M: Matrix,
231{
232 lwe_vector: M::R,
233 decomposition_matrix: M,
234}
235
236impl<M: MatrixEntity> ScratchMemory<M>
237where
238 M::R: RowEntity,
239{
240 fn new(parameters: &BoolParameters<M::MatElement>) -> Self {
241 // Vector to store LWE ciphertext with LWE dimesnion n
242 let lwe_vector = M::R::zeros(parameters.lwe_n().0 + 1);
243
244 // Matrix to store decomposed polynomials
245 // Max decompistion count + space for temporary RLWE
246 let d = std::cmp::max(
247 parameters.auto_decomposition_count().0,
248 std::cmp::max(
249 parameters.rlwe_rgsw_decomposition_count().0 .0,
250 parameters.rlwe_rgsw_decomposition_count().1 .0,
251 ),
252 ) + 2;
253 let decomposition_matrix = M::zeros(d, parameters.rlwe_n().0);
254
255 Self {
256 lwe_vector,
257 decomposition_matrix,
258 }
259 }
260}
261
262pub(super) trait BoolEncoding {
263 type Element;
264 fn true_el(&self) -> Self::Element;
265 fn false_el(&self) -> Self::Element;
266 fn qby4(&self) -> Self::Element;
267 fn decode(&self, m: Self::Element) -> bool;
268}
269
270impl<T> BoolEncoding for CiphertextModulus<T>
271where
272 CiphertextModulus<T>: Modulus<Element = T>,
273 T: PrimInt,
274{
275 type Element = T;
276
277 fn qby4(&self) -> Self::Element {
278 if self.is_native() {
279 T::one() << (CiphertextModulus::<T>::_bits() - 2)
280 } else {
281 self.q().unwrap() >> 2
282 }
283 }
284 /// Q/8
285 fn true_el(&self) -> Self::Element {
286 if self.is_native() {
287 T::one() << (CiphertextModulus::<T>::_bits() - 3)
288 } else {
289 self.q().unwrap() >> 3
290 }
291 }
292 /// -Q/8
293 fn false_el(&self) -> Self::Element {
294 self.largest_unsigned_value() - self.true_el() + T::one()
295 }
296 fn decode(&self, m: Self::Element) -> bool {
297 let qby8 = self.true_el();
298 let m = (((m + qby8).to_f64().unwrap() * 4.0f64) / self.q_as_f64().unwrap()).round()
299 as usize
300 % 4usize;
301
302 if m == 0 {
303 return false;
304 } else if m == 1 {
305 return true;
306 } else {
307 panic!("Incorrect bool decryption. Got m={m} but expected m to be 0 or 1")
308 }
309 }
310}
311
312pub(super) struct BoolPbsInfo<M: Matrix, Ntt, RlweModOp, LweModOp> {
313 auto_decomposer: DefaultDecomposer<M::MatElement>,
314 rlwe_rgsw_decomposer: (
315 DefaultDecomposer<M::MatElement>,
316 DefaultDecomposer<M::MatElement>,
317 ),
318 lwe_decomposer: DefaultDecomposer<M::MatElement>,
319 g_k_dlog_map: Vec<usize>,
320 rlwe_nttop: Ntt,
321 rlwe_modop: RlweModOp,
322 lwe_modop: LweModOp,
323 embedding_factor: usize,
324 rlwe_qby4: M::MatElement,
325 rlwe_auto_maps: Vec<(Vec<usize>, Vec<bool>)>,
326 parameters: BoolParameters<M::MatElement>,
327}
328
329impl<M: Matrix, NttOp, RlweModOp, LweModOp> PbsInfo for BoolPbsInfo<M, NttOp, RlweModOp, LweModOp>
330where
331 M::MatElement: PrimInt + WrappingSub + NumInfo + FromPrimitive + From<bool> + Display,
332 RlweModOp: ArithmeticOps<Element = M::MatElement> + ShoupMatrixFMA<M::R>,
333 LweModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
334 NttOp: Ntt<Element = M::MatElement>,
335{
336 type M = M;
337 type Modulus = CiphertextModulus<M::MatElement>;
338 type D = DefaultDecomposer<M::MatElement>;
339 type RlweModOp = RlweModOp;
340 type LweModOp = LweModOp;
341 type NttOp = NttOp;
342 fn rlwe_auto_map(&self, k: usize) -> &(Vec<usize>, Vec<bool>) {
343 &self.rlwe_auto_maps[k]
344 }
345 fn br_q(&self) -> usize {
346 *self.parameters.br_q()
347 }
348 fn lwe_decomposer(&self) -> &Self::D {
349 &self.lwe_decomposer
350 }
351 fn rlwe_rgsw_decomposer(&self) -> &(Self::D, Self::D) {
352 &self.rlwe_rgsw_decomposer
353 }
354 fn auto_decomposer(&self) -> &Self::D {
355 &self.auto_decomposer
356 }
357 fn embedding_factor(&self) -> usize {
358 self.embedding_factor
359 }
360 fn g(&self) -> isize {
361 self.parameters.g() as isize
362 }
363 fn w(&self) -> usize {
364 self.parameters.w()
365 }
366 fn g_k_dlog_map(&self) -> &[usize] {
367 &self.g_k_dlog_map
368 }
369 fn lwe_n(&self) -> usize {
370 self.parameters.lwe_n().0
371 }
372 fn lwe_q(&self) -> &Self::Modulus {
373 self.parameters.lwe_q()
374 }
375 fn rlwe_n(&self) -> usize {
376 self.parameters.rlwe_n().0
377 }
378 fn rlwe_q(&self) -> &Self::Modulus {
379 self.parameters.rlwe_q()
380 }
381 fn modop_lweq(&self) -> &Self::LweModOp {
382 &self.lwe_modop
383 }
384 fn modop_rlweq(&self) -> &Self::RlweModOp {
385 &self.rlwe_modop
386 }
387 fn nttop_rlweq(&self) -> &Self::NttOp {
388 &self.rlwe_nttop
389 }
390}
391
392pub(crate) struct BoolEvaluator<M, Ntt, RlweModOp, LweModOp, SKey>
393where
394 M: Matrix,
395{
396 pbs_info: BoolPbsInfo<M, Ntt, RlweModOp, LweModOp>,
397 scratch_memory: ScratchMemory<M>,
398 nand_test_vec: M::R,
399 and_test_vec: M::R,
400 or_test_vec: M::R,
401 nor_test_vec: M::R,
402 xor_test_vec: M::R,
403 xnor_test_vec: M::R,
404 _phantom: PhantomData<SKey>,
405}
406
407impl<M: Matrix, NttOp, RlweModOp, LweModOp, Skey>
408 BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
409{
410 pub(super) fn parameters(&self) -> &BoolParameters<M::MatElement> {
411 &self.pbs_info.parameters
412 }
413
414 pub(super) fn pbs_info(&self) -> &BoolPbsInfo<M, NttOp, RlweModOp, LweModOp> {
415 &self.pbs_info
416 }
417}
418
419fn trim_rgsw_ct_matrix_from_rgrg_to_rlrg<
420 M: MatrixMut + MatrixEntity,
421 D: DoubleDecomposerParams<Count = DecompositionCount>,
422>(
423 rgsw_ct_in: M,
424 rgrg_params: D,
425 rlrg_params: D,
426) -> M
427where
428 M::R: RowMut,
429 M::MatElement: Copy,
430{
431 let (rgswrgsw_d_a, rgswrgsw_d_b) = (
432 rgrg_params.decomposition_count_a(),
433 rgrg_params.decomposition_count_b(),
434 );
435 let (rlrg_d_a, rlrg_d_b) = (
436 rlrg_params.decomposition_count_a(),
437 rlrg_params.decomposition_count_b(),
438 );
439 let rgsw_ct_rows_in = rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 * 2;
440 let rgsw_ct_rows_out = rlrg_d_a.0 * 2 + rlrg_d_b.0 * 2;
441 assert!(rgsw_ct_in.dimension().0 == rgsw_ct_rows_in);
442 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);
443 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);
444
445 let mut reduced_ct_i_out = M::zeros(rgsw_ct_rows_out, rgsw_ct_in.dimension().1);
446
447 // RLWE'(-sm) part A
448 izip!(
449 reduced_ct_i_out.iter_rows_mut().take(rlrg_d_a.0),
450 rgsw_ct_in
451 .iter_rows()
452 .skip(rgswrgsw_d_a.0 - rlrg_d_a.0)
453 .take(rlrg_d_a.0)
454 )
455 .for_each(|(to_ri, from_ri)| {
456 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
457 });
458
459 // RLWE'(-sm) part B
460 izip!(
461 reduced_ct_i_out
462 .iter_rows_mut()
463 .skip(rlrg_d_a.0)
464 .take(rlrg_d_a.0),
465 rgsw_ct_in
466 .iter_rows()
467 .skip(rgswrgsw_d_a.0 + (rgswrgsw_d_a.0 - rlrg_d_a.0))
468 .take(rlrg_d_a.0)
469 )
470 .for_each(|(to_ri, from_ri)| {
471 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
472 });
473
474 // RLWE'(m) Part A
475 izip!(
476 reduced_ct_i_out
477 .iter_rows_mut()
478 .skip(rlrg_d_a.0 * 2)
479 .take(rlrg_d_b.0),
480 rgsw_ct_in
481 .iter_rows()
482 .skip(rgswrgsw_d_a.0 * 2 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
483 .take(rlrg_d_b.0)
484 )
485 .for_each(|(to_ri, from_ri)| {
486 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
487 });
488
489 // RLWE'(m) Part B
490 izip!(
491 reduced_ct_i_out
492 .iter_rows_mut()
493 .skip(rlrg_d_a.0 * 2 + rlrg_d_b.0)
494 .take(rlrg_d_b.0),
495 rgsw_ct_in
496 .iter_rows()
497 .skip(rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
498 .take(rlrg_d_b.0)
499 )
500 .for_each(|(to_ri, from_ri)| {
501 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
502 });
503
504 reduced_ct_i_out
505}
506
507impl<M: Matrix, NttOp, RlweModOp, LweModOp, SKey> BoolEvaluator<M, NttOp, RlweModOp, LweModOp, SKey>
508where
509 M: MatrixEntity + MatrixMut,
510 M::MatElement: PrimInt
511 + Debug
512 + Display
513 + NumInfo
514 + FromPrimitive
515 + WrappingSub
516 + SampleUniform
517 + From<bool>,
518 NttOp: Ntt<Element = M::MatElement>,
519 RlweModOp: ArithmeticOps<Element = M::MatElement>
520 + VectorOps<Element = M::MatElement>
521 + GetModulus<Element = M::MatElement, M = CiphertextModulus<M::MatElement>>
522 + ShoupMatrixFMA<M::R>,
523 LweModOp: ArithmeticOps<Element = M::MatElement>
524 + VectorOps<Element = M::MatElement>
525 + GetModulus<Element = M::MatElement, M = CiphertextModulus<M::MatElement>>,
526 M::R: TryConvertFrom1<[i32], CiphertextModulus<M::MatElement>> + RowEntity + Debug,
527 <M as Matrix>::R: RowMut,
528{
529 pub(super) fn new(parameters: BoolParameters<M::MatElement>) -> Self
530 where
531 RlweModOp: ModInit<M = CiphertextModulus<M::MatElement>>,
532 LweModOp: ModInit<M = CiphertextModulus<M::MatElement>>,
533 NttOp: NttInit<CiphertextModulus<M::MatElement>>,
534 {
535 //TODO(Jay): Run sanity checks for modulus values in parameters
536
537 // generates dlog map s.t. (+/-)g^{k} % q = a, for all a \in Z*_{q} and k \in
538 // [0, q/4). We store the dlog `k` at index `a`. This makes it easier to
539 // simply look up `k` at runtime as vec[a]. If a = g^{k} then dlog is
540 // stored as k. If a = -g^{k} then dlog is stored as k = q/4. This is done to
541 // differentiate sign.
542 let g = parameters.g();
543 let q = *parameters.br_q();
544 let mut g_k_dlog_map = vec![0usize; q];
545 for i in 0..q / 4 {
546 let v = mod_exponent(g as u64, i as u64, q as u64) as usize;
547 // g^i
548 g_k_dlog_map[v] = i;
549 // -(g^i)
550 g_k_dlog_map[q - v] = i + (q / 4);
551 }
552
553 let embedding_factor = (2 * parameters.rlwe_n().0) / q;
554
555 let rlwe_nttop = NttOp::new(parameters.rlwe_q(), parameters.rlwe_n().0);
556 let rlwe_modop = RlweModOp::new(*parameters.rlwe_q());
557 let lwe_modop = LweModOp::new(*parameters.lwe_q());
558
559 let q = *parameters.br_q();
560 let qby2 = q >> 1;
561 let qby8 = q >> 3;
562 // Q/8 (Q: rlwe_q)
563 let true_m_el = parameters.rlwe_q().true_el();
564 // -Q/8
565 let false_m_el = parameters.rlwe_q().false_el();
566 let (auto_map_index, auto_map_sign) = generate_auto_map(qby2, -(g as isize));
567
568 let init_test_vec = |partition_el: usize,
569 before_partition_el: M::MatElement,
570 after_partition_el: M::MatElement| {
571 let mut test_vec = M::R::zeros(qby2);
572 for i in 0..qby2 {
573 if i < partition_el {
574 test_vec.as_mut()[i] = before_partition_el;
575 } else {
576 test_vec.as_mut()[i] = after_partition_el;
577 }
578 }
579
580 // v(X) -> v(X^{-g})
581 let mut test_vec_autog = M::R::zeros(qby2);
582 izip!(
583 test_vec.as_ref().iter(),
584 auto_map_index.iter(),
585 auto_map_sign.iter()
586 )
587 .for_each(|(v, to_index, to_sign)| {
588 if !to_sign {
589 // negate
590 test_vec_autog.as_mut()[*to_index] = rlwe_modop.neg(v);
591 } else {
592 test_vec_autog.as_mut()[*to_index] = *v;
593 }
594 });
595
596 return test_vec_autog;
597 };
598
599 let nand_test_vec = init_test_vec(3 * qby8, true_m_el, false_m_el);
600 let and_test_vec = init_test_vec(3 * qby8, false_m_el, true_m_el);
601 let or_test_vec = init_test_vec(qby8, false_m_el, true_m_el);
602 let nor_test_vec = init_test_vec(qby8, true_m_el, false_m_el);
603 let xor_test_vec = init_test_vec(qby8, false_m_el, true_m_el);
604 let xnor_test_vec = init_test_vec(qby8, true_m_el, false_m_el);
605
606 // auto map indices and sign
607 // Auto maps are stored as [-g, g^{1}, g^{2}, ..., g^{w}]
608 let mut rlwe_auto_maps = vec![];
609 let ring_size = parameters.rlwe_n().0;
610 let g = parameters.g();
611 let br_q = parameters.br_q();
612 let auto_element_dlogs = parameters.auto_element_dlogs();
613 assert!(auto_element_dlogs[0] == 0);
614 for i in auto_element_dlogs.into_iter() {
615 let el = if i == 0 {
616 -(g as isize)
617 } else {
618 (g.pow(i as u32) % br_q) as isize
619 };
620 rlwe_auto_maps.push(generate_auto_map(ring_size, el))
621 }
622
623 let rlwe_qby4 = parameters.rlwe_q().qby4();
624
625 let scratch_memory = ScratchMemory::new(¶meters);
626
627 let pbs_info = BoolPbsInfo {
628 auto_decomposer: parameters.auto_decomposer(),
629 lwe_decomposer: parameters.lwe_decomposer(),
630 rlwe_rgsw_decomposer: parameters.rlwe_rgsw_decomposer(),
631 g_k_dlog_map,
632 embedding_factor,
633 lwe_modop,
634 rlwe_modop,
635 rlwe_nttop,
636 rlwe_qby4,
637 rlwe_auto_maps,
638 parameters: parameters,
639 };
640
641 BoolEvaluator {
642 pbs_info,
643 scratch_memory,
644 nand_test_vec,
645 and_test_vec,
646 or_test_vec,
647 nor_test_vec,
648 xnor_test_vec,
649 xor_test_vec,
650 _phantom: PhantomData,
651 }
652 }
653
654 pub(super) fn client_key(&self) -> ClientKey {
655 let sk_lwe = LweSecret::random(
656 self.pbs_info.parameters.lwe_n().0 >> 1,
657 self.pbs_info.parameters.lwe_n().0,
658 );
659 let sk_rlwe = RlweSecret::random(
660 self.pbs_info.parameters.rlwe_n().0 >> 1,
661 self.pbs_info.parameters.rlwe_n().0,
662 );
663 ClientKey::new(sk_rlwe, sk_lwe)
664 }
665
666 pub(super) fn non_interactive_client_key(&self) -> ThrowMeAwayKey {
667 let sk_lwe = LweSecret::random(
668 self.pbs_info.parameters.lwe_n().0 >> 1,
669 self.pbs_info.parameters.lwe_n().0,
670 );
671 let sk_rlwe = RlweSecret::random(
672 self.pbs_info.parameters.rlwe_n().0 >> 1,
673 self.pbs_info.parameters.rlwe_n().0,
674 );
675 let sk_u_rlwe = RlweSecret::random(
676 self.pbs_info.parameters.rlwe_n().0 >> 1,
677 self.pbs_info.parameters.rlwe_n().0,
678 );
679 ThrowMeAwayKey::new(sk_rlwe, sk_u_rlwe, sk_lwe)
680 }
681
682 pub(super) fn single_party_server_key(
683 &self,
684 client_key: &ClientKey,
685 ) -> SeededSinglePartyServerKey<M, BoolParameters<M::MatElement>, [u8; 32]> {
686 DefaultSecureRng::with_local_mut(|rng| {
687 let mut main_seed = [0u8; 32];
688 rng.fill_bytes(&mut main_seed);
689
690 let mut main_prng = DefaultSecureRng::new_seeded(main_seed);
691
692 let rlwe_n = self.pbs_info.parameters.rlwe_n().0;
693 let sk_rlwe = client_key.sk_rlwe();
694 let sk_lwe = client_key.sk_lwe();
695
696 // generate auto keys
697 let mut auto_keys = HashMap::new();
698 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
699 let g = self.pbs_info.parameters.g();
700 let br_q = self.pbs_info.parameters.br_q();
701 let auto_els = self.pbs_info.parameters.auto_element_dlogs();
702 for i in auto_els.into_iter() {
703 let g_pow = if i == 0 {
704 -(g as isize)
705 } else {
706 (g.pow(i as u32) % br_q) as isize
707 };
708 let mut gk = M::zeros(self.pbs_info.auto_decomposer.decomposition_count(), rlwe_n);
709 galois_key_gen(
710 &mut gk,
711 sk_rlwe.values(),
712 g_pow,
713 &auto_gadget,
714 &self.pbs_info.rlwe_modop,
715 &self.pbs_info.rlwe_nttop,
716 &mut main_prng,
717 rng,
718 );
719 auto_keys.insert(i, gk);
720 }
721
722 // generate rgsw ciphertexts RGSW(si) where si is i^th LWE secret element
723 let ring_size = self.pbs_info.parameters.rlwe_n().0;
724 let rlwe_q = self.pbs_info.parameters.rlwe_q();
725 let (rlrg_d_a, rlrg_d_b) = (
726 self.pbs_info.rlwe_rgsw_decomposer.0.decomposition_count(),
727 self.pbs_info.rlwe_rgsw_decomposer.1.decomposition_count(),
728 );
729 let rlrg_gadget_a = self.pbs_info.rlwe_rgsw_decomposer.0.gadget_vector();
730 let rlrg_gadget_b = self.pbs_info.rlwe_rgsw_decomposer.1.gadget_vector();
731 let rgsw_cts = sk_lwe
732 .values()
733 .iter()
734 .map(|si| {
735 // X^{si}; assume |emebedding_factor * si| < N
736 let mut m = M::R::zeros(ring_size);
737 let si = (self.pbs_info.embedding_factor as i32) * si;
738 // dbg!(si);
739 if si < 0 {
740 // X^{-i} = X^{2N - i} = -X^{N-i}
741 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q.neg_one();
742 } else {
743 // X^{i}
744 m.as_mut()[si.abs() as usize] = M::MatElement::one();
745 }
746
747 let mut rgsw_si = M::zeros(rlrg_d_a * 2 + rlrg_d_b, ring_size);
748 secret_key_encrypt_rgsw(
749 &mut rgsw_si,
750 m.as_ref(),
751 &rlrg_gadget_a,
752 &rlrg_gadget_b,
753 sk_rlwe.values(),
754 &self.pbs_info.rlwe_modop,
755 &self.pbs_info.rlwe_nttop,
756 &mut main_prng,
757 rng,
758 );
759
760 rgsw_si
761 })
762 .collect_vec();
763
764 // LWE KSK from RLWE secret s -> LWE secret z
765 let d_lwe_gadget = self.pbs_info.lwe_decomposer.gadget_vector();
766 let mut lwe_ksk =
767 M::R::zeros(self.pbs_info.lwe_decomposer.decomposition_count() * ring_size);
768 lwe_ksk_keygen(
769 &sk_rlwe.values(),
770 &sk_lwe.values(),
771 &mut lwe_ksk,
772 &d_lwe_gadget,
773 &self.pbs_info.lwe_modop,
774 &mut main_prng,
775 rng,
776 );
777
778 SeededSinglePartyServerKey::from_raw(
779 auto_keys,
780 rgsw_cts,
781 lwe_ksk,
782 self.pbs_info.parameters.clone(),
783 main_seed,
784 )
785 })
786 }
787
788 pub(super) fn multi_party_server_key_share(
789 &self,
790 cr_seed: [u8; 32],
791 collective_pk: &M,
792 client_key: &ClientKey,
793 ) -> CommonReferenceSeededMultiPartyServerKeyShare<M, BoolParameters<M::MatElement>, [u8; 32]>
794 {
795 DefaultSecureRng::with_local_mut(|rng| {
796 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
797
798 let sk_rlwe = client_key.sk_rlwe();
799 let sk_lwe = client_key.sk_lwe();
800
801 let g = self.pbs_info.parameters.g();
802 let ring_size = self.pbs_info.parameters.rlwe_n().0;
803 let rlwe_q = self.pbs_info.parameters.rlwe_q();
804 let lwe_q = self.pbs_info.parameters.lwe_q();
805
806 let rlweq_modop = &self.pbs_info.rlwe_modop;
807 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
808
809 // sanity check
810 assert!(sk_rlwe.values().len() == ring_size);
811 assert!(sk_lwe.values().len() == self.pbs_info.parameters.lwe_n().0);
812
813 // auto keys
814 let mut auto_keys = HashMap::new();
815 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
816 let auto_element_dlogs = self.pbs_info.parameters.auto_element_dlogs();
817 let br_q = self.pbs_info.parameters.br_q();
818 for i in auto_element_dlogs.into_iter() {
819 let g_pow = if i == 0 {
820 -(g as isize)
821 } else {
822 (g.pow(i as u32) % br_q) as isize
823 };
824
825 let mut ksk_out = M::zeros(
826 self.pbs_info.auto_decomposer.decomposition_count(),
827 ring_size,
828 );
829 galois_key_gen(
830 &mut ksk_out,
831 sk_rlwe.values(),
832 g_pow,
833 &auto_gadget,
834 rlweq_modop,
835 rlweq_nttop,
836 &mut main_prng,
837 rng,
838 );
839 auto_keys.insert(i, ksk_out);
840 }
841
842 // rgsw ciphertexts of lwe secret elements
843 let rgsw_rgsw_decomposer = self
844 .pbs_info
845 .parameters
846 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
847 let (rgrg_d_a, rgrg_d_b) = (
848 rgsw_rgsw_decomposer.0.decomposition_count(),
849 rgsw_rgsw_decomposer.1.decomposition_count(),
850 );
851 let (rgrg_gadget_a, rgrg_gadget_b) = (
852 rgsw_rgsw_decomposer.0.gadget_vector(),
853 rgsw_rgsw_decomposer.1.gadget_vector(),
854 );
855 let rgsw_cts = sk_lwe
856 .values()
857 .iter()
858 .map(|si| {
859 let mut m = M::R::zeros(ring_size);
860 //TODO(Jay): It will be nice to have a function that returns polynomial
861 // (monomial infact!) corresponding to secret element embedded in ring X^{2N+1}.
862 // Save lots of mistakes where one forgest to emebed si in bigger ring.
863 let si = *si * (self.pbs_info.embedding_factor as i32);
864 if si < 0 {
865 // X^{-si} = X^{2N-si} = -X^{N-si}, assuming abs(si) < N
866 // (which it is given si is secret element)
867 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q.neg_one();
868 } else {
869 m.as_mut()[si as usize] = M::MatElement::one();
870 }
871
872 // public key RGSW encryption has no part that can be seeded, unlike secret key
873 // RGSW encryption where RLWE'_A(m) is seeded
874 let mut out_rgsw = M::zeros(rgrg_d_a * 2 + rgrg_d_b * 2, ring_size);
875 public_key_encrypt_rgsw(
876 &mut out_rgsw,
877 &m.as_ref(),
878 collective_pk,
879 &rgrg_gadget_a,
880 &rgrg_gadget_b,
881 rlweq_modop,
882 rlweq_nttop,
883 rng,
884 );
885
886 out_rgsw
887 })
888 .collect_vec();
889
890 // LWE ksk
891 let mut lwe_ksk =
892 M::R::zeros(self.pbs_info.lwe_decomposer.decomposition_count() * ring_size);
893 let lwe_modop = &self.pbs_info.lwe_modop;
894 let d_lwe_gadget_vec = self.pbs_info.lwe_decomposer.gadget_vector();
895 lwe_ksk_keygen(
896 sk_rlwe.values(),
897 sk_lwe.values(),
898 &mut lwe_ksk,
899 &d_lwe_gadget_vec,
900 lwe_modop,
901 &mut main_prng,
902 rng,
903 );
904
905 CommonReferenceSeededMultiPartyServerKeyShare::new(
906 rgsw_cts,
907 auto_keys,
908 lwe_ksk,
909 cr_seed,
910 self.pbs_info.parameters.clone(),
911 )
912 })
913 }
914
915 pub(super) fn aggregate_non_interactive_multi_party_key_share(
916 &self,
917 cr_seed: &NonInteractiveMultiPartyCrs<[u8; 32]>,
918 total_users: usize,
919 key_shares: &[NonInteractiveMultiPartyServerKeyShare<
920 M,
921 NonInteractiveMultiPartyCrs<[u8; 32]>,
922 >],
923 ) -> SeededNonInteractiveMultiPartyServerKey<
924 M,
925 NonInteractiveMultiPartyCrs<[u8; 32]>,
926 BoolParameters<M::MatElement>,
927 >
928 where
929 M: Clone + Debug,
930 {
931 // sanity checks
932 let key_order = {
933 let existing_key_order = key_shares.iter().map(|s| s.user_index).collect_vec();
934
935 // record the order s.t. key_order[i] stores the position of i^th
936 // users key share in existing order
937 let mut key_order = Vec::with_capacity(existing_key_order.len());
938 (0..total_users).map(|i| {
939 // find i
940 let index = existing_key_order
941 .iter()
942 .position(|x| x == &i)
943 .expect(&format!("Missing user {i}'s key!"));
944 key_order.push(index);
945 });
946
947 key_order
948 };
949
950 let rlwe_modop = &self.pbs_info().rlwe_modop;
951 let nttop = &self.pbs_info().rlwe_nttop;
952 let ring_size = self.parameters().rlwe_n().0;
953 let rlwe_q = self.parameters().rlwe_q();
954 let lwe_modop = self.pbs_info().modop_lweq();
955
956 // genrate key switching key from u_i to s
957 let ui_to_s_ksk_decomposition_count = self
958 .parameters()
959 .non_interactive_ui_to_s_key_switch_decomposition_count();
960 let mut ui_to_s_ksks = key_shares
961 .iter()
962 .map(|share| {
963 let mut useri_ui_to_s_ksk = share.ui_to_s_ksk.clone();
964 assert!(
965 useri_ui_to_s_ksk.dimension() == (ui_to_s_ksk_decomposition_count.0, ring_size)
966 );
967 key_shares
968 .iter()
969 .filter(|x| x.user_index != share.user_index)
970 .for_each(|(other_share)| {
971 let op2 = other_share.ui_to_s_ksk_zero_encs_for_user_i(share.user_index);
972 assert!(op2.dimension() == (ui_to_s_ksk_decomposition_count.0, ring_size));
973 izip!(useri_ui_to_s_ksk.iter_rows_mut(), op2.iter_rows()).for_each(
974 |(add_to, add_from)| {
975 rlwe_modop.elwise_add_mut(add_to.as_mut(), add_from.as_ref())
976 },
977 );
978 });
979 useri_ui_to_s_ksk
980 })
981 .collect_vec();
982
983 let rgsw_cts = {
984 let mut rgsw_prng =
985 DefaultSecureRng::new_seeded(cr_seed.rgsw_cts_seed::<DefaultSecureRng>());
986
987 let rgsw_by_rgsw_decomposer = self
988 .parameters()
989 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
990
991 // Generate RGSW Cts
992 let rgsw_cts_all_users_eval = {
993 // temporarily put ui_to_s in evaluation domain and sample a_i's for u_i to s
994 // ksk for upcomong key switches
995 ui_to_s_ksks.iter_mut().for_each(|ksk_i| {
996 ksk_i
997 .iter_rows_mut()
998 .for_each(|r| nttop.forward(r.as_mut()))
999 });
1000 let ui_to_s_ksks_part_a_eval = key_shares
1001 .iter()
1002 .map(|share| {
1003 let mut ksk_prng = DefaultSecureRng::new_seeded(
1004 cr_seed
1005 .ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(share.user_index),
1006 );
1007 let mut ais = M::zeros(ui_to_s_ksk_decomposition_count.0, ring_size);
1008
1009 ais.iter_rows_mut().for_each(|r_ai| {
1010 RandomFillUniformInModulus::random_fill(
1011 &mut ksk_prng,
1012 rlwe_q,
1013 r_ai.as_mut(),
1014 );
1015
1016 nttop.forward(r_ai.as_mut())
1017 });
1018 ais
1019 })
1020 .collect_vec();
1021
1022 let max_rgrg_deocmposer = if rgsw_by_rgsw_decomposer.a().decomposition_count()
1023 > rgsw_by_rgsw_decomposer.b().decomposition_count()
1024 {
1025 rgsw_by_rgsw_decomposer.a()
1026 } else {
1027 rgsw_by_rgsw_decomposer.b()
1028 };
1029
1030 let ui_to_s_ksk_decomposer = self
1031 .parameters()
1032 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>(
1033 );
1034
1035 // Generate a_i*s + E = \sum_{j \in P} a_i*s_j + e for all rlwes in each
1036 // non-interactive rgsws. Then decompose and put decompositions in evaluation
1037 // for u_i -> s key switch.
1038 let decomp_ni_rgsws_part_1_acc = {
1039 let mut tmp_space = M::R::zeros(ring_size);
1040
1041 (0..self.parameters().lwe_n().0)
1042 .into_iter()
1043 .map(|lwe_index| {
1044 (0..max_rgrg_deocmposer.decomposition_count())
1045 .into_iter()
1046 .map(|d_index| {
1047 let mut sum = M::zeros(
1048 ui_to_s_ksk_decomposer.decomposition_count(),
1049 ring_size,
1050 );
1051
1052 // set temp_space to all zeros
1053 tmp_space.as_mut().fill(M::MatElement::zero());
1054
1055 // a_i*s + E
1056 key_shares.iter().for_each(|s| {
1057 rlwe_modop.elwise_add_mut(
1058 tmp_space.as_mut(),
1059 s.ni_rgsw_cts.1[lwe_index].get_row_slice(d_index),
1060 );
1061 });
1062
1063 tmp_space.as_ref().iter().enumerate().for_each(|(ri, el)| {
1064 ui_to_s_ksk_decomposer
1065 .decompose_iter(el)
1066 .enumerate()
1067 .for_each(|(row_j, d_el)| {
1068 (sum.as_mut()[row_j]).as_mut()[ri] = d_el;
1069 });
1070 });
1071
1072 sum.iter_rows_mut().for_each(|r| nttop.forward(r.as_mut()));
1073
1074 sum
1075 })
1076 .collect_vec()
1077 })
1078 .collect_vec()
1079 };
1080
1081 // Sample a_i's are used to generate non-interactive rgsw cts for all lwe
1082 // indices. Since a_i are just needed for key switches , decompose them
1083 // and put them in evaluation domain
1084 // Decomposition count used for RGSW ct in non-interactive key share gen equals
1085 // max of A and B decomposition required in RGSWxRGSW. This is because same
1086 // polynomials are used to generate RLWE'(m) and RLWE'(-sm)
1087 let decomp_ni_rgsw_neg_ais = {
1088 let mut tmp_space = M::R::zeros(ring_size);
1089 (0..self.parameters().lwe_n().0)
1090 .into_iter()
1091 .map(|_| {
1092 // FIXME(Jay): well well, ais are only required for key switching to
1093 // generate RLWE'(m) and RLWE'(m) itself
1094 // requires RLWE(\beta^i m) for i \in RGSWxRGSW
1095 // part B decomposition count. However, we still need to puncture prng
1096 // for ais corresponding to ignored limbs.
1097 // Probably it will be nice idea to
1098 // avoid decomposition after punturing for a_i's corresponding to
1099 // ignored limbs. Moreover, note that, for
1100 // RGSWxRGSW often times decompostion count for part A
1101 // > part B. Hence, it's very likely that we are doing
1102 // unecesary decompositions for ignored limbs all the time.
1103 (0..max_rgrg_deocmposer.decomposition_count())
1104 .map(|_| {
1105 RandomFillUniformInModulus::random_fill(
1106 &mut rgsw_prng,
1107 rlwe_q,
1108 tmp_space.as_mut(),
1109 );
1110
1111 // negate
1112 rlwe_modop.elwise_neg_mut(tmp_space.as_mut());
1113
1114 // decomposer a_i for ui -> s key switch
1115 let mut decomp_neg_ai = M::zeros(
1116 ui_to_s_ksk_decomposer.decomposition_count(),
1117 ring_size,
1118 );
1119 tmp_space.as_ref().iter().enumerate().for_each(
1120 |(index, el)| {
1121 ui_to_s_ksk_decomposer
1122 .decompose_iter(el)
1123 .enumerate()
1124 .for_each(|(row_j, d_el)| {
1125 (decomp_neg_ai.as_mut()[row_j]).as_mut()
1126 [index] = d_el;
1127 });
1128 },
1129 );
1130
1131 // put in evaluation domain
1132 decomp_neg_ai
1133 .iter_rows_mut()
1134 .for_each(|r| nttop.forward(r.as_mut()));
1135
1136 decomp_neg_ai
1137 })
1138 .collect_vec()
1139 })
1140 .collect_vec()
1141 };
1142
1143 // genrate RGSW cts
1144 let rgsw_cts_all_users_eval = izip!(
1145 key_shares.iter(),
1146 ui_to_s_ksks.iter(),
1147 ui_to_s_ksks_part_a_eval.iter()
1148 )
1149 .map(
1150 |(share, user_uitos_ksk_partb_eval, user_uitos_ksk_parta_eval)| {
1151 // RGSW_s(X^{s[i]})
1152 let rgsw_cts_user_i_eval = izip!(
1153 share.ni_rgsw_cts.0.iter(),
1154 decomp_ni_rgsw_neg_ais.iter(),
1155 decomp_ni_rgsws_part_1_acc.iter()
1156 )
1157 .map(
1158 |(
1159 m_encs_under_ui,
1160 decomposed_rgsw_i_neg_ais,
1161 decomposed_acc_rgsw_part1,
1162 )| {
1163 let d_a = rgsw_by_rgsw_decomposer.a().decomposition_count();
1164 let d_b = rgsw_by_rgsw_decomposer.b().decomposition_count();
1165 let max_d = std::cmp::max(d_a, d_b);
1166
1167 assert!(decomposed_rgsw_i_neg_ais.len() == max_d);
1168
1169 // To be RGSW(X^{s[i]}) = [RLWE'(-sm), RLWE'(m)]
1170 let mut rgsw_ct_eval = M::zeros(d_a * 2 + d_b * 2, ring_size);
1171 let (rlwe_dash_nsm, rlwe_dash_m) =
1172 rgsw_ct_eval.split_at_row_mut(d_a * 2);
1173
1174 let mut scratch_row = M::R::zeros(ring_size);
1175
1176 let mut m_encs_under_ui_eval = m_encs_under_ui.clone();
1177 m_encs_under_ui_eval
1178 .iter_rows_mut()
1179 .for_each(|r| nttop.forward(r.as_mut()));
1180
1181 // RLWE(-sm)
1182 {
1183 // Recall that we have RLWE(a_i * s + e). We key
1184 // switch RLWE(a_i * s + e) using ksk(u_i -> s) to
1185 // get RLWE(a_i*s*u_i + e*u_i).
1186 // Given (u_i * a_i + e + \beta m), we obtain
1187 // RLWE(-sm) = RLWE(a_i*s*u_i + e*u_i) + (0, (u_i *
1188 // a_i + e + \beta m))
1189 //
1190 // Again RLWE'(-sm) only cares for RLWE(\beta -sm)
1191 // with scaling factor \beta corresponding to most
1192 // signficant d_a limbs. Hence, we skip (d_max -
1193 // d_a) least signficant limbs
1194
1195 let (rlwe_dash_neg_sm_part_a, rlwe_dash_neg_sm_part_b) =
1196 rlwe_dash_nsm.split_at_mut(d_a);
1197
1198 izip!(
1199 rlwe_dash_neg_sm_part_a.iter_mut(),
1200 rlwe_dash_neg_sm_part_b.iter_mut(),
1201 decomposed_acc_rgsw_part1.iter().skip(max_d - d_a),
1202 m_encs_under_ui_eval.iter_rows().skip(max_d - d_a)
1203 )
1204 .for_each(
1205 |(rlwe_a, rlwe_b, decomp_ai_s, beta_m_enc_ui)| {
1206 // RLWE_s(a_i * s * u_i + u_i * e) = decomp<a_i * s + e>
1207 // * ksk(u_i
1208 // -> s)
1209 izip!(
1210 decomp_ai_s.iter_rows(),
1211 user_uitos_ksk_partb_eval.iter_rows(),
1212 user_uitos_ksk_parta_eval.iter_rows()
1213 )
1214 .for_each(
1215 |(a0, part_b, part_a)| {
1216 // rlwe_b += decomp<a_i * s + e>[i] * ksk
1217 // part_b[i]
1218 rlwe_modop.elwise_mul(
1219 scratch_row.as_mut(),
1220 a0.as_ref(),
1221 part_b.as_ref(),
1222 );
1223 rlwe_modop.elwise_add_mut(
1224 rlwe_b.as_mut(),
1225 scratch_row.as_ref(),
1226 );
1227
1228 // rlwe_a += decomp<a_i * s + e>[i] * ksk
1229 // part_a[i]
1230 rlwe_modop.elwise_mul(
1231 scratch_row.as_mut(),
1232 a0.as_ref(),
1233 part_a.as_ref(),
1234 );
1235 rlwe_modop.elwise_add_mut(
1236 rlwe_a.as_mut(),
1237 scratch_row.as_ref(),
1238 );
1239 },
1240 );
1241
1242 // RLWE_s(-sm) = RLWE_s(a_i * s * u_i + u_i
1243 // * e) + (0, a_i * u + e + m)
1244 rlwe_modop.elwise_add_mut(
1245 rlwe_a.as_mut(),
1246 beta_m_enc_ui.as_ref(),
1247 );
1248 },
1249 );
1250 }
1251
1252 // RLWE(m)
1253 {
1254 // Routine:
1255 // Let RLWE(-a_i * u_i) = (decomp<-a_i> \cdot ksk(u_i -> s)),
1256 // then RLWE(m) = RLWE(a'*s + e + m) = (a_i
1257 // * u_i + e + m, 0) + RLWE(-a_i * u_i)
1258 //
1259 // Since RLWE'(m) only cares for RLWE ciphertexts corresponding
1260 // to higher d_b limbs, we skip routine 1 for lower max(d_a,
1261 // d_b) - d_b limbs
1262 let (rlwe_dash_m_part_a, rlwe_dash_m_part_b) =
1263 rlwe_dash_m.split_at_mut(d_b);
1264
1265 izip!(
1266 rlwe_dash_m_part_a.iter_mut(),
1267 rlwe_dash_m_part_b.iter_mut(),
1268 decomposed_rgsw_i_neg_ais.iter().skip(max_d - d_b),
1269 m_encs_under_ui_eval.iter_rows().skip(max_d - d_b)
1270 )
1271 .for_each(
1272 |(rlwe_a, rlwe_b, decomp_neg_ai, beta_m_enc_ui)| {
1273 // RLWE_s(-a_i * ui) = decomp<-a_i> \cdot ksk(ui -> s)
1274 izip!(
1275 decomp_neg_ai.iter_rows(),
1276 user_uitos_ksk_partb_eval.iter_rows(),
1277 user_uitos_ksk_parta_eval.iter_rows()
1278 )
1279 .for_each(
1280 |(a0, part_b, part_a)| {
1281 // rlwe_b += decomp<a>[i] * ksk part_b[i]
1282 rlwe_modop.elwise_mul(
1283 scratch_row.as_mut(),
1284 a0.as_ref(),
1285 part_b.as_ref(),
1286 );
1287 rlwe_modop.elwise_add_mut(
1288 rlwe_b.as_mut(),
1289 scratch_row.as_ref(),
1290 );
1291
1292 // rlwe_a += decomp<a>[i] * ksk
1293 // part_a[i]
1294 rlwe_modop.elwise_mul(
1295 scratch_row.as_mut(),
1296 a0.as_ref(),
1297 part_a.as_ref(),
1298 );
1299 rlwe_modop.elwise_add_mut(
1300 rlwe_a.as_mut(),
1301 scratch_row.as_ref(),
1302 );
1303 },
1304 );
1305
1306 // RLWE_s(m) = (a_i * ui + e + \beta m, 0)
1307 // +
1308 // RLWE_s(-a_i * ui)
1309 rlwe_modop.elwise_add_mut(
1310 rlwe_b.as_mut(),
1311 beta_m_enc_ui.as_ref(),
1312 );
1313 },
1314 );
1315 }
1316
1317 rgsw_ct_eval
1318 },
1319 )
1320 .collect_vec();
1321 rgsw_cts_user_i_eval
1322 },
1323 )
1324 .collect_vec();
1325
1326 // put u_i -> s ksks back in coefficient domain
1327 ui_to_s_ksks.iter_mut().for_each(|ksk_i| {
1328 ksk_i
1329 .iter_rows_mut()
1330 .for_each(|r| nttop.backward(r.as_mut()))
1331 });
1332
1333 rgsw_cts_all_users_eval
1334 };
1335
1336 // RGSW x RGSW
1337 let lwe_n = self.parameters().lwe_n().0;
1338 let mut scratch_matrix = M::zeros(
1339 std::cmp::max(
1340 rgsw_by_rgsw_decomposer.a().decomposition_count(),
1341 rgsw_by_rgsw_decomposer.b().decomposition_count(),
1342 ) + (rgsw_by_rgsw_decomposer.a().decomposition_count() * 2
1343 + rgsw_by_rgsw_decomposer.b().decomposition_count() * 2),
1344 ring_size,
1345 );
1346 let rgsw_cts_untrimmed = (0..lwe_n).map(|s_index| {
1347 // copy over s_index^th rgsw ct of user 0. Use it to accumulate RGSW products of
1348 // all RGSW ciphertexts at s_index
1349 let mut rgsw_i = rgsw_cts_all_users_eval[0][s_index].clone();
1350 rgsw_i
1351 .iter_rows_mut()
1352 .for_each(|r| nttop.backward(r.as_mut()));
1353
1354 rgsw_cts_all_users_eval
1355 .iter()
1356 .skip(1)
1357 .for_each(|user_i_rgsws| {
1358 rgsw_by_rgsw_inplace(
1359 &mut rgsw_i,
1360 &user_i_rgsws[s_index],
1361 &rgsw_by_rgsw_decomposer,
1362 &mut scratch_matrix,
1363 nttop,
1364 rlwe_modop,
1365 );
1366 });
1367
1368 rgsw_i
1369 });
1370
1371 // After this point we don't require RGSW cts for RGSWxRGSW
1372 // multiplicaiton anymore. So we trim them to suit RLWExRGSW require for PBS
1373 let rgsw_cts = rgsw_cts_untrimmed
1374 .map(|rgsw_ct| {
1375 trim_rgsw_ct_matrix_from_rgrg_to_rlrg(
1376 rgsw_ct,
1377 self.parameters().rgsw_by_rgsw_decomposition_params(),
1378 self.parameters().rlwe_by_rgsw_decomposition_params(),
1379 )
1380 })
1381 .collect_vec();
1382 rgsw_cts
1383 };
1384
1385 // auto keys
1386 let auto_keys = {
1387 let mut auto_keys = HashMap::new();
1388 let auto_elements_dlog = self.parameters().auto_element_dlogs();
1389 for i in auto_elements_dlog.into_iter() {
1390 let mut key = M::zeros(self.parameters().auto_decomposition_count().0, ring_size);
1391
1392 key_shares.iter().for_each(|s| {
1393 let auto_key_share_i = s.auto_keys_share.get(&i).expect("Auto key {i} missing");
1394 assert!(
1395 auto_key_share_i.dimension()
1396 == (self.parameters().auto_decomposition_count().0, ring_size)
1397 );
1398 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
1399 |(partb_out, partb_share)| {
1400 rlwe_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
1401 },
1402 );
1403 });
1404
1405 auto_keys.insert(i, key);
1406 }
1407 auto_keys
1408 };
1409
1410 // LWE ksk
1411 let lwe_ksk = {
1412 let mut lwe_ksk =
1413 M::R::zeros(self.parameters().lwe_decomposition_count().0 * ring_size);
1414 key_shares.iter().for_each(|s| {
1415 assert!(
1416 s.lwe_ksk_share.as_ref().len()
1417 == self.parameters().lwe_decomposition_count().0 * ring_size
1418 );
1419 lwe_modop.elwise_add_mut(lwe_ksk.as_mut(), s.lwe_ksk_share.as_ref());
1420 });
1421 lwe_ksk
1422 };
1423
1424 SeededNonInteractiveMultiPartyServerKey::new(
1425 ui_to_s_ksks,
1426 key_order,
1427 rgsw_cts,
1428 auto_keys,
1429 lwe_ksk,
1430 cr_seed.clone(),
1431 self.parameters().clone(),
1432 )
1433 }
1434
1435 pub(super) fn non_interactive_multi_party_key_share(
1436 &self,
1437 // TODO(Jay): Should get a common reference seed here and derive the rest.
1438 cr_seed: &NonInteractiveMultiPartyCrs<[u8; 32]>,
1439 self_index: usize,
1440 total_users: usize,
1441 client_key: &ThrowMeAwayKey,
1442 ) -> NonInteractiveMultiPartyServerKeyShare<M, NonInteractiveMultiPartyCrs<[u8; 32]>> {
1443 // TODO: check whether parameters support `total_users`
1444 let nttop = self.pbs_info().nttop_rlweq();
1445 let rlwe_modop = self.pbs_info().modop_rlweq();
1446 let ring_size = self.pbs_info().rlwe_n();
1447 let rlwe_q = self.parameters().rlwe_q();
1448
1449 let (ui_to_s_ksk, zero_encs_for_others) = DefaultSecureRng::with_local_mut(|rng| {
1450 // ui_to_s_ksk
1451 let non_interactive_decomposer = self
1452 .parameters()
1453 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>(
1454 );
1455 let non_interactive_gadget_vec = non_interactive_decomposer.gadget_vector();
1456 let ui_to_s_ksk = {
1457 let mut p_rng = DefaultSecureRng::new_seeded(
1458 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(self_index),
1459 );
1460
1461 non_interactive_ksk_gen::<M, _, _, _, _, _>(
1462 client_key.sk_rlwe().values(),
1463 client_key.sk_u_rlwe().values(),
1464 &non_interactive_gadget_vec,
1465 &mut p_rng,
1466 rng,
1467 nttop,
1468 rlwe_modop,
1469 )
1470 };
1471
1472 // zero encryptions for others uj_to_s ksk
1473 let all_users_except_self = (0..total_users).filter(|x| *x != self_index);
1474 let zero_encs_for_others = all_users_except_self
1475 .map(|other_user_index| {
1476 let mut p_rng = DefaultSecureRng::new_seeded(
1477 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(other_user_index),
1478 );
1479 let zero_encs =
1480 non_interactive_ksk_zero_encryptions_for_other_party_i::<M, _, _, _, _, _>(
1481 client_key.sk_rlwe().values(),
1482 &non_interactive_gadget_vec,
1483 &mut p_rng,
1484 rng,
1485 nttop,
1486 rlwe_modop,
1487 );
1488 zero_encs
1489 })
1490 .collect_vec();
1491
1492 (ui_to_s_ksk, zero_encs_for_others)
1493 });
1494
1495 // Non-interactive RGSW cts = (a_i * u_j + e + \beta X^{s[i]}, a_i * s_j + e')
1496 let ni_rgsw_cts = DefaultSecureRng::with_local_mut(|rng| {
1497 let mut rgsw_cts_prng =
1498 DefaultSecureRng::new_seeded(cr_seed.rgsw_cts_seed::<DefaultSecureRng>());
1499 // generate non-interactive rgsw cts
1500 let rgsw_by_rgsw_decomposer = self
1501 .parameters()
1502 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1503
1504 let ni_rgrg_gadget_vec = {
1505 if rgsw_by_rgsw_decomposer.a().decomposition_count()
1506 > rgsw_by_rgsw_decomposer.b().decomposition_count()
1507 {
1508 rgsw_by_rgsw_decomposer.a().gadget_vector()
1509 } else {
1510 rgsw_by_rgsw_decomposer.b().gadget_vector()
1511 }
1512 };
1513 let ni_rgsw_cts: (Vec<M>, Vec<M>) = client_key
1514 .sk_lwe()
1515 .values()
1516 .iter()
1517 .map(|s_i| {
1518 // X^{s[i]}
1519 let mut m = M::R::zeros(ring_size);
1520 let s_i = s_i * (self.pbs_info().embedding_factor() as i32);
1521 if s_i < 0 {
1522 // X^{-s[i]} -> -X^{N+s[i]}
1523 m.as_mut()[ring_size - (s_i.abs() as usize)] = rlwe_q.neg_one();
1524 } else {
1525 m.as_mut()[s_i as usize] = M::MatElement::one();
1526 }
1527
1528 non_interactive_rgsw_ct::<M, _, _, _, _, _>(
1529 client_key.sk_rlwe().values(),
1530 client_key.sk_u_rlwe().values(),
1531 m.as_ref(),
1532 &ni_rgrg_gadget_vec,
1533 &mut rgsw_cts_prng,
1534 rng,
1535 nttop,
1536 rlwe_modop,
1537 )
1538 })
1539 .unzip();
1540 ni_rgsw_cts
1541 });
1542
1543 // Auto key share
1544 let auto_keys_share = {
1545 let auto_seed = cr_seed.auto_keys_cts_seed::<DefaultSecureRng>();
1546 self._common_rountine_multi_party_auto_keys_share_gen(auto_seed, client_key.sk_rlwe())
1547 };
1548
1549 // Lwe Ksk share
1550 let lwe_ksk_share = {
1551 let lwe_ksk_seed = cr_seed.lwe_ksk_cts_seed::<DefaultSecureRng>();
1552 self._common_rountine_multi_party_lwe_ksk_share_gen(
1553 lwe_ksk_seed,
1554 client_key.sk_rlwe(),
1555 client_key.sk_lwe(),
1556 )
1557 };
1558
1559 NonInteractiveMultiPartyServerKeyShare {
1560 ni_rgsw_cts,
1561 ui_to_s_ksk,
1562 others_ksk_zero_encs: zero_encs_for_others,
1563 user_index: self_index,
1564 auto_keys_share,
1565 lwe_ksk_share,
1566 cr_seed: cr_seed.clone(),
1567 }
1568 }
1569
1570 fn _common_rountine_multi_party_auto_keys_share_gen(
1571 &self,
1572 auto_seed: <DefaultSecureRng as NewWithSeed>::Seed,
1573 sk_rlwe: &RlweSecret,
1574 ) -> HashMap<usize, M> {
1575 let g = self.pbs_info.parameters.g();
1576 let ring_size = self.pbs_info.parameters.rlwe_n().0;
1577 let br_q = self.pbs_info.parameters.br_q();
1578 let rlweq_modop = &self.pbs_info.rlwe_modop;
1579 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1580
1581 DefaultSecureRng::with_local_mut(|rng| {
1582 let mut p_rng = DefaultSecureRng::new_seeded(auto_seed);
1583
1584 let mut auto_keys = HashMap::new();
1585 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
1586 let auto_element_dlogs = self.pbs_info.parameters.auto_element_dlogs();
1587
1588 for i in auto_element_dlogs.into_iter() {
1589 let g_pow = if i == 0 {
1590 -(g as isize)
1591 } else {
1592 (g.pow(i as u32) % br_q) as isize
1593 };
1594
1595 let mut ksk_out = M::zeros(
1596 self.pbs_info.auto_decomposer.decomposition_count(),
1597 ring_size,
1598 );
1599 galois_key_gen(
1600 &mut ksk_out,
1601 sk_rlwe.values(),
1602 g_pow,
1603 &auto_gadget,
1604 rlweq_modop,
1605 rlweq_nttop,
1606 &mut p_rng,
1607 rng,
1608 );
1609 auto_keys.insert(i, ksk_out);
1610 }
1611
1612 auto_keys
1613 })
1614 }
1615
1616 fn _common_rountine_multi_party_lwe_ksk_share_gen(
1617 &self,
1618 lwe_ksk_seed: <DefaultSecureRng as NewWithSeed>::Seed,
1619 sk_rlwe: &RlweSecret,
1620 sk_lwe: &LweSecret,
1621 ) -> M::R {
1622 DefaultSecureRng::with_local_mut(|rng| {
1623 let mut p_rng = DefaultSecureRng::new_seeded(lwe_ksk_seed);
1624 let mut lwe_ksk = M::R::zeros(
1625 self.pbs_info.lwe_decomposer.decomposition_count() * self.parameters().rlwe_n().0,
1626 );
1627 let lwe_modop = &self.pbs_info.lwe_modop;
1628 let d_lwe_gadget_vec = self.pbs_info.lwe_decomposer.gadget_vector();
1629 lwe_ksk_keygen(
1630 sk_rlwe.values(),
1631 sk_lwe.values(),
1632 &mut lwe_ksk,
1633 &d_lwe_gadget_vec,
1634 lwe_modop,
1635 &mut p_rng,
1636 rng,
1637 );
1638 lwe_ksk
1639 })
1640 }
1641
1642 pub(super) fn multi_party_public_key_share(
1643 &self,
1644 cr_seed: [u8; 32],
1645 client_key: &ClientKey,
1646 ) -> CommonReferenceSeededCollectivePublicKeyShare<
1647 <M as Matrix>::R,
1648 [u8; 32],
1649 BoolParameters<<M as Matrix>::MatElement>,
1650 > {
1651 DefaultSecureRng::with_local_mut(|rng| {
1652 let mut share_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0);
1653 let modop = &self.pbs_info.rlwe_modop;
1654 let nttop = &self.pbs_info.rlwe_nttop;
1655 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
1656 public_key_share(
1657 &mut share_out,
1658 client_key.sk_rlwe().values(),
1659 modop,
1660 nttop,
1661 &mut main_prng,
1662 rng,
1663 );
1664 CommonReferenceSeededCollectivePublicKeyShare::new(
1665 share_out,
1666 cr_seed,
1667 self.pbs_info.parameters.clone(),
1668 )
1669 })
1670 }
1671
1672 pub(super) fn multi_party_decryption_share(
1673 &self,
1674 lwe_ct: &M::R,
1675 client_key: &ClientKey,
1676 ) -> <M as Matrix>::MatElement {
1677 assert!(lwe_ct.as_ref().len() == self.pbs_info.parameters.rlwe_n().0 + 1);
1678 let modop = &self.pbs_info.rlwe_modop;
1679 let mut neg_s = M::R::try_convert_from(
1680 client_key.sk_rlwe().values(),
1681 &self.pbs_info.parameters.rlwe_q(),
1682 );
1683 modop.elwise_neg_mut(neg_s.as_mut());
1684
1685 let mut neg_sa = M::MatElement::zero();
1686 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
1687 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
1688 });
1689
1690 let e = DefaultSecureRng::with_local_mut(|rng| {
1691 let mut e =
1692 RandomGaussianElementInModulus::random(rng, self.pbs_info.parameters.rlwe_q());
1693 e
1694 });
1695 let share = modop.add(&neg_sa, &e);
1696
1697 share
1698 }
1699
1700 pub(crate) fn multi_party_decrypt(&self, shares: &[M::MatElement], lwe_ct: &M::R) -> bool {
1701 let modop = &self.pbs_info.rlwe_modop;
1702 let mut sum_a = M::MatElement::zero();
1703 shares
1704 .iter()
1705 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i));
1706
1707 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
1708 self.pbs_info.parameters.rlwe_q().decode(encoded_m)
1709 }
1710
1711 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
1712 self.pk_encrypt_batched(pk, &vec![m]).remove(0)
1713 }
1714
1715 /// Encrypts a batch booleans as multiple LWE ciphertexts.
1716 ///
1717 /// For public key encryption we first encrypt `m` as a RLWE ciphertext and
1718 /// then sample extract LWE samples at required indices.
1719 ///
1720 /// - TODO(Jay:) Communication can be improved by not sample exctracting and
1721 /// instead just truncate degree 0 values (part Bs)
1722 pub(crate) fn pk_encrypt_batched(&self, pk: &M, m: &[bool]) -> Vec<M::R> {
1723 DefaultSecureRng::with_local_mut(|rng| {
1724 let ring_size = self.pbs_info.parameters.rlwe_n().0;
1725 assert!(
1726 m.len() <= ring_size,
1727 "Cannot batch encrypt > ring_size{ring_size} elements at once"
1728 );
1729
1730 let modop = &self.pbs_info.rlwe_modop;
1731 let nttop = &self.pbs_info.rlwe_nttop;
1732
1733 // RLWE(0)
1734 // sample ephemeral key u
1735 let mut u = vec![0i32; ring_size];
1736 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1737 let mut u = M::R::try_convert_from(&u, &self.pbs_info.parameters.rlwe_q());
1738 nttop.forward(u.as_mut());
1739
1740 let mut ua = M::R::zeros(ring_size);
1741 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1742 let mut ub = M::R::zeros(ring_size);
1743 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1744
1745 // a*u
1746 nttop.forward(ua.as_mut());
1747 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
1748 nttop.backward(ua.as_mut());
1749
1750 // b*u
1751 nttop.forward(ub.as_mut());
1752 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
1753 nttop.backward(ub.as_mut());
1754
1755 let mut rlwe = M::zeros(2, ring_size);
1756 // sample error
1757 rlwe.iter_rows_mut().for_each(|ri| {
1758 RandomFillGaussianInModulus::<[M::MatElement], CiphertextModulus<M::MatElement>>::random_fill(
1759 rng,
1760 &self.pbs_info.parameters.rlwe_q(),
1761 ri.as_mut(),
1762 );
1763 });
1764
1765 // a*u + e0
1766 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
1767 // b*u + e1
1768 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
1769
1770 //FIXME(Jay): Figure out a way to get Q/8 form modulus
1771 let mut m_vec = M::R::zeros(ring_size);
1772 izip!(m_vec.as_mut().iter_mut(), m.iter()).for_each(|(m_el, m_bool)| {
1773 if *m_bool {
1774 // Q/8
1775 *m_el = self.pbs_info.rlwe_q().true_el()
1776 } else {
1777 // -Q/8
1778 *m_el = self.pbs_info.rlwe_q().false_el()
1779 }
1780 });
1781
1782 // b*u + e1 + m
1783 modop.elwise_add_mut(rlwe.get_row_mut(1), m_vec.as_ref());
1784 // rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
1785
1786 // sample extract index required indices
1787 let samples = m.len();
1788 (0..samples)
1789 .into_iter()
1790 .map(|i| {
1791 let mut lwe_out = M::R::zeros(ring_size + 1);
1792 sample_extract(&mut lwe_out, &rlwe, modop, i);
1793 lwe_out
1794 })
1795 .collect_vec()
1796 })
1797 }
1798
1799 /// TODO(Jay): Fetch client key from thread local
1800 pub fn sk_encrypt(&self, m: bool, client_key: &ClientKey) -> M::R {
1801 //FIXME(Jay): Figure out a way to get Q/8 form modulus
1802 let m = if m {
1803 // Q/8
1804 self.pbs_info.rlwe_q().true_el()
1805 } else {
1806 // -Q/8
1807 self.pbs_info.rlwe_q().false_el()
1808 };
1809
1810 DefaultSecureRng::with_local_mut(|rng| {
1811 let mut lwe_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0 + 1);
1812 encrypt_lwe(
1813 &mut lwe_out,
1814 &m,
1815 client_key.sk_rlwe().values(),
1816 &self.pbs_info.rlwe_modop,
1817 rng,
1818 );
1819 lwe_out
1820 })
1821 }
1822
1823 pub fn sk_decrypt(&self, lwe_ct: &M::R, client_key: &ClientKey) -> bool {
1824 let m = decrypt_lwe(
1825 lwe_ct,
1826 client_key.sk_rlwe().values(),
1827 &self.pbs_info.rlwe_modop,
1828 );
1829 self.pbs_info.rlwe_q().decode(m)
1830 }
1831
1832 pub(super) fn aggregate_multi_party_server_key_shares<S>(
1833 &self,
1834 shares: &[CommonReferenceSeededMultiPartyServerKeyShare<
1835 M,
1836 BoolParameters<M::MatElement>,
1837 S,
1838 >],
1839 ) -> SeededMultiPartyServerKey<M, S, BoolParameters<M::MatElement>>
1840 where
1841 S: PartialEq + Clone,
1842 M: Clone,
1843 {
1844 assert!(shares.len() > 0);
1845 let parameters = shares[0].parameters().clone();
1846 let cr_seed = shares[0].cr_seed();
1847
1848 let rlwe_n = parameters.rlwe_n().0;
1849 let g = parameters.g() as isize;
1850 let rlwe_q = parameters.rlwe_q();
1851 let lwe_q = parameters.lwe_q();
1852
1853 // sanity checks
1854 shares.iter().skip(1).for_each(|s| {
1855 assert!(s.parameters() == ¶meters);
1856 assert!(s.cr_seed() == cr_seed);
1857 });
1858
1859 let rlweq_modop = &self.pbs_info.rlwe_modop;
1860 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1861
1862 // auto keys
1863 let mut auto_keys = HashMap::new();
1864 let auto_elements_dlog = parameters.auto_element_dlogs();
1865 for i in auto_elements_dlog.into_iter() {
1866 let mut key = M::zeros(parameters.auto_decomposition_count().0, rlwe_n);
1867
1868 shares.iter().for_each(|s| {
1869 let auto_key_share_i = s.auto_keys().get(&i).expect("Auto key {i} missing");
1870 assert!(
1871 auto_key_share_i.dimension()
1872 == (parameters.auto_decomposition_count().0, rlwe_n)
1873 );
1874 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
1875 |(partb_out, partb_share)| {
1876 rlweq_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
1877 },
1878 );
1879 });
1880
1881 auto_keys.insert(i, key);
1882 }
1883
1884 // rgsw ciphertext (most expensive part!)
1885 let lwe_n = parameters.lwe_n().0;
1886 let rgsw_by_rgsw_decomposer =
1887 parameters.rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1888 let mut scratch_matrix = M::zeros(
1889 std::cmp::max(
1890 rgsw_by_rgsw_decomposer.a().decomposition_count(),
1891 rgsw_by_rgsw_decomposer.b().decomposition_count(),
1892 ) + (rgsw_by_rgsw_decomposer.a().decomposition_count() * 2
1893 + rgsw_by_rgsw_decomposer.b().decomposition_count() * 2),
1894 rlwe_n,
1895 );
1896
1897 let mut tmp_rgsw =
1898 RgswCiphertext::<M, _>::empty(rlwe_n, &rgsw_by_rgsw_decomposer, rlwe_q.clone()).data;
1899 let rgsw_cts = (0..lwe_n).into_iter().map(|index| {
1900 // copy over rgsw ciphertext for index^th secret element from first share and
1901 // treat it as accumulating rgsw ciphertext
1902 let mut rgsw_i = shares[0].rgsw_cts()[index].clone();
1903
1904 shares.iter().skip(1).for_each(|si| {
1905 // copy over si's RGSW[index] ciphertext and send to evaluation domain
1906 izip!(tmp_rgsw.iter_rows_mut(), si.rgsw_cts()[index].iter_rows()).for_each(
1907 |(to_ri, from_ri)| {
1908 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
1909 rlweq_nttop.forward(to_ri.as_mut())
1910 },
1911 );
1912
1913 rgsw_by_rgsw_inplace(
1914 &mut rgsw_i,
1915 &tmp_rgsw,
1916 &rgsw_by_rgsw_decomposer,
1917 &mut scratch_matrix,
1918 rlweq_nttop,
1919 rlweq_modop,
1920 );
1921 });
1922
1923 rgsw_i
1924 });
1925 // d_a and d_b may differ for RGSWxRGSW multiplication and RLWExRGSW
1926 // multiplication. After this point RGSW ciphertexts will only be used for
1927 // RLWExRGSW multiplication (in blind rotation). Thus we drop any additional
1928 // RLWE ciphertexts in RGSW ciphertexts after RGSw x RGSW multiplication
1929 let rgsw_cts = rgsw_cts
1930 .map(|ct_i_in| {
1931 trim_rgsw_ct_matrix_from_rgrg_to_rlrg(
1932 ct_i_in,
1933 self.parameters().rgsw_by_rgsw_decomposition_params(),
1934 self.parameters().rlwe_by_rgsw_decomposition_params(),
1935 )
1936 })
1937 .collect_vec();
1938
1939 // LWE ksks
1940 let mut lwe_ksk = M::R::zeros(rlwe_n * parameters.lwe_decomposition_count().0);
1941 let lweq_modop = &self.pbs_info.lwe_modop;
1942 shares.iter().for_each(|si| {
1943 assert!(si.lwe_ksk().as_ref().len() == rlwe_n * parameters.lwe_decomposition_count().0);
1944 lweq_modop.elwise_add_mut(lwe_ksk.as_mut(), si.lwe_ksk().as_ref())
1945 });
1946
1947 SeededMultiPartyServerKey::new(rgsw_cts, auto_keys, lwe_ksk, cr_seed.clone(), parameters)
1948 }
1949}
1950
1951impl<M, NttOp, RlweModOp, LweModOp, Skey> BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
1952where
1953 M: MatrixMut + MatrixEntity,
1954 M::R: RowMut + RowEntity,
1955 M::MatElement: PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo,
1956 RlweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1957 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1958 NttOp: Ntt<Element = M::MatElement>,
1959{
1960 /// Returns c0 + c1 + Q/4
1961 fn _add_and_shift_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
1962 let modop = &self.pbs_info.rlwe_modop;
1963 modop.elwise_add_mut(c0.as_mut(), c1.as_ref());
1964 // +Q/4
1965 c0.as_mut()[0] = modop.add(&c0.as_ref()[0], &self.pbs_info.rlwe_qby4);
1966 }
1967
1968 /// Returns 2(c0 - c1) + Q/4
1969 fn _subtract_double_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
1970 let modop = &self.pbs_info.rlwe_modop;
1971 // c0 - c1
1972 modop.elwise_sub_mut(c0.as_mut(), c1.as_ref());
1973
1974 // double
1975 c0.as_mut().iter_mut().for_each(|v| *v = modop.add(v, v));
1976 }
1977}
1978
1979impl<M, NttOp, RlweModOp, LweModOp, Skey> BooleanGates
1980 for BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
1981where
1982 M: MatrixMut + MatrixEntity,
1983 M::R: RowMut + RowEntity + Clone,
1984 M::MatElement:
1985 PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo + From<bool>,
1986 RlweModOp: VectorOps<Element = M::MatElement>
1987 + ArithmeticOps<Element = M::MatElement>
1988 + ShoupMatrixFMA<M::R>,
1989 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1990 NttOp: Ntt<Element = M::MatElement>,
1991 Skey: PbsKey<AutoKey = <Skey as PbsKey>::RgswCt, LweKskKey = M>,
1992 <Skey as PbsKey>::RgswCt: WithShoupRepr<M = M>,
1993{
1994 type Ciphertext = M::R;
1995 type Key = Skey;
1996
1997 fn nand_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1998 self._add_and_shift_lwe_cts(c0, c1);
1999
2000 // PBS
2001 pbs(
2002 &self.pbs_info,
2003 &self.nand_test_vec,
2004 c0,
2005 server_key,
2006 &mut self.scratch_memory.lwe_vector,
2007 &mut self.scratch_memory.decomposition_matrix,
2008 );
2009 }
2010
2011 fn and_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2012 self._add_and_shift_lwe_cts(c0, c1);
2013
2014 // PBS
2015 pbs(
2016 &self.pbs_info,
2017 &self.and_test_vec,
2018 c0,
2019 server_key,
2020 &mut self.scratch_memory.lwe_vector,
2021 &mut self.scratch_memory.decomposition_matrix,
2022 );
2023 }
2024
2025 fn or_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2026 self._add_and_shift_lwe_cts(c0, c1);
2027
2028 // PBS
2029 pbs(
2030 &self.pbs_info,
2031 &self.or_test_vec,
2032 c0,
2033 server_key,
2034 &mut self.scratch_memory.lwe_vector,
2035 &mut self.scratch_memory.decomposition_matrix,
2036 );
2037 }
2038
2039 fn nor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2040 self._add_and_shift_lwe_cts(c0, c1);
2041
2042 // PBS
2043 pbs(
2044 &self.pbs_info,
2045 &self.nor_test_vec,
2046 c0,
2047 server_key,
2048 &mut self.scratch_memory.lwe_vector,
2049 &mut self.scratch_memory.decomposition_matrix,
2050 )
2051 }
2052
2053 fn xor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2054 self._subtract_double_lwe_cts(c0, c1);
2055
2056 // PBS
2057 pbs(
2058 &self.pbs_info,
2059 &self.xor_test_vec,
2060 c0,
2061 server_key,
2062 &mut self.scratch_memory.lwe_vector,
2063 &mut self.scratch_memory.decomposition_matrix,
2064 );
2065 }
2066
2067 fn xnor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2068 self._subtract_double_lwe_cts(c0, c1);
2069
2070 // PBS
2071 pbs(
2072 &self.pbs_info,
2073 &self.xnor_test_vec,
2074 c0,
2075 server_key,
2076 &mut self.scratch_memory.lwe_vector,
2077 &mut self.scratch_memory.decomposition_matrix,
2078 );
2079 }
2080
2081 fn not_inplace(&mut self, c0: &mut M::R) {
2082 let modop = &self.pbs_info.rlwe_modop;
2083 c0.as_mut().iter_mut().for_each(|v| *v = modop.neg(v));
2084 }
2085
2086 fn and(
2087 &mut self,
2088 c0: &Self::Ciphertext,
2089 c1: &Self::Ciphertext,
2090 key: &Self::Key,
2091 ) -> Self::Ciphertext {
2092 let mut out = c0.clone();
2093 self.and_inplace(&mut out, c1, key);
2094 out
2095 }
2096
2097 fn nand(
2098 &mut self,
2099 c0: &Self::Ciphertext,
2100 c1: &Self::Ciphertext,
2101 key: &Self::Key,
2102 ) -> Self::Ciphertext {
2103 let mut out = c0.clone();
2104 self.nand_inplace(&mut out, c1, key);
2105 out
2106 }
2107
2108 fn or(
2109 &mut self,
2110 c0: &Self::Ciphertext,
2111 c1: &Self::Ciphertext,
2112 key: &Self::Key,
2113 ) -> Self::Ciphertext {
2114 let mut out = c0.clone();
2115 self.or_inplace(&mut out, c1, key);
2116 out
2117 }
2118
2119 fn nor(
2120 &mut self,
2121 c0: &Self::Ciphertext,
2122 c1: &Self::Ciphertext,
2123 key: &Self::Key,
2124 ) -> Self::Ciphertext {
2125 let mut out = c0.clone();
2126 self.nor_inplace(&mut out, c1, key);
2127 out
2128 }
2129
2130 fn xnor(
2131 &mut self,
2132 c0: &Self::Ciphertext,
2133 c1: &Self::Ciphertext,
2134 key: &Self::Key,
2135 ) -> Self::Ciphertext {
2136 let mut out = c0.clone();
2137 self.xnor_inplace(&mut out, c1, key);
2138 out
2139 }
2140
2141 fn xor(
2142 &mut self,
2143 c0: &Self::Ciphertext,
2144 c1: &Self::Ciphertext,
2145 key: &Self::Key,
2146 ) -> Self::Ciphertext {
2147 let mut out = c0.clone();
2148 self.xor_inplace(&mut out, c1, key);
2149 out
2150 }
2151
2152 fn not(&mut self, c: &Self::Ciphertext) -> Self::Ciphertext {
2153 let mut out = c.clone();
2154 self.not_inplace(&mut out);
2155 out
2156 }
2157}
2158
2159#[cfg(test)]
2160mod tests {
2161 use bool::parameters::{MP_BOOL_PARAMS, SP_BOOL_PARAMS};
2162 use rand::{thread_rng, Rng};
2163 use rand_distr::Uniform;
2164
2165 use crate::{
2166 backend::ModulusPowerOf2,
2167 bool::{
2168 self, CommonReferenceSeededMultiPartyServerKeyShare, PublicKey,
2169 SeededMultiPartyServerKey, NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS, SMALL_MP_BOOL_PARAMS,
2170 },
2171 ntt::NttBackendU64,
2172 random::{RandomElementInModulus, DEFAULT_RNG},
2173 rgsw::{
2174 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
2175 tests::{_measure_noise_rgsw, _sk_encrypt_rlwe},
2176 RgswCiphertext, RgswCiphertextEvaluationDomain, SeededRgswCiphertext,
2177 SeededRlweCiphertext,
2178 },
2179 utils::{negacyclic_mul, Stats},
2180 };
2181
2182 use super::*;
2183
2184 #[test]
2185 fn bool_encrypt_decrypt_works() {
2186 let bool_evaluator = BoolEvaluator::<
2187 Vec<Vec<u64>>,
2188 NttBackendU64,
2189 ModularOpsU64<CiphertextModulus<u64>>,
2190 ModularOpsU64<CiphertextModulus<u64>>,
2191 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2192 >::new(SP_BOOL_PARAMS);
2193 let client_key = bool_evaluator.client_key();
2194
2195 let mut m = true;
2196 for _ in 0..1000 {
2197 let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
2198 let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
2199 assert_eq!(m, m_back);
2200 m = !m;
2201 }
2202 }
2203
2204 #[test]
2205 fn bool_nand() {
2206 let mut bool_evaluator = BoolEvaluator::<
2207 Vec<Vec<u64>>,
2208 NttBackendU64,
2209 ModularOpsU64<CiphertextModulus<u64>>,
2210 ModularOpsU64<CiphertextModulus<u64>>,
2211 ShoupServerKeyEvaluationDomain<_>,
2212 >::new(SP_BOOL_PARAMS);
2213
2214 // println!("{:?}", bool_evaluator.nand_test_vec);
2215 let client_key = bool_evaluator.client_key();
2216 let seeded_server_key = bool_evaluator.single_party_server_key(&client_key);
2217 let runtime_server_key =
2218 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2219 _,
2220 _,
2221 DefaultSecureRng,
2222 NttBackendU64,
2223 >::from(&seeded_server_key));
2224
2225 let mut m0 = false;
2226 let mut m1 = true;
2227
2228 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
2229 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
2230
2231 for _ in 0..500 {
2232 let ct_back = bool_evaluator.nand(&ct0, &ct1, &runtime_server_key);
2233
2234 let m_out = !(m0 && m1);
2235
2236 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
2237 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
2238
2239 m1 = m0;
2240 m0 = m_out;
2241
2242 ct1 = ct0;
2243 ct0 = ct_back;
2244 }
2245 }
2246
2247 #[test]
2248 fn bool_xor() {
2249 let mut bool_evaluator = BoolEvaluator::<
2250 Vec<Vec<u64>>,
2251 NttBackendU64,
2252 ModularOpsU64<CiphertextModulus<u64>>,
2253 ModularOpsU64<CiphertextModulus<u64>>,
2254 ShoupServerKeyEvaluationDomain<_>,
2255 >::new(SP_BOOL_PARAMS);
2256
2257 // println!("{:?}", bool_evaluator.nand_test_vec);
2258 let client_key = bool_evaluator.client_key();
2259 let seeded_server_key = bool_evaluator.single_party_server_key(&client_key);
2260 let runtime_server_key =
2261 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2262 _,
2263 _,
2264 DefaultSecureRng,
2265 NttBackendU64,
2266 >::from(&seeded_server_key));
2267
2268 let mut m0 = false;
2269 let mut m1 = true;
2270
2271 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
2272 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
2273
2274 for _ in 0..1000 {
2275 let ct_back = bool_evaluator.xor(&ct0, &ct1, &runtime_server_key);
2276 let m_out = (m0 ^ m1);
2277
2278 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
2279 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
2280
2281 m1 = m0;
2282 m0 = m_out;
2283
2284 ct1 = ct0;
2285 ct0 = ct_back;
2286 }
2287 }
2288
2289 #[test]
2290 fn multi_party_encryption_decryption() {
2291 let bool_evaluator = BoolEvaluator::<
2292 Vec<Vec<u64>>,
2293 NttBackendU64,
2294 ModularOpsU64<CiphertextModulus<u64>>,
2295 ModularOpsU64<CiphertextModulus<u64>>,
2296 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2297 >::new(MP_BOOL_PARAMS);
2298
2299 let no_of_parties = 500;
2300 let parties = (0..no_of_parties)
2301 .map(|_| bool_evaluator.client_key())
2302 .collect_vec();
2303
2304 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2305 parties.iter().for_each(|k| {
2306 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2307 *ideal_i = *ideal_i + s_i;
2308 });
2309 });
2310
2311 let mut m = true;
2312 for i in 0..100 {
2313 let pk_cr_seed = [0u8; 32];
2314
2315 let public_key_share = parties
2316 .iter()
2317 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2318 .collect_vec();
2319
2320 let collective_pk = PublicKey::<
2321 Vec<Vec<u64>>,
2322 DefaultSecureRng,
2323 ModularOpsU64<CiphertextModulus<u64>>,
2324 >::from(public_key_share.as_slice());
2325 let lwe_ct = bool_evaluator.pk_encrypt(collective_pk.key(), m);
2326
2327 let decryption_shares = parties
2328 .iter()
2329 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct, k))
2330 .collect_vec();
2331
2332 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
2333
2334 {
2335 let ideal_m = if m {
2336 bool_evaluator.pbs_info.parameters.rlwe_q().true_el()
2337 } else {
2338 bool_evaluator.pbs_info.parameters.rlwe_q().false_el()
2339 };
2340 let noise = measure_noise_lwe(
2341 &lwe_ct,
2342 &ideal_rlwe_sk,
2343 &bool_evaluator.pbs_info.rlwe_modop,
2344 &ideal_m,
2345 );
2346 println!("Noise: {noise}");
2347 }
2348
2349 assert_eq!(m_back, m);
2350 m = !m;
2351 }
2352 }
2353
2354 fn _collecitve_public_key_gen(rlwe_q: u64, parties_rlwe_sk: &[RlweSecret]) -> Vec<Vec<u64>> {
2355 let ring_size = parties_rlwe_sk[0].values.len();
2356 assert!(ring_size.is_power_of_two());
2357 let mut rng = DefaultSecureRng::new();
2358 let nttop = NttBackendU64::new(&rlwe_q, ring_size);
2359 let modop = ModularOpsU64::new(rlwe_q);
2360
2361 // Generate Pk shares
2362 let pk_seed = [0u8; 32];
2363 let pk_shares = parties_rlwe_sk.iter().map(|sk| {
2364 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2365 let mut share_out = vec![0u64; ring_size];
2366 public_key_share(
2367 &mut share_out,
2368 sk.values(),
2369 &modop,
2370 &nttop,
2371 &mut p_rng,
2372 &mut rng,
2373 );
2374 share_out
2375 });
2376
2377 let mut pk_part_b = vec![0u64; ring_size];
2378 pk_shares.for_each(|share| modop.elwise_add_mut(&mut pk_part_b, &share));
2379 let mut pk_part_a = vec![0u64; ring_size];
2380 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2381 RandomFillUniformInModulus::random_fill(&mut p_rng, &rlwe_q, pk_part_a.as_mut_slice());
2382
2383 vec![pk_part_a, pk_part_b]
2384 }
2385
2386 fn _multi_party_all_keygen(
2387 bool_evaluator: &BoolEvaluator<
2388 Vec<Vec<u64>>,
2389 NttBackendU64,
2390 ModularOpsU64<CiphertextModulus<u64>>,
2391 ModularOpsU64<CiphertextModulus<u64>>,
2392 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2393 >,
2394 no_of_parties: usize,
2395 ) -> (
2396 Vec<ClientKey>,
2397 PublicKey<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64<CiphertextModulus<u64>>>,
2398 Vec<
2399 CommonReferenceSeededMultiPartyServerKeyShare<
2400 Vec<Vec<u64>>,
2401 BoolParameters<u64>,
2402 [u8; 32],
2403 >,
2404 >,
2405 SeededMultiPartyServerKey<Vec<Vec<u64>>, [u8; 32], BoolParameters<u64>>,
2406 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2407 ClientKey,
2408 ) {
2409 let parties = (0..no_of_parties)
2410 .map(|_| bool_evaluator.client_key())
2411 .collect_vec();
2412
2413 let mut rng = DefaultSecureRng::new();
2414
2415 // Collective public key
2416 let mut pk_cr_seed = [0u8; 32];
2417 rng.fill_bytes(&mut pk_cr_seed);
2418 let public_key_share = parties
2419 .iter()
2420 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2421 .collect_vec();
2422 let collective_pk =
2423 PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, _>::from(public_key_share.as_slice());
2424
2425 // Server key
2426 let mut pbs_cr_seed = [0u8; 32];
2427 rng.fill_bytes(&mut pbs_cr_seed);
2428 let server_key_shares = parties
2429 .iter()
2430 .map(|k| {
2431 bool_evaluator.multi_party_server_key_share(pbs_cr_seed, &collective_pk.key(), k)
2432 })
2433 .collect_vec();
2434 let seeded_server_key =
2435 bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
2436 let runtime_server_key =
2437 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2438 _,
2439 _,
2440 DefaultSecureRng,
2441 NttBackendU64,
2442 >::from(&seeded_server_key));
2443
2444 // construct ideal rlwe sk for meauring noise
2445 let ideal_client_key = {
2446 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2447 parties.iter().for_each(|k| {
2448 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2449 *ideal_i = *ideal_i + s_i;
2450 });
2451 });
2452 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.pbs_info.lwe_n()];
2453 parties.iter().for_each(|k| {
2454 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe().values()).for_each(|(ideal_i, s_i)| {
2455 *ideal_i = *ideal_i + s_i;
2456 });
2457 });
2458
2459 ClientKey::new(
2460 RlweSecret {
2461 values: ideal_rlwe_sk,
2462 },
2463 LweSecret {
2464 values: ideal_lwe_sk,
2465 },
2466 )
2467 };
2468
2469 (
2470 parties,
2471 collective_pk,
2472 server_key_shares,
2473 seeded_server_key,
2474 runtime_server_key,
2475 ideal_client_key,
2476 )
2477 }
2478
2479 #[test]
2480 fn multi_party_nand() {
2481 let mut bool_evaluator = BoolEvaluator::<
2482 Vec<Vec<u64>>,
2483 NttBackendU64,
2484 ModularOpsU64<CiphertextModulus<u64>>,
2485 ModularOpsU64<CiphertextModulus<u64>>,
2486 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2487 >::new(MP_BOOL_PARAMS);
2488
2489 let (parties, collective_pk, _, _, server_key_eval, ideal_client_key) =
2490 _multi_party_all_keygen(&bool_evaluator, 2);
2491
2492 let mut m0 = true;
2493 let mut m1 = false;
2494
2495 let mut lwe0 = bool_evaluator.pk_encrypt(collective_pk.key(), m0);
2496 let mut lwe1 = bool_evaluator.pk_encrypt(collective_pk.key(), m1);
2497
2498 for _ in 0..2000 {
2499 let lwe_out = bool_evaluator.nand(&lwe0, &lwe1, &server_key_eval);
2500
2501 let m_expected = !(m0 & m1);
2502
2503 // multi-party decrypt
2504 let decryption_shares = parties
2505 .iter()
2506 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_out, k))
2507 .collect_vec();
2508 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
2509
2510 let m_back = bool_evaluator.sk_decrypt(&lwe_out, &ideal_client_key);
2511
2512 assert!(
2513 m_expected == m_back,
2514 "Expected {m_expected}, got
2515{m_back}"
2516 );
2517 m1 = m0;
2518 m0 = m_expected;
2519
2520 lwe1 = lwe0;
2521 lwe0 = lwe_out;
2522 }
2523 }
2524
2525 #[test]
2526 fn noise_tester() {
2527 let bool_evaluator = BoolEvaluator::<
2528 Vec<Vec<u64>>,
2529 NttBackendU64,
2530 ModularOpsU64<CiphertextModulus<u64>>,
2531 ModularOpsU64<CiphertextModulus<u64>>,
2532 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2533 >::new(SMALL_MP_BOOL_PARAMS);
2534
2535 // let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2536 // _multi_party_all_keygen(&bool_evaluator, 20);
2537 let no_of_parties = 16;
2538 let lwe_q = bool_evaluator.pbs_info.parameters.lwe_q();
2539 let rlwe_q = bool_evaluator.pbs_info.parameters.rlwe_q();
2540 let lwe_n = bool_evaluator.pbs_info.parameters.lwe_n().0;
2541 let rlwe_n = bool_evaluator.pbs_info.parameters.rlwe_n().0;
2542 let lwe_modop = &bool_evaluator.pbs_info.lwe_modop;
2543 let rlwe_nttop = &bool_evaluator.pbs_info.rlwe_nttop;
2544 let rlwe_modop = &bool_evaluator.pbs_info.rlwe_modop;
2545
2546 // let rgsw_rgsw_decomposer = &bool_evaluator
2547 // .pbs_info
2548 // .parameters
2549 // .rgsw_rgsw_decomposer::<DefaultDecomposer<u64>>();
2550 // let rgsw_rgsw_gadget_a = rgsw_rgsw_decomposer.0.gadget_vector();
2551 // let rgsw_rgsw_gadget_b = rgsw_rgsw_decomposer.1.gadget_vector();
2552
2553 let rlwe_rgsw_decomposer = &bool_evaluator.pbs_info.rlwe_rgsw_decomposer;
2554 let rlwe_rgsw_gadget_a = rlwe_rgsw_decomposer.0.gadget_vector();
2555 let rlwe_rgsw_gadget_b = rlwe_rgsw_decomposer.1.gadget_vector();
2556
2557 let auto_decomposer = &bool_evaluator.pbs_info.auto_decomposer;
2558 let auto_gadget = auto_decomposer.gadget_vector();
2559
2560 let parties = (0..no_of_parties)
2561 .map(|_| bool_evaluator.client_key())
2562 .collect_vec();
2563
2564 let ideal_client_key = {
2565 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2566 parties.iter().for_each(|k| {
2567 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2568 *ideal_i = *ideal_i + s_i;
2569 });
2570 });
2571 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.pbs_info.lwe_n()];
2572 parties.iter().for_each(|k| {
2573 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe().values()).for_each(|(ideal_i, s_i)| {
2574 *ideal_i = *ideal_i + s_i;
2575 });
2576 });
2577
2578 ClientKey::new(
2579 RlweSecret {
2580 values: ideal_rlwe_sk,
2581 },
2582 LweSecret {
2583 values: ideal_lwe_sk,
2584 },
2585 )
2586 };
2587
2588 // check noise in freshly encrypted RLWE ciphertext (ie var_fresh)
2589 if true {
2590 let mut rng = DefaultSecureRng::new();
2591 let mut check = Stats { samples: vec![] };
2592 for _ in 0..10 {
2593 // generate a new collective public key
2594 let mut pk_cr_seed = [0u8; 32];
2595 rng.fill_bytes(&mut pk_cr_seed);
2596 let public_key_share = parties
2597 .iter()
2598 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2599 .collect_vec();
2600 let collective_pk = PublicKey::<
2601 Vec<Vec<u64>>,
2602 DefaultSecureRng,
2603 ModularOpsU64<CiphertextModulus<u64>>,
2604 >::from(public_key_share.as_slice());
2605
2606 let mut m = vec![0u64; rlwe_n];
2607 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2608 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2609 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2610 &mut rlwe_ct,
2611 collective_pk.key(),
2612 &m,
2613 rlwe_modop,
2614 rlwe_nttop,
2615 &mut rng,
2616 );
2617
2618 let mut m_back = vec![0u64; rlwe_n];
2619 decrypt_rlwe(
2620 &rlwe_ct,
2621 ideal_client_key.sk_rlwe().values(),
2622 &mut m_back,
2623 rlwe_nttop,
2624 rlwe_modop,
2625 );
2626
2627 rlwe_modop.elwise_sub_mut(m_back.as_mut_slice(), m.as_slice());
2628
2629 check.add_more(Vec::<i64>::try_convert_from(&m_back, rlwe_q).as_slice());
2630 }
2631
2632 println!("Public key Std: {}", check.std_dev().abs().log2());
2633 }
2634
2635 if true {
2636 // Generate server key shares
2637 let mut rng = DefaultSecureRng::new();
2638 let mut pk_cr_seed = [0u8; 32];
2639 rng.fill_bytes(&mut pk_cr_seed);
2640 let public_key_share = parties
2641 .iter()
2642 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2643 .collect_vec();
2644 let collective_pk = PublicKey::<
2645 Vec<Vec<u64>>,
2646 DefaultSecureRng,
2647 ModularOpsU64<CiphertextModulus<u64>>,
2648 >::from(public_key_share.as_slice());
2649
2650 let pbs_cr_seed = [0u8; 32];
2651 rng.fill_bytes(&mut pk_cr_seed);
2652 let server_key_shares = parties
2653 .iter()
2654 .map(|k| {
2655 bool_evaluator.multi_party_server_key_share(pbs_cr_seed, collective_pk.key(), k)
2656 })
2657 .collect_vec();
2658
2659 let seeded_server_key =
2660 bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
2661
2662 // Check noise in RGSW ciphertexts of ideal LWE secret elements
2663 if false {
2664 let mut check = Stats { samples: vec![] };
2665 izip!(
2666 ideal_client_key.sk_lwe().values.iter(),
2667 seeded_server_key.rgsw_cts().iter()
2668 )
2669 .for_each(|(s_i, rgsw_ct_i)| {
2670 // X^{s[i]}
2671 let mut m_si = vec![0u64; rlwe_n];
2672 let s_i = *s_i * (bool_evaluator.pbs_info.embedding_factor as i32);
2673 if s_i < 0 {
2674 m_si[rlwe_n - (s_i.abs() as usize)] = rlwe_q.neg_one();
2675 } else {
2676 m_si[s_i as usize] = 1;
2677 }
2678
2679 // RLWE'(-sm)
2680 let mut neg_s_eval =
2681 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
2682 rlwe_modop.elwise_neg_mut(&mut neg_s_eval);
2683 rlwe_nttop.forward(&mut neg_s_eval);
2684 for j in 0..rlwe_rgsw_decomposer.a().decomposition_count() {
2685 // RLWE(B^{j} * -s[X]*X^{s_lwe[i]})
2686
2687 // -s[X]*X^{s_lwe[i]}*B_j
2688 let mut m_ideal = m_si.clone();
2689 rlwe_nttop.forward(m_ideal.as_mut_slice());
2690 rlwe_modop.elwise_mul_mut(m_ideal.as_mut_slice(), neg_s_eval.as_slice());
2691 rlwe_nttop.backward(m_ideal.as_mut_slice());
2692 rlwe_modop
2693 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_rgsw_gadget_a[j]);
2694
2695 // RLWE(-s*X^{s_lwe[i]}*B_j)
2696 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2697 rlwe_ct[0].copy_from_slice(&rgsw_ct_i[j]);
2698 rlwe_ct[1].copy_from_slice(
2699 &rgsw_ct_i[j + rlwe_rgsw_decomposer.a().decomposition_count()],
2700 );
2701
2702 let mut m_back = vec![0u64; rlwe_n];
2703 decrypt_rlwe(
2704 &rlwe_ct,
2705 ideal_client_key.sk_rlwe().values(),
2706 &mut m_back,
2707 rlwe_nttop,
2708 rlwe_modop,
2709 );
2710
2711 // diff
2712 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2713 check.add_more(&Vec::<i64>::try_convert_from(&m_back, rlwe_q));
2714 }
2715
2716 // RLWE'(m)
2717 for j in 0..rlwe_rgsw_decomposer.b().decomposition_count() {
2718 // RLWE(B^{j} * X^{s_lwe[i]})
2719
2720 // X^{s_lwe[i]}*B_j
2721 let mut m_ideal = m_si.clone();
2722 rlwe_modop
2723 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_rgsw_gadget_b[j]);
2724
2725 // RLWE(X^{s_lwe[i]}*B_j)
2726 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2727 rlwe_ct[0].copy_from_slice(
2728 &rgsw_ct_i[j + (2 * rlwe_rgsw_decomposer.a().decomposition_count())],
2729 );
2730 rlwe_ct[1].copy_from_slice(
2731 &rgsw_ct_i[j
2732 + (2 * rlwe_rgsw_decomposer.a().decomposition_count()
2733 + rlwe_rgsw_decomposer.b().decomposition_count())],
2734 );
2735
2736 let mut m_back = vec![0u64; rlwe_n];
2737 decrypt_rlwe(
2738 &rlwe_ct,
2739 ideal_client_key.sk_rlwe().values(),
2740 &mut m_back,
2741 rlwe_nttop,
2742 rlwe_modop,
2743 );
2744
2745 // diff
2746 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2747 check.add_more(&Vec::<i64>::try_convert_from(&m_back, rlwe_q));
2748 }
2749 });
2750 println!(
2751 "RGSW Std: {} {} ;; max={}",
2752 check.mean(),
2753 check.std_dev().abs().log2(),
2754 check.samples.iter().max().unwrap()
2755 );
2756 }
2757
2758 // server key in Evaluation domain
2759 let runtime_server_key =
2760 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2761 _,
2762 _,
2763 DefaultSecureRng,
2764 NttBackendU64,
2765 >::from(&seeded_server_key));
2766
2767 // check noise in RLWE x RGSW(X^{s_i}) where RGSW is accunulated RGSW ciphertext
2768 if false {
2769 let mut check = Stats { samples: vec![] };
2770
2771 ideal_client_key
2772 .sk_lwe()
2773 .values()
2774 .iter()
2775 .enumerate()
2776 .for_each(|(index, s_i)| {
2777 let rgsw_ct_i = runtime_server_key.rgsw_ct_lwe_si(index).as_ref();
2778
2779 let mut m = vec![0u64; rlwe_n];
2780 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2781 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2782 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2783 &mut rlwe_ct,
2784 collective_pk.key(),
2785 &m,
2786 rlwe_modop,
2787 rlwe_nttop,
2788 &mut rng,
2789 );
2790
2791 let mut rlwe_after = RlweCiphertext::<_, DefaultSecureRng> {
2792 data: rlwe_ct.clone(),
2793 is_trivial: false,
2794 _phatom: PhantomData,
2795 };
2796 let mut scratch = vec![
2797 vec![0u64; rlwe_n];
2798 std::cmp::max(
2799 rlwe_rgsw_decomposer.0.decomposition_count(),
2800 rlwe_rgsw_decomposer.1.decomposition_count()
2801 ) + 2
2802 ];
2803 rlwe_by_rgsw(
2804 &mut rlwe_after,
2805 rgsw_ct_i,
2806 &mut scratch,
2807 rlwe_rgsw_decomposer,
2808 rlwe_nttop,
2809 rlwe_modop,
2810 );
2811
2812 // m1 = X^{s[i]}
2813 let mut m1 = vec![0u64; rlwe_n];
2814 let s_i = *s_i * (bool_evaluator.pbs_info.embedding_factor as i32);
2815 if s_i < 0 {
2816 m1[rlwe_n - (s_i.abs() as usize)] = rlwe_q.neg_one()
2817 } else {
2818 m1[s_i as usize] = 1;
2819 }
2820
2821 // (m+e) * m1
2822 let mut m_plus_e_times_m1 = vec![0u64; rlwe_n];
2823 decrypt_rlwe(
2824 &rlwe_ct,
2825 ideal_client_key.sk_rlwe().values(),
2826 &mut m_plus_e_times_m1,
2827 rlwe_nttop,
2828 rlwe_modop,
2829 );
2830 rlwe_nttop.forward(m_plus_e_times_m1.as_mut_slice());
2831 rlwe_nttop.forward(m1.as_mut_slice());
2832
2833 rlwe_modop.elwise_mul_mut(m_plus_e_times_m1.as_mut_slice(), m1.as_slice());
2834 rlwe_nttop.backward(m_plus_e_times_m1.as_mut_slice());
2835
2836 // Resulting RLWE ciphertext will equal: (m0m1 + em1) + e_{rlsw x rgsw}.
2837 // Hence, resulting rlwe ciphertext will have error em1 + e_{rlwe x rgsw}.
2838 // Here we're only concerned with e_{rlwe x rgsw}, that is noise added by
2839 // RLWExRGSW. Also note in practice m1 is a monomial, for ex, X^{s_{i}}, for
2840 // some i and var(em1) = var(e).
2841 let mut m_plus_e_times_m1_more_e = vec![0u64; rlwe_n];
2842 decrypt_rlwe(
2843 &rlwe_after,
2844 ideal_client_key.sk_rlwe().values(),
2845 &mut m_plus_e_times_m1_more_e,
2846 rlwe_nttop,
2847 rlwe_modop,
2848 );
2849
2850 // diff
2851 rlwe_modop.elwise_sub_mut(
2852 m_plus_e_times_m1_more_e.as_mut_slice(),
2853 m_plus_e_times_m1.as_slice(),
2854 );
2855
2856 // let noise = measure_noise(
2857 // &rlwe_after,
2858 // &m_plus_e_times_m1,
2859 // rlwe_nttop,
2860 // rlwe_modop,
2861 // ideal_client_key.sk_rlwe.values(),
2862 // );
2863 // print!("NOISE: {}", noise);
2864
2865 check.add_more(&Vec::<i64>::try_convert_from(
2866 &m_plus_e_times_m1_more_e,
2867 rlwe_q,
2868 ));
2869 });
2870 println!(
2871 "RLWE x RGSW, where RGSW has noise var_brk, std: {} {}",
2872 check.std_dev(),
2873 check.std_dev().abs().log2()
2874 )
2875 }
2876
2877 // check noise in Auto key
2878 if false {
2879 let mut check = Stats { samples: vec![] };
2880
2881 let mut neg_s_poly =
2882 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
2883 rlwe_modop.elwise_neg_mut(neg_s_poly.as_mut_slice());
2884
2885 let g = bool_evaluator.pbs_info.g();
2886 let br_q = bool_evaluator.pbs_info.br_q();
2887 let auto_element_dlogs = bool_evaluator.pbs_info.parameters.auto_element_dlogs();
2888 for i in auto_element_dlogs.into_iter() {
2889 let g_pow = if i == 0 {
2890 -g
2891 } else {
2892 (((g as usize).pow(i as u32)) % br_q) as isize
2893 };
2894
2895 // -s[X^k]
2896 let (auto_indices, auto_sign) = generate_auto_map(rlwe_n, g_pow);
2897 let mut neg_s_poly_auto_i = vec![0u64; rlwe_n];
2898 izip!(neg_s_poly.iter(), auto_indices.iter(), auto_sign.iter()).for_each(
2899 |(v, to_i, to_sign)| {
2900 if !to_sign {
2901 neg_s_poly_auto_i[*to_i] = rlwe_modop.neg(v);
2902 } else {
2903 neg_s_poly_auto_i[*to_i] = *v;
2904 }
2905 },
2906 );
2907
2908 let mut auto_key_i = runtime_server_key.galois_key_for_auto(i).as_ref().clone(); //send i^th auto key to coefficient domain
2909 auto_key_i
2910 .iter_mut()
2911 .for_each(|r| rlwe_nttop.backward(r.as_mut_slice()));
2912 auto_gadget.iter().enumerate().for_each(|(i, b_i)| {
2913 // B^i * -s[X^k]
2914 let mut m_ideal = neg_s_poly_auto_i.clone();
2915
2916 rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut_slice(), b_i);
2917
2918 let mut m_out = vec![0u64; rlwe_n];
2919 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2920 rlwe_ct[0].copy_from_slice(&auto_key_i[i]);
2921 rlwe_ct[1].copy_from_slice(
2922 &auto_key_i[auto_decomposer.decomposition_count() + i],
2923 );
2924 decrypt_rlwe(
2925 &rlwe_ct,
2926 ideal_client_key.sk_rlwe().values(),
2927 &mut m_out,
2928 rlwe_nttop,
2929 rlwe_modop,
2930 );
2931
2932 // diff
2933 rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(), m_ideal.as_slice());
2934
2935 check.add_more(&Vec::<i64>::try_convert_from(&m_out, rlwe_q));
2936 });
2937 }
2938
2939 println!("Auto key noise std dev: {}", check.std_dev().abs().log2());
2940 }
2941
2942 // check noise in RLWE(X^k) after sending RLWE(X) -> RLWE(X^k)using collective
2943 // auto key
2944 if true {
2945 let mut check = Stats { samples: vec![] };
2946 let br_q = bool_evaluator.pbs_info.br_q();
2947 let g = bool_evaluator.pbs_info.g();
2948 let auto_element_dlogs = bool_evaluator.pbs_info.parameters.auto_element_dlogs();
2949 for i in auto_element_dlogs.into_iter() {
2950 for _ in 0..10 {
2951 let mut m = vec![0u64; rlwe_n];
2952 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2953 let mut rlwe_ct = RlweCiphertext::<_, DefaultSecureRng> {
2954 data: vec![vec![0u64; rlwe_n]; 2],
2955 is_trivial: false,
2956 _phatom: PhantomData,
2957 };
2958 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2959 &mut rlwe_ct,
2960 collective_pk.key(),
2961 &m,
2962 rlwe_modop,
2963 rlwe_nttop,
2964 &mut rng,
2965 );
2966
2967 // We're only interested in noise increased as a result of automorphism.
2968 // Hence, we take m+e as the bench.
2969 let mut m_plus_e = vec![0u64; rlwe_n];
2970 decrypt_rlwe(
2971 &rlwe_ct,
2972 ideal_client_key.sk_rlwe().values(),
2973 &mut m_plus_e,
2974 rlwe_nttop,
2975 rlwe_modop,
2976 );
2977
2978 let auto_key = runtime_server_key.galois_key_for_auto(i).as_ref();
2979 let (auto_map_index, auto_map_sign) =
2980 bool_evaluator.pbs_info.rlwe_auto_map(i);
2981 let mut scratch =
2982 vec![vec![0u64; rlwe_n]; auto_decomposer.decomposition_count() + 2];
2983 galois_auto(
2984 &mut rlwe_ct,
2985 auto_key,
2986 &mut scratch,
2987 &auto_map_index,
2988 &auto_map_sign,
2989 rlwe_modop,
2990 rlwe_nttop,
2991 auto_decomposer,
2992 );
2993
2994 // send m+e from X to X^k
2995 let mut m_plus_e_auto = vec![0u64; rlwe_n];
2996 izip!(m_plus_e.iter(), auto_map_index.iter(), auto_map_sign.iter())
2997 .for_each(|(v, to_index, to_sign)| {
2998 if !to_sign {
2999 m_plus_e_auto[*to_index] = rlwe_modop.neg(v);
3000 } else {
3001 m_plus_e_auto[*to_index] = *v
3002 }
3003 });
3004
3005 let mut m_out = vec![0u64; rlwe_n];
3006 decrypt_rlwe(
3007 &rlwe_ct,
3008 ideal_client_key.sk_rlwe().values(),
3009 &mut m_out,
3010 rlwe_nttop,
3011 rlwe_modop,
3012 );
3013
3014 // diff
3015 rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(), m_plus_e_auto.as_slice());
3016
3017 check.add_more(&Vec::<i64>::try_convert_from(m_out.as_slice(), rlwe_q));
3018 }
3019 }
3020
3021 println!("Rlwe Auto Noise Std: {}", check.std_dev().abs().log2());
3022 }
3023
3024 // Check noise growth in ksk
3025 // TODO check in LWE key switching keys
3026 if true {
3027 // 1. encrypt LWE ciphertext
3028 // 2. Key switching
3029 // 3.
3030 let mut check = Stats { samples: vec![] };
3031
3032 for _ in 0..1024 {
3033 // Encrypt m \in Q_{ks} using RLWE sk
3034 let mut lwe_in_ct = vec![0u64; rlwe_n + 1];
3035 let m = RandomElementInModulus::random(&mut rng, &lwe_q.q().unwrap());
3036 encrypt_lwe(
3037 &mut lwe_in_ct,
3038 &m,
3039 ideal_client_key.sk_rlwe().values(),
3040 lwe_modop,
3041 &mut rng,
3042 );
3043
3044 // Key switch
3045 let mut lwe_out = vec![0u64; lwe_n + 1];
3046 lwe_key_switch(
3047 &mut lwe_out,
3048 &lwe_in_ct,
3049 runtime_server_key.lwe_ksk(),
3050 lwe_modop,
3051 bool_evaluator.pbs_info.lwe_decomposer(),
3052 );
3053
3054 // We only care about noise added by LWE key switch
3055 // m+e
3056 let m_plus_e =
3057 decrypt_lwe(&lwe_in_ct, ideal_client_key.sk_rlwe().values(), lwe_modop);
3058
3059 let m_plus_e_plus_lwe_ksk_noise =
3060 decrypt_lwe(&lwe_out, ideal_client_key.sk_lwe().values(), lwe_modop);
3061
3062 let diff = lwe_modop.sub(&m_plus_e_plus_lwe_ksk_noise, &m_plus_e);
3063
3064 check.add_more(&vec![lwe_q.map_element_to_i64(&diff)]);
3065 }
3066
3067 println!("Lwe ksk std dev: {}", check.std_dev().abs().log2());
3068 }
3069 }
3070
3071 // Check noise in fresh RGSW ciphertexts, ie X^{s_j[i]}, must equalnoise in
3072 // // fresh RLWE ciphertext
3073 if true {}
3074 // test LWE ksk from RLWE -> LWE
3075 // if false {
3076 // let logp = 2;
3077 // let mut rng = DefaultSecureRng::new();
3078
3079 // let m = 1;
3080 // let encoded_m = m << (lwe_logq - logp);
3081
3082 // // Encrypt
3083 // let mut lwe_ct = vec![0u64; rlwe_n + 1];
3084 // encrypt_lwe(
3085 // &mut lwe_ct,
3086 // &encoded_m,
3087 // ideal_client_key.sk_rlwe.values(),
3088 // lwe_modop,
3089 // &mut rng,
3090 // );
3091
3092 // // key switch
3093 // let lwe_decomposer = &bool_evaluator.decomposer_lwe;
3094 // let mut lwe_out = vec![0u64; lwe_n + 1];
3095 // lwe_key_switch(
3096 // &mut lwe_out,
3097 // &lwe_ct,
3098 // &server_key_eval.lwe_ksk,
3099 // lwe_modop,
3100 // lwe_decomposer,
3101 // );
3102
3103 // let encoded_m_back = decrypt_lwe(&lwe_out,
3104 // ideal_client_key.sk_lwe.values(), lwe_modop); let m_back
3105 // = ((encoded_m_back as f64 * (1 << logp) as f64) /
3106 // (lwe_q as f64)).round() as u64; dbg!(m_back, m);
3107
3108 // let noise = measure_noise_lwe(
3109 // &lwe_out,
3110 // ideal_client_key.sk_lwe.values(),
3111 // lwe_modop,
3112 // &encoded_m,
3113 // );
3114
3115 // println!("Noise: {noise}");
3116 // }
3117
3118 // Measure noise in RGSW ciphertexts of ideal LWE secrets
3119 // if true {
3120 // let gadget_vec = gadget_vector(
3121 // bool_evaluator.parameters.rlwe_logq,
3122 // bool_evaluator.parameters.logb_rgsw,
3123 // bool_evaluator.parameters.d_rgsw,
3124 // );
3125
3126 // for i in 0..20 {
3127 // // measure noise in RGSW(s[i])
3128 // let si =
3129 // ideal_client_key.sk_lwe.values[i] *
3130 // (bool_evaluator.embedding_factor as i32); let mut
3131 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
3132 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
3133 // } else {
3134 // si_poly[(si.abs() as usize)] = 1;
3135 // }
3136
3137 // let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
3138 // rgsw_si
3139 // .iter_mut()
3140 // .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
3141
3142 // println!("####### Noise in RGSW(X^s_{i}) #######");
3143 // _measure_noise_rgsw(
3144 // &rgsw_si,
3145 // &si_poly,
3146 // ideal_client_key.sk_rlwe.values(),
3147 // &gadget_vec,
3148 // rlwe_q,
3149 // );
3150 // println!("####### ##################### #######");
3151 // }
3152 // }
3153
3154 // // measure noise grwoth in RLWExRGSW
3155 // if true {
3156 // let mut rng = DefaultSecureRng::new();
3157 // let mut carry_m = vec![0u64; rlwe_n];
3158 // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
3159 // carry_m.as_mut_slice());
3160
3161 // // RGSW(carrym)
3162 // let trivial_rlwect = vec![vec![0u64; rlwe_n],carry_m.clone()];
3163 // let mut rlwe_ct = RlweCiphertext::<_,
3164 // DefaultSecureRng>::from_raw(trivial_rlwect, true);
3165
3166 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
3167 // d_rgsw + 2]; let mul_mod =
3168 // |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
3169
3170 // for i in 0..bool_evaluator.parameters.lwe_n {
3171 // rlwe_by_rgsw(
3172 // &mut rlwe_ct,
3173 // server_key_eval.rgsw_ct_lwe_si(i),
3174 // &mut scratch_matrix_dplus2_ring,
3175 // rlwe_decomposer,
3176 // rlwe_nttop,
3177 // rlwe_modop,
3178 // );
3179
3180 // // carry_m[X] * s_i[X]
3181 // let si =
3182 // ideal_client_key.sk_lwe.values[i] *
3183 // (bool_evaluator.embedding_factor as i32); let mut
3184 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
3185 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
3186 // } else {
3187 // si_poly[(si.abs() as usize)] = 1;
3188 // }
3189 // carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod,
3190 // rlwe_q);
3191
3192 // let noise = measure_noise(
3193 // &rlwe_ct,
3194 // &carry_m,
3195 // rlwe_nttop,
3196 // rlwe_modop,
3197 // ideal_client_key.sk_rlwe.values(),
3198 // );
3199 // println!("Noise RLWE(carry_m) accumulating {i}^th secret
3200 // monomial: {noise}"); }
3201 // }
3202
3203 // // Check galois keys
3204 // if false {
3205 // let g = bool_evaluator.g() as isize;
3206 // let mut rng = DefaultSecureRng::new();
3207 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
3208 // d_rgsw + 2]; for i in [g, -g] {
3209 // let mut m = vec![0u64; rlwe_n];
3210 // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
3211 // m.as_mut_slice()); let mut rlwe_ct = {
3212 // let mut data = vec![vec![0u64; rlwe_n]; 2];
3213 // public_key_encrypt_rlwe(
3214 // &mut data,
3215 // &collective_pk.key,
3216 // &m,
3217 // rlwe_modop,
3218 // rlwe_nttop,
3219 // &mut rng,
3220 // );
3221 // RlweCiphertext::<_, DefaultSecureRng>::from_raw(data,
3222 // false) };
3223
3224 // let auto_key = server_key_eval.galois_key_for_auto(i);
3225 // let (auto_map_index, auto_map_sign) =
3226 // generate_auto_map(rlwe_n, i); galois_auto(
3227 // &mut rlwe_ct,
3228 // auto_key,
3229 // &mut scratch_matrix_dplus2_ring,
3230 // &auto_map_index,
3231 // &auto_map_sign,
3232 // rlwe_modop,
3233 // rlwe_nttop,
3234 // rlwe_decomposer,
3235 // );
3236
3237 // // send m(X) -> m(X^i)
3238 // let mut m_k = vec![0u64; rlwe_n];
3239 // izip!(m.iter(), auto_map_index.iter(),
3240 // auto_map_sign.iter()).for_each( |(mi, to_index,to_sign)|
3241 // // { if !to_sign {
3242 // m_k[*to_index] = rlwe_q - *mi; } else {
3243 // m_k[*to_index] = *mi;
3244 // }
3245 // },
3246 // );
3247
3248 // // measure noise
3249 // let noise = measure_noise(
3250 // &rlwe_ct,
3251 // &m_k,
3252 // rlwe_nttop,
3253 // rlwe_modop,
3254 // ideal_client_key.sk_rlwe.values(),
3255 // );
3256
3257 // println!("Noise after auto k={i}: {noise}");
3258 // }
3259 // }
3260 }
3261
3262 #[test]
3263 fn testtest() {
3264 let evaluator = BoolEvaluator::<
3265 Vec<Vec<u64>>,
3266 NttBackendU64,
3267 ModularOpsU64<CiphertextModulus<u64>>,
3268 ModulusPowerOf2<CiphertextModulus<u64>>,
3269 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
3270 >::new(NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS);
3271 let mp_seed = NonInteractiveMultiPartyCrs { seed: [1u8; 32] };
3272
3273 let ring_size = evaluator.parameters().rlwe_n().0;
3274 let rlwe_q = evaluator.parameters().rlwe_q();
3275 let rlwe_modop = evaluator.pbs_info().modop_rlweq();
3276 let nttop = evaluator.pbs_info().nttop_rlweq();
3277
3278 let parties = 2;
3279
3280 let cks = (0..parties)
3281 .map(|_| evaluator.non_interactive_client_key())
3282 .collect_vec();
3283
3284 let key_shares = (0..parties)
3285 .map(|i| evaluator.non_interactive_multi_party_key_share(&mp_seed, i, parties, &cks[i]))
3286 .collect_vec();
3287 // dbg!(key_shares[1].user_index);
3288
3289 let rgsw_cts = evaluator.aggregate_non_interactive_multi_party_key_share(
3290 &mp_seed,
3291 parties,
3292 &key_shares,
3293 );
3294
3295 let mut ideal_rlwe = vec![0; ring_size];
3296 cks.iter().for_each(|k| {
3297 izip!(ideal_rlwe.iter_mut(), k.sk_rlwe().values().iter()).for_each(|(a, b)| {
3298 *a = *a + b;
3299 });
3300 });
3301
3302 let mut ideal_lwe = vec![0; evaluator.parameters().lwe_n().0];
3303 cks.iter().for_each(|k| {
3304 izip!(ideal_lwe.iter_mut(), k.sk_lwe().values().iter()).for_each(|(a, b)| {
3305 *a = *a + b;
3306 });
3307 });
3308
3309 // let mut stats = Stats::new();
3310
3311 let (rlrg_decomp_a, rlrg_decomp_b) = evaluator
3312 .parameters()
3313 .rlwe_rgsw_decomposer::<DefaultDecomposer<u64>>();
3314 let gadget_vec_a = rlrg_decomp_a.gadget_vector();
3315 let gadget_vec_b = rlrg_decomp_b.gadget_vector();
3316 let d_a = rlrg_decomp_a.decomposition_count();
3317 let d_b = rlrg_decomp_b.decomposition_count();
3318 let s_poly = Vec::<u64>::try_convert_from(ideal_rlwe.as_slice(), rlwe_q);
3319 let mut neg_s_poly_eval = s_poly.clone();
3320 rlwe_modop.elwise_neg_mut(&mut neg_s_poly_eval);
3321 nttop.forward(neg_s_poly_eval.as_mut());
3322
3323 // rgsw_cts.iter().enumerate().for_each(|(s_index, ct)| {
3324 // // X^{lwe_s[i]}
3325 // let mut m = vec![0u64; ring_size];
3326 // if ideal_lwe[s_index] < 0 {
3327 // m[ring_size - (ideal_lwe[s_index].abs() as usize)] =
3328 // rlwe_q.neg_one(); } else {
3329 // m[(ideal_lwe[s_index] as usize)] = 1;
3330 // }
3331
3332 // let mut neg_sm = m.clone();
3333 // nttop.forward(&mut neg_sm);
3334 // rlwe_modop.elwise_mul_mut(&mut neg_sm, &neg_s_poly_eval);
3335 // nttop.backward(&mut neg_sm);
3336
3337 // // RLWE'(-sm)
3338 // gadget_vec_a.iter().enumerate().for_each(|(index, beta)| {
3339 // // RLWE(\beta -sm)
3340
3341 // // \beta * -sX^[lwe_s[i]]
3342 // let mut beta_neg_sm = neg_sm.clone();
3343 // rlwe_modop.elwise_scalar_mul_mut(&mut beta_neg_sm, beta);
3344
3345 // // extract RLWE(-sm \beta)
3346 // let mut rlwe = vec![vec![0u64; ring_size]; 2];
3347 // rlwe[0].copy_from_slice(&ct[index]);
3348 // rlwe[1].copy_from_slice(&ct[index + d_a]);
3349
3350 // // decrypt
3351 // let mut m_out = vec![0u64; ring_size];
3352 // decrypt_rlwe(&rlwe, &ideal_rlwe, &mut m_out, nttop,
3353 // rlwe_modop); // println!("{:?}", &beta_neg_sm);
3354
3355 // let mut diff = m_out;
3356 // rlwe_modop.elwise_sub_mut(&mut diff, &beta_neg_sm);
3357
3358 // stats.add_more(&Vec::<i64>::try_convert_from(&diff, rlwe_q));
3359 // });
3360 // });
3361
3362 // println!("Stats: {}", stats.std_dev().abs().log2());
3363 }
3364}
3365
3366// let (rgswrgsw_d_a, rgswrgsw_d_b) =
3367// self.pbs_info.parameters.rgsw_rgsw_decomposition_count(); let (rlrg_d_a,
3368// rlrg_d_b) = self.pbs_info.parameters.rlwe_rgsw_decomposition_count(); let
3369// rgsw_ct_rows_in = rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 * 2;
3370// let rgsw_ct_rows_out = rlrg_d_a.0 * 2 + rlrg_d_b.0 * 2;
3371// 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);
3372// 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);
3373// let rgsw_cts = rgsw_cts
3374// .map(|ct_i_in| {
3375// assert!(ct_i_in.dimension() == (rgsw_ct_rows_in, rlwe_n));
3376// let mut reduced_ct_i_out = M::zeros(rgsw_ct_rows_out, rlwe_n);
3377
3378// // RLWE'(-sm) part A
3379// izip!(
3380// reduced_ct_i_out.iter_rows_mut().take(rlrg_d_a.0),
3381// ct_i_in
3382// .iter_rows()
3383// .skip(rgswrgsw_d_a.0 - rlrg_d_a.0)
3384// .take(rlrg_d_a.0)
3385// )
3386// .for_each(|(to_ri, from_ri)| {
3387// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3388// });
3389
3390// // RLWE'(-sm) part B
3391// izip!(
3392// reduced_ct_i_out
3393// .iter_rows_mut()
3394// .skip(rlrg_d_a.0)
3395// .take(rlrg_d_a.0),
3396// ct_i_in
3397// .iter_rows()
3398// .skip(rgswrgsw_d_a.0 + (rgswrgsw_d_a.0 - rlrg_d_a.0))
3399// .take(rlrg_d_a.0)
3400// )
3401// .for_each(|(to_ri, from_ri)| {
3402// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3403// });
3404
3405// // RLWE'(m) Part A
3406// izip!(
3407// reduced_ct_i_out
3408// .iter_rows_mut()
3409// .skip(rlrg_d_a.0 * 2)
3410// .take(rlrg_d_b.0),
3411// ct_i_in
3412// .iter_rows()
3413// .skip(rgswrgsw_d_a.0 * 2 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
3414// .take(rlrg_d_b.0)
3415// )
3416// .for_each(|(to_ri, from_ri)| {
3417// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3418// });
3419
3420// // RLWE'(m) Part B
3421// izip!(
3422// reduced_ct_i_out
3423// .iter_rows_mut()
3424// .skip(rlrg_d_a.0 * 2 + rlrg_d_b.0)
3425// .take(rlrg_d_b.0),
3426// ct_i_in
3427// .iter_rows()
3428// .skip(rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 +
3429// (rgswrgsw_d_b.0 - rlrg_d_b.0)) .take(rlrg_d_b.0)
3430// )
3431// .for_each(|(to_ri, from_ri)| {
3432// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3433// });
3434
3435// reduced_ct_i_out
3436// })
3437// .collect_vec();