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 SeededNonInteractiveMultiPartyServerKeyShare<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> SeededNonInteractiveMultiPartyServerKeyShare<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: &[SeededNonInteractiveMultiPartyServerKeyShare<
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 ) -> SeededNonInteractiveMultiPartyServerKeyShare<M, NonInteractiveMultiPartyCrs<[u8; 32]>>
1443 {
1444 // TODO: check whether parameters support `total_users`
1445 let nttop = self.pbs_info().nttop_rlweq();
1446 let rlwe_modop = self.pbs_info().modop_rlweq();
1447 let ring_size = self.pbs_info().rlwe_n();
1448 let rlwe_q = self.parameters().rlwe_q();
1449
1450 let (ui_to_s_ksk, zero_encs_for_others) = DefaultSecureRng::with_local_mut(|rng| {
1451 // ui_to_s_ksk
1452 let non_interactive_decomposer = self
1453 .parameters()
1454 .non_interactive_ui_to_s_key_switch_decomposer::<DefaultDecomposer<M::MatElement>>(
1455 );
1456 let non_interactive_gadget_vec = non_interactive_decomposer.gadget_vector();
1457 let ui_to_s_ksk = {
1458 let mut p_rng = DefaultSecureRng::new_seeded(
1459 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(self_index),
1460 );
1461
1462 non_interactive_ksk_gen::<M, _, _, _, _, _>(
1463 client_key.sk_rlwe().values(),
1464 client_key.sk_u_rlwe().values(),
1465 &non_interactive_gadget_vec,
1466 &mut p_rng,
1467 rng,
1468 nttop,
1469 rlwe_modop,
1470 )
1471 };
1472
1473 // zero encryptions for others uj_to_s ksk
1474 let all_users_except_self = (0..total_users).filter(|x| *x != self_index);
1475 let zero_encs_for_others = all_users_except_self
1476 .map(|other_user_index| {
1477 let mut p_rng = DefaultSecureRng::new_seeded(
1478 cr_seed.ui_to_s_ks_seed_for_user_i::<DefaultSecureRng>(other_user_index),
1479 );
1480 let zero_encs =
1481 non_interactive_ksk_zero_encryptions_for_other_party_i::<M, _, _, _, _, _>(
1482 client_key.sk_rlwe().values(),
1483 &non_interactive_gadget_vec,
1484 &mut p_rng,
1485 rng,
1486 nttop,
1487 rlwe_modop,
1488 );
1489 zero_encs
1490 })
1491 .collect_vec();
1492
1493 (ui_to_s_ksk, zero_encs_for_others)
1494 });
1495
1496 // Non-interactive RGSW cts = (a_i * u_j + e + \beta X^{s[i]}, a_i * s_j + e')
1497 let ni_rgsw_cts = DefaultSecureRng::with_local_mut(|rng| {
1498 let mut rgsw_cts_prng =
1499 DefaultSecureRng::new_seeded(cr_seed.rgsw_cts_seed::<DefaultSecureRng>());
1500 // generate non-interactive rgsw cts
1501 let rgsw_by_rgsw_decomposer = self
1502 .parameters()
1503 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1504
1505 let ni_rgrg_gadget_vec = {
1506 if rgsw_by_rgsw_decomposer.a().decomposition_count()
1507 > rgsw_by_rgsw_decomposer.b().decomposition_count()
1508 {
1509 rgsw_by_rgsw_decomposer.a().gadget_vector()
1510 } else {
1511 rgsw_by_rgsw_decomposer.b().gadget_vector()
1512 }
1513 };
1514 let ni_rgsw_cts: (Vec<M>, Vec<M>) = client_key
1515 .sk_lwe()
1516 .values()
1517 .iter()
1518 .map(|s_i| {
1519 // X^{s[i]}
1520 let mut m = M::R::zeros(ring_size);
1521 let s_i = s_i * (self.pbs_info().embedding_factor() as i32);
1522 if s_i < 0 {
1523 // X^{-s[i]} -> -X^{N+s[i]}
1524 m.as_mut()[ring_size - (s_i.abs() as usize)] = rlwe_q.neg_one();
1525 } else {
1526 m.as_mut()[s_i as usize] = M::MatElement::one();
1527 }
1528
1529 non_interactive_rgsw_ct::<M, _, _, _, _, _>(
1530 client_key.sk_rlwe().values(),
1531 client_key.sk_u_rlwe().values(),
1532 m.as_ref(),
1533 &ni_rgrg_gadget_vec,
1534 &mut rgsw_cts_prng,
1535 rng,
1536 nttop,
1537 rlwe_modop,
1538 )
1539 })
1540 .unzip();
1541 ni_rgsw_cts
1542 });
1543
1544 // Auto key share
1545 let auto_keys_share = {
1546 let auto_seed = cr_seed.auto_keys_cts_seed::<DefaultSecureRng>();
1547 self._common_rountine_multi_party_auto_keys_share_gen(auto_seed, client_key.sk_rlwe())
1548 };
1549
1550 // Lwe Ksk share
1551 let lwe_ksk_share = {
1552 let lwe_ksk_seed = cr_seed.lwe_ksk_cts_seed::<DefaultSecureRng>();
1553 self._common_rountine_multi_party_lwe_ksk_share_gen(
1554 lwe_ksk_seed,
1555 client_key.sk_rlwe(),
1556 client_key.sk_lwe(),
1557 )
1558 };
1559
1560 SeededNonInteractiveMultiPartyServerKeyShare {
1561 ni_rgsw_cts,
1562 ui_to_s_ksk,
1563 others_ksk_zero_encs: zero_encs_for_others,
1564 user_index: self_index,
1565 auto_keys_share,
1566 lwe_ksk_share,
1567 cr_seed: cr_seed.clone(),
1568 }
1569 }
1570
1571 fn _common_rountine_multi_party_auto_keys_share_gen(
1572 &self,
1573 auto_seed: <DefaultSecureRng as NewWithSeed>::Seed,
1574 sk_rlwe: &RlweSecret,
1575 ) -> HashMap<usize, M> {
1576 let g = self.pbs_info.parameters.g();
1577 let ring_size = self.pbs_info.parameters.rlwe_n().0;
1578 let br_q = self.pbs_info.parameters.br_q();
1579 let rlweq_modop = &self.pbs_info.rlwe_modop;
1580 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1581
1582 DefaultSecureRng::with_local_mut(|rng| {
1583 let mut p_rng = DefaultSecureRng::new_seeded(auto_seed);
1584
1585 let mut auto_keys = HashMap::new();
1586 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
1587 let auto_element_dlogs = self.pbs_info.parameters.auto_element_dlogs();
1588
1589 for i in auto_element_dlogs.into_iter() {
1590 let g_pow = if i == 0 {
1591 -(g as isize)
1592 } else {
1593 (g.pow(i as u32) % br_q) as isize
1594 };
1595
1596 let mut ksk_out = M::zeros(
1597 self.pbs_info.auto_decomposer.decomposition_count(),
1598 ring_size,
1599 );
1600 galois_key_gen(
1601 &mut ksk_out,
1602 sk_rlwe.values(),
1603 g_pow,
1604 &auto_gadget,
1605 rlweq_modop,
1606 rlweq_nttop,
1607 &mut p_rng,
1608 rng,
1609 );
1610 auto_keys.insert(i, ksk_out);
1611 }
1612
1613 auto_keys
1614 })
1615 }
1616
1617 fn _common_rountine_multi_party_lwe_ksk_share_gen(
1618 &self,
1619 lwe_ksk_seed: <DefaultSecureRng as NewWithSeed>::Seed,
1620 sk_rlwe: &RlweSecret,
1621 sk_lwe: &LweSecret,
1622 ) -> M::R {
1623 DefaultSecureRng::with_local_mut(|rng| {
1624 let mut p_rng = DefaultSecureRng::new_seeded(lwe_ksk_seed);
1625 let mut lwe_ksk = M::R::zeros(
1626 self.pbs_info.lwe_decomposer.decomposition_count() * self.parameters().rlwe_n().0,
1627 );
1628 let lwe_modop = &self.pbs_info.lwe_modop;
1629 let d_lwe_gadget_vec = self.pbs_info.lwe_decomposer.gadget_vector();
1630 lwe_ksk_keygen(
1631 sk_rlwe.values(),
1632 sk_lwe.values(),
1633 &mut lwe_ksk,
1634 &d_lwe_gadget_vec,
1635 lwe_modop,
1636 &mut p_rng,
1637 rng,
1638 );
1639 lwe_ksk
1640 })
1641 }
1642
1643 pub(super) fn multi_party_public_key_share(
1644 &self,
1645 cr_seed: [u8; 32],
1646 client_key: &ClientKey,
1647 ) -> CommonReferenceSeededCollectivePublicKeyShare<
1648 <M as Matrix>::R,
1649 [u8; 32],
1650 BoolParameters<<M as Matrix>::MatElement>,
1651 > {
1652 DefaultSecureRng::with_local_mut(|rng| {
1653 let mut share_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0);
1654 let modop = &self.pbs_info.rlwe_modop;
1655 let nttop = &self.pbs_info.rlwe_nttop;
1656 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
1657 public_key_share(
1658 &mut share_out,
1659 client_key.sk_rlwe().values(),
1660 modop,
1661 nttop,
1662 &mut main_prng,
1663 rng,
1664 );
1665 CommonReferenceSeededCollectivePublicKeyShare::new(
1666 share_out,
1667 cr_seed,
1668 self.pbs_info.parameters.clone(),
1669 )
1670 })
1671 }
1672
1673 pub(super) fn multi_party_decryption_share(
1674 &self,
1675 lwe_ct: &M::R,
1676 client_key: &ClientKey,
1677 ) -> <M as Matrix>::MatElement {
1678 assert!(lwe_ct.as_ref().len() == self.pbs_info.parameters.rlwe_n().0 + 1);
1679 let modop = &self.pbs_info.rlwe_modop;
1680 let mut neg_s = M::R::try_convert_from(
1681 client_key.sk_rlwe().values(),
1682 &self.pbs_info.parameters.rlwe_q(),
1683 );
1684 modop.elwise_neg_mut(neg_s.as_mut());
1685
1686 let mut neg_sa = M::MatElement::zero();
1687 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
1688 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
1689 });
1690
1691 let e = DefaultSecureRng::with_local_mut(|rng| {
1692 let mut e =
1693 RandomGaussianElementInModulus::random(rng, self.pbs_info.parameters.rlwe_q());
1694 e
1695 });
1696 let share = modop.add(&neg_sa, &e);
1697
1698 share
1699 }
1700
1701 pub(crate) fn multi_party_decrypt(&self, shares: &[M::MatElement], lwe_ct: &M::R) -> bool {
1702 let modop = &self.pbs_info.rlwe_modop;
1703 let mut sum_a = M::MatElement::zero();
1704 shares
1705 .iter()
1706 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i));
1707
1708 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
1709 self.pbs_info.parameters.rlwe_q().decode(encoded_m)
1710 }
1711
1712 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
1713 self.pk_encrypt_batched(pk, &vec![m]).remove(0)
1714 }
1715
1716 /// Encrypts a batch booleans as multiple LWE ciphertexts.
1717 ///
1718 /// For public key encryption we first encrypt `m` as a RLWE ciphertext and
1719 /// then sample extract LWE samples at required indices.
1720 ///
1721 /// - TODO(Jay:) Communication can be improved by not sample exctracting and
1722 /// instead just truncate degree 0 values (part Bs)
1723 pub(crate) fn pk_encrypt_batched(&self, pk: &M, m: &[bool]) -> Vec<M::R> {
1724 DefaultSecureRng::with_local_mut(|rng| {
1725 let ring_size = self.pbs_info.parameters.rlwe_n().0;
1726 assert!(
1727 m.len() <= ring_size,
1728 "Cannot batch encrypt > ring_size{ring_size} elements at once"
1729 );
1730
1731 let modop = &self.pbs_info.rlwe_modop;
1732 let nttop = &self.pbs_info.rlwe_nttop;
1733
1734 // RLWE(0)
1735 // sample ephemeral key u
1736 let mut u = vec![0i32; ring_size];
1737 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1738 let mut u = M::R::try_convert_from(&u, &self.pbs_info.parameters.rlwe_q());
1739 nttop.forward(u.as_mut());
1740
1741 let mut ua = M::R::zeros(ring_size);
1742 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1743 let mut ub = M::R::zeros(ring_size);
1744 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1745
1746 // a*u
1747 nttop.forward(ua.as_mut());
1748 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
1749 nttop.backward(ua.as_mut());
1750
1751 // b*u
1752 nttop.forward(ub.as_mut());
1753 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
1754 nttop.backward(ub.as_mut());
1755
1756 let mut rlwe = M::zeros(2, ring_size);
1757 // sample error
1758 rlwe.iter_rows_mut().for_each(|ri| {
1759 RandomFillGaussianInModulus::<[M::MatElement], CiphertextModulus<M::MatElement>>::random_fill(
1760 rng,
1761 &self.pbs_info.parameters.rlwe_q(),
1762 ri.as_mut(),
1763 );
1764 });
1765
1766 // a*u + e0
1767 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
1768 // b*u + e1
1769 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
1770
1771 //FIXME(Jay): Figure out a way to get Q/8 form modulus
1772 let mut m_vec = M::R::zeros(ring_size);
1773 izip!(m_vec.as_mut().iter_mut(), m.iter()).for_each(|(m_el, m_bool)| {
1774 if *m_bool {
1775 // Q/8
1776 *m_el = self.pbs_info.rlwe_q().true_el()
1777 } else {
1778 // -Q/8
1779 *m_el = self.pbs_info.rlwe_q().false_el()
1780 }
1781 });
1782
1783 // b*u + e1 + m
1784 modop.elwise_add_mut(rlwe.get_row_mut(1), m_vec.as_ref());
1785 // rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
1786
1787 // sample extract index required indices
1788 let samples = m.len();
1789 (0..samples)
1790 .into_iter()
1791 .map(|i| {
1792 let mut lwe_out = M::R::zeros(ring_size + 1);
1793 sample_extract(&mut lwe_out, &rlwe, modop, i);
1794 lwe_out
1795 })
1796 .collect_vec()
1797 })
1798 }
1799
1800 /// TODO(Jay): Fetch client key from thread local
1801 pub fn sk_encrypt(&self, m: bool, client_key: &ClientKey) -> M::R {
1802 //FIXME(Jay): Figure out a way to get Q/8 form modulus
1803 let m = if m {
1804 // Q/8
1805 self.pbs_info.rlwe_q().true_el()
1806 } else {
1807 // -Q/8
1808 self.pbs_info.rlwe_q().false_el()
1809 };
1810
1811 DefaultSecureRng::with_local_mut(|rng| {
1812 let mut lwe_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0 + 1);
1813 encrypt_lwe(
1814 &mut lwe_out,
1815 &m,
1816 client_key.sk_rlwe().values(),
1817 &self.pbs_info.rlwe_modop,
1818 rng,
1819 );
1820 lwe_out
1821 })
1822 }
1823
1824 pub fn sk_decrypt(&self, lwe_ct: &M::R, client_key: &ClientKey) -> bool {
1825 let m = decrypt_lwe(
1826 lwe_ct,
1827 client_key.sk_rlwe().values(),
1828 &self.pbs_info.rlwe_modop,
1829 );
1830 self.pbs_info.rlwe_q().decode(m)
1831 }
1832
1833 pub(super) fn aggregate_multi_party_server_key_shares<S>(
1834 &self,
1835 shares: &[CommonReferenceSeededMultiPartyServerKeyShare<
1836 M,
1837 BoolParameters<M::MatElement>,
1838 S,
1839 >],
1840 ) -> SeededMultiPartyServerKey<M, S, BoolParameters<M::MatElement>>
1841 where
1842 S: PartialEq + Clone,
1843 M: Clone,
1844 {
1845 assert!(shares.len() > 0);
1846 let parameters = shares[0].parameters().clone();
1847 let cr_seed = shares[0].cr_seed();
1848
1849 let rlwe_n = parameters.rlwe_n().0;
1850 let g = parameters.g() as isize;
1851 let rlwe_q = parameters.rlwe_q();
1852 let lwe_q = parameters.lwe_q();
1853
1854 // sanity checks
1855 shares.iter().skip(1).for_each(|s| {
1856 assert!(s.parameters() == ¶meters);
1857 assert!(s.cr_seed() == cr_seed);
1858 });
1859
1860 let rlweq_modop = &self.pbs_info.rlwe_modop;
1861 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
1862
1863 // auto keys
1864 let mut auto_keys = HashMap::new();
1865 let auto_elements_dlog = parameters.auto_element_dlogs();
1866 for i in auto_elements_dlog.into_iter() {
1867 let mut key = M::zeros(parameters.auto_decomposition_count().0, rlwe_n);
1868
1869 shares.iter().for_each(|s| {
1870 let auto_key_share_i = s.auto_keys().get(&i).expect("Auto key {i} missing");
1871 assert!(
1872 auto_key_share_i.dimension()
1873 == (parameters.auto_decomposition_count().0, rlwe_n)
1874 );
1875 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
1876 |(partb_out, partb_share)| {
1877 rlweq_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
1878 },
1879 );
1880 });
1881
1882 auto_keys.insert(i, key);
1883 }
1884
1885 // rgsw ciphertext (most expensive part!)
1886 let lwe_n = parameters.lwe_n().0;
1887 let rgsw_by_rgsw_decomposer =
1888 parameters.rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
1889 let mut scratch_matrix = M::zeros(
1890 std::cmp::max(
1891 rgsw_by_rgsw_decomposer.a().decomposition_count(),
1892 rgsw_by_rgsw_decomposer.b().decomposition_count(),
1893 ) + (rgsw_by_rgsw_decomposer.a().decomposition_count() * 2
1894 + rgsw_by_rgsw_decomposer.b().decomposition_count() * 2),
1895 rlwe_n,
1896 );
1897
1898 let mut tmp_rgsw =
1899 RgswCiphertext::<M, _>::empty(rlwe_n, &rgsw_by_rgsw_decomposer, rlwe_q.clone()).data;
1900 let rgsw_cts = (0..lwe_n).into_iter().map(|index| {
1901 // copy over rgsw ciphertext for index^th secret element from first share and
1902 // treat it as accumulating rgsw ciphertext
1903 let mut rgsw_i = shares[0].rgsw_cts()[index].clone();
1904
1905 shares.iter().skip(1).for_each(|si| {
1906 // copy over si's RGSW[index] ciphertext and send to evaluation domain
1907 izip!(tmp_rgsw.iter_rows_mut(), si.rgsw_cts()[index].iter_rows()).for_each(
1908 |(to_ri, from_ri)| {
1909 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
1910 rlweq_nttop.forward(to_ri.as_mut())
1911 },
1912 );
1913
1914 rgsw_by_rgsw_inplace(
1915 &mut rgsw_i,
1916 &tmp_rgsw,
1917 &rgsw_by_rgsw_decomposer,
1918 &mut scratch_matrix,
1919 rlweq_nttop,
1920 rlweq_modop,
1921 );
1922 });
1923
1924 rgsw_i
1925 });
1926 // d_a and d_b may differ for RGSWxRGSW multiplication and RLWExRGSW
1927 // multiplication. After this point RGSW ciphertexts will only be used for
1928 // RLWExRGSW multiplication (in blind rotation). Thus we drop any additional
1929 // RLWE ciphertexts in RGSW ciphertexts after RGSw x RGSW multiplication
1930 let rgsw_cts = rgsw_cts
1931 .map(|ct_i_in| {
1932 trim_rgsw_ct_matrix_from_rgrg_to_rlrg(
1933 ct_i_in,
1934 self.parameters().rgsw_by_rgsw_decomposition_params(),
1935 self.parameters().rlwe_by_rgsw_decomposition_params(),
1936 )
1937 })
1938 .collect_vec();
1939
1940 // LWE ksks
1941 let mut lwe_ksk = M::R::zeros(rlwe_n * parameters.lwe_decomposition_count().0);
1942 let lweq_modop = &self.pbs_info.lwe_modop;
1943 shares.iter().for_each(|si| {
1944 assert!(si.lwe_ksk().as_ref().len() == rlwe_n * parameters.lwe_decomposition_count().0);
1945 lweq_modop.elwise_add_mut(lwe_ksk.as_mut(), si.lwe_ksk().as_ref())
1946 });
1947
1948 SeededMultiPartyServerKey::new(rgsw_cts, auto_keys, lwe_ksk, cr_seed.clone(), parameters)
1949 }
1950}
1951
1952impl<M, NttOp, RlweModOp, LweModOp, Skey> BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
1953where
1954 M: MatrixMut + MatrixEntity,
1955 M::R: RowMut + RowEntity,
1956 M::MatElement: PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo,
1957 RlweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1958 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1959 NttOp: Ntt<Element = M::MatElement>,
1960{
1961 /// Returns c0 + c1 + Q/4
1962 fn _add_and_shift_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
1963 let modop = &self.pbs_info.rlwe_modop;
1964 modop.elwise_add_mut(c0.as_mut(), c1.as_ref());
1965 // +Q/4
1966 c0.as_mut()[0] = modop.add(&c0.as_ref()[0], &self.pbs_info.rlwe_qby4);
1967 }
1968
1969 /// Returns 2(c0 - c1) + Q/4
1970 fn _subtract_double_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
1971 let modop = &self.pbs_info.rlwe_modop;
1972 // c0 - c1
1973 modop.elwise_sub_mut(c0.as_mut(), c1.as_ref());
1974
1975 // double
1976 c0.as_mut().iter_mut().for_each(|v| *v = modop.add(v, v));
1977 }
1978}
1979
1980impl<M, NttOp, RlweModOp, LweModOp, Skey> BooleanGates
1981 for BoolEvaluator<M, NttOp, RlweModOp, LweModOp, Skey>
1982where
1983 M: MatrixMut + MatrixEntity,
1984 M::R: RowMut + RowEntity + Clone,
1985 M::MatElement:
1986 PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo + From<bool>,
1987 RlweModOp: VectorOps<Element = M::MatElement>
1988 + ArithmeticOps<Element = M::MatElement>
1989 + ShoupMatrixFMA<M::R>,
1990 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1991 NttOp: Ntt<Element = M::MatElement>,
1992 Skey: PbsKey<AutoKey = <Skey as PbsKey>::RgswCt, LweKskKey = M>,
1993 <Skey as PbsKey>::RgswCt: WithShoupRepr<M = M>,
1994{
1995 type Ciphertext = M::R;
1996 type Key = Skey;
1997
1998 fn nand_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1999 self._add_and_shift_lwe_cts(c0, c1);
2000
2001 // PBS
2002 pbs(
2003 &self.pbs_info,
2004 &self.nand_test_vec,
2005 c0,
2006 server_key,
2007 &mut self.scratch_memory.lwe_vector,
2008 &mut self.scratch_memory.decomposition_matrix,
2009 );
2010 }
2011
2012 fn and_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2013 self._add_and_shift_lwe_cts(c0, c1);
2014
2015 // PBS
2016 pbs(
2017 &self.pbs_info,
2018 &self.and_test_vec,
2019 c0,
2020 server_key,
2021 &mut self.scratch_memory.lwe_vector,
2022 &mut self.scratch_memory.decomposition_matrix,
2023 );
2024 }
2025
2026 fn or_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2027 self._add_and_shift_lwe_cts(c0, c1);
2028
2029 // PBS
2030 pbs(
2031 &self.pbs_info,
2032 &self.or_test_vec,
2033 c0,
2034 server_key,
2035 &mut self.scratch_memory.lwe_vector,
2036 &mut self.scratch_memory.decomposition_matrix,
2037 );
2038 }
2039
2040 fn nor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2041 self._add_and_shift_lwe_cts(c0, c1);
2042
2043 // PBS
2044 pbs(
2045 &self.pbs_info,
2046 &self.nor_test_vec,
2047 c0,
2048 server_key,
2049 &mut self.scratch_memory.lwe_vector,
2050 &mut self.scratch_memory.decomposition_matrix,
2051 )
2052 }
2053
2054 fn xor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2055 self._subtract_double_lwe_cts(c0, c1);
2056
2057 // PBS
2058 pbs(
2059 &self.pbs_info,
2060 &self.xor_test_vec,
2061 c0,
2062 server_key,
2063 &mut self.scratch_memory.lwe_vector,
2064 &mut self.scratch_memory.decomposition_matrix,
2065 );
2066 }
2067
2068 fn xnor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
2069 self._subtract_double_lwe_cts(c0, c1);
2070
2071 // PBS
2072 pbs(
2073 &self.pbs_info,
2074 &self.xnor_test_vec,
2075 c0,
2076 server_key,
2077 &mut self.scratch_memory.lwe_vector,
2078 &mut self.scratch_memory.decomposition_matrix,
2079 );
2080 }
2081
2082 fn not_inplace(&mut self, c0: &mut M::R) {
2083 let modop = &self.pbs_info.rlwe_modop;
2084 c0.as_mut().iter_mut().for_each(|v| *v = modop.neg(v));
2085 }
2086
2087 fn and(
2088 &mut self,
2089 c0: &Self::Ciphertext,
2090 c1: &Self::Ciphertext,
2091 key: &Self::Key,
2092 ) -> Self::Ciphertext {
2093 let mut out = c0.clone();
2094 self.and_inplace(&mut out, c1, key);
2095 out
2096 }
2097
2098 fn nand(
2099 &mut self,
2100 c0: &Self::Ciphertext,
2101 c1: &Self::Ciphertext,
2102 key: &Self::Key,
2103 ) -> Self::Ciphertext {
2104 let mut out = c0.clone();
2105 self.nand_inplace(&mut out, c1, key);
2106 out
2107 }
2108
2109 fn or(
2110 &mut self,
2111 c0: &Self::Ciphertext,
2112 c1: &Self::Ciphertext,
2113 key: &Self::Key,
2114 ) -> Self::Ciphertext {
2115 let mut out = c0.clone();
2116 self.or_inplace(&mut out, c1, key);
2117 out
2118 }
2119
2120 fn nor(
2121 &mut self,
2122 c0: &Self::Ciphertext,
2123 c1: &Self::Ciphertext,
2124 key: &Self::Key,
2125 ) -> Self::Ciphertext {
2126 let mut out = c0.clone();
2127 self.nor_inplace(&mut out, c1, key);
2128 out
2129 }
2130
2131 fn xnor(
2132 &mut self,
2133 c0: &Self::Ciphertext,
2134 c1: &Self::Ciphertext,
2135 key: &Self::Key,
2136 ) -> Self::Ciphertext {
2137 let mut out = c0.clone();
2138 self.xnor_inplace(&mut out, c1, key);
2139 out
2140 }
2141
2142 fn xor(
2143 &mut self,
2144 c0: &Self::Ciphertext,
2145 c1: &Self::Ciphertext,
2146 key: &Self::Key,
2147 ) -> Self::Ciphertext {
2148 let mut out = c0.clone();
2149 self.xor_inplace(&mut out, c1, key);
2150 out
2151 }
2152
2153 fn not(&mut self, c: &Self::Ciphertext) -> Self::Ciphertext {
2154 let mut out = c.clone();
2155 self.not_inplace(&mut out);
2156 out
2157 }
2158}
2159
2160#[cfg(test)]
2161mod tests {
2162 use bool::parameters::{MP_BOOL_PARAMS, SP_BOOL_PARAMS};
2163 use rand::{thread_rng, Rng};
2164 use rand_distr::Uniform;
2165
2166 use crate::{
2167 backend::ModulusPowerOf2,
2168 bool::{
2169 self, CommonReferenceSeededMultiPartyServerKeyShare, PublicKey,
2170 SeededMultiPartyServerKey, NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS, SMALL_MP_BOOL_PARAMS,
2171 },
2172 ntt::NttBackendU64,
2173 random::{RandomElementInModulus, DEFAULT_RNG},
2174 rgsw::{
2175 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
2176 tests::{_measure_noise_rgsw, _sk_encrypt_rlwe},
2177 RgswCiphertext, RgswCiphertextEvaluationDomain, SeededRgswCiphertext,
2178 SeededRlweCiphertext,
2179 },
2180 utils::{negacyclic_mul, Stats},
2181 };
2182
2183 use super::*;
2184
2185 #[test]
2186 fn bool_encrypt_decrypt_works() {
2187 let bool_evaluator = BoolEvaluator::<
2188 Vec<Vec<u64>>,
2189 NttBackendU64,
2190 ModularOpsU64<CiphertextModulus<u64>>,
2191 ModularOpsU64<CiphertextModulus<u64>>,
2192 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2193 >::new(SP_BOOL_PARAMS);
2194 let client_key = bool_evaluator.client_key();
2195
2196 let mut m = true;
2197 for _ in 0..1000 {
2198 let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
2199 let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
2200 assert_eq!(m, m_back);
2201 m = !m;
2202 }
2203 }
2204
2205 #[test]
2206 fn bool_nand() {
2207 let mut bool_evaluator = BoolEvaluator::<
2208 Vec<Vec<u64>>,
2209 NttBackendU64,
2210 ModularOpsU64<CiphertextModulus<u64>>,
2211 ModularOpsU64<CiphertextModulus<u64>>,
2212 ShoupServerKeyEvaluationDomain<_>,
2213 >::new(SP_BOOL_PARAMS);
2214
2215 // println!("{:?}", bool_evaluator.nand_test_vec);
2216 let client_key = bool_evaluator.client_key();
2217 let seeded_server_key = bool_evaluator.single_party_server_key(&client_key);
2218 let runtime_server_key =
2219 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2220 _,
2221 _,
2222 DefaultSecureRng,
2223 NttBackendU64,
2224 >::from(&seeded_server_key));
2225
2226 let mut m0 = false;
2227 let mut m1 = true;
2228
2229 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
2230 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
2231
2232 for _ in 0..500 {
2233 let ct_back = bool_evaluator.nand(&ct0, &ct1, &runtime_server_key);
2234
2235 let m_out = !(m0 && m1);
2236
2237 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
2238 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
2239
2240 m1 = m0;
2241 m0 = m_out;
2242
2243 ct1 = ct0;
2244 ct0 = ct_back;
2245 }
2246 }
2247
2248 #[test]
2249 fn bool_xor() {
2250 let mut bool_evaluator = BoolEvaluator::<
2251 Vec<Vec<u64>>,
2252 NttBackendU64,
2253 ModularOpsU64<CiphertextModulus<u64>>,
2254 ModularOpsU64<CiphertextModulus<u64>>,
2255 ShoupServerKeyEvaluationDomain<_>,
2256 >::new(SP_BOOL_PARAMS);
2257
2258 // println!("{:?}", bool_evaluator.nand_test_vec);
2259 let client_key = bool_evaluator.client_key();
2260 let seeded_server_key = bool_evaluator.single_party_server_key(&client_key);
2261 let runtime_server_key =
2262 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2263 _,
2264 _,
2265 DefaultSecureRng,
2266 NttBackendU64,
2267 >::from(&seeded_server_key));
2268
2269 let mut m0 = false;
2270 let mut m1 = true;
2271
2272 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
2273 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
2274
2275 for _ in 0..1000 {
2276 let ct_back = bool_evaluator.xor(&ct0, &ct1, &runtime_server_key);
2277 let m_out = (m0 ^ m1);
2278
2279 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
2280 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
2281
2282 m1 = m0;
2283 m0 = m_out;
2284
2285 ct1 = ct0;
2286 ct0 = ct_back;
2287 }
2288 }
2289
2290 #[test]
2291 fn multi_party_encryption_decryption() {
2292 let bool_evaluator = BoolEvaluator::<
2293 Vec<Vec<u64>>,
2294 NttBackendU64,
2295 ModularOpsU64<CiphertextModulus<u64>>,
2296 ModularOpsU64<CiphertextModulus<u64>>,
2297 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2298 >::new(MP_BOOL_PARAMS);
2299
2300 let no_of_parties = 500;
2301 let parties = (0..no_of_parties)
2302 .map(|_| bool_evaluator.client_key())
2303 .collect_vec();
2304
2305 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2306 parties.iter().for_each(|k| {
2307 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2308 *ideal_i = *ideal_i + s_i;
2309 });
2310 });
2311
2312 let mut m = true;
2313 for i in 0..100 {
2314 let pk_cr_seed = [0u8; 32];
2315
2316 let public_key_share = parties
2317 .iter()
2318 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2319 .collect_vec();
2320
2321 let collective_pk = PublicKey::<
2322 Vec<Vec<u64>>,
2323 DefaultSecureRng,
2324 ModularOpsU64<CiphertextModulus<u64>>,
2325 >::from(public_key_share.as_slice());
2326 let lwe_ct = bool_evaluator.pk_encrypt(collective_pk.key(), m);
2327
2328 let decryption_shares = parties
2329 .iter()
2330 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct, k))
2331 .collect_vec();
2332
2333 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
2334
2335 {
2336 let ideal_m = if m {
2337 bool_evaluator.pbs_info.parameters.rlwe_q().true_el()
2338 } else {
2339 bool_evaluator.pbs_info.parameters.rlwe_q().false_el()
2340 };
2341 let noise = measure_noise_lwe(
2342 &lwe_ct,
2343 &ideal_rlwe_sk,
2344 &bool_evaluator.pbs_info.rlwe_modop,
2345 &ideal_m,
2346 );
2347 println!("Noise: {noise}");
2348 }
2349
2350 assert_eq!(m_back, m);
2351 m = !m;
2352 }
2353 }
2354
2355 fn _collecitve_public_key_gen(rlwe_q: u64, parties_rlwe_sk: &[RlweSecret]) -> Vec<Vec<u64>> {
2356 let ring_size = parties_rlwe_sk[0].values.len();
2357 assert!(ring_size.is_power_of_two());
2358 let mut rng = DefaultSecureRng::new();
2359 let nttop = NttBackendU64::new(&rlwe_q, ring_size);
2360 let modop = ModularOpsU64::new(rlwe_q);
2361
2362 // Generate Pk shares
2363 let pk_seed = [0u8; 32];
2364 let pk_shares = parties_rlwe_sk.iter().map(|sk| {
2365 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2366 let mut share_out = vec![0u64; ring_size];
2367 public_key_share(
2368 &mut share_out,
2369 sk.values(),
2370 &modop,
2371 &nttop,
2372 &mut p_rng,
2373 &mut rng,
2374 );
2375 share_out
2376 });
2377
2378 let mut pk_part_b = vec![0u64; ring_size];
2379 pk_shares.for_each(|share| modop.elwise_add_mut(&mut pk_part_b, &share));
2380 let mut pk_part_a = vec![0u64; ring_size];
2381 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2382 RandomFillUniformInModulus::random_fill(&mut p_rng, &rlwe_q, pk_part_a.as_mut_slice());
2383
2384 vec![pk_part_a, pk_part_b]
2385 }
2386
2387 fn _multi_party_all_keygen(
2388 bool_evaluator: &BoolEvaluator<
2389 Vec<Vec<u64>>,
2390 NttBackendU64,
2391 ModularOpsU64<CiphertextModulus<u64>>,
2392 ModularOpsU64<CiphertextModulus<u64>>,
2393 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2394 >,
2395 no_of_parties: usize,
2396 ) -> (
2397 Vec<ClientKey>,
2398 PublicKey<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64<CiphertextModulus<u64>>>,
2399 Vec<
2400 CommonReferenceSeededMultiPartyServerKeyShare<
2401 Vec<Vec<u64>>,
2402 BoolParameters<u64>,
2403 [u8; 32],
2404 >,
2405 >,
2406 SeededMultiPartyServerKey<Vec<Vec<u64>>, [u8; 32], BoolParameters<u64>>,
2407 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2408 ClientKey,
2409 ) {
2410 let parties = (0..no_of_parties)
2411 .map(|_| bool_evaluator.client_key())
2412 .collect_vec();
2413
2414 let mut rng = DefaultSecureRng::new();
2415
2416 // Collective public key
2417 let mut pk_cr_seed = [0u8; 32];
2418 rng.fill_bytes(&mut pk_cr_seed);
2419 let public_key_share = parties
2420 .iter()
2421 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2422 .collect_vec();
2423 let collective_pk =
2424 PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, _>::from(public_key_share.as_slice());
2425
2426 // Server key
2427 let mut pbs_cr_seed = [0u8; 32];
2428 rng.fill_bytes(&mut pbs_cr_seed);
2429 let server_key_shares = parties
2430 .iter()
2431 .map(|k| {
2432 bool_evaluator.multi_party_server_key_share(pbs_cr_seed, &collective_pk.key(), k)
2433 })
2434 .collect_vec();
2435 let seeded_server_key =
2436 bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
2437 let runtime_server_key =
2438 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2439 _,
2440 _,
2441 DefaultSecureRng,
2442 NttBackendU64,
2443 >::from(&seeded_server_key));
2444
2445 // construct ideal rlwe sk for meauring noise
2446 let ideal_client_key = {
2447 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2448 parties.iter().for_each(|k| {
2449 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2450 *ideal_i = *ideal_i + s_i;
2451 });
2452 });
2453 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.pbs_info.lwe_n()];
2454 parties.iter().for_each(|k| {
2455 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe().values()).for_each(|(ideal_i, s_i)| {
2456 *ideal_i = *ideal_i + s_i;
2457 });
2458 });
2459
2460 ClientKey::new(
2461 RlweSecret {
2462 values: ideal_rlwe_sk,
2463 },
2464 LweSecret {
2465 values: ideal_lwe_sk,
2466 },
2467 )
2468 };
2469
2470 (
2471 parties,
2472 collective_pk,
2473 server_key_shares,
2474 seeded_server_key,
2475 runtime_server_key,
2476 ideal_client_key,
2477 )
2478 }
2479
2480 #[test]
2481 fn multi_party_nand() {
2482 let mut bool_evaluator = BoolEvaluator::<
2483 Vec<Vec<u64>>,
2484 NttBackendU64,
2485 ModularOpsU64<CiphertextModulus<u64>>,
2486 ModularOpsU64<CiphertextModulus<u64>>,
2487 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2488 >::new(MP_BOOL_PARAMS);
2489
2490 let (parties, collective_pk, _, _, server_key_eval, ideal_client_key) =
2491 _multi_party_all_keygen(&bool_evaluator, 2);
2492
2493 let mut m0 = true;
2494 let mut m1 = false;
2495
2496 let mut lwe0 = bool_evaluator.pk_encrypt(collective_pk.key(), m0);
2497 let mut lwe1 = bool_evaluator.pk_encrypt(collective_pk.key(), m1);
2498
2499 for _ in 0..2000 {
2500 let lwe_out = bool_evaluator.nand(&lwe0, &lwe1, &server_key_eval);
2501
2502 let m_expected = !(m0 & m1);
2503
2504 // multi-party decrypt
2505 let decryption_shares = parties
2506 .iter()
2507 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_out, k))
2508 .collect_vec();
2509 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
2510
2511 let m_back = bool_evaluator.sk_decrypt(&lwe_out, &ideal_client_key);
2512
2513 assert!(
2514 m_expected == m_back,
2515 "Expected {m_expected}, got
2516{m_back}"
2517 );
2518 m1 = m0;
2519 m0 = m_expected;
2520
2521 lwe1 = lwe0;
2522 lwe0 = lwe_out;
2523 }
2524 }
2525
2526 #[test]
2527 fn noise_tester() {
2528 let bool_evaluator = BoolEvaluator::<
2529 Vec<Vec<u64>>,
2530 NttBackendU64,
2531 ModularOpsU64<CiphertextModulus<u64>>,
2532 ModularOpsU64<CiphertextModulus<u64>>,
2533 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2534 >::new(SMALL_MP_BOOL_PARAMS);
2535
2536 // let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2537 // _multi_party_all_keygen(&bool_evaluator, 20);
2538 let no_of_parties = 16;
2539 let lwe_q = bool_evaluator.pbs_info.parameters.lwe_q();
2540 let rlwe_q = bool_evaluator.pbs_info.parameters.rlwe_q();
2541 let lwe_n = bool_evaluator.pbs_info.parameters.lwe_n().0;
2542 let rlwe_n = bool_evaluator.pbs_info.parameters.rlwe_n().0;
2543 let lwe_modop = &bool_evaluator.pbs_info.lwe_modop;
2544 let rlwe_nttop = &bool_evaluator.pbs_info.rlwe_nttop;
2545 let rlwe_modop = &bool_evaluator.pbs_info.rlwe_modop;
2546
2547 // let rgsw_rgsw_decomposer = &bool_evaluator
2548 // .pbs_info
2549 // .parameters
2550 // .rgsw_rgsw_decomposer::<DefaultDecomposer<u64>>();
2551 // let rgsw_rgsw_gadget_a = rgsw_rgsw_decomposer.0.gadget_vector();
2552 // let rgsw_rgsw_gadget_b = rgsw_rgsw_decomposer.1.gadget_vector();
2553
2554 let rlwe_rgsw_decomposer = &bool_evaluator.pbs_info.rlwe_rgsw_decomposer;
2555 let rlwe_rgsw_gadget_a = rlwe_rgsw_decomposer.0.gadget_vector();
2556 let rlwe_rgsw_gadget_b = rlwe_rgsw_decomposer.1.gadget_vector();
2557
2558 let auto_decomposer = &bool_evaluator.pbs_info.auto_decomposer;
2559 let auto_gadget = auto_decomposer.gadget_vector();
2560
2561 let parties = (0..no_of_parties)
2562 .map(|_| bool_evaluator.client_key())
2563 .collect_vec();
2564
2565 let ideal_client_key = {
2566 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2567 parties.iter().for_each(|k| {
2568 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2569 *ideal_i = *ideal_i + s_i;
2570 });
2571 });
2572 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.pbs_info.lwe_n()];
2573 parties.iter().for_each(|k| {
2574 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe().values()).for_each(|(ideal_i, s_i)| {
2575 *ideal_i = *ideal_i + s_i;
2576 });
2577 });
2578
2579 ClientKey::new(
2580 RlweSecret {
2581 values: ideal_rlwe_sk,
2582 },
2583 LweSecret {
2584 values: ideal_lwe_sk,
2585 },
2586 )
2587 };
2588
2589 // check noise in freshly encrypted RLWE ciphertext (ie var_fresh)
2590 if true {
2591 let mut rng = DefaultSecureRng::new();
2592 let mut check = Stats { samples: vec![] };
2593 for _ in 0..10 {
2594 // generate a new collective public key
2595 let mut pk_cr_seed = [0u8; 32];
2596 rng.fill_bytes(&mut pk_cr_seed);
2597 let public_key_share = parties
2598 .iter()
2599 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2600 .collect_vec();
2601 let collective_pk = PublicKey::<
2602 Vec<Vec<u64>>,
2603 DefaultSecureRng,
2604 ModularOpsU64<CiphertextModulus<u64>>,
2605 >::from(public_key_share.as_slice());
2606
2607 let mut m = vec![0u64; rlwe_n];
2608 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2609 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2610 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2611 &mut rlwe_ct,
2612 collective_pk.key(),
2613 &m,
2614 rlwe_modop,
2615 rlwe_nttop,
2616 &mut rng,
2617 );
2618
2619 let mut m_back = vec![0u64; rlwe_n];
2620 decrypt_rlwe(
2621 &rlwe_ct,
2622 ideal_client_key.sk_rlwe().values(),
2623 &mut m_back,
2624 rlwe_nttop,
2625 rlwe_modop,
2626 );
2627
2628 rlwe_modop.elwise_sub_mut(m_back.as_mut_slice(), m.as_slice());
2629
2630 check.add_more(Vec::<i64>::try_convert_from(&m_back, rlwe_q).as_slice());
2631 }
2632
2633 println!("Public key Std: {}", check.std_dev().abs().log2());
2634 }
2635
2636 if true {
2637 // Generate server key shares
2638 let mut rng = DefaultSecureRng::new();
2639 let mut pk_cr_seed = [0u8; 32];
2640 rng.fill_bytes(&mut pk_cr_seed);
2641 let public_key_share = parties
2642 .iter()
2643 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2644 .collect_vec();
2645 let collective_pk = PublicKey::<
2646 Vec<Vec<u64>>,
2647 DefaultSecureRng,
2648 ModularOpsU64<CiphertextModulus<u64>>,
2649 >::from(public_key_share.as_slice());
2650
2651 let pbs_cr_seed = [0u8; 32];
2652 rng.fill_bytes(&mut pk_cr_seed);
2653 let server_key_shares = parties
2654 .iter()
2655 .map(|k| {
2656 bool_evaluator.multi_party_server_key_share(pbs_cr_seed, collective_pk.key(), k)
2657 })
2658 .collect_vec();
2659
2660 let seeded_server_key =
2661 bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
2662
2663 // Check noise in RGSW ciphertexts of ideal LWE secret elements
2664 if false {
2665 let mut check = Stats { samples: vec![] };
2666 izip!(
2667 ideal_client_key.sk_lwe().values.iter(),
2668 seeded_server_key.rgsw_cts().iter()
2669 )
2670 .for_each(|(s_i, rgsw_ct_i)| {
2671 // X^{s[i]}
2672 let mut m_si = vec![0u64; rlwe_n];
2673 let s_i = *s_i * (bool_evaluator.pbs_info.embedding_factor as i32);
2674 if s_i < 0 {
2675 m_si[rlwe_n - (s_i.abs() as usize)] = rlwe_q.neg_one();
2676 } else {
2677 m_si[s_i as usize] = 1;
2678 }
2679
2680 // RLWE'(-sm)
2681 let mut neg_s_eval =
2682 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
2683 rlwe_modop.elwise_neg_mut(&mut neg_s_eval);
2684 rlwe_nttop.forward(&mut neg_s_eval);
2685 for j in 0..rlwe_rgsw_decomposer.a().decomposition_count() {
2686 // RLWE(B^{j} * -s[X]*X^{s_lwe[i]})
2687
2688 // -s[X]*X^{s_lwe[i]}*B_j
2689 let mut m_ideal = m_si.clone();
2690 rlwe_nttop.forward(m_ideal.as_mut_slice());
2691 rlwe_modop.elwise_mul_mut(m_ideal.as_mut_slice(), neg_s_eval.as_slice());
2692 rlwe_nttop.backward(m_ideal.as_mut_slice());
2693 rlwe_modop
2694 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_rgsw_gadget_a[j]);
2695
2696 // RLWE(-s*X^{s_lwe[i]}*B_j)
2697 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2698 rlwe_ct[0].copy_from_slice(&rgsw_ct_i[j]);
2699 rlwe_ct[1].copy_from_slice(
2700 &rgsw_ct_i[j + rlwe_rgsw_decomposer.a().decomposition_count()],
2701 );
2702
2703 let mut m_back = vec![0u64; rlwe_n];
2704 decrypt_rlwe(
2705 &rlwe_ct,
2706 ideal_client_key.sk_rlwe().values(),
2707 &mut m_back,
2708 rlwe_nttop,
2709 rlwe_modop,
2710 );
2711
2712 // diff
2713 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2714 check.add_more(&Vec::<i64>::try_convert_from(&m_back, rlwe_q));
2715 }
2716
2717 // RLWE'(m)
2718 for j in 0..rlwe_rgsw_decomposer.b().decomposition_count() {
2719 // RLWE(B^{j} * X^{s_lwe[i]})
2720
2721 // X^{s_lwe[i]}*B_j
2722 let mut m_ideal = m_si.clone();
2723 rlwe_modop
2724 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_rgsw_gadget_b[j]);
2725
2726 // RLWE(X^{s_lwe[i]}*B_j)
2727 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2728 rlwe_ct[0].copy_from_slice(
2729 &rgsw_ct_i[j + (2 * rlwe_rgsw_decomposer.a().decomposition_count())],
2730 );
2731 rlwe_ct[1].copy_from_slice(
2732 &rgsw_ct_i[j
2733 + (2 * rlwe_rgsw_decomposer.a().decomposition_count()
2734 + rlwe_rgsw_decomposer.b().decomposition_count())],
2735 );
2736
2737 let mut m_back = vec![0u64; rlwe_n];
2738 decrypt_rlwe(
2739 &rlwe_ct,
2740 ideal_client_key.sk_rlwe().values(),
2741 &mut m_back,
2742 rlwe_nttop,
2743 rlwe_modop,
2744 );
2745
2746 // diff
2747 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2748 check.add_more(&Vec::<i64>::try_convert_from(&m_back, rlwe_q));
2749 }
2750 });
2751 println!(
2752 "RGSW Std: {} {} ;; max={}",
2753 check.mean(),
2754 check.std_dev().abs().log2(),
2755 check.samples.iter().max().unwrap()
2756 );
2757 }
2758
2759 // server key in Evaluation domain
2760 let runtime_server_key =
2761 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2762 _,
2763 _,
2764 DefaultSecureRng,
2765 NttBackendU64,
2766 >::from(&seeded_server_key));
2767
2768 // check noise in RLWE x RGSW(X^{s_i}) where RGSW is accunulated RGSW ciphertext
2769 if false {
2770 let mut check = Stats { samples: vec![] };
2771
2772 ideal_client_key
2773 .sk_lwe()
2774 .values()
2775 .iter()
2776 .enumerate()
2777 .for_each(|(index, s_i)| {
2778 let rgsw_ct_i = runtime_server_key.rgsw_ct_lwe_si(index).as_ref();
2779
2780 let mut m = vec![0u64; rlwe_n];
2781 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2782 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2783 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2784 &mut rlwe_ct,
2785 collective_pk.key(),
2786 &m,
2787 rlwe_modop,
2788 rlwe_nttop,
2789 &mut rng,
2790 );
2791
2792 let mut rlwe_after = RlweCiphertext::<_, DefaultSecureRng> {
2793 data: rlwe_ct.clone(),
2794 is_trivial: false,
2795 _phatom: PhantomData,
2796 };
2797 let mut scratch = vec![
2798 vec![0u64; rlwe_n];
2799 std::cmp::max(
2800 rlwe_rgsw_decomposer.0.decomposition_count(),
2801 rlwe_rgsw_decomposer.1.decomposition_count()
2802 ) + 2
2803 ];
2804 rlwe_by_rgsw(
2805 &mut rlwe_after,
2806 rgsw_ct_i,
2807 &mut scratch,
2808 rlwe_rgsw_decomposer,
2809 rlwe_nttop,
2810 rlwe_modop,
2811 );
2812
2813 // m1 = X^{s[i]}
2814 let mut m1 = vec![0u64; rlwe_n];
2815 let s_i = *s_i * (bool_evaluator.pbs_info.embedding_factor as i32);
2816 if s_i < 0 {
2817 m1[rlwe_n - (s_i.abs() as usize)] = rlwe_q.neg_one()
2818 } else {
2819 m1[s_i as usize] = 1;
2820 }
2821
2822 // (m+e) * m1
2823 let mut m_plus_e_times_m1 = vec![0u64; rlwe_n];
2824 decrypt_rlwe(
2825 &rlwe_ct,
2826 ideal_client_key.sk_rlwe().values(),
2827 &mut m_plus_e_times_m1,
2828 rlwe_nttop,
2829 rlwe_modop,
2830 );
2831 rlwe_nttop.forward(m_plus_e_times_m1.as_mut_slice());
2832 rlwe_nttop.forward(m1.as_mut_slice());
2833
2834 rlwe_modop.elwise_mul_mut(m_plus_e_times_m1.as_mut_slice(), m1.as_slice());
2835 rlwe_nttop.backward(m_plus_e_times_m1.as_mut_slice());
2836
2837 // Resulting RLWE ciphertext will equal: (m0m1 + em1) + e_{rlsw x rgsw}.
2838 // Hence, resulting rlwe ciphertext will have error em1 + e_{rlwe x rgsw}.
2839 // Here we're only concerned with e_{rlwe x rgsw}, that is noise added by
2840 // RLWExRGSW. Also note in practice m1 is a monomial, for ex, X^{s_{i}}, for
2841 // some i and var(em1) = var(e).
2842 let mut m_plus_e_times_m1_more_e = vec![0u64; rlwe_n];
2843 decrypt_rlwe(
2844 &rlwe_after,
2845 ideal_client_key.sk_rlwe().values(),
2846 &mut m_plus_e_times_m1_more_e,
2847 rlwe_nttop,
2848 rlwe_modop,
2849 );
2850
2851 // diff
2852 rlwe_modop.elwise_sub_mut(
2853 m_plus_e_times_m1_more_e.as_mut_slice(),
2854 m_plus_e_times_m1.as_slice(),
2855 );
2856
2857 // let noise = measure_noise(
2858 // &rlwe_after,
2859 // &m_plus_e_times_m1,
2860 // rlwe_nttop,
2861 // rlwe_modop,
2862 // ideal_client_key.sk_rlwe.values(),
2863 // );
2864 // print!("NOISE: {}", noise);
2865
2866 check.add_more(&Vec::<i64>::try_convert_from(
2867 &m_plus_e_times_m1_more_e,
2868 rlwe_q,
2869 ));
2870 });
2871 println!(
2872 "RLWE x RGSW, where RGSW has noise var_brk, std: {} {}",
2873 check.std_dev(),
2874 check.std_dev().abs().log2()
2875 )
2876 }
2877
2878 // check noise in Auto key
2879 if false {
2880 let mut check = Stats { samples: vec![] };
2881
2882 let mut neg_s_poly =
2883 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
2884 rlwe_modop.elwise_neg_mut(neg_s_poly.as_mut_slice());
2885
2886 let g = bool_evaluator.pbs_info.g();
2887 let br_q = bool_evaluator.pbs_info.br_q();
2888 let auto_element_dlogs = bool_evaluator.pbs_info.parameters.auto_element_dlogs();
2889 for i in auto_element_dlogs.into_iter() {
2890 let g_pow = if i == 0 {
2891 -g
2892 } else {
2893 (((g as usize).pow(i as u32)) % br_q) as isize
2894 };
2895
2896 // -s[X^k]
2897 let (auto_indices, auto_sign) = generate_auto_map(rlwe_n, g_pow);
2898 let mut neg_s_poly_auto_i = vec![0u64; rlwe_n];
2899 izip!(neg_s_poly.iter(), auto_indices.iter(), auto_sign.iter()).for_each(
2900 |(v, to_i, to_sign)| {
2901 if !to_sign {
2902 neg_s_poly_auto_i[*to_i] = rlwe_modop.neg(v);
2903 } else {
2904 neg_s_poly_auto_i[*to_i] = *v;
2905 }
2906 },
2907 );
2908
2909 let mut auto_key_i = runtime_server_key.galois_key_for_auto(i).as_ref().clone(); //send i^th auto key to coefficient domain
2910 auto_key_i
2911 .iter_mut()
2912 .for_each(|r| rlwe_nttop.backward(r.as_mut_slice()));
2913 auto_gadget.iter().enumerate().for_each(|(i, b_i)| {
2914 // B^i * -s[X^k]
2915 let mut m_ideal = neg_s_poly_auto_i.clone();
2916
2917 rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut_slice(), b_i);
2918
2919 let mut m_out = vec![0u64; rlwe_n];
2920 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2921 rlwe_ct[0].copy_from_slice(&auto_key_i[i]);
2922 rlwe_ct[1].copy_from_slice(
2923 &auto_key_i[auto_decomposer.decomposition_count() + i],
2924 );
2925 decrypt_rlwe(
2926 &rlwe_ct,
2927 ideal_client_key.sk_rlwe().values(),
2928 &mut m_out,
2929 rlwe_nttop,
2930 rlwe_modop,
2931 );
2932
2933 // diff
2934 rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(), m_ideal.as_slice());
2935
2936 check.add_more(&Vec::<i64>::try_convert_from(&m_out, rlwe_q));
2937 });
2938 }
2939
2940 println!("Auto key noise std dev: {}", check.std_dev().abs().log2());
2941 }
2942
2943 // check noise in RLWE(X^k) after sending RLWE(X) -> RLWE(X^k)using collective
2944 // auto key
2945 if true {
2946 let mut check = Stats { samples: vec![] };
2947 let br_q = bool_evaluator.pbs_info.br_q();
2948 let g = bool_evaluator.pbs_info.g();
2949 let auto_element_dlogs = bool_evaluator.pbs_info.parameters.auto_element_dlogs();
2950 for i in auto_element_dlogs.into_iter() {
2951 for _ in 0..10 {
2952 let mut m = vec![0u64; rlwe_n];
2953 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2954 let mut rlwe_ct = RlweCiphertext::<_, DefaultSecureRng> {
2955 data: vec![vec![0u64; rlwe_n]; 2],
2956 is_trivial: false,
2957 _phatom: PhantomData,
2958 };
2959 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2960 &mut rlwe_ct,
2961 collective_pk.key(),
2962 &m,
2963 rlwe_modop,
2964 rlwe_nttop,
2965 &mut rng,
2966 );
2967
2968 // We're only interested in noise increased as a result of automorphism.
2969 // Hence, we take m+e as the bench.
2970 let mut m_plus_e = vec![0u64; rlwe_n];
2971 decrypt_rlwe(
2972 &rlwe_ct,
2973 ideal_client_key.sk_rlwe().values(),
2974 &mut m_plus_e,
2975 rlwe_nttop,
2976 rlwe_modop,
2977 );
2978
2979 let auto_key = runtime_server_key.galois_key_for_auto(i).as_ref();
2980 let (auto_map_index, auto_map_sign) =
2981 bool_evaluator.pbs_info.rlwe_auto_map(i);
2982 let mut scratch =
2983 vec![vec![0u64; rlwe_n]; auto_decomposer.decomposition_count() + 2];
2984 galois_auto(
2985 &mut rlwe_ct,
2986 auto_key,
2987 &mut scratch,
2988 &auto_map_index,
2989 &auto_map_sign,
2990 rlwe_modop,
2991 rlwe_nttop,
2992 auto_decomposer,
2993 );
2994
2995 // send m+e from X to X^k
2996 let mut m_plus_e_auto = vec![0u64; rlwe_n];
2997 izip!(m_plus_e.iter(), auto_map_index.iter(), auto_map_sign.iter())
2998 .for_each(|(v, to_index, to_sign)| {
2999 if !to_sign {
3000 m_plus_e_auto[*to_index] = rlwe_modop.neg(v);
3001 } else {
3002 m_plus_e_auto[*to_index] = *v
3003 }
3004 });
3005
3006 let mut m_out = vec![0u64; rlwe_n];
3007 decrypt_rlwe(
3008 &rlwe_ct,
3009 ideal_client_key.sk_rlwe().values(),
3010 &mut m_out,
3011 rlwe_nttop,
3012 rlwe_modop,
3013 );
3014
3015 // diff
3016 rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(), m_plus_e_auto.as_slice());
3017
3018 check.add_more(&Vec::<i64>::try_convert_from(m_out.as_slice(), rlwe_q));
3019 }
3020 }
3021
3022 println!("Rlwe Auto Noise Std: {}", check.std_dev().abs().log2());
3023 }
3024
3025 // Check noise growth in ksk
3026 // TODO check in LWE key switching keys
3027 if true {
3028 // 1. encrypt LWE ciphertext
3029 // 2. Key switching
3030 // 3.
3031 let mut check = Stats { samples: vec![] };
3032
3033 for _ in 0..1024 {
3034 // Encrypt m \in Q_{ks} using RLWE sk
3035 let mut lwe_in_ct = vec![0u64; rlwe_n + 1];
3036 let m = RandomElementInModulus::random(&mut rng, &lwe_q.q().unwrap());
3037 encrypt_lwe(
3038 &mut lwe_in_ct,
3039 &m,
3040 ideal_client_key.sk_rlwe().values(),
3041 lwe_modop,
3042 &mut rng,
3043 );
3044
3045 // Key switch
3046 let mut lwe_out = vec![0u64; lwe_n + 1];
3047 lwe_key_switch(
3048 &mut lwe_out,
3049 &lwe_in_ct,
3050 runtime_server_key.lwe_ksk(),
3051 lwe_modop,
3052 bool_evaluator.pbs_info.lwe_decomposer(),
3053 );
3054
3055 // We only care about noise added by LWE key switch
3056 // m+e
3057 let m_plus_e =
3058 decrypt_lwe(&lwe_in_ct, ideal_client_key.sk_rlwe().values(), lwe_modop);
3059
3060 let m_plus_e_plus_lwe_ksk_noise =
3061 decrypt_lwe(&lwe_out, ideal_client_key.sk_lwe().values(), lwe_modop);
3062
3063 let diff = lwe_modop.sub(&m_plus_e_plus_lwe_ksk_noise, &m_plus_e);
3064
3065 check.add_more(&vec![lwe_q.map_element_to_i64(&diff)]);
3066 }
3067
3068 println!("Lwe ksk std dev: {}", check.std_dev().abs().log2());
3069 }
3070 }
3071
3072 // Check noise in fresh RGSW ciphertexts, ie X^{s_j[i]}, must equalnoise in
3073 // // fresh RLWE ciphertext
3074 if true {}
3075 // test LWE ksk from RLWE -> LWE
3076 // if false {
3077 // let logp = 2;
3078 // let mut rng = DefaultSecureRng::new();
3079
3080 // let m = 1;
3081 // let encoded_m = m << (lwe_logq - logp);
3082
3083 // // Encrypt
3084 // let mut lwe_ct = vec![0u64; rlwe_n + 1];
3085 // encrypt_lwe(
3086 // &mut lwe_ct,
3087 // &encoded_m,
3088 // ideal_client_key.sk_rlwe.values(),
3089 // lwe_modop,
3090 // &mut rng,
3091 // );
3092
3093 // // key switch
3094 // let lwe_decomposer = &bool_evaluator.decomposer_lwe;
3095 // let mut lwe_out = vec![0u64; lwe_n + 1];
3096 // lwe_key_switch(
3097 // &mut lwe_out,
3098 // &lwe_ct,
3099 // &server_key_eval.lwe_ksk,
3100 // lwe_modop,
3101 // lwe_decomposer,
3102 // );
3103
3104 // let encoded_m_back = decrypt_lwe(&lwe_out,
3105 // ideal_client_key.sk_lwe.values(), lwe_modop); let m_back
3106 // = ((encoded_m_back as f64 * (1 << logp) as f64) /
3107 // (lwe_q as f64)).round() as u64; dbg!(m_back, m);
3108
3109 // let noise = measure_noise_lwe(
3110 // &lwe_out,
3111 // ideal_client_key.sk_lwe.values(),
3112 // lwe_modop,
3113 // &encoded_m,
3114 // );
3115
3116 // println!("Noise: {noise}");
3117 // }
3118
3119 // Measure noise in RGSW ciphertexts of ideal LWE secrets
3120 // if true {
3121 // let gadget_vec = gadget_vector(
3122 // bool_evaluator.parameters.rlwe_logq,
3123 // bool_evaluator.parameters.logb_rgsw,
3124 // bool_evaluator.parameters.d_rgsw,
3125 // );
3126
3127 // for i in 0..20 {
3128 // // measure noise in RGSW(s[i])
3129 // let si =
3130 // ideal_client_key.sk_lwe.values[i] *
3131 // (bool_evaluator.embedding_factor as i32); let mut
3132 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
3133 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
3134 // } else {
3135 // si_poly[(si.abs() as usize)] = 1;
3136 // }
3137
3138 // let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
3139 // rgsw_si
3140 // .iter_mut()
3141 // .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
3142
3143 // println!("####### Noise in RGSW(X^s_{i}) #######");
3144 // _measure_noise_rgsw(
3145 // &rgsw_si,
3146 // &si_poly,
3147 // ideal_client_key.sk_rlwe.values(),
3148 // &gadget_vec,
3149 // rlwe_q,
3150 // );
3151 // println!("####### ##################### #######");
3152 // }
3153 // }
3154
3155 // // measure noise grwoth in RLWExRGSW
3156 // if true {
3157 // let mut rng = DefaultSecureRng::new();
3158 // let mut carry_m = vec![0u64; rlwe_n];
3159 // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
3160 // carry_m.as_mut_slice());
3161
3162 // // RGSW(carrym)
3163 // let trivial_rlwect = vec![vec![0u64; rlwe_n],carry_m.clone()];
3164 // let mut rlwe_ct = RlweCiphertext::<_,
3165 // DefaultSecureRng>::from_raw(trivial_rlwect, true);
3166
3167 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
3168 // d_rgsw + 2]; let mul_mod =
3169 // |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
3170
3171 // for i in 0..bool_evaluator.parameters.lwe_n {
3172 // rlwe_by_rgsw(
3173 // &mut rlwe_ct,
3174 // server_key_eval.rgsw_ct_lwe_si(i),
3175 // &mut scratch_matrix_dplus2_ring,
3176 // rlwe_decomposer,
3177 // rlwe_nttop,
3178 // rlwe_modop,
3179 // );
3180
3181 // // carry_m[X] * s_i[X]
3182 // let si =
3183 // ideal_client_key.sk_lwe.values[i] *
3184 // (bool_evaluator.embedding_factor as i32); let mut
3185 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
3186 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
3187 // } else {
3188 // si_poly[(si.abs() as usize)] = 1;
3189 // }
3190 // carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod,
3191 // rlwe_q);
3192
3193 // let noise = measure_noise(
3194 // &rlwe_ct,
3195 // &carry_m,
3196 // rlwe_nttop,
3197 // rlwe_modop,
3198 // ideal_client_key.sk_rlwe.values(),
3199 // );
3200 // println!("Noise RLWE(carry_m) accumulating {i}^th secret
3201 // monomial: {noise}"); }
3202 // }
3203
3204 // // Check galois keys
3205 // if false {
3206 // let g = bool_evaluator.g() as isize;
3207 // let mut rng = DefaultSecureRng::new();
3208 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
3209 // d_rgsw + 2]; for i in [g, -g] {
3210 // let mut m = vec![0u64; rlwe_n];
3211 // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
3212 // m.as_mut_slice()); let mut rlwe_ct = {
3213 // let mut data = vec![vec![0u64; rlwe_n]; 2];
3214 // public_key_encrypt_rlwe(
3215 // &mut data,
3216 // &collective_pk.key,
3217 // &m,
3218 // rlwe_modop,
3219 // rlwe_nttop,
3220 // &mut rng,
3221 // );
3222 // RlweCiphertext::<_, DefaultSecureRng>::from_raw(data,
3223 // false) };
3224
3225 // let auto_key = server_key_eval.galois_key_for_auto(i);
3226 // let (auto_map_index, auto_map_sign) =
3227 // generate_auto_map(rlwe_n, i); galois_auto(
3228 // &mut rlwe_ct,
3229 // auto_key,
3230 // &mut scratch_matrix_dplus2_ring,
3231 // &auto_map_index,
3232 // &auto_map_sign,
3233 // rlwe_modop,
3234 // rlwe_nttop,
3235 // rlwe_decomposer,
3236 // );
3237
3238 // // send m(X) -> m(X^i)
3239 // let mut m_k = vec![0u64; rlwe_n];
3240 // izip!(m.iter(), auto_map_index.iter(),
3241 // auto_map_sign.iter()).for_each( |(mi, to_index,to_sign)|
3242 // // { if !to_sign {
3243 // m_k[*to_index] = rlwe_q - *mi; } else {
3244 // m_k[*to_index] = *mi;
3245 // }
3246 // },
3247 // );
3248
3249 // // measure noise
3250 // let noise = measure_noise(
3251 // &rlwe_ct,
3252 // &m_k,
3253 // rlwe_nttop,
3254 // rlwe_modop,
3255 // ideal_client_key.sk_rlwe.values(),
3256 // );
3257
3258 // println!("Noise after auto k={i}: {noise}");
3259 // }
3260 // }
3261 }
3262
3263 #[test]
3264 fn testtest() {
3265 let evaluator = BoolEvaluator::<
3266 Vec<Vec<u64>>,
3267 NttBackendU64,
3268 ModularOpsU64<CiphertextModulus<u64>>,
3269 ModulusPowerOf2<CiphertextModulus<u64>>,
3270 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
3271 >::new(NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS);
3272 let mp_seed = NonInteractiveMultiPartyCrs { seed: [1u8; 32] };
3273
3274 let ring_size = evaluator.parameters().rlwe_n().0;
3275 let rlwe_q = evaluator.parameters().rlwe_q();
3276 let rlwe_modop = evaluator.pbs_info().modop_rlweq();
3277 let nttop = evaluator.pbs_info().nttop_rlweq();
3278
3279 let parties = 2;
3280
3281 let cks = (0..parties)
3282 .map(|_| evaluator.non_interactive_client_key())
3283 .collect_vec();
3284
3285 let key_shares = (0..parties)
3286 .map(|i| evaluator.non_interactive_multi_party_key_share(&mp_seed, i, parties, &cks[i]))
3287 .collect_vec();
3288 // dbg!(key_shares[1].user_index);
3289
3290 let rgsw_cts = evaluator.aggregate_non_interactive_multi_party_key_share(
3291 &mp_seed,
3292 parties,
3293 &key_shares,
3294 );
3295
3296 let mut ideal_rlwe = vec![0; ring_size];
3297 cks.iter().for_each(|k| {
3298 izip!(ideal_rlwe.iter_mut(), k.sk_rlwe().values().iter()).for_each(|(a, b)| {
3299 *a = *a + b;
3300 });
3301 });
3302
3303 let mut ideal_lwe = vec![0; evaluator.parameters().lwe_n().0];
3304 cks.iter().for_each(|k| {
3305 izip!(ideal_lwe.iter_mut(), k.sk_lwe().values().iter()).for_each(|(a, b)| {
3306 *a = *a + b;
3307 });
3308 });
3309
3310 // let mut stats = Stats::new();
3311
3312 let (rlrg_decomp_a, rlrg_decomp_b) = evaluator
3313 .parameters()
3314 .rlwe_rgsw_decomposer::<DefaultDecomposer<u64>>();
3315 let gadget_vec_a = rlrg_decomp_a.gadget_vector();
3316 let gadget_vec_b = rlrg_decomp_b.gadget_vector();
3317 let d_a = rlrg_decomp_a.decomposition_count();
3318 let d_b = rlrg_decomp_b.decomposition_count();
3319 let s_poly = Vec::<u64>::try_convert_from(ideal_rlwe.as_slice(), rlwe_q);
3320 let mut neg_s_poly_eval = s_poly.clone();
3321 rlwe_modop.elwise_neg_mut(&mut neg_s_poly_eval);
3322 nttop.forward(neg_s_poly_eval.as_mut());
3323
3324 // rgsw_cts.iter().enumerate().for_each(|(s_index, ct)| {
3325 // // X^{lwe_s[i]}
3326 // let mut m = vec![0u64; ring_size];
3327 // if ideal_lwe[s_index] < 0 {
3328 // m[ring_size - (ideal_lwe[s_index].abs() as usize)] =
3329 // rlwe_q.neg_one(); } else {
3330 // m[(ideal_lwe[s_index] as usize)] = 1;
3331 // }
3332
3333 // let mut neg_sm = m.clone();
3334 // nttop.forward(&mut neg_sm);
3335 // rlwe_modop.elwise_mul_mut(&mut neg_sm, &neg_s_poly_eval);
3336 // nttop.backward(&mut neg_sm);
3337
3338 // // RLWE'(-sm)
3339 // gadget_vec_a.iter().enumerate().for_each(|(index, beta)| {
3340 // // RLWE(\beta -sm)
3341
3342 // // \beta * -sX^[lwe_s[i]]
3343 // let mut beta_neg_sm = neg_sm.clone();
3344 // rlwe_modop.elwise_scalar_mul_mut(&mut beta_neg_sm, beta);
3345
3346 // // extract RLWE(-sm \beta)
3347 // let mut rlwe = vec![vec![0u64; ring_size]; 2];
3348 // rlwe[0].copy_from_slice(&ct[index]);
3349 // rlwe[1].copy_from_slice(&ct[index + d_a]);
3350
3351 // // decrypt
3352 // let mut m_out = vec![0u64; ring_size];
3353 // decrypt_rlwe(&rlwe, &ideal_rlwe, &mut m_out, nttop,
3354 // rlwe_modop); // println!("{:?}", &beta_neg_sm);
3355
3356 // let mut diff = m_out;
3357 // rlwe_modop.elwise_sub_mut(&mut diff, &beta_neg_sm);
3358
3359 // stats.add_more(&Vec::<i64>::try_convert_from(&diff, rlwe_q));
3360 // });
3361 // });
3362
3363 // println!("Stats: {}", stats.std_dev().abs().log2());
3364 }
3365}
3366
3367// let (rgswrgsw_d_a, rgswrgsw_d_b) =
3368// self.pbs_info.parameters.rgsw_rgsw_decomposition_count(); let (rlrg_d_a,
3369// rlrg_d_b) = self.pbs_info.parameters.rlwe_rgsw_decomposition_count(); let
3370// rgsw_ct_rows_in = rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 * 2;
3371// let rgsw_ct_rows_out = rlrg_d_a.0 * 2 + rlrg_d_b.0 * 2;
3372// 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);
3373// 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);
3374// let rgsw_cts = rgsw_cts
3375// .map(|ct_i_in| {
3376// assert!(ct_i_in.dimension() == (rgsw_ct_rows_in, rlwe_n));
3377// let mut reduced_ct_i_out = M::zeros(rgsw_ct_rows_out, rlwe_n);
3378
3379// // RLWE'(-sm) part A
3380// izip!(
3381// reduced_ct_i_out.iter_rows_mut().take(rlrg_d_a.0),
3382// ct_i_in
3383// .iter_rows()
3384// .skip(rgswrgsw_d_a.0 - rlrg_d_a.0)
3385// .take(rlrg_d_a.0)
3386// )
3387// .for_each(|(to_ri, from_ri)| {
3388// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3389// });
3390
3391// // RLWE'(-sm) part B
3392// izip!(
3393// reduced_ct_i_out
3394// .iter_rows_mut()
3395// .skip(rlrg_d_a.0)
3396// .take(rlrg_d_a.0),
3397// ct_i_in
3398// .iter_rows()
3399// .skip(rgswrgsw_d_a.0 + (rgswrgsw_d_a.0 - rlrg_d_a.0))
3400// .take(rlrg_d_a.0)
3401// )
3402// .for_each(|(to_ri, from_ri)| {
3403// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3404// });
3405
3406// // RLWE'(m) Part A
3407// izip!(
3408// reduced_ct_i_out
3409// .iter_rows_mut()
3410// .skip(rlrg_d_a.0 * 2)
3411// .take(rlrg_d_b.0),
3412// ct_i_in
3413// .iter_rows()
3414// .skip(rgswrgsw_d_a.0 * 2 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
3415// .take(rlrg_d_b.0)
3416// )
3417// .for_each(|(to_ri, from_ri)| {
3418// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3419// });
3420
3421// // RLWE'(m) Part B
3422// izip!(
3423// reduced_ct_i_out
3424// .iter_rows_mut()
3425// .skip(rlrg_d_a.0 * 2 + rlrg_d_b.0)
3426// .take(rlrg_d_b.0),
3427// ct_i_in
3428// .iter_rows()
3429// .skip(rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 +
3430// (rgswrgsw_d_b.0 - rlrg_d_b.0)) .take(rlrg_d_b.0)
3431// )
3432// .for_each(|(to_ri, from_ri)| {
3433// to_ri.as_mut().copy_from_slice(from_ri.as_ref());
3434// });
3435
3436// reduced_ct_i_out
3437// })
3438// .collect_vec();