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