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