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