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