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).for_each(|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,
2170 NonInteractiveServerKeyEvaluationDomain, PublicKey, SeededMultiPartyServerKey,
2171 ShoupNonInteractiveServerKeyEvaluationDomain, NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS,
2172 SMALL_MP_BOOL_PARAMS,
2173 },
2174 ntt::NttBackendU64,
2175 random::{RandomElementInModulus, DEFAULT_RNG},
2176 rgsw::{
2177 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
2178 tests::{_measure_noise_rgsw, _sk_encrypt_rlwe},
2179 RgswCiphertext, RgswCiphertextEvaluationDomain, SeededRgswCiphertext,
2180 SeededRlweCiphertext,
2181 },
2182 utils::{negacyclic_mul, Stats},
2183 };
2184
2185 use super::*;
2186
2187 #[test]
2188 fn bool_encrypt_decrypt_works() {
2189 let bool_evaluator = BoolEvaluator::<
2190 Vec<Vec<u64>>,
2191 NttBackendU64,
2192 ModularOpsU64<CiphertextModulus<u64>>,
2193 ModularOpsU64<CiphertextModulus<u64>>,
2194 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2195 >::new(SP_BOOL_PARAMS);
2196 let client_key = bool_evaluator.client_key();
2197
2198 let mut m = true;
2199 for _ in 0..1000 {
2200 let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
2201 let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
2202 assert_eq!(m, m_back);
2203 m = !m;
2204 }
2205 }
2206
2207 #[test]
2208 fn bool_nand() {
2209 let mut bool_evaluator = BoolEvaluator::<
2210 Vec<Vec<u64>>,
2211 NttBackendU64,
2212 ModularOpsU64<CiphertextModulus<u64>>,
2213 ModularOpsU64<CiphertextModulus<u64>>,
2214 ShoupServerKeyEvaluationDomain<_>,
2215 >::new(SP_BOOL_PARAMS);
2216
2217 // println!("{:?}", bool_evaluator.nand_test_vec);
2218 let client_key = bool_evaluator.client_key();
2219 let seeded_server_key = bool_evaluator.single_party_server_key(&client_key);
2220 let runtime_server_key =
2221 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2222 _,
2223 _,
2224 DefaultSecureRng,
2225 NttBackendU64,
2226 >::from(&seeded_server_key));
2227
2228 let mut m0 = false;
2229 let mut m1 = true;
2230
2231 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
2232 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
2233
2234 for _ in 0..500 {
2235 let ct_back = bool_evaluator.nand(&ct0, &ct1, &runtime_server_key);
2236
2237 let m_out = !(m0 && m1);
2238
2239 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
2240 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
2241
2242 m1 = m0;
2243 m0 = m_out;
2244
2245 ct1 = ct0;
2246 ct0 = ct_back;
2247 }
2248 }
2249
2250 #[test]
2251 fn bool_xor() {
2252 let mut bool_evaluator = BoolEvaluator::<
2253 Vec<Vec<u64>>,
2254 NttBackendU64,
2255 ModularOpsU64<CiphertextModulus<u64>>,
2256 ModularOpsU64<CiphertextModulus<u64>>,
2257 ShoupServerKeyEvaluationDomain<_>,
2258 >::new(SP_BOOL_PARAMS);
2259
2260 // println!("{:?}", bool_evaluator.nand_test_vec);
2261 let client_key = bool_evaluator.client_key();
2262 let seeded_server_key = bool_evaluator.single_party_server_key(&client_key);
2263 let runtime_server_key =
2264 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2265 _,
2266 _,
2267 DefaultSecureRng,
2268 NttBackendU64,
2269 >::from(&seeded_server_key));
2270
2271 let mut m0 = false;
2272 let mut m1 = true;
2273
2274 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
2275 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
2276
2277 for _ in 0..1000 {
2278 let ct_back = bool_evaluator.xor(&ct0, &ct1, &runtime_server_key);
2279 let m_out = (m0 ^ m1);
2280
2281 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
2282 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
2283
2284 m1 = m0;
2285 m0 = m_out;
2286
2287 ct1 = ct0;
2288 ct0 = ct_back;
2289 }
2290 }
2291
2292 #[test]
2293 fn multi_party_encryption_decryption() {
2294 let bool_evaluator = BoolEvaluator::<
2295 Vec<Vec<u64>>,
2296 NttBackendU64,
2297 ModularOpsU64<CiphertextModulus<u64>>,
2298 ModularOpsU64<CiphertextModulus<u64>>,
2299 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2300 >::new(MP_BOOL_PARAMS);
2301
2302 let no_of_parties = 500;
2303 let parties = (0..no_of_parties)
2304 .map(|_| bool_evaluator.client_key())
2305 .collect_vec();
2306
2307 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2308 parties.iter().for_each(|k| {
2309 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2310 *ideal_i = *ideal_i + s_i;
2311 });
2312 });
2313
2314 let mut m = true;
2315 for i in 0..100 {
2316 let pk_cr_seed = [0u8; 32];
2317
2318 let public_key_share = parties
2319 .iter()
2320 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2321 .collect_vec();
2322
2323 let collective_pk = PublicKey::<
2324 Vec<Vec<u64>>,
2325 DefaultSecureRng,
2326 ModularOpsU64<CiphertextModulus<u64>>,
2327 >::from(public_key_share.as_slice());
2328 let lwe_ct = bool_evaluator.pk_encrypt(collective_pk.key(), m);
2329
2330 let decryption_shares = parties
2331 .iter()
2332 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct, k))
2333 .collect_vec();
2334
2335 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
2336
2337 {
2338 let ideal_m = if m {
2339 bool_evaluator.pbs_info.parameters.rlwe_q().true_el()
2340 } else {
2341 bool_evaluator.pbs_info.parameters.rlwe_q().false_el()
2342 };
2343 let noise = measure_noise_lwe(
2344 &lwe_ct,
2345 &ideal_rlwe_sk,
2346 &bool_evaluator.pbs_info.rlwe_modop,
2347 &ideal_m,
2348 );
2349 println!("Noise: {noise}");
2350 }
2351
2352 assert_eq!(m_back, m);
2353 m = !m;
2354 }
2355 }
2356
2357 fn _collecitve_public_key_gen(rlwe_q: u64, parties_rlwe_sk: &[RlweSecret]) -> Vec<Vec<u64>> {
2358 let ring_size = parties_rlwe_sk[0].values.len();
2359 assert!(ring_size.is_power_of_two());
2360 let mut rng = DefaultSecureRng::new();
2361 let nttop = NttBackendU64::new(&rlwe_q, ring_size);
2362 let modop = ModularOpsU64::new(rlwe_q);
2363
2364 // Generate Pk shares
2365 let pk_seed = [0u8; 32];
2366 let pk_shares = parties_rlwe_sk.iter().map(|sk| {
2367 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2368 let mut share_out = vec![0u64; ring_size];
2369 public_key_share(
2370 &mut share_out,
2371 sk.values(),
2372 &modop,
2373 &nttop,
2374 &mut p_rng,
2375 &mut rng,
2376 );
2377 share_out
2378 });
2379
2380 let mut pk_part_b = vec![0u64; ring_size];
2381 pk_shares.for_each(|share| modop.elwise_add_mut(&mut pk_part_b, &share));
2382 let mut pk_part_a = vec![0u64; ring_size];
2383 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2384 RandomFillUniformInModulus::random_fill(&mut p_rng, &rlwe_q, pk_part_a.as_mut_slice());
2385
2386 vec![pk_part_a, pk_part_b]
2387 }
2388
2389 fn _multi_party_all_keygen(
2390 bool_evaluator: &BoolEvaluator<
2391 Vec<Vec<u64>>,
2392 NttBackendU64,
2393 ModularOpsU64<CiphertextModulus<u64>>,
2394 ModularOpsU64<CiphertextModulus<u64>>,
2395 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2396 >,
2397 no_of_parties: usize,
2398 ) -> (
2399 Vec<ClientKey>,
2400 PublicKey<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64<CiphertextModulus<u64>>>,
2401 Vec<
2402 CommonReferenceSeededMultiPartyServerKeyShare<
2403 Vec<Vec<u64>>,
2404 BoolParameters<u64>,
2405 [u8; 32],
2406 >,
2407 >,
2408 SeededMultiPartyServerKey<Vec<Vec<u64>>, [u8; 32], BoolParameters<u64>>,
2409 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2410 ClientKey,
2411 ) {
2412 let parties = (0..no_of_parties)
2413 .map(|_| bool_evaluator.client_key())
2414 .collect_vec();
2415
2416 let mut rng = DefaultSecureRng::new();
2417
2418 // Collective public key
2419 let mut pk_cr_seed = [0u8; 32];
2420 rng.fill_bytes(&mut pk_cr_seed);
2421 let public_key_share = parties
2422 .iter()
2423 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2424 .collect_vec();
2425 let collective_pk =
2426 PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, _>::from(public_key_share.as_slice());
2427
2428 // Server key
2429 let mut pbs_cr_seed = [0u8; 32];
2430 rng.fill_bytes(&mut pbs_cr_seed);
2431 let server_key_shares = parties
2432 .iter()
2433 .map(|k| {
2434 bool_evaluator.multi_party_server_key_share(pbs_cr_seed, &collective_pk.key(), k)
2435 })
2436 .collect_vec();
2437 let seeded_server_key =
2438 bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
2439 let runtime_server_key =
2440 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2441 _,
2442 _,
2443 DefaultSecureRng,
2444 NttBackendU64,
2445 >::from(&seeded_server_key));
2446
2447 // construct ideal rlwe sk for meauring noise
2448 let ideal_client_key = {
2449 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2450 parties.iter().for_each(|k| {
2451 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2452 *ideal_i = *ideal_i + s_i;
2453 });
2454 });
2455 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.pbs_info.lwe_n()];
2456 parties.iter().for_each(|k| {
2457 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe().values()).for_each(|(ideal_i, s_i)| {
2458 *ideal_i = *ideal_i + s_i;
2459 });
2460 });
2461
2462 ClientKey::new(
2463 RlweSecret {
2464 values: ideal_rlwe_sk,
2465 },
2466 LweSecret {
2467 values: ideal_lwe_sk,
2468 },
2469 )
2470 };
2471
2472 (
2473 parties,
2474 collective_pk,
2475 server_key_shares,
2476 seeded_server_key,
2477 runtime_server_key,
2478 ideal_client_key,
2479 )
2480 }
2481
2482 #[test]
2483 fn interactive_multi_party_nand() {
2484 let mut bool_evaluator = BoolEvaluator::<
2485 Vec<Vec<u64>>,
2486 NttBackendU64,
2487 ModularOpsU64<CiphertextModulus<u64>>,
2488 ModularOpsU64<CiphertextModulus<u64>>,
2489 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2490 >::new(MP_BOOL_PARAMS);
2491
2492 let (parties, collective_pk, _, _, server_key_eval, ideal_client_key) =
2493 _multi_party_all_keygen(&bool_evaluator, 2);
2494
2495 let mut m0 = true;
2496 let mut m1 = false;
2497
2498 let mut lwe0 = bool_evaluator.pk_encrypt(collective_pk.key(), m0);
2499 let mut lwe1 = bool_evaluator.pk_encrypt(collective_pk.key(), m1);
2500
2501 for _ in 0..2000 {
2502 let lwe_out = bool_evaluator.nand(&lwe0, &lwe1, &server_key_eval);
2503
2504 let m_expected = !(m0 & m1);
2505
2506 // multi-party decrypt
2507 let decryption_shares = parties
2508 .iter()
2509 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_out, k))
2510 .collect_vec();
2511 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
2512
2513 assert!(m_expected == m_back, "Expected {m_expected}, got {m_back}");
2514 m1 = m0;
2515 m0 = m_expected;
2516
2517 lwe1 = lwe0;
2518 lwe0 = lwe_out;
2519 }
2520 }
2521
2522 #[test]
2523 fn noise_tester() {
2524 let bool_evaluator = BoolEvaluator::<
2525 Vec<Vec<u64>>,
2526 NttBackendU64,
2527 ModularOpsU64<CiphertextModulus<u64>>,
2528 ModularOpsU64<CiphertextModulus<u64>>,
2529 ShoupServerKeyEvaluationDomain<Vec<Vec<u64>>>,
2530 >::new(SMALL_MP_BOOL_PARAMS);
2531
2532 // let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2533 // _multi_party_all_keygen(&bool_evaluator, 20);
2534 let no_of_parties = 16;
2535 let lwe_q = bool_evaluator.pbs_info.parameters.lwe_q();
2536 let rlwe_q = bool_evaluator.pbs_info.parameters.rlwe_q();
2537 let lwe_n = bool_evaluator.pbs_info.parameters.lwe_n().0;
2538 let rlwe_n = bool_evaluator.pbs_info.parameters.rlwe_n().0;
2539 let lwe_modop = &bool_evaluator.pbs_info.lwe_modop;
2540 let rlwe_nttop = &bool_evaluator.pbs_info.rlwe_nttop;
2541 let rlwe_modop = &bool_evaluator.pbs_info.rlwe_modop;
2542
2543 // let rgsw_rgsw_decomposer = &bool_evaluator
2544 // .pbs_info
2545 // .parameters
2546 // .rgsw_rgsw_decomposer::<DefaultDecomposer<u64>>();
2547 // let rgsw_rgsw_gadget_a = rgsw_rgsw_decomposer.0.gadget_vector();
2548 // let rgsw_rgsw_gadget_b = rgsw_rgsw_decomposer.1.gadget_vector();
2549
2550 let rlwe_rgsw_decomposer = &bool_evaluator.pbs_info.rlwe_rgsw_decomposer;
2551 let rlwe_rgsw_gadget_a = rlwe_rgsw_decomposer.0.gadget_vector();
2552 let rlwe_rgsw_gadget_b = rlwe_rgsw_decomposer.1.gadget_vector();
2553
2554 let auto_decomposer = &bool_evaluator.pbs_info.auto_decomposer;
2555 let auto_gadget = auto_decomposer.gadget_vector();
2556
2557 let parties = (0..no_of_parties)
2558 .map(|_| bool_evaluator.client_key())
2559 .collect_vec();
2560
2561 let ideal_client_key = {
2562 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
2563 parties.iter().for_each(|k| {
2564 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
2565 *ideal_i = *ideal_i + s_i;
2566 });
2567 });
2568 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.pbs_info.lwe_n()];
2569 parties.iter().for_each(|k| {
2570 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe().values()).for_each(|(ideal_i, s_i)| {
2571 *ideal_i = *ideal_i + s_i;
2572 });
2573 });
2574
2575 ClientKey::new(
2576 RlweSecret {
2577 values: ideal_rlwe_sk,
2578 },
2579 LweSecret {
2580 values: ideal_lwe_sk,
2581 },
2582 )
2583 };
2584
2585 // check noise in freshly encrypted RLWE ciphertext (ie var_fresh)
2586 if true {
2587 let mut rng = DefaultSecureRng::new();
2588 let mut check = Stats { samples: vec![] };
2589 for _ in 0..10 {
2590 // generate a new collective public key
2591 let mut pk_cr_seed = [0u8; 32];
2592 rng.fill_bytes(&mut pk_cr_seed);
2593 let public_key_share = parties
2594 .iter()
2595 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2596 .collect_vec();
2597 let collective_pk = PublicKey::<
2598 Vec<Vec<u64>>,
2599 DefaultSecureRng,
2600 ModularOpsU64<CiphertextModulus<u64>>,
2601 >::from(public_key_share.as_slice());
2602
2603 let mut m = vec![0u64; rlwe_n];
2604 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2605 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2606 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2607 &mut rlwe_ct,
2608 collective_pk.key(),
2609 &m,
2610 rlwe_modop,
2611 rlwe_nttop,
2612 &mut rng,
2613 );
2614
2615 let mut m_back = vec![0u64; rlwe_n];
2616 decrypt_rlwe(
2617 &rlwe_ct,
2618 ideal_client_key.sk_rlwe().values(),
2619 &mut m_back,
2620 rlwe_nttop,
2621 rlwe_modop,
2622 );
2623
2624 rlwe_modop.elwise_sub_mut(m_back.as_mut_slice(), m.as_slice());
2625
2626 check.add_more(Vec::<i64>::try_convert_from(&m_back, rlwe_q).as_slice());
2627 }
2628
2629 println!("Public key Std: {}", check.std_dev().abs().log2());
2630 }
2631
2632 if true {
2633 // Generate server key shares
2634 let mut rng = DefaultSecureRng::new();
2635 let mut pk_cr_seed = [0u8; 32];
2636 rng.fill_bytes(&mut pk_cr_seed);
2637 let public_key_share = parties
2638 .iter()
2639 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2640 .collect_vec();
2641 let collective_pk = PublicKey::<
2642 Vec<Vec<u64>>,
2643 DefaultSecureRng,
2644 ModularOpsU64<CiphertextModulus<u64>>,
2645 >::from(public_key_share.as_slice());
2646
2647 let pbs_cr_seed = [0u8; 32];
2648 rng.fill_bytes(&mut pk_cr_seed);
2649 let server_key_shares = parties
2650 .iter()
2651 .map(|k| {
2652 bool_evaluator.multi_party_server_key_share(pbs_cr_seed, collective_pk.key(), k)
2653 })
2654 .collect_vec();
2655
2656 let seeded_server_key =
2657 bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
2658
2659 // Check noise in RGSW ciphertexts of ideal LWE secret elements
2660 if false {
2661 let mut check = Stats { samples: vec![] };
2662 izip!(
2663 ideal_client_key.sk_lwe().values.iter(),
2664 seeded_server_key.rgsw_cts().iter()
2665 )
2666 .for_each(|(s_i, rgsw_ct_i)| {
2667 // X^{s[i]}
2668 let mut m_si = vec![0u64; rlwe_n];
2669 let s_i = *s_i * (bool_evaluator.pbs_info.embedding_factor as i32);
2670 if s_i < 0 {
2671 m_si[rlwe_n - (s_i.abs() as usize)] = rlwe_q.neg_one();
2672 } else {
2673 m_si[s_i as usize] = 1;
2674 }
2675
2676 // RLWE'(-sm)
2677 let mut neg_s_eval =
2678 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
2679 rlwe_modop.elwise_neg_mut(&mut neg_s_eval);
2680 rlwe_nttop.forward(&mut neg_s_eval);
2681 for j in 0..rlwe_rgsw_decomposer.a().decomposition_count() {
2682 // RLWE(B^{j} * -s[X]*X^{s_lwe[i]})
2683
2684 // -s[X]*X^{s_lwe[i]}*B_j
2685 let mut m_ideal = m_si.clone();
2686 rlwe_nttop.forward(m_ideal.as_mut_slice());
2687 rlwe_modop.elwise_mul_mut(m_ideal.as_mut_slice(), neg_s_eval.as_slice());
2688 rlwe_nttop.backward(m_ideal.as_mut_slice());
2689 rlwe_modop
2690 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_rgsw_gadget_a[j]);
2691
2692 // RLWE(-s*X^{s_lwe[i]}*B_j)
2693 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2694 rlwe_ct[0].copy_from_slice(&rgsw_ct_i[j]);
2695 rlwe_ct[1].copy_from_slice(
2696 &rgsw_ct_i[j + rlwe_rgsw_decomposer.a().decomposition_count()],
2697 );
2698
2699 let mut m_back = vec![0u64; rlwe_n];
2700 decrypt_rlwe(
2701 &rlwe_ct,
2702 ideal_client_key.sk_rlwe().values(),
2703 &mut m_back,
2704 rlwe_nttop,
2705 rlwe_modop,
2706 );
2707
2708 // diff
2709 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2710 check.add_more(&Vec::<i64>::try_convert_from(&m_back, rlwe_q));
2711 }
2712
2713 // RLWE'(m)
2714 for j in 0..rlwe_rgsw_decomposer.b().decomposition_count() {
2715 // RLWE(B^{j} * X^{s_lwe[i]})
2716
2717 // X^{s_lwe[i]}*B_j
2718 let mut m_ideal = m_si.clone();
2719 rlwe_modop
2720 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_rgsw_gadget_b[j]);
2721
2722 // RLWE(X^{s_lwe[i]}*B_j)
2723 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2724 rlwe_ct[0].copy_from_slice(
2725 &rgsw_ct_i[j + (2 * rlwe_rgsw_decomposer.a().decomposition_count())],
2726 );
2727 rlwe_ct[1].copy_from_slice(
2728 &rgsw_ct_i[j
2729 + (2 * rlwe_rgsw_decomposer.a().decomposition_count()
2730 + rlwe_rgsw_decomposer.b().decomposition_count())],
2731 );
2732
2733 let mut m_back = vec![0u64; rlwe_n];
2734 decrypt_rlwe(
2735 &rlwe_ct,
2736 ideal_client_key.sk_rlwe().values(),
2737 &mut m_back,
2738 rlwe_nttop,
2739 rlwe_modop,
2740 );
2741
2742 // diff
2743 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2744 check.add_more(&Vec::<i64>::try_convert_from(&m_back, rlwe_q));
2745 }
2746 });
2747 println!(
2748 "RGSW Std: {} {} ;; max={}",
2749 check.mean(),
2750 check.std_dev().abs().log2(),
2751 check.samples.iter().max().unwrap()
2752 );
2753 }
2754
2755 // server key in Evaluation domain
2756 let runtime_server_key =
2757 ShoupServerKeyEvaluationDomain::from(ServerKeyEvaluationDomain::<
2758 _,
2759 _,
2760 DefaultSecureRng,
2761 NttBackendU64,
2762 >::from(&seeded_server_key));
2763
2764 // check noise in RLWE x RGSW(X^{s_i}) where RGSW is accunulated RGSW ciphertext
2765 if false {
2766 let mut check = Stats { samples: vec![] };
2767
2768 ideal_client_key
2769 .sk_lwe()
2770 .values()
2771 .iter()
2772 .enumerate()
2773 .for_each(|(index, s_i)| {
2774 let rgsw_ct_i = runtime_server_key.rgsw_ct_lwe_si(index).as_ref();
2775
2776 let mut m = vec![0u64; rlwe_n];
2777 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2778 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2779 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2780 &mut rlwe_ct,
2781 collective_pk.key(),
2782 &m,
2783 rlwe_modop,
2784 rlwe_nttop,
2785 &mut rng,
2786 );
2787
2788 let mut rlwe_after = RlweCiphertext::<_, DefaultSecureRng> {
2789 data: rlwe_ct.clone(),
2790 is_trivial: false,
2791 _phatom: PhantomData,
2792 };
2793 let mut scratch = vec![
2794 vec![0u64; rlwe_n];
2795 std::cmp::max(
2796 rlwe_rgsw_decomposer.0.decomposition_count(),
2797 rlwe_rgsw_decomposer.1.decomposition_count()
2798 ) + 2
2799 ];
2800 rlwe_by_rgsw(
2801 &mut rlwe_after,
2802 rgsw_ct_i,
2803 &mut scratch,
2804 rlwe_rgsw_decomposer,
2805 rlwe_nttop,
2806 rlwe_modop,
2807 );
2808
2809 // m1 = X^{s[i]}
2810 let mut m1 = vec![0u64; rlwe_n];
2811 let s_i = *s_i * (bool_evaluator.pbs_info.embedding_factor as i32);
2812 if s_i < 0 {
2813 m1[rlwe_n - (s_i.abs() as usize)] = rlwe_q.neg_one()
2814 } else {
2815 m1[s_i as usize] = 1;
2816 }
2817
2818 // (m+e) * m1
2819 let mut m_plus_e_times_m1 = vec![0u64; rlwe_n];
2820 decrypt_rlwe(
2821 &rlwe_ct,
2822 ideal_client_key.sk_rlwe().values(),
2823 &mut m_plus_e_times_m1,
2824 rlwe_nttop,
2825 rlwe_modop,
2826 );
2827 rlwe_nttop.forward(m_plus_e_times_m1.as_mut_slice());
2828 rlwe_nttop.forward(m1.as_mut_slice());
2829
2830 rlwe_modop.elwise_mul_mut(m_plus_e_times_m1.as_mut_slice(), m1.as_slice());
2831 rlwe_nttop.backward(m_plus_e_times_m1.as_mut_slice());
2832
2833 // Resulting RLWE ciphertext will equal: (m0m1 + em1) + e_{rlsw x rgsw}.
2834 // Hence, resulting rlwe ciphertext will have error em1 + e_{rlwe x rgsw}.
2835 // Here we're only concerned with e_{rlwe x rgsw}, that is noise added by
2836 // RLWExRGSW. Also note in practice m1 is a monomial, for ex, X^{s_{i}}, for
2837 // some i and var(em1) = var(e).
2838 let mut m_plus_e_times_m1_more_e = vec![0u64; rlwe_n];
2839 decrypt_rlwe(
2840 &rlwe_after,
2841 ideal_client_key.sk_rlwe().values(),
2842 &mut m_plus_e_times_m1_more_e,
2843 rlwe_nttop,
2844 rlwe_modop,
2845 );
2846
2847 // diff
2848 rlwe_modop.elwise_sub_mut(
2849 m_plus_e_times_m1_more_e.as_mut_slice(),
2850 m_plus_e_times_m1.as_slice(),
2851 );
2852
2853 // let noise = measure_noise(
2854 // &rlwe_after,
2855 // &m_plus_e_times_m1,
2856 // rlwe_nttop,
2857 // rlwe_modop,
2858 // ideal_client_key.sk_rlwe.values(),
2859 // );
2860 // print!("NOISE: {}", noise);
2861
2862 check.add_more(&Vec::<i64>::try_convert_from(
2863 &m_plus_e_times_m1_more_e,
2864 rlwe_q,
2865 ));
2866 });
2867 println!(
2868 "RLWE x RGSW, where RGSW has noise var_brk, std: {} {}",
2869 check.std_dev(),
2870 check.std_dev().abs().log2()
2871 )
2872 }
2873
2874 // check noise in Auto key
2875 if false {
2876 let mut check = Stats { samples: vec![] };
2877
2878 let mut neg_s_poly =
2879 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
2880 rlwe_modop.elwise_neg_mut(neg_s_poly.as_mut_slice());
2881
2882 let g = bool_evaluator.pbs_info.g();
2883 let br_q = bool_evaluator.pbs_info.br_q();
2884 let auto_element_dlogs = bool_evaluator.pbs_info.parameters.auto_element_dlogs();
2885 for i in auto_element_dlogs.into_iter() {
2886 let g_pow = if i == 0 {
2887 -g
2888 } else {
2889 (((g as usize).pow(i as u32)) % br_q) as isize
2890 };
2891
2892 // -s[X^k]
2893 let (auto_indices, auto_sign) = generate_auto_map(rlwe_n, g_pow);
2894 let mut neg_s_poly_auto_i = vec![0u64; rlwe_n];
2895 izip!(neg_s_poly.iter(), auto_indices.iter(), auto_sign.iter()).for_each(
2896 |(v, to_i, to_sign)| {
2897 if !to_sign {
2898 neg_s_poly_auto_i[*to_i] = rlwe_modop.neg(v);
2899 } else {
2900 neg_s_poly_auto_i[*to_i] = *v;
2901 }
2902 },
2903 );
2904
2905 let mut auto_key_i = runtime_server_key.galois_key_for_auto(i).as_ref().clone(); //send i^th auto key to coefficient domain
2906 auto_key_i
2907 .iter_mut()
2908 .for_each(|r| rlwe_nttop.backward(r.as_mut_slice()));
2909 auto_gadget.iter().enumerate().for_each(|(i, b_i)| {
2910 // B^i * -s[X^k]
2911 let mut m_ideal = neg_s_poly_auto_i.clone();
2912
2913 rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut_slice(), b_i);
2914
2915 let mut m_out = vec![0u64; rlwe_n];
2916 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2917 rlwe_ct[0].copy_from_slice(&auto_key_i[i]);
2918 rlwe_ct[1].copy_from_slice(
2919 &auto_key_i[auto_decomposer.decomposition_count() + i],
2920 );
2921 decrypt_rlwe(
2922 &rlwe_ct,
2923 ideal_client_key.sk_rlwe().values(),
2924 &mut m_out,
2925 rlwe_nttop,
2926 rlwe_modop,
2927 );
2928
2929 // diff
2930 rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(), m_ideal.as_slice());
2931
2932 check.add_more(&Vec::<i64>::try_convert_from(&m_out, rlwe_q));
2933 });
2934 }
2935
2936 println!("Auto key noise std dev: {}", check.std_dev().abs().log2());
2937 }
2938
2939 // check noise in RLWE(X^k) after sending RLWE(X) -> RLWE(X^k)using collective
2940 // auto key
2941 if true {
2942 let mut check = Stats { samples: vec![] };
2943 let br_q = bool_evaluator.pbs_info.br_q();
2944 let g = bool_evaluator.pbs_info.g();
2945 let auto_element_dlogs = bool_evaluator.pbs_info.parameters.auto_element_dlogs();
2946 for i in auto_element_dlogs.into_iter() {
2947 for _ in 0..10 {
2948 let mut m = vec![0u64; rlwe_n];
2949 RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q, m.as_mut_slice());
2950 let mut rlwe_ct = RlweCiphertext::<_, DefaultSecureRng> {
2951 data: vec![vec![0u64; rlwe_n]; 2],
2952 is_trivial: false,
2953 _phatom: PhantomData,
2954 };
2955 public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2956 &mut rlwe_ct,
2957 collective_pk.key(),
2958 &m,
2959 rlwe_modop,
2960 rlwe_nttop,
2961 &mut rng,
2962 );
2963
2964 // We're only interested in noise increased as a result of automorphism.
2965 // Hence, we take m+e as the bench.
2966 let mut m_plus_e = vec![0u64; rlwe_n];
2967 decrypt_rlwe(
2968 &rlwe_ct,
2969 ideal_client_key.sk_rlwe().values(),
2970 &mut m_plus_e,
2971 rlwe_nttop,
2972 rlwe_modop,
2973 );
2974
2975 let auto_key = runtime_server_key.galois_key_for_auto(i).as_ref();
2976 let (auto_map_index, auto_map_sign) =
2977 bool_evaluator.pbs_info.rlwe_auto_map(i);
2978 let mut scratch =
2979 vec![vec![0u64; rlwe_n]; auto_decomposer.decomposition_count() + 2];
2980 galois_auto(
2981 &mut rlwe_ct,
2982 auto_key,
2983 &mut scratch,
2984 &auto_map_index,
2985 &auto_map_sign,
2986 rlwe_modop,
2987 rlwe_nttop,
2988 auto_decomposer,
2989 );
2990
2991 // send m+e from X to X^k
2992 let mut m_plus_e_auto = vec![0u64; rlwe_n];
2993 izip!(m_plus_e.iter(), auto_map_index.iter(), auto_map_sign.iter())
2994 .for_each(|(v, to_index, to_sign)| {
2995 if !to_sign {
2996 m_plus_e_auto[*to_index] = rlwe_modop.neg(v);
2997 } else {
2998 m_plus_e_auto[*to_index] = *v
2999 }
3000 });
3001
3002 let mut m_out = vec![0u64; rlwe_n];
3003 decrypt_rlwe(
3004 &rlwe_ct,
3005 ideal_client_key.sk_rlwe().values(),
3006 &mut m_out,
3007 rlwe_nttop,
3008 rlwe_modop,
3009 );
3010
3011 // diff
3012 rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(), m_plus_e_auto.as_slice());
3013
3014 check.add_more(&Vec::<i64>::try_convert_from(m_out.as_slice(), rlwe_q));
3015 }
3016 }
3017
3018 println!("Rlwe Auto Noise Std: {}", check.std_dev().abs().log2());
3019 }
3020
3021 // Check noise growth in ksk
3022 // TODO check in LWE key switching keys
3023 if true {
3024 // 1. encrypt LWE ciphertext
3025 // 2. Key switching
3026 // 3.
3027 let mut check = Stats { samples: vec![] };
3028
3029 for _ in 0..1024 {
3030 // Encrypt m \in Q_{ks} using RLWE sk
3031 let mut lwe_in_ct = vec![0u64; rlwe_n + 1];
3032 let m = RandomElementInModulus::random(&mut rng, &lwe_q.q().unwrap());
3033 encrypt_lwe(
3034 &mut lwe_in_ct,
3035 &m,
3036 ideal_client_key.sk_rlwe().values(),
3037 lwe_modop,
3038 &mut rng,
3039 );
3040
3041 // Key switch
3042 let mut lwe_out = vec![0u64; lwe_n + 1];
3043 lwe_key_switch(
3044 &mut lwe_out,
3045 &lwe_in_ct,
3046 runtime_server_key.lwe_ksk(),
3047 lwe_modop,
3048 bool_evaluator.pbs_info.lwe_decomposer(),
3049 );
3050
3051 // We only care about noise added by LWE key switch
3052 // m+e
3053 let m_plus_e =
3054 decrypt_lwe(&lwe_in_ct, ideal_client_key.sk_rlwe().values(), lwe_modop);
3055
3056 let m_plus_e_plus_lwe_ksk_noise =
3057 decrypt_lwe(&lwe_out, ideal_client_key.sk_lwe().values(), lwe_modop);
3058
3059 let diff = lwe_modop.sub(&m_plus_e_plus_lwe_ksk_noise, &m_plus_e);
3060
3061 check.add_more(&vec![lwe_q.map_element_to_i64(&diff)]);
3062 }
3063
3064 println!("Lwe ksk std dev: {}", check.std_dev().abs().log2());
3065 }
3066 }
3067
3068 // Check noise in fresh RGSW ciphertexts, ie X^{s_j[i]}, must equalnoise in
3069 // // fresh RLWE ciphertext
3070 if true {}
3071 // test LWE ksk from RLWE -> LWE
3072 // if false {
3073 // let logp = 2;
3074 // let mut rng = DefaultSecureRng::new();
3075
3076 // let m = 1;
3077 // let encoded_m = m << (lwe_logq - logp);
3078
3079 // // Encrypt
3080 // let mut lwe_ct = vec![0u64; rlwe_n + 1];
3081 // encrypt_lwe(
3082 // &mut lwe_ct,
3083 // &encoded_m,
3084 // ideal_client_key.sk_rlwe.values(),
3085 // lwe_modop,
3086 // &mut rng,
3087 // );
3088
3089 // // key switch
3090 // let lwe_decomposer = &bool_evaluator.decomposer_lwe;
3091 // let mut lwe_out = vec![0u64; lwe_n + 1];
3092 // lwe_key_switch(
3093 // &mut lwe_out,
3094 // &lwe_ct,
3095 // &server_key_eval.lwe_ksk,
3096 // lwe_modop,
3097 // lwe_decomposer,
3098 // );
3099
3100 // let encoded_m_back = decrypt_lwe(&lwe_out,
3101 // ideal_client_key.sk_lwe.values(), lwe_modop); let m_back
3102 // = ((encoded_m_back as f64 * (1 << logp) as f64) /
3103 // (lwe_q as f64)).round() as u64; dbg!(m_back, m);
3104
3105 // let noise = measure_noise_lwe(
3106 // &lwe_out,
3107 // ideal_client_key.sk_lwe.values(),
3108 // lwe_modop,
3109 // &encoded_m,
3110 // );
3111
3112 // println!("Noise: {noise}");
3113 // }
3114
3115 // Measure noise in RGSW ciphertexts of ideal LWE secrets
3116 // if true {
3117 // let gadget_vec = gadget_vector(
3118 // bool_evaluator.parameters.rlwe_logq,
3119 // bool_evaluator.parameters.logb_rgsw,
3120 // bool_evaluator.parameters.d_rgsw,
3121 // );
3122
3123 // for i in 0..20 {
3124 // // measure noise in RGSW(s[i])
3125 // let si =
3126 // ideal_client_key.sk_lwe.values[i] *
3127 // (bool_evaluator.embedding_factor as i32); let mut
3128 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
3129 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
3130 // } else {
3131 // si_poly[(si.abs() as usize)] = 1;
3132 // }
3133
3134 // let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
3135 // rgsw_si
3136 // .iter_mut()
3137 // .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
3138
3139 // println!("####### Noise in RGSW(X^s_{i}) #######");
3140 // _measure_noise_rgsw(
3141 // &rgsw_si,
3142 // &si_poly,
3143 // ideal_client_key.sk_rlwe.values(),
3144 // &gadget_vec,
3145 // rlwe_q,
3146 // );
3147 // println!("####### ##################### #######");
3148 // }
3149 // }
3150
3151 // // measure noise grwoth in RLWExRGSW
3152 // if true {
3153 // let mut rng = DefaultSecureRng::new();
3154 // let mut carry_m = vec![0u64; rlwe_n];
3155 // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
3156 // carry_m.as_mut_slice());
3157
3158 // // RGSW(carrym)
3159 // let trivial_rlwect = vec![vec![0u64; rlwe_n],carry_m.clone()];
3160 // let mut rlwe_ct = RlweCiphertext::<_,
3161 // DefaultSecureRng>::from_raw(trivial_rlwect, true);
3162
3163 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
3164 // d_rgsw + 2]; let mul_mod =
3165 // |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
3166
3167 // for i in 0..bool_evaluator.parameters.lwe_n {
3168 // rlwe_by_rgsw(
3169 // &mut rlwe_ct,
3170 // server_key_eval.rgsw_ct_lwe_si(i),
3171 // &mut scratch_matrix_dplus2_ring,
3172 // rlwe_decomposer,
3173 // rlwe_nttop,
3174 // rlwe_modop,
3175 // );
3176
3177 // // carry_m[X] * s_i[X]
3178 // let si =
3179 // ideal_client_key.sk_lwe.values[i] *
3180 // (bool_evaluator.embedding_factor as i32); let mut
3181 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
3182 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
3183 // } else {
3184 // si_poly[(si.abs() as usize)] = 1;
3185 // }
3186 // carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod,
3187 // rlwe_q);
3188
3189 // let noise = measure_noise(
3190 // &rlwe_ct,
3191 // &carry_m,
3192 // rlwe_nttop,
3193 // rlwe_modop,
3194 // ideal_client_key.sk_rlwe.values(),
3195 // );
3196 // println!("Noise RLWE(carry_m) accumulating {i}^th secret
3197 // monomial: {noise}"); }
3198 // }
3199
3200 // // Check galois keys
3201 // if false {
3202 // let g = bool_evaluator.g() as isize;
3203 // let mut rng = DefaultSecureRng::new();
3204 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
3205 // d_rgsw + 2]; for i in [g, -g] {
3206 // let mut m = vec![0u64; rlwe_n];
3207 // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
3208 // m.as_mut_slice()); let mut rlwe_ct = {
3209 // let mut data = vec![vec![0u64; rlwe_n]; 2];
3210 // public_key_encrypt_rlwe(
3211 // &mut data,
3212 // &collective_pk.key,
3213 // &m,
3214 // rlwe_modop,
3215 // rlwe_nttop,
3216 // &mut rng,
3217 // );
3218 // RlweCiphertext::<_, DefaultSecureRng>::from_raw(data,
3219 // false) };
3220
3221 // let auto_key = server_key_eval.galois_key_for_auto(i);
3222 // let (auto_map_index, auto_map_sign) =
3223 // generate_auto_map(rlwe_n, i); galois_auto(
3224 // &mut rlwe_ct,
3225 // auto_key,
3226 // &mut scratch_matrix_dplus2_ring,
3227 // &auto_map_index,
3228 // &auto_map_sign,
3229 // rlwe_modop,
3230 // rlwe_nttop,
3231 // rlwe_decomposer,
3232 // );
3233
3234 // // send m(X) -> m(X^i)
3235 // let mut m_k = vec![0u64; rlwe_n];
3236 // izip!(m.iter(), auto_map_index.iter(),
3237 // auto_map_sign.iter()).for_each( |(mi, to_index,to_sign)|
3238 // // { if !to_sign {
3239 // m_k[*to_index] = rlwe_q - *mi; } else {
3240 // m_k[*to_index] = *mi;
3241 // }
3242 // },
3243 // );
3244
3245 // // measure noise
3246 // let noise = measure_noise(
3247 // &rlwe_ct,
3248 // &m_k,
3249 // rlwe_nttop,
3250 // rlwe_modop,
3251 // ideal_client_key.sk_rlwe.values(),
3252 // );
3253
3254 // println!("Noise after auto k={i}: {noise}");
3255 // }
3256 // }
3257 }
3258
3259 #[test]
3260 fn testtest() {
3261 let evaluator = BoolEvaluator::<
3262 Vec<Vec<u64>>,
3263 NttBackendU64,
3264 ModularOpsU64<CiphertextModulus<u64>>,
3265 ModulusPowerOf2<CiphertextModulus<u64>>,
3266 ShoupNonInteractiveServerKeyEvaluationDomain<Vec<Vec<u64>>>,
3267 >::new(NON_INTERACTIVE_SMALL_MP_BOOL_PARAMS);
3268 let mp_seed = NonInteractiveMultiPartyCrs { seed: [1u8; 32] };
3269
3270 let ring_size = evaluator.parameters().rlwe_n().0;
3271 let rlwe_q = evaluator.parameters().rlwe_q();
3272 let rlwe_modop = evaluator.pbs_info().modop_rlweq();
3273 let nttop = evaluator.pbs_info().nttop_rlweq();
3274
3275 let parties = 2;
3276
3277 let cks = (0..parties)
3278 .map(|_| evaluator.non_interactive_client_key())
3279 .collect_vec();
3280
3281 let key_shares = (0..parties)
3282 .map(|i| evaluator.non_interactive_multi_party_key_share(&mp_seed, i, parties, &cks[i]))
3283 .collect_vec();
3284 // dbg!(key_shares[1].user_index);
3285
3286 let seeded_server_key = evaluator.aggregate_non_interactive_multi_party_key_share(
3287 &mp_seed,
3288 parties,
3289 &key_shares,
3290 );
3291 let server_key_evaluation_domain =
3292 NonInteractiveServerKeyEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
3293 seeded_server_key,
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 {
3313 let (rlrg_decomp_a, rlrg_decomp_b) = evaluator
3314 .parameters()
3315 .rlwe_rgsw_decomposer::<DefaultDecomposer<u64>>();
3316 let gadget_vec_a = rlrg_decomp_a.gadget_vector();
3317 let gadget_vec_b = rlrg_decomp_b.gadget_vector();
3318 let d_a = rlrg_decomp_a.decomposition_count();
3319 let d_b = rlrg_decomp_b.decomposition_count();
3320
3321 // s[X]
3322 let s_poly = Vec::<u64>::try_convert_from(ideal_rlwe.as_slice(), rlwe_q);
3323
3324 // -s[X]
3325 let mut neg_s_poly_eval = s_poly.clone();
3326 rlwe_modop.elwise_neg_mut(&mut neg_s_poly_eval);
3327 nttop.forward(neg_s_poly_eval.as_mut());
3328
3329 server_key_evaluation_domain
3330 .rgsw_cts()
3331 .iter()
3332 .enumerate()
3333 .for_each(|(s_index, ct)| {
3334 // X^{lwe_s[i]}
3335 let mut m = vec![0u64; ring_size];
3336 let s_i = ideal_lwe[s_index] * (evaluator.pbs_info().embedding_factor() as i32);
3337 if s_i < 0 {
3338 m[ring_size - (s_i.abs() as usize)] = rlwe_q.neg_one();
3339 } else {
3340 m[(s_i as usize)] = 1;
3341 }
3342
3343 let mut neg_sm = m.clone();
3344 nttop.forward(&mut neg_sm);
3345 rlwe_modop.elwise_mul_mut(&mut neg_sm, &neg_s_poly_eval);
3346 nttop.backward(&mut neg_sm);
3347
3348 // RLWE'(-sm)
3349 gadget_vec_a.iter().enumerate().for_each(|(index, beta)| {
3350 // RLWE(\beta -sm)
3351
3352 // \beta * -sX^[lwe_s[i]]
3353 let mut beta_neg_sm = neg_sm.clone();
3354 rlwe_modop.elwise_scalar_mul_mut(&mut beta_neg_sm, beta);
3355
3356 // extract RLWE(-sm \beta)
3357 let mut rlwe = vec![vec![0u64; ring_size]; 2];
3358 rlwe[0].copy_from_slice(&ct[index]);
3359 rlwe[1].copy_from_slice(&ct[index + d_a]);
3360 // send back to coefficient domain
3361 rlwe.iter_rows_mut()
3362 .for_each(|r| nttop.backward(r.as_mut_slice()));
3363
3364 // decrypt
3365 let mut m_out = vec![0u64; ring_size];
3366 decrypt_rlwe(&rlwe, &ideal_rlwe, &mut m_out, nttop, rlwe_modop); // println!("{:?}", &beta_neg_sm);
3367
3368 let mut diff = m_out;
3369 rlwe_modop.elwise_sub_mut(&mut diff, &beta_neg_sm);
3370
3371 stats.add_more(&Vec::<i64>::try_convert_from(&diff, rlwe_q));
3372 });
3373 });
3374 }
3375 println!("Stats: {}", stats.std_dev().abs().log2());
3376 }
3377}