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};
12
13use itertools::{izip, partition, Itertools};
14use num_traits::{FromPrimitive, Num, One, Pow, PrimInt, ToPrimitive, WrappingSub, Zero};
15use rand_distr::uniform::SampleUniform;
16
17use crate::{
18 backend::{
19 ArithmeticOps, GetModulus, ModInit, ModularOpsU64, Modulus, ShoupMatrixFMA, VectorOps,
20 },
21 decomposer::{Decomposer, DefaultDecomposer, NumInfo, RlweDecomposer},
22 lwe::{decrypt_lwe, encrypt_lwe, lwe_key_switch, lwe_ksk_keygen, measure_noise_lwe, LweSecret},
23 multi_party::public_key_share,
24 ntt::{self, Ntt, NttBackendU64, NttInit},
25 pbs::{pbs, sample_extract, PbsInfo, PbsKey},
26 random::{
27 DefaultSecureRng, NewWithSeed, RandomFill, RandomFillGaussianInModulus,
28 RandomFillUniformInModulus, RandomGaussianElementInModulus,
29 },
30 rgsw::{
31 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, public_key_encrypt_rgsw,
32 rgsw_by_rgsw_inplace, rlwe_by_rgsw, secret_key_encrypt_rgsw, IsTrivial, RgswCiphertext,
33 RlweCiphertext, RlweSecret,
34 },
35 utils::{
36 fill_random_ternary_secret_with_hamming_weight, generate_prime, mod_exponent, Global,
37 TryConvertFrom1, WithLocal,
38 },
39 Decryptor, Encryptor, Matrix, MatrixEntity, MatrixMut, MultiPartyDecryptor, Row, RowEntity,
40 RowMut, Secret,
41};
42
43use super::{
44 keys::ClientKey,
45 parameters::{BoolParameters, CiphertextModulus},
46 CommonReferenceSeededCollectivePublicKeyShare, CommonReferenceSeededMultiPartyServerKeyShare,
47 SeededMultiPartyServerKey, SeededServerKey, ServerKeyEvaluationDomain,
48 ShoupServerKeyEvaluationDomain,
49};
50
51pub struct MultiPartyCrs<S> {
52 pub(super) seed: S,
53}
54
55impl<S: Default + Copy> MultiPartyCrs<S> {
56 /// Seed to generate public key share using MultiPartyCrs as the main seed.
57 ///
58 /// Public key seed equals the 1st seed extracted from PRNG Seeded with
59 /// MiltiPartyCrs's seed.
60 pub(super) fn public_key_share_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
61 let mut prng = Rng::new_with_seed(self.seed);
62
63 let mut seed = S::default();
64 RandomFill::<S>::random_fill(&mut prng, &mut seed);
65 seed
66 }
67
68 /// Seed to generate server key share using MultiPartyCrs as the main seed.
69 ///
70 /// Server key seed equals the 2nd seed extracted from PRNG Seeded with
71 /// MiltiPartyCrs's seed.
72 pub(super) fn server_key_share_seed<Rng: NewWithSeed<Seed = S> + RandomFill<S>>(&self) -> S {
73 let mut prng = Rng::new_with_seed(self.seed);
74
75 let mut seed = S::default();
76 RandomFill::<S>::random_fill(&mut prng, &mut seed);
77 RandomFill::<S>::random_fill(&mut prng, &mut seed);
78 seed
79 }
80}
81
82pub(crate) trait BooleanGates {
83 type Ciphertext: RowEntity;
84 type Key: Global;
85
86 fn and_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
87 fn nand_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
88 fn or_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
89 fn nor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
90 fn xor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
91 fn xnor_inplace(&mut self, c0: &mut Self::Ciphertext, c1: &Self::Ciphertext, key: &Self::Key);
92 fn not_inplace(&mut self, c: &mut Self::Ciphertext);
93
94 fn and(
95 &mut self,
96 c0: &Self::Ciphertext,
97 c1: &Self::Ciphertext,
98 key: &Self::Key,
99 ) -> Self::Ciphertext;
100 fn nand(
101 &mut self,
102 c0: &Self::Ciphertext,
103 c1: &Self::Ciphertext,
104 key: &Self::Key,
105 ) -> Self::Ciphertext;
106 fn or(
107 &mut self,
108 c0: &Self::Ciphertext,
109 c1: &Self::Ciphertext,
110 key: &Self::Key,
111 ) -> Self::Ciphertext;
112 fn nor(
113 &mut self,
114 c0: &Self::Ciphertext,
115 c1: &Self::Ciphertext,
116 key: &Self::Key,
117 ) -> Self::Ciphertext;
118 fn xor(
119 &mut self,
120 c0: &Self::Ciphertext,
121 c1: &Self::Ciphertext,
122 key: &Self::Key,
123 ) -> Self::Ciphertext;
124 fn xnor(
125 &mut self,
126 c0: &Self::Ciphertext,
127 c1: &Self::Ciphertext,
128 key: &Self::Key,
129 ) -> Self::Ciphertext;
130 fn not(&mut self, c: &Self::Ciphertext) -> Self::Ciphertext;
131}
132
133struct ScratchMemory<M>
134where
135 M: Matrix,
136{
137 lwe_vector: M::R,
138 decomposition_matrix: M,
139}
140
141impl<M: MatrixEntity> ScratchMemory<M>
142where
143 M::R: RowEntity,
144{
145 fn new(parameters: &BoolParameters<M::MatElement>) -> Self {
146 // Vector to store LWE ciphertext with LWE dimesnion n
147 let lwe_vector = M::R::zeros(parameters.lwe_n().0 + 1);
148
149 // Matrix to store decomposed polynomials
150 // Max decompistion count + space for temporary RLWE
151 let d = std::cmp::max(
152 parameters.auto_decomposition_count().0,
153 std::cmp::max(
154 parameters.rlwe_rgsw_decomposition_count().0 .0,
155 parameters.rlwe_rgsw_decomposition_count().1 .0,
156 ),
157 ) + 2;
158 let decomposition_matrix = M::zeros(d, parameters.rlwe_n().0);
159
160 Self {
161 lwe_vector,
162 decomposition_matrix,
163 }
164 }
165}
166
167pub(super) trait BoolEncoding {
168 type Element;
169 fn true_el(&self) -> Self::Element;
170 fn false_el(&self) -> Self::Element;
171 fn qby4(&self) -> Self::Element;
172 fn decode(&self, m: Self::Element) -> bool;
173}
174
175impl<T> BoolEncoding for CiphertextModulus<T>
176where
177 CiphertextModulus<T>: Modulus<Element = T>,
178 T: PrimInt,
179{
180 type Element = T;
181
182 fn qby4(&self) -> Self::Element {
183 if self.is_native() {
184 T::one() << (CiphertextModulus::<T>::_bits() - 2)
185 } else {
186 self.q().unwrap() >> 2
187 }
188 }
189 /// Q/8
190 fn true_el(&self) -> Self::Element {
191 if self.is_native() {
192 T::one() << (CiphertextModulus::<T>::_bits() - 3)
193 } else {
194 self.q().unwrap() >> 3
195 }
196 }
197 /// -Q/8
198 fn false_el(&self) -> Self::Element {
199 self.largest_unsigned_value() - self.true_el() + T::one()
200 }
201 fn decode(&self, m: Self::Element) -> bool {
202 let qby8 = self.true_el();
203 let m = (((m + qby8).to_f64().unwrap() * 4.0f64) / self.q_as_f64().unwrap()).round()
204 as usize
205 % 4usize;
206
207 if m == 0 {
208 return false;
209 } else if m == 1 {
210 return true;
211 } else {
212 panic!("Incorrect bool decryption. Got m={m} but expected m to be 0 or 1")
213 }
214 }
215}
216
217pub(super) struct BoolPbsInfo<M: Matrix, Ntt, RlweModOp, LweModOp> {
218 auto_decomposer: DefaultDecomposer<M::MatElement>,
219 rlwe_rgsw_decomposer: (
220 DefaultDecomposer<M::MatElement>,
221 DefaultDecomposer<M::MatElement>,
222 ),
223 lwe_decomposer: DefaultDecomposer<M::MatElement>,
224 g_k_dlog_map: Vec<usize>,
225 rlwe_nttop: Ntt,
226 rlwe_modop: RlweModOp,
227 lwe_modop: LweModOp,
228 embedding_factor: usize,
229 rlwe_qby4: M::MatElement,
230 rlwe_auto_maps: Vec<(Vec<usize>, Vec<bool>)>,
231 parameters: BoolParameters<M::MatElement>,
232}
233
234impl<M: Matrix, NttOp, RlweModOp, LweModOp> PbsInfo for BoolPbsInfo<M, NttOp, RlweModOp, LweModOp>
235where
236 M::MatElement: PrimInt + WrappingSub + NumInfo + FromPrimitive + From<bool> + Display,
237 RlweModOp: ArithmeticOps<Element = M::MatElement> + ShoupMatrixFMA<M::R>,
238 LweModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
239 NttOp: Ntt<Element = M::MatElement>,
240{
241 type M = M;
242 type Modulus = CiphertextModulus<M::MatElement>;
243 type D = DefaultDecomposer<M::MatElement>;
244 type RlweModOp = RlweModOp;
245 type LweModOp = LweModOp;
246 type NttOp = NttOp;
247 fn rlwe_auto_map(&self, k: usize) -> &(Vec<usize>, Vec<bool>) {
248 &self.rlwe_auto_maps[k]
249 }
250 fn br_q(&self) -> usize {
251 *self.parameters.br_q()
252 }
253 fn lwe_decomposer(&self) -> &Self::D {
254 &self.lwe_decomposer
255 }
256 fn rlwe_rgsw_decomposer(&self) -> &(Self::D, Self::D) {
257 &self.rlwe_rgsw_decomposer
258 }
259 fn auto_decomposer(&self) -> &Self::D {
260 &self.auto_decomposer
261 }
262 fn embedding_factor(&self) -> usize {
263 self.embedding_factor
264 }
265 fn g(&self) -> isize {
266 self.parameters.g() as isize
267 }
268 fn w(&self) -> usize {
269 self.parameters.w()
270 }
271 fn g_k_dlog_map(&self) -> &[usize] {
272 &self.g_k_dlog_map
273 }
274 fn lwe_n(&self) -> usize {
275 self.parameters.lwe_n().0
276 }
277 fn lwe_q(&self) -> &Self::Modulus {
278 self.parameters.lwe_q()
279 }
280 fn rlwe_n(&self) -> usize {
281 self.parameters.rlwe_n().0
282 }
283 fn rlwe_q(&self) -> &Self::Modulus {
284 self.parameters.rlwe_q()
285 }
286 fn modop_lweq(&self) -> &Self::LweModOp {
287 &self.lwe_modop
288 }
289 fn modop_rlweq(&self) -> &Self::RlweModOp {
290 &self.rlwe_modop
291 }
292 fn nttop_rlweq(&self) -> &Self::NttOp {
293 &self.rlwe_nttop
294 }
295}
296
297pub(crate) struct BoolEvaluator<Info, SKey>
298where
299 M: Matrix,
300{
301 pbs_info: BoolPbsInfo<M, Ntt, RlweModOp, LweModOp>,
302 scratch_memory: ScratchMemory<M>,
303 nand_test_vec: M::R,
304 and_test_vec: M::R,
305 or_test_vec: M::R,
306 nor_test_vec: M::R,
307 xor_test_vec: M::R,
308 xnor_test_vec: M::R,
309 _phantom: PhantomData<M>,
310}
311
312impl<M: Matrix, NttOp, RlweModOp, LweModOp> BoolEvaluator<M, NttOp, RlweModOp, LweModOp> {
313 pub(super) fn parameters(&self) -> &BoolParameters<M::MatElement> {
314 &self.pbs_info.parameters
315 }
316
317 pub(super) fn pbs_info(&self) -> &BoolPbsInfo<M, NttOp, RlweModOp, LweModOp> {
318 &self.pbs_info
319 }
320}
321
322impl<M: Matrix, NttOp, RlweModOp, LweModOp, SKey> BoolEvaluator<M, NttOp, RlweModOp, LweModOp, SKey>
323where
324 M: MatrixEntity + MatrixMut,
325 M::MatElement: PrimInt
326 + Debug
327 + Display
328 + NumInfo
329 + FromPrimitive
330 + WrappingSub
331 + SampleUniform
332 + From<bool>,
333 NttOp: Ntt<Element = M::MatElement>,
334 RlweModOp: ArithmeticOps<Element = M::MatElement>
335 + VectorOps<Element = M::MatElement>
336 + GetModulus<Element = M::MatElement, M = CiphertextModulus<M::MatElement>>
337 + ShoupMatrixFMA<M::R>,
338 LweModOp: ArithmeticOps<Element = M::MatElement>
339 + VectorOps<Element = M::MatElement>
340 + GetModulus<Element = M::MatElement, M = CiphertextModulus<M::MatElement>>,
341 M::R: TryConvertFrom1<[i32], CiphertextModulus<M::MatElement>> + RowEntity + Debug,
342 <M as Matrix>::R: RowMut,
343{
344 pub(super) fn new(parameters: BoolParameters<M::MatElement>) -> Self
345 where
346 RlweModOp: ModInit<M = CiphertextModulus<M::MatElement>>,
347 LweModOp: ModInit<M = CiphertextModulus<M::MatElement>>,
348 NttOp: NttInit<CiphertextModulus<M::MatElement>>,
349 {
350 //TODO(Jay): Run sanity checks for modulus values in parameters
351
352 // generates dlog map s.t. (+/-)g^{k} % q = a, for all a \in Z*_{q} and k \in
353 // [0, q/4). We store the dlog `k` at index `a`. This makes it easier to
354 // simply look up `k` at runtime as vec[a]. If a = g^{k} then dlog is
355 // stored as k. If a = -g^{k} then dlog is stored as k = q/4. This is done to
356 // differentiate sign.
357 let g = parameters.g();
358 let q = *parameters.br_q();
359 let mut g_k_dlog_map = vec![0usize; q];
360 for i in 0..q / 4 {
361 let v = mod_exponent(g as u64, i as u64, q as u64) as usize;
362 // g^i
363 g_k_dlog_map[v] = i;
364 // -(g^i)
365 g_k_dlog_map[q - v] = i + (q / 4);
366 }
367
368 let embedding_factor = (2 * parameters.rlwe_n().0) / q;
369
370 let rlwe_nttop = NttOp::new(parameters.rlwe_q(), parameters.rlwe_n().0);
371 let rlwe_modop = RlweModOp::new(*parameters.rlwe_q());
372 let lwe_modop = LweModOp::new(*parameters.lwe_q());
373
374 let q = *parameters.br_q();
375 let qby2 = q >> 1;
376 let qby8 = q >> 3;
377 // Q/8 (Q: rlwe_q)
378 let true_m_el = parameters.rlwe_q().true_el();
379 // -Q/8
380 let false_m_el = parameters.rlwe_q().false_el();
381 let (auto_map_index, auto_map_sign) = generate_auto_map(qby2, -(g as isize));
382
383 let init_test_vec = |partition_el: usize,
384 before_partition_el: M::MatElement,
385 after_partition_el: M::MatElement| {
386 let mut test_vec = M::R::zeros(qby2);
387 for i in 0..qby2 {
388 if i < partition_el {
389 test_vec.as_mut()[i] = before_partition_el;
390 } else {
391 test_vec.as_mut()[i] = after_partition_el;
392 }
393 }
394
395 // v(X) -> v(X^{-g})
396 let mut test_vec_autog = M::R::zeros(qby2);
397 izip!(
398 test_vec.as_ref().iter(),
399 auto_map_index.iter(),
400 auto_map_sign.iter()
401 )
402 .for_each(|(v, to_index, to_sign)| {
403 if !to_sign {
404 // negate
405 test_vec_autog.as_mut()[*to_index] = rlwe_modop.neg(v);
406 } else {
407 test_vec_autog.as_mut()[*to_index] = *v;
408 }
409 });
410
411 return test_vec_autog;
412 };
413
414 let nand_test_vec = init_test_vec(3 * qby8, true_m_el, false_m_el);
415 let and_test_vec = init_test_vec(3 * qby8, false_m_el, true_m_el);
416 let or_test_vec = init_test_vec(qby8, false_m_el, true_m_el);
417 let nor_test_vec = init_test_vec(qby8, true_m_el, false_m_el);
418 let xor_test_vec = init_test_vec(qby8, false_m_el, true_m_el);
419 let xnor_test_vec = init_test_vec(qby8, true_m_el, false_m_el);
420
421 // auto map indices and sign
422 // Auto maps are stored as [-g, g^{1}, g^{2}, ..., g^{w}]
423 let mut rlwe_auto_maps = vec![];
424 let ring_size = parameters.rlwe_n().0;
425 let g = parameters.g();
426 let br_q = parameters.br_q();
427 let auto_element_dlogs = parameters.auto_element_dlogs();
428 assert!(auto_element_dlogs[0] == 0);
429 for i in auto_element_dlogs.into_iter() {
430 let el = if i == 0 {
431 -(g as isize)
432 } else {
433 (g.pow(i as u32) % br_q) as isize
434 };
435 rlwe_auto_maps.push(generate_auto_map(ring_size, el))
436 }
437
438 let rlwe_qby4 = parameters.rlwe_q().qby4();
439
440 let scratch_memory = ScratchMemory::new(¶meters);
441
442 let pbs_info = BoolPbsInfo {
443 auto_decomposer: parameters.auto_decomposer(),
444 lwe_decomposer: parameters.lwe_decomposer(),
445 rlwe_rgsw_decomposer: parameters.rlwe_rgsw_decomposer(),
446 g_k_dlog_map,
447 embedding_factor,
448 lwe_modop,
449 rlwe_modop,
450 rlwe_nttop,
451 rlwe_qby4,
452 rlwe_auto_maps,
453 parameters: parameters,
454 };
455
456 BoolEvaluator {
457 pbs_info,
458 scratch_memory,
459 nand_test_vec,
460 and_test_vec,
461 or_test_vec,
462 nor_test_vec,
463 xnor_test_vec,
464 xor_test_vec,
465 _phantom: PhantomData,
466 }
467 }
468
469 pub(super) fn client_key(&self) -> ClientKey {
470 let sk_lwe = LweSecret::random(
471 self.pbs_info.parameters.lwe_n().0 >> 1,
472 self.pbs_info.parameters.lwe_n().0,
473 );
474 let sk_rlwe = RlweSecret::random(
475 self.pbs_info.parameters.rlwe_n().0 >> 1,
476 self.pbs_info.parameters.rlwe_n().0,
477 );
478 ClientKey::new(sk_rlwe, sk_lwe)
479 }
480
481 pub(super) fn server_key(
482 &self,
483 client_key: &ClientKey,
484 ) -> SeededServerKey<M, BoolParameters<M::MatElement>, [u8; 32]> {
485 DefaultSecureRng::with_local_mut(|rng| {
486 let mut main_seed = [0u8; 32];
487 rng.fill_bytes(&mut main_seed);
488
489 let mut main_prng = DefaultSecureRng::new_seeded(main_seed);
490
491 let rlwe_n = self.pbs_info.parameters.rlwe_n().0;
492 let sk_rlwe = client_key.sk_rlwe();
493 let sk_lwe = client_key.sk_lwe();
494
495 // generate auto keys
496 let mut auto_keys = HashMap::new();
497 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
498 let g = self.pbs_info.parameters.g();
499 let br_q = self.pbs_info.parameters.br_q();
500 let auto_els = self.pbs_info.parameters.auto_element_dlogs();
501 for i in auto_els.into_iter() {
502 let g_pow = if i == 0 {
503 -(g as isize)
504 } else {
505 (g.pow(i as u32) % br_q) as isize
506 };
507 let mut gk = M::zeros(self.pbs_info.auto_decomposer.decomposition_count(), rlwe_n);
508 galois_key_gen(
509 &mut gk,
510 sk_rlwe.values(),
511 g_pow,
512 &auto_gadget,
513 &self.pbs_info.rlwe_modop,
514 &self.pbs_info.rlwe_nttop,
515 &mut main_prng,
516 rng,
517 );
518 auto_keys.insert(i, gk);
519 }
520
521 // generate rgsw ciphertexts RGSW(si) where si is i^th LWE secret element
522 let ring_size = self.pbs_info.parameters.rlwe_n().0;
523 let rlwe_q = self.pbs_info.parameters.rlwe_q();
524 let (rlrg_d_a, rlrg_d_b) = (
525 self.pbs_info.rlwe_rgsw_decomposer.0.decomposition_count(),
526 self.pbs_info.rlwe_rgsw_decomposer.1.decomposition_count(),
527 );
528 let rlrg_gadget_a = self.pbs_info.rlwe_rgsw_decomposer.0.gadget_vector();
529 let rlrg_gadget_b = self.pbs_info.rlwe_rgsw_decomposer.1.gadget_vector();
530 let rgsw_cts = sk_lwe
531 .values()
532 .iter()
533 .map(|si| {
534 // X^{si}; assume |emebedding_factor * si| < N
535 let mut m = M::R::zeros(ring_size);
536 let si = (self.pbs_info.embedding_factor as i32) * si;
537 // dbg!(si);
538 if si < 0 {
539 // X^{-i} = X^{2N - i} = -X^{N-i}
540 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q.neg_one();
541 } else {
542 // X^{i}
543 m.as_mut()[si.abs() as usize] = M::MatElement::one();
544 }
545
546 let mut rgsw_si = M::zeros(rlrg_d_a * 2 + rlrg_d_b, ring_size);
547 secret_key_encrypt_rgsw(
548 &mut rgsw_si,
549 m.as_ref(),
550 &rlrg_gadget_a,
551 &rlrg_gadget_b,
552 sk_rlwe.values(),
553 &self.pbs_info.rlwe_modop,
554 &self.pbs_info.rlwe_nttop,
555 &mut main_prng,
556 rng,
557 );
558
559 rgsw_si
560 })
561 .collect_vec();
562
563 // LWE KSK from RLWE secret s -> LWE secret z
564 let d_lwe_gadget = self.pbs_info.lwe_decomposer.gadget_vector();
565 let mut lwe_ksk =
566 M::R::zeros(self.pbs_info.lwe_decomposer.decomposition_count() * ring_size);
567 lwe_ksk_keygen(
568 &sk_rlwe.values(),
569 &sk_lwe.values(),
570 &mut lwe_ksk,
571 &d_lwe_gadget,
572 &self.pbs_info.lwe_modop,
573 &mut main_prng,
574 rng,
575 );
576
577 SeededServerKey::from_raw(
578 auto_keys,
579 rgsw_cts,
580 lwe_ksk,
581 self.pbs_info.parameters.clone(),
582 main_seed,
583 )
584 })
585 }
586
587 pub(super) fn multi_party_server_key_share(
588 &self,
589 cr_seed: [u8; 32],
590 collective_pk: &M,
591 client_key: &ClientKey,
592 ) -> CommonReferenceSeededMultiPartyServerKeyShare<M, BoolParameters<M::MatElement>, [u8; 32]>
593 {
594 DefaultSecureRng::with_local_mut(|rng| {
595 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
596
597 let sk_rlwe = client_key.sk_rlwe();
598 let sk_lwe = client_key.sk_lwe();
599
600 let g = self.pbs_info.parameters.g();
601 let ring_size = self.pbs_info.parameters.rlwe_n().0;
602 let rlwe_q = self.pbs_info.parameters.rlwe_q();
603 let lwe_q = self.pbs_info.parameters.lwe_q();
604
605 let rlweq_modop = &self.pbs_info.rlwe_modop;
606 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
607
608 // sanity check
609 assert!(sk_rlwe.values().len() == ring_size);
610 assert!(sk_lwe.values().len() == self.pbs_info.parameters.lwe_n().0);
611
612 // auto keys
613 let mut auto_keys = HashMap::new();
614 let auto_gadget = self.pbs_info.auto_decomposer.gadget_vector();
615 let auto_element_dlogs = self.pbs_info.parameters.auto_element_dlogs();
616 let br_q = self.pbs_info.parameters.br_q();
617 for i in auto_element_dlogs.into_iter() {
618 let g_pow = if i == 0 {
619 -(g as isize)
620 } else {
621 (g.pow(i as u32) % br_q) as isize
622 };
623
624 let mut ksk_out = M::zeros(
625 self.pbs_info.auto_decomposer.decomposition_count(),
626 ring_size,
627 );
628 galois_key_gen(
629 &mut ksk_out,
630 sk_rlwe.values(),
631 g_pow,
632 &auto_gadget,
633 rlweq_modop,
634 rlweq_nttop,
635 &mut main_prng,
636 rng,
637 );
638 auto_keys.insert(i, ksk_out);
639 }
640
641 // rgsw ciphertexts of lwe secret elements
642 let rgsw_rgsw_decomposer = self
643 .pbs_info
644 .parameters
645 .rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
646 let (rgrg_d_a, rgrg_d_b) = (
647 rgsw_rgsw_decomposer.0.decomposition_count(),
648 rgsw_rgsw_decomposer.1.decomposition_count(),
649 );
650 let (rgrg_gadget_a, rgrg_gadget_b) = (
651 rgsw_rgsw_decomposer.0.gadget_vector(),
652 rgsw_rgsw_decomposer.1.gadget_vector(),
653 );
654 let rgsw_cts = sk_lwe
655 .values()
656 .iter()
657 .map(|si| {
658 let mut m = M::R::zeros(ring_size);
659 //TODO(Jay): It will be nice to have a function that returns polynomial
660 // (monomial infact!) corresponding to secret element embedded in ring X^{2N+1}.
661 // Save lots of mistakes where one forgest to emebed si in bigger ring.
662 let si = *si * (self.pbs_info.embedding_factor as i32);
663 if si < 0 {
664 // X^{-si} = X^{2N-si} = -X^{N-si}, assuming abs(si) < N
665 // (which it is given si is secret element)
666 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q.neg_one();
667 } else {
668 m.as_mut()[si as usize] = M::MatElement::one();
669 }
670
671 // public key RGSW encryption has no part that can be seeded, unlike secret key
672 // RGSW encryption where RLWE'_A(m) is seeded
673 let mut out_rgsw = M::zeros(rgrg_d_a * 2 + rgrg_d_b * 2, ring_size);
674 public_key_encrypt_rgsw(
675 &mut out_rgsw,
676 &m.as_ref(),
677 collective_pk,
678 &rgrg_gadget_a,
679 &rgrg_gadget_b,
680 rlweq_modop,
681 rlweq_nttop,
682 rng,
683 );
684
685 out_rgsw
686 })
687 .collect_vec();
688
689 // LWE ksk
690 let mut lwe_ksk =
691 M::R::zeros(self.pbs_info.lwe_decomposer.decomposition_count() * ring_size);
692 let lwe_modop = &self.pbs_info.lwe_modop;
693 let d_lwe_gadget_vec = self.pbs_info.lwe_decomposer.gadget_vector();
694 lwe_ksk_keygen(
695 sk_rlwe.values(),
696 sk_lwe.values(),
697 &mut lwe_ksk,
698 &d_lwe_gadget_vec,
699 lwe_modop,
700 &mut main_prng,
701 rng,
702 );
703
704 CommonReferenceSeededMultiPartyServerKeyShare::new(
705 rgsw_cts,
706 auto_keys,
707 lwe_ksk,
708 cr_seed,
709 self.pbs_info.parameters.clone(),
710 )
711 })
712 }
713
714 pub(super) fn multi_party_public_key_share(
715 &self,
716 cr_seed: [u8; 32],
717 client_key: &ClientKey,
718 ) -> CommonReferenceSeededCollectivePublicKeyShare<
719 <M as Matrix>::R,
720 [u8; 32],
721 BoolParameters<<M as Matrix>::MatElement>,
722 > {
723 DefaultSecureRng::with_local_mut(|rng| {
724 let mut share_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0);
725 let modop = &self.pbs_info.rlwe_modop;
726 let nttop = &self.pbs_info.rlwe_nttop;
727 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
728 public_key_share(
729 &mut share_out,
730 client_key.sk_rlwe().values(),
731 modop,
732 nttop,
733 &mut main_prng,
734 rng,
735 );
736 CommonReferenceSeededCollectivePublicKeyShare::new(
737 share_out,
738 cr_seed,
739 self.pbs_info.parameters.clone(),
740 )
741 })
742 }
743
744 pub(super) fn multi_party_decryption_share(
745 &self,
746 lwe_ct: &M::R,
747 client_key: &ClientKey,
748 ) -> <M as Matrix>::MatElement {
749 assert!(lwe_ct.as_ref().len() == self.pbs_info.parameters.rlwe_n().0 + 1);
750 let modop = &self.pbs_info.rlwe_modop;
751 let mut neg_s = M::R::try_convert_from(
752 client_key.sk_rlwe().values(),
753 &self.pbs_info.parameters.rlwe_q(),
754 );
755 modop.elwise_neg_mut(neg_s.as_mut());
756
757 let mut neg_sa = M::MatElement::zero();
758 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
759 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
760 });
761
762 let e = DefaultSecureRng::with_local_mut(|rng| {
763 let mut e =
764 RandomGaussianElementInModulus::random(rng, self.pbs_info.parameters.rlwe_q());
765 e
766 });
767 let share = modop.add(&neg_sa, &e);
768
769 share
770 }
771
772 pub(crate) fn multi_party_decrypt(&self, shares: &[M::MatElement], lwe_ct: &M::R) -> bool {
773 let modop = &self.pbs_info.rlwe_modop;
774 let mut sum_a = M::MatElement::zero();
775 shares
776 .iter()
777 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i));
778
779 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
780 self.pbs_info.parameters.rlwe_q().decode(encoded_m)
781 }
782
783 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
784 self.pk_encrypt_batched(pk, &vec![m]).remove(0)
785 }
786
787 /// Encrypts a batch booleans as multiple LWE ciphertexts.
788 ///
789 /// For public key encryption we first encrypt `m` as a RLWE ciphertext and
790 /// then sample extract LWE samples at required indices.
791 ///
792 /// - TODO(Jay:) Communication can be improved by not sample exctracting and
793 /// instead just truncate degree 0 values (part Bs)
794 pub(crate) fn pk_encrypt_batched(&self, pk: &M, m: &[bool]) -> Vec<M::R> {
795 DefaultSecureRng::with_local_mut(|rng| {
796 let ring_size = self.pbs_info.parameters.rlwe_n().0;
797 assert!(
798 m.len() <= ring_size,
799 "Cannot batch encrypt > ring_size{ring_size} elements at once"
800 );
801
802 let modop = &self.pbs_info.rlwe_modop;
803 let nttop = &self.pbs_info.rlwe_nttop;
804
805 // RLWE(0)
806 // sample ephemeral key u
807 let mut u = vec![0i32; ring_size];
808 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
809 let mut u = M::R::try_convert_from(&u, &self.pbs_info.parameters.rlwe_q());
810 nttop.forward(u.as_mut());
811
812 let mut ua = M::R::zeros(ring_size);
813 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
814 let mut ub = M::R::zeros(ring_size);
815 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
816
817 // a*u
818 nttop.forward(ua.as_mut());
819 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
820 nttop.backward(ua.as_mut());
821
822 // b*u
823 nttop.forward(ub.as_mut());
824 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
825 nttop.backward(ub.as_mut());
826
827 let mut rlwe = M::zeros(2, ring_size);
828 // sample error
829 rlwe.iter_rows_mut().for_each(|ri| {
830 RandomFillGaussianInModulus::<[M::MatElement], CiphertextModulus<M::MatElement>>::random_fill(
831 rng,
832 &self.pbs_info.parameters.rlwe_q(),
833 ri.as_mut(),
834 );
835 });
836
837 // a*u + e0
838 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
839 // b*u + e1
840 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
841
842 //FIXME(Jay): Figure out a way to get Q/8 form modulus
843 let mut m_vec = M::R::zeros(ring_size);
844 izip!(m_vec.as_mut().iter_mut(), m.iter()).for_each(|(m_el, m_bool)| {
845 if *m_bool {
846 // Q/8
847 *m_el = self.pbs_info.rlwe_q().true_el()
848 } else {
849 // -Q/8
850 *m_el = self.pbs_info.rlwe_q().false_el()
851 }
852 });
853
854 // b*u + e1 + m
855 modop.elwise_add_mut(rlwe.get_row_mut(1), m_vec.as_ref());
856 // rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
857
858 // sample extract index required indices
859 let samples = m.len();
860 (0..samples)
861 .into_iter()
862 .map(|i| {
863 let mut lwe_out = M::R::zeros(ring_size + 1);
864 sample_extract(&mut lwe_out, &rlwe, modop, i);
865 lwe_out
866 })
867 .collect_vec()
868 })
869 }
870
871 /// TODO(Jay): Fetch client key from thread local
872 pub fn sk_encrypt(&self, m: bool, client_key: &ClientKey) -> M::R {
873 //FIXME(Jay): Figure out a way to get Q/8 form modulus
874 let m = if m {
875 // Q/8
876 self.pbs_info.rlwe_q().true_el()
877 } else {
878 // -Q/8
879 self.pbs_info.rlwe_q().false_el()
880 };
881
882 DefaultSecureRng::with_local_mut(|rng| {
883 let mut lwe_out = M::R::zeros(self.pbs_info.parameters.rlwe_n().0 + 1);
884 encrypt_lwe(
885 &mut lwe_out,
886 &m,
887 client_key.sk_rlwe().values(),
888 &self.pbs_info.rlwe_modop,
889 rng,
890 );
891 lwe_out
892 })
893 }
894
895 pub fn sk_decrypt(&self, lwe_ct: &M::R, client_key: &ClientKey) -> bool {
896 let m = decrypt_lwe(
897 lwe_ct,
898 client_key.sk_rlwe().values(),
899 &self.pbs_info.rlwe_modop,
900 );
901 self.pbs_info.rlwe_q().decode(m)
902 }
903
904 pub(super) fn aggregate_multi_party_server_key_shares<S>(
905 &self,
906 shares: &[CommonReferenceSeededMultiPartyServerKeyShare<
907 M,
908 BoolParameters<M::MatElement>,
909 S,
910 >],
911 ) -> SeededMultiPartyServerKey<M, S, BoolParameters<M::MatElement>>
912 where
913 S: PartialEq + Clone,
914 M: Clone,
915 {
916 assert!(shares.len() > 0);
917 let parameters = shares[0].parameters().clone();
918 let cr_seed = shares[0].cr_seed();
919
920 let rlwe_n = parameters.rlwe_n().0;
921 let g = parameters.g() as isize;
922 let rlwe_q = parameters.rlwe_q();
923 let lwe_q = parameters.lwe_q();
924
925 // sanity checks
926 shares.iter().skip(1).for_each(|s| {
927 assert!(s.parameters() == ¶meters);
928 assert!(s.cr_seed() == cr_seed);
929 });
930
931 let rlweq_modop = &self.pbs_info.rlwe_modop;
932 let rlweq_nttop = &self.pbs_info.rlwe_nttop;
933
934 // auto keys
935 let mut auto_keys = HashMap::new();
936 let auto_elements_dlog = parameters.auto_element_dlogs();
937 for i in auto_elements_dlog.into_iter() {
938 let mut key = M::zeros(parameters.auto_decomposition_count().0, rlwe_n);
939
940 shares.iter().for_each(|s| {
941 let auto_key_share_i = s.auto_keys().get(&i).expect("Auto key {i} missing");
942 assert!(
943 auto_key_share_i.dimension()
944 == (parameters.auto_decomposition_count().0, rlwe_n)
945 );
946 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
947 |(partb_out, partb_share)| {
948 rlweq_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
949 },
950 );
951 });
952
953 auto_keys.insert(i, key);
954 }
955
956 // rgsw ciphertext (most expensive part!)
957 let lwe_n = parameters.lwe_n().0;
958 let rgsw_by_rgsw_decomposer =
959 parameters.rgsw_rgsw_decomposer::<DefaultDecomposer<M::MatElement>>();
960 let mut scratch_matrix = M::zeros(
961 std::cmp::max(
962 rgsw_by_rgsw_decomposer.a().decomposition_count(),
963 rgsw_by_rgsw_decomposer.b().decomposition_count(),
964 ) + (rgsw_by_rgsw_decomposer.a().decomposition_count() * 2
965 + rgsw_by_rgsw_decomposer.b().decomposition_count() * 2),
966 rlwe_n,
967 );
968
969 let mut tmp_rgsw =
970 RgswCiphertext::<M, _>::empty(rlwe_n, &rgsw_by_rgsw_decomposer, rlwe_q.clone()).data;
971 let rgsw_cts = (0..lwe_n).into_iter().map(|index| {
972 // copy over rgsw ciphertext for index^th secret element from first share and
973 // treat it as accumulating rgsw ciphertext
974 let mut rgsw_i = shares[0].rgsw_cts()[index].clone();
975
976 shares.iter().skip(1).for_each(|si| {
977 // copy over si's RGSW[index] ciphertext and send to evaluation domain
978 izip!(tmp_rgsw.iter_rows_mut(), si.rgsw_cts()[index].iter_rows()).for_each(
979 |(to_ri, from_ri)| {
980 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
981 rlweq_nttop.forward(to_ri.as_mut())
982 },
983 );
984
985 rgsw_by_rgsw_inplace(
986 &mut rgsw_i,
987 &tmp_rgsw,
988 &rgsw_by_rgsw_decomposer,
989 &mut scratch_matrix,
990 rlweq_nttop,
991 rlweq_modop,
992 );
993 });
994
995 rgsw_i
996 });
997 // d_a and d_b may differ for RGSWxRGSW multiplication and RLWExRGSW
998 // multiplication. After this point RGSW ciphertexts will only be used for
999 // RLWExRGSW multiplication (in blind rotation). Thus we drop any additional
1000 // RLWE ciphertexts in RGSW ciphertexts after RGSw x RGSW multiplication
1001 let (rgswrgsw_d_a, rgswrgsw_d_b) = self.pbs_info.parameters.rgsw_rgsw_decomposition_count();
1002 let (rlrg_d_a, rlrg_d_b) = self.pbs_info.parameters.rlwe_rgsw_decomposition_count();
1003 let rgsw_ct_rows_in = rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 * 2;
1004 let rgsw_ct_rows_out = rlrg_d_a.0 * 2 + rlrg_d_b.0 * 2;
1005 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);
1006 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);
1007 let rgsw_cts = rgsw_cts
1008 .map(|ct_i_in| {
1009 assert!(ct_i_in.dimension() == (rgsw_ct_rows_in, rlwe_n));
1010 let mut reduced_ct_i_out = M::zeros(rgsw_ct_rows_out, rlwe_n);
1011
1012 // RLWE'(-sm) part A
1013 izip!(
1014 reduced_ct_i_out.iter_rows_mut().take(rlrg_d_a.0),
1015 ct_i_in
1016 .iter_rows()
1017 .skip(rgswrgsw_d_a.0 - rlrg_d_a.0)
1018 .take(rlrg_d_a.0)
1019 )
1020 .for_each(|(to_ri, from_ri)| {
1021 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
1022 });
1023
1024 // RLWE'(-sm) part B
1025 izip!(
1026 reduced_ct_i_out
1027 .iter_rows_mut()
1028 .skip(rlrg_d_a.0)
1029 .take(rlrg_d_a.0),
1030 ct_i_in
1031 .iter_rows()
1032 .skip(rgswrgsw_d_a.0 + (rgswrgsw_d_a.0 - rlrg_d_a.0))
1033 .take(rlrg_d_a.0)
1034 )
1035 .for_each(|(to_ri, from_ri)| {
1036 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
1037 });
1038
1039 // RLWE'(m) Part A
1040 izip!(
1041 reduced_ct_i_out
1042 .iter_rows_mut()
1043 .skip(rlrg_d_a.0 * 2)
1044 .take(rlrg_d_b.0),
1045 ct_i_in
1046 .iter_rows()
1047 .skip(rgswrgsw_d_a.0 * 2 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
1048 .take(rlrg_d_b.0)
1049 )
1050 .for_each(|(to_ri, from_ri)| {
1051 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
1052 });
1053
1054 // RLWE'(m) Part B
1055 izip!(
1056 reduced_ct_i_out
1057 .iter_rows_mut()
1058 .skip(rlrg_d_a.0 * 2 + rlrg_d_b.0)
1059 .take(rlrg_d_b.0),
1060 ct_i_in
1061 .iter_rows()
1062 .skip(rgswrgsw_d_a.0 * 2 + rgswrgsw_d_b.0 + (rgswrgsw_d_b.0 - rlrg_d_b.0))
1063 .take(rlrg_d_b.0)
1064 )
1065 .for_each(|(to_ri, from_ri)| {
1066 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
1067 });
1068
1069 reduced_ct_i_out
1070 })
1071 .collect_vec();
1072
1073 // LWE ksks
1074 let mut lwe_ksk = M::R::zeros(rlwe_n * parameters.lwe_decomposition_count().0);
1075 let lweq_modop = &self.pbs_info.lwe_modop;
1076 shares.iter().for_each(|si| {
1077 assert!(si.lwe_ksk().as_ref().len() == rlwe_n * parameters.lwe_decomposition_count().0);
1078 lweq_modop.elwise_add_mut(lwe_ksk.as_mut(), si.lwe_ksk().as_ref())
1079 });
1080
1081 SeededMultiPartyServerKey::new(rgsw_cts, auto_keys, lwe_ksk, cr_seed.clone(), parameters)
1082 }
1083}
1084
1085impl<M, NttOp, RlweModOp, LweModOp> BoolEvaluator<M, NttOp, RlweModOp, LweModOp>
1086where
1087 M: MatrixMut + MatrixEntity,
1088 M::R: RowMut + RowEntity,
1089 M::MatElement: PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo,
1090 RlweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1091 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1092 NttOp: Ntt<Element = M::MatElement>,
1093{
1094 /// Returns c0 + c1 + Q/4
1095 fn _add_and_shift_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
1096 let modop = &self.pbs_info.rlwe_modop;
1097 modop.elwise_add_mut(c0.as_mut(), c1.as_ref());
1098 // +Q/4
1099 c0.as_mut()[0] = modop.add(&c0.as_ref()[0], &self.pbs_info.rlwe_qby4);
1100 }
1101
1102 /// Returns 2(c0 - c1) + Q/4
1103 fn _subtract_double_lwe_cts(&self, c0: &mut M::R, c1: &M::R) {
1104 let modop = &self.pbs_info.rlwe_modop;
1105 // c0 - c1
1106 modop.elwise_sub_mut(c0.as_mut(), c1.as_ref());
1107
1108 // double
1109 c0.as_mut().iter_mut().for_each(|v| *v = modop.add(v, v));
1110 }
1111}
1112
1113impl<M, NttOp, RlweModOp, LweModOp> BooleanGates for BoolEvaluator<M, NttOp, RlweModOp, LweModOp>
1114where
1115 M: MatrixMut + MatrixEntity,
1116 M::R: RowMut + RowEntity + Clone,
1117 M::MatElement:
1118 PrimInt + FromPrimitive + One + Copy + Zero + Display + WrappingSub + NumInfo + From<bool>,
1119 RlweModOp: VectorOps<Element = M::MatElement>
1120 + ArithmeticOps<Element = M::MatElement>
1121 + ShoupMatrixFMA<M::R>,
1122 LweModOp: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
1123 NttOp: Ntt<Element = M::MatElement>,
1124{
1125 type Ciphertext = M::R;
1126 type Key = Key;
1127
1128 fn nand_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1129 self._add_and_shift_lwe_cts(c0, c1);
1130
1131 // PBS
1132 pbs(
1133 &self.pbs_info,
1134 &self.nand_test_vec,
1135 c0,
1136 server_key,
1137 &mut self.scratch_memory.lwe_vector,
1138 &mut self.scratch_memory.decomposition_matrix,
1139 );
1140 }
1141
1142 fn and_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1143 self._add_and_shift_lwe_cts(c0, c1);
1144
1145 // PBS
1146 pbs(
1147 &self.pbs_info,
1148 &self.and_test_vec,
1149 c0,
1150 server_key,
1151 &mut self.scratch_memory.lwe_vector,
1152 &mut self.scratch_memory.decomposition_matrix,
1153 );
1154 }
1155
1156 fn or_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1157 self._add_and_shift_lwe_cts(c0, c1);
1158
1159 // PBS
1160 pbs(
1161 &self.pbs_info,
1162 &self.or_test_vec,
1163 c0,
1164 server_key,
1165 &mut self.scratch_memory.lwe_vector,
1166 &mut self.scratch_memory.decomposition_matrix,
1167 );
1168 }
1169
1170 fn nor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1171 self._add_and_shift_lwe_cts(c0, c1);
1172
1173 // PBS
1174 pbs(
1175 &self.pbs_info,
1176 &self.nor_test_vec,
1177 c0,
1178 server_key,
1179 &mut self.scratch_memory.lwe_vector,
1180 &mut self.scratch_memory.decomposition_matrix,
1181 )
1182 }
1183
1184 fn xor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1185 self._subtract_double_lwe_cts(c0, c1);
1186
1187 // PBS
1188 pbs(
1189 &self.pbs_info,
1190 &self.xor_test_vec,
1191 c0,
1192 server_key,
1193 &mut self.scratch_memory.lwe_vector,
1194 &mut self.scratch_memory.decomposition_matrix,
1195 );
1196 }
1197
1198 fn xnor_inplace(&mut self, c0: &mut M::R, c1: &M::R, server_key: &Self::Key) {
1199 self._subtract_double_lwe_cts(c0, c1);
1200
1201 // PBS
1202 pbs(
1203 &self.pbs_info,
1204 &self.xnor_test_vec,
1205 c0,
1206 server_key,
1207 &mut self.scratch_memory.lwe_vector,
1208 &mut self.scratch_memory.decomposition_matrix,
1209 );
1210 }
1211
1212 fn not_inplace(&mut self, c0: &mut M::R) {
1213 let modop = &self.pbs_info.rlwe_modop;
1214 c0.as_mut().iter_mut().for_each(|v| *v = modop.neg(v));
1215 }
1216
1217 fn and(
1218 &mut self,
1219 c0: &Self::Ciphertext,
1220 c1: &Self::Ciphertext,
1221 key: &Self::Key,
1222 ) -> Self::Ciphertext {
1223 let mut out = c0.clone();
1224 self.and_inplace(&mut out, c1, key);
1225 out
1226 }
1227
1228 fn nand(
1229 &mut self,
1230 c0: &Self::Ciphertext,
1231 c1: &Self::Ciphertext,
1232 key: &Self::Key,
1233 ) -> Self::Ciphertext {
1234 let mut out = c0.clone();
1235 self.nand_inplace(&mut out, c1, key);
1236 out
1237 }
1238
1239 fn or(
1240 &mut self,
1241 c0: &Self::Ciphertext,
1242 c1: &Self::Ciphertext,
1243 key: &Self::Key,
1244 ) -> Self::Ciphertext {
1245 let mut out = c0.clone();
1246 self.or_inplace(&mut out, c1, key);
1247 out
1248 }
1249
1250 fn nor(
1251 &mut self,
1252 c0: &Self::Ciphertext,
1253 c1: &Self::Ciphertext,
1254 key: &Self::Key,
1255 ) -> Self::Ciphertext {
1256 let mut out = c0.clone();
1257 self.nor_inplace(&mut out, c1, key);
1258 out
1259 }
1260
1261 fn xnor(
1262 &mut self,
1263 c0: &Self::Ciphertext,
1264 c1: &Self::Ciphertext,
1265 key: &Self::Key,
1266 ) -> Self::Ciphertext {
1267 let mut out = c0.clone();
1268 self.xnor_inplace(&mut out, c1, key);
1269 out
1270 }
1271
1272 fn xor(
1273 &mut self,
1274 c0: &Self::Ciphertext,
1275 c1: &Self::Ciphertext,
1276 key: &Self::Key,
1277 ) -> Self::Ciphertext {
1278 let mut out = c0.clone();
1279 self.xor_inplace(&mut out, c1, key);
1280 out
1281 }
1282
1283 fn not(&mut self, c: &Self::Ciphertext) -> Self::Ciphertext {
1284 let mut out = c.clone();
1285 self.not_inplace(&mut out);
1286 out
1287 }
1288}
1289
1290// #[cfg(test)]
1291// mod tests {
1292// use bool::parameters::{MP_BOOL_PARAMS, SP_BOOL_PARAMS};
1293// use rand::{thread_rng, Rng};
1294// use rand_distr::Uniform;
1295
1296// use crate::{
1297// backend::{GetModulus, ModInit, ModularOpsU64, WordSizeModulus},
1298// bool::{
1299// self, CommonReferenceSeededMultiPartyServerKeyShare, PublicKey,
1300// SeededMultiPartyServerKey,
1301// },
1302// ntt::NttBackendU64,
1303// random::{RandomElementInModulus, DEFAULT_RNG},
1304// rgsw::{
1305// self, measure_noise, public_key_encrypt_rlwe,
1306// secret_key_encrypt_rlwe, tests::{_measure_noise_rgsw,
1307// _sk_encrypt_rlwe}, RgswCiphertext,
1308// RgswCiphertextEvaluationDomain, SeededRgswCiphertext,
1309// SeededRlweCiphertext, },
1310// utils::{negacyclic_mul, Stats},
1311// };
1312
1313// use super::*;
1314
1315// #[test]
1316// fn bool_encrypt_decrypt_works() {
1317// let bool_evaluator = BoolEvaluator::<
1318// Vec<Vec<u64>>,
1319// NttBackendU64,
1320// ModularOpsU64<CiphertextModulus<u64>>,
1321// ModularOpsU64<CiphertextModulus<u64>>,
1322// >::new(SP_BOOL_PARAMS);
1323// let client_key = bool_evaluator.client_key();
1324
1325// let mut m = true;
1326// for _ in 0..1000 {
1327// let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
1328// let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
1329// assert_eq!(m, m_back);
1330// m = !m;
1331// }
1332// }
1333
1334// #[test]
1335// fn bool_nand() {
1336// let mut bool_evaluator = BoolEvaluator::<
1337// Vec<Vec<u64>>,
1338// NttBackendU64,
1339// ModularOpsU64<CiphertextModulus<u64>>,
1340// ModularOpsU64<CiphertextModulus<u64>>,
1341// >::new(SP_BOOL_PARAMS);
1342
1343// // println!("{:?}", bool_evaluator.nand_test_vec);
1344// let client_key = bool_evaluator.client_key();
1345// let seeded_server_key = bool_evaluator.server_key(&client_key);
1346// let server_key_eval_domain =
1347// ServerKeyEvaluationDomain::<_, DefaultSecureRng,
1348// NttBackendU64>::from( &seeded_server_key,
1349// );
1350
1351// let mut m0 = false;
1352// let mut m1 = true;
1353
1354// let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
1355// let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
1356
1357// for _ in 0..500 {
1358// let ct_back = bool_evaluator.nand(&ct0, &ct1,
1359// &server_key_eval_domain);
1360
1361// let m_out = !(m0 && m1);
1362
1363// let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
1364// assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
1365
1366// m1 = m0;
1367// m0 = m_out;
1368
1369// ct1 = ct0;
1370// ct0 = ct_back;
1371// }
1372// }
1373
1374// #[test]
1375// fn bool_xor() {
1376// let mut bool_evaluator = BoolEvaluator::<
1377// Vec<Vec<u64>>,
1378// NttBackendU64,
1379// ModularOpsU64<CiphertextModulus<u64>>,
1380// ModularOpsU64<CiphertextModulus<u64>>,
1381// >::new(SP_BOOL_PARAMS);
1382
1383// // println!("{:?}", bool_evaluator.nand_test_vec);
1384// let client_key = bool_evaluator.client_key();
1385// let seeded_server_key = bool_evaluator.server_key(&client_key);
1386// let server_key_eval_domain =
1387// ServerKeyEvaluationDomain::<_, DefaultSecureRng,
1388// NttBackendU64>::from( &seeded_server_key,
1389// );
1390
1391// let mut m0 = false;
1392// let mut m1 = true;
1393
1394// let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
1395// let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
1396
1397// for _ in 0..1000 {
1398// let ct_back = bool_evaluator.xor(&ct0, &ct1,
1399// &server_key_eval_domain); let m_out = (m0 ^ m1);
1400
1401// let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
1402// assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
1403
1404// m1 = m0;
1405// m0 = m_out;
1406
1407// ct1 = ct0;
1408// ct0 = ct_back;
1409// }
1410// }
1411
1412// #[test]
1413// fn multi_party_encryption_decryption() {
1414// let bool_evaluator = BoolEvaluator::<
1415// Vec<Vec<u64>>,
1416// NttBackendU64,
1417// ModularOpsU64<CiphertextModulus<u64>>,
1418// ModularOpsU64<CiphertextModulus<u64>>,
1419// >::new(MP_BOOL_PARAMS);
1420
1421// let no_of_parties = 500;
1422// let parties = (0..no_of_parties)
1423// .map(|_| bool_evaluator.client_key())
1424// .collect_vec();
1425
1426// let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.pbs_info.rlwe_n()];
1427// parties.iter().for_each(|k| {
1428// izip!(ideal_rlwe_sk.iter_mut(),
1429// k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| { *ideal_i =
1430// *ideal_i + s_i; });
1431// });
1432
1433// let mut m = true;
1434// for i in 0..100 {
1435// let pk_cr_seed = [0u8; 32];
1436
1437// let public_key_share = parties
1438// .iter()
1439// .map(|k|
1440// bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1441// .collect_vec();
1442
1443// let collective_pk = PublicKey::<
1444// Vec<Vec<u64>>,
1445// DefaultSecureRng,
1446// ModularOpsU64<CiphertextModulus<u64>>,
1447// >::from(public_key_share.as_slice());
1448// let lwe_ct = bool_evaluator.pk_encrypt(collective_pk.key(), m);
1449
1450// let decryption_shares = parties
1451// .iter()
1452// .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct,
1453// k)) .collect_vec();
1454
1455// let m_back =
1456// bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
1457
1458// {
1459// let ideal_m = if m {
1460// bool_evaluator.pbs_info.parameters.rlwe_q().true_el()
1461// } else {
1462// bool_evaluator.pbs_info.parameters.rlwe_q().false_el()
1463// };
1464// let noise = measure_noise_lwe(
1465// &lwe_ct,
1466// &ideal_rlwe_sk,
1467// &bool_evaluator.pbs_info.rlwe_modop,
1468// &ideal_m,
1469// );
1470// println!("Noise: {noise}");
1471// }
1472
1473// assert_eq!(m_back, m);
1474// m = !m;
1475// }
1476// }
1477
1478// fn _collecitve_public_key_gen(rlwe_q: u64, parties_rlwe_sk:
1479// &[RlweSecret]) -> Vec<Vec<u64>> { let ring_size =
1480// parties_rlwe_sk[0].values.len(); assert!(ring_size.
1481// is_power_of_two()); let mut rng = DefaultSecureRng::new();
1482// let nttop = NttBackendU64::new(&rlwe_q, ring_size);
1483// let modop = ModularOpsU64::new(rlwe_q);
1484
1485// // Generate Pk shares
1486// let pk_seed = [0u8; 32];
1487// let pk_shares = parties_rlwe_sk.iter().map(|sk| {
1488// let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
1489// let mut share_out = vec![0u64; ring_size];
1490// public_key_share(
1491// &mut share_out,
1492// sk.values(),
1493// &modop,
1494// &nttop,
1495// &mut p_rng,
1496// &mut rng,
1497// );
1498// share_out
1499// });
1500
1501// let mut pk_part_b = vec![0u64; ring_size];
1502// pk_shares.for_each(|share| modop.elwise_add_mut(&mut pk_part_b,
1503// &share)); let mut pk_part_a = vec![0u64; ring_size];
1504// let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
1505// RandomFillUniformInModulus::random_fill(&mut p_rng, &rlwe_q,
1506// pk_part_a.as_mut_slice());
1507
1508// vec![pk_part_a, pk_part_b]
1509// }
1510
1511// fn _multi_party_all_keygen(
1512// bool_evaluator: &BoolEvaluator<
1513// Vec<Vec<u64>>,
1514// NttBackendU64,
1515// ModularOpsU64<CiphertextModulus<u64>>,
1516// ModularOpsU64<CiphertextModulus<u64>>,
1517// >,
1518// no_of_parties: usize,
1519// ) -> (
1520// Vec<ClientKey>,
1521// PublicKey<Vec<Vec<u64>>, DefaultSecureRng,
1522// ModularOpsU64<CiphertextModulus<u64>>>, Vec<
1523// CommonReferenceSeededMultiPartyServerKeyShare<
1524// Vec<Vec<u64>>,
1525// BoolParameters<u64>,
1526// [u8; 32],
1527// >,
1528// >,
1529// SeededMultiPartyServerKey<Vec<Vec<u64>>, [u8; 32],
1530// BoolParameters<u64>>, ServerKeyEvaluationDomain<Vec<Vec<u64>>,
1531// DefaultSecureRng, NttBackendU64>, ClientKey,
1532// ) {
1533// let parties = (0..no_of_parties)
1534// .map(|_| bool_evaluator.client_key())
1535// .collect_vec();
1536
1537// let mut rng = DefaultSecureRng::new();
1538
1539// // Collective public key
1540// let mut pk_cr_seed = [0u8; 32];
1541// rng.fill_bytes(&mut pk_cr_seed);
1542// let public_key_share = parties
1543// .iter()
1544// .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed,
1545// k)) .collect_vec();
1546// let collective_pk =
1547// PublicKey::<Vec<Vec<u64>>, DefaultSecureRng,
1548// _>::from(public_key_share.as_slice());
1549
1550// // Server key
1551// let mut pbs_cr_seed = [0u8; 32];
1552// rng.fill_bytes(&mut pbs_cr_seed);
1553// let server_key_shares = parties
1554// .iter()
1555// .map(|k| {
1556// bool_evaluator.multi_party_server_key_share(pbs_cr_seed,
1557// &collective_pk.key(), k) })
1558// .collect_vec();
1559// let seeded_server_key =
1560//
1561// bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
1562// let server_key_eval = ServerKeyEvaluationDomain::<_,
1563// DefaultSecureRng, NttBackendU64>::from( &seeded_server_key,
1564// );
1565
1566// // construct ideal rlwe sk for meauring noise
1567// let ideal_client_key = {
1568// let mut ideal_rlwe_sk = vec![0i32;
1569// bool_evaluator.pbs_info.rlwe_n()]; parties.iter().for_each(|k| {
1570// izip!(ideal_rlwe_sk.iter_mut(),
1571// k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
1572// *ideal_i = *ideal_i + s_i; });
1573// });
1574// let mut ideal_lwe_sk = vec![0i32;
1575// bool_evaluator.pbs_info.lwe_n()]; parties.iter().for_each(|k| {
1576// izip!(ideal_lwe_sk.iter_mut(),
1577// k.sk_lwe().values()).for_each(|(ideal_i, s_i)| { *ideal_i
1578// = *ideal_i + s_i; });
1579// });
1580
1581// ClientKey::new(
1582// RlweSecret {
1583// values: ideal_rlwe_sk,
1584// },
1585// LweSecret {
1586// values: ideal_lwe_sk,
1587// },
1588// )
1589// };
1590
1591// (
1592// parties,
1593// collective_pk,
1594// server_key_shares,
1595// seeded_server_key,
1596// server_key_eval,
1597// ideal_client_key,
1598// )
1599// }
1600
1601// #[test]
1602// fn multi_party_nand() {
1603// let mut bool_evaluator = BoolEvaluator::<
1604// Vec<Vec<u64>>,
1605// NttBackendU64,
1606// ModularOpsU64<CiphertextModulus<u64>>,
1607// ModularOpsU64<CiphertextModulus<u64>>,
1608// >::new(MP_BOOL_PARAMS);
1609
1610// let (parties, collective_pk, _, _, server_key_eval, ideal_client_key)
1611// = _multi_party_all_keygen(&bool_evaluator, 2);
1612
1613// let mut m0 = true;
1614// let mut m1 = false;
1615
1616// let mut lwe0 = bool_evaluator.pk_encrypt(collective_pk.key(), m0);
1617// let mut lwe1 = bool_evaluator.pk_encrypt(collective_pk.key(), m1);
1618
1619// for _ in 0..2000 {
1620// let lwe_out = bool_evaluator.nand(&lwe0, &lwe1,
1621// &server_key_eval);
1622
1623// let m_expected = !(m0 & m1);
1624
1625// // multi-party decrypt
1626// let decryption_shares = parties
1627// .iter()
1628// .map(|k|
1629// bool_evaluator.multi_party_decryption_share(&lwe_out, k))
1630// .collect_vec(); let m_back =
1631// bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
1632
1633// // let m_back = bool_evaluator.sk_decrypt(&lwe_out,
1634// &ideal_client_key);
1635
1636// assert!(m_expected == m_back, "Expected {m_expected}, got
1637// {m_back}"); m1 = m0;
1638// m0 = m_expected;
1639
1640// lwe1 = lwe0;
1641// lwe0 = lwe_out;
1642// }
1643// }
1644
1645// #[test]
1646// fn noise_tester() {
1647// let bool_evaluator = BoolEvaluator::<
1648// Vec<Vec<u64>>,
1649// NttBackendU64,
1650// ModularOpsU64<CiphertextModulus<u64>>,
1651// ModularOpsU64<CiphertextModulus<u64>>,
1652// >::new(SP_BOOL_PARAMS);
1653
1654// // let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
1655// // _multi_party_all_keygen(&bool_evaluator, 20);
1656// let no_of_parties = 2;
1657// let lwe_q = bool_evaluator.pbs_info.parameters.lwe_q();
1658// let rlwe_q = bool_evaluator.pbs_info.parameters.rlwe_q();
1659// let lwe_n = bool_evaluator.pbs_info.parameters.lwe_n().0;
1660// let rlwe_n = bool_evaluator.pbs_info.parameters.rlwe_n().0;
1661// let lwe_modop = &bool_evaluator.pbs_info.lwe_modop;
1662// let rlwe_nttop = &bool_evaluator.pbs_info.rlwe_nttop;
1663// let rlwe_modop = &bool_evaluator.pbs_info.rlwe_modop;
1664
1665// // let rgsw_rgsw_decomposer = &bool_evaluator
1666// // .pbs_info
1667// // .parameters
1668// // .rgsw_rgsw_decomposer::<DefaultDecomposer<u64>>();
1669// // let rgsw_rgsw_gadget_a = rgsw_rgsw_decomposer.0.gadget_vector();
1670// // let rgsw_rgsw_gadget_b = rgsw_rgsw_decomposer.1.gadget_vector();
1671
1672// let rlwe_rgsw_decomposer =
1673// &bool_evaluator.pbs_info.rlwe_rgsw_decomposer; let rlwe_rgsw_gadget_a
1674// = rlwe_rgsw_decomposer.0.gadget_vector(); let rlwe_rgsw_gadget_b =
1675// rlwe_rgsw_decomposer.1.gadget_vector();
1676
1677// let auto_decomposer = &bool_evaluator.pbs_info.auto_decomposer;
1678// let auto_gadget = auto_decomposer.gadget_vector();
1679
1680// let parties = (0..no_of_parties)
1681// .map(|_| bool_evaluator.client_key())
1682// .collect_vec();
1683
1684// let ideal_client_key = {
1685// let mut ideal_rlwe_sk = vec![0i32;
1686// bool_evaluator.pbs_info.rlwe_n()]; parties.iter().for_each(|k| {
1687// izip!(ideal_rlwe_sk.iter_mut(),
1688// k.sk_rlwe().values()).for_each(|(ideal_i, s_i)| {
1689// *ideal_i = *ideal_i + s_i; });
1690// });
1691// let mut ideal_lwe_sk = vec![0i32;
1692// bool_evaluator.pbs_info.lwe_n()]; parties.iter().for_each(|k| {
1693// izip!(ideal_lwe_sk.iter_mut(),
1694// k.sk_lwe().values()).for_each(|(ideal_i, s_i)| { *ideal_i
1695// = *ideal_i + s_i; });
1696// });
1697
1698// ClientKey::new(
1699// RlweSecret {
1700// values: ideal_rlwe_sk,
1701// },
1702// LweSecret {
1703// values: ideal_lwe_sk,
1704// },
1705// )
1706// };
1707
1708// // check noise in freshly encrypted RLWE ciphertext (ie var_fresh)
1709// if true {
1710// let mut rng = DefaultSecureRng::new();
1711// let mut check = Stats { samples: vec![] };
1712// for _ in 0..10 {
1713// // generate a new collective public key
1714// let mut pk_cr_seed = [0u8; 32];
1715// rng.fill_bytes(&mut pk_cr_seed);
1716// let public_key_share = parties
1717// .iter()
1718// .map(|k|
1719// bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1720// .collect_vec(); let collective_pk = PublicKey::<
1721// Vec<Vec<u64>>,
1722// DefaultSecureRng,
1723// ModularOpsU64<CiphertextModulus<u64>>,
1724// >::from(public_key_share.as_slice());
1725
1726// let mut m = vec![0u64; rlwe_n];
1727// RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q,
1728// m.as_mut_slice()); let mut rlwe_ct = vec![vec![0u64; rlwe_n];
1729// 2]; public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
1730// &mut rlwe_ct,
1731// collective_pk.key(),
1732// &m,
1733// rlwe_modop,
1734// rlwe_nttop,
1735// &mut rng,
1736// );
1737
1738// let mut m_back = vec![0u64; rlwe_n];
1739// decrypt_rlwe(
1740// &rlwe_ct,
1741// ideal_client_key.sk_rlwe().values(),
1742// &mut m_back,
1743// rlwe_nttop,
1744// rlwe_modop,
1745// );
1746
1747// rlwe_modop.elwise_sub_mut(m_back.as_mut_slice(),
1748// m.as_slice());
1749
1750// check.add_more(Vec::<i64>::try_convert_from(&m_back,
1751// rlwe_q).as_slice()); }
1752
1753// println!("Public key Std: {}", check.std_dev().abs().log2());
1754// }
1755
1756// if true {
1757// // Generate server key shares
1758// let mut rng = DefaultSecureRng::new();
1759// let mut pk_cr_seed = [0u8; 32];
1760// rng.fill_bytes(&mut pk_cr_seed);
1761// let public_key_share = parties
1762// .iter()
1763// .map(|k|
1764// bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1765// .collect_vec(); let collective_pk = PublicKey::<
1766// Vec<Vec<u64>>,
1767// DefaultSecureRng,
1768// ModularOpsU64<CiphertextModulus<u64>>,
1769// >::from(public_key_share.as_slice());
1770
1771// let pbs_cr_seed = [0u8; 32];
1772// rng.fill_bytes(&mut pk_cr_seed);
1773// let server_key_shares = parties
1774// .iter()
1775// .map(|k| {
1776// bool_evaluator.multi_party_server_key_share(pbs_cr_seed,
1777// collective_pk.key(), k) })
1778// .collect_vec();
1779
1780// let seeded_server_key =
1781//
1782// bool_evaluator.aggregate_multi_party_server_key_shares(&server_key_shares);
1783
1784// // Check noise in RGSW ciphertexts of ideal LWE secret elements
1785// if false {
1786// let mut check = Stats { samples: vec![] };
1787// izip!(
1788// ideal_client_key.sk_lwe().values.iter(),
1789// seeded_server_key.rgsw_cts().iter()
1790// )
1791// .for_each(|(s_i, rgsw_ct_i)| {
1792// // X^{s[i]}
1793// let mut m_si = vec![0u64; rlwe_n];
1794// let s_i = *s_i *
1795// (bool_evaluator.pbs_info.embedding_factor as i32); if s_i
1796// < 0 { m_si[rlwe_n - (s_i.abs() as usize)] =
1797// rlwe_q.neg_one(); } else {
1798// m_si[s_i as usize] = 1;
1799// }
1800
1801// // RLWE'(-sm)
1802// let mut neg_s_eval =
1803//
1804// Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
1805// rlwe_modop.elwise_neg_mut(&mut neg_s_eval);
1806// rlwe_nttop.forward(&mut neg_s_eval);
1807// for j in
1808// 0..rlwe_rgsw_decomposer.a().decomposition_count() {
1809// // RLWE(B^{j} * -s[X]*X^{s_lwe[i]})
1810
1811// // -s[X]*X^{s_lwe[i]}*B_j
1812// let mut m_ideal = m_si.clone();
1813// rlwe_nttop.forward(m_ideal.as_mut_slice());
1814// rlwe_modop.elwise_mul_mut(m_ideal.as_mut_slice(),
1815// neg_s_eval.as_slice());
1816// rlwe_nttop.backward(m_ideal.as_mut_slice());
1817// rlwe_modop
1818// .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_rgsw_gadget_a[j]);
1819
1820// // RLWE(-s*X^{s_lwe[i]}*B_j)
1821// let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
1822// rlwe_ct[0].copy_from_slice(&rgsw_ct_i[j]);
1823// rlwe_ct[1].copy_from_slice(
1824// &rgsw_ct_i[j +
1825// rlwe_rgsw_decomposer.a().decomposition_count()], );
1826
1827// let mut m_back = vec![0u64; rlwe_n];
1828// decrypt_rlwe(
1829// &rlwe_ct,
1830// ideal_client_key.sk_rlwe().values(),
1831// &mut m_back,
1832// rlwe_nttop,
1833// rlwe_modop,
1834// );
1835
1836// // diff
1837// rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
1838// check.add_more(&Vec::<i64>::try_convert_from(&m_back,
1839// rlwe_q)); }
1840
1841// // RLWE'(m)
1842// for j in
1843// 0..rlwe_rgsw_decomposer.b().decomposition_count() {
1844// // RLWE(B^{j} * X^{s_lwe[i]})
1845
1846// // X^{s_lwe[i]}*B_j
1847// let mut m_ideal = m_si.clone();
1848// rlwe_modop
1849// .elwise_scalar_mul_mut(m_ideal.as_mut_slice(),
1850// &rlwe_rgsw_gadget_b[j]);
1851
1852// // RLWE(X^{s_lwe[i]}*B_j)
1853// let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
1854// rlwe_ct[0].copy_from_slice(
1855// &rgsw_ct_i[j + (2 *
1856// rlwe_rgsw_decomposer.a().decomposition_count())], );
1857// rlwe_ct[1].copy_from_slice(
1858// &rgsw_ct_i[j
1859// + (2 * rlwe_rgsw_decomposer.a().
1860// decomposition_count()
1861// + rlwe_rgsw_decomposer.b().
1862// decomposition_count())],
1863// );
1864
1865// let mut m_back = vec![0u64; rlwe_n];
1866// decrypt_rlwe(
1867// &rlwe_ct,
1868// ideal_client_key.sk_rlwe().values(),
1869// &mut m_back,
1870// rlwe_nttop,
1871// rlwe_modop,
1872// );
1873
1874// // diff
1875// rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
1876// check.add_more(&Vec::<i64>::try_convert_from(&m_back,
1877// rlwe_q)); }
1878// });
1879// println!(
1880// "RGSW Std: {} {} ;; max={}",
1881// check.mean(),
1882// check.std_dev().abs().log2(),
1883// check.samples.iter().max().unwrap()
1884// );
1885// }
1886
1887// // server key in Evaluation domain
1888// let server_key_eval_domain =
1889// ServerKeyEvaluationDomain::<_, DefaultSecureRng,
1890// NttBackendU64>::from( &seeded_server_key,
1891// );
1892
1893// // check noise in RLWE x RGSW(X^{s_i}) where RGSW is accunulated
1894// RGSW ciphertext if false {
1895// let mut check = Stats { samples: vec![] };
1896
1897// izip!(
1898// ideal_client_key.sk_lwe().values(),
1899// server_key_eval_domain.rgsw_cts().iter()
1900// )
1901// .for_each(|(s_i, rgsw_ct_i)| {
1902// let mut m = vec![0u64; rlwe_n];
1903// RandomFillUniformInModulus::random_fill(&mut rng, rlwe_q,
1904// m.as_mut_slice()); let mut rlwe_ct = vec![vec![0u64;
1905// rlwe_n]; 2]; public_key_encrypt_rlwe::<_, _, _, _, i32,
1906// _>( &mut rlwe_ct,
1907// collective_pk.key(),
1908// &m,
1909// rlwe_modop,
1910// rlwe_nttop,
1911// &mut rng,
1912// );
1913
1914// // RLWE(m*X^{s[i]}) = RLWE(m) x RGSW(X^{s[i]})
1915// // let mut rlwe_after = RlweCiphertext::<_,
1916// DefaultSecureRng>::new_trivial(vec![ // vec![0u64;
1917// rlwe_n], // m.clone(),
1918// // ]);
1919// let mut rlwe_after = RlweCiphertext::<_,
1920// DefaultSecureRng> { data: rlwe_ct.clone(),
1921// is_trivial: false,
1922// _phatom: PhantomData,
1923// };
1924// let mut scratch = vec![
1925// vec![0u64; rlwe_n];
1926// std::cmp::max(
1927// rlwe_rgsw_decomposer.0.decomposition_count(),
1928// rlwe_rgsw_decomposer.1.decomposition_count()
1929// ) + 2
1930// ];
1931// rlwe_by_rgsw(
1932// &mut rlwe_after,
1933// rgsw_ct_i,
1934// &mut scratch,
1935// rlwe_rgsw_decomposer,
1936// rlwe_nttop,
1937// rlwe_modop,
1938// );
1939
1940// // m1 = X^{s[i]}
1941// let mut m1 = vec![0u64; rlwe_n];
1942// let s_i = *s_i *
1943// (bool_evaluator.pbs_info.embedding_factor as i32); if s_i
1944// < 0 { m1[rlwe_n - (s_i.abs() as usize)] =
1945// rlwe_q.neg_one() } else {
1946// m1[s_i as usize] = 1;
1947// }
1948
1949// // (m+e) * m1
1950// let mut m_plus_e_times_m1 = vec![0u64; rlwe_n];
1951// decrypt_rlwe(
1952// &rlwe_ct,
1953// ideal_client_key.sk_rlwe().values(),
1954// &mut m_plus_e_times_m1,
1955// rlwe_nttop,
1956// rlwe_modop,
1957// );
1958// rlwe_nttop.forward(m_plus_e_times_m1.as_mut_slice());
1959// rlwe_nttop.forward(m1.as_mut_slice());
1960//
1961// rlwe_modop.elwise_mul_mut(m_plus_e_times_m1.as_mut_slice(), m1.as_slice());
1962// rlwe_nttop.backward(m_plus_e_times_m1.as_mut_slice());
1963
1964// // Resulting RLWE ciphertext will equal: (m0m1 + em1) +
1965// e_{rlsw x rgsw}. // Hence, resulting rlwe ciphertext will
1966// have error em1 + e_{rlwe x rgsw}. // Here we're only
1967// concerned with e_{rlwe x rgsw}, that is noise added by //
1968// RLWExRGSW. Also note in practice m1 is a monomial, for ex, X^{s_{i}}, for
1969// // some i and var(em1) = var(e).
1970// let mut m_plus_e_times_m1_more_e = vec![0u64; rlwe_n];
1971// decrypt_rlwe(
1972// &rlwe_after,
1973// ideal_client_key.sk_rlwe().values(),
1974// &mut m_plus_e_times_m1_more_e,
1975// rlwe_nttop,
1976// rlwe_modop,
1977// );
1978
1979// // diff
1980// rlwe_modop.elwise_sub_mut(
1981// m_plus_e_times_m1_more_e.as_mut_slice(),
1982// m_plus_e_times_m1.as_slice(),
1983// );
1984
1985// // let noise = measure_noise(
1986// // &rlwe_after,
1987// // &m_plus_e_times_m1,
1988// // rlwe_nttop,
1989// // rlwe_modop,
1990// // ideal_client_key.sk_rlwe.values(),
1991// // );
1992// // print!("NOISE: {}", noise);
1993
1994// check.add_more(&Vec::<i64>::try_convert_from(
1995// &m_plus_e_times_m1_more_e,
1996// rlwe_q,
1997// ));
1998// });
1999// println!(
2000// "RLWE x RGSW, where RGSW has noise var_brk, std: {} {}",
2001// check.std_dev(),
2002// check.std_dev().abs().log2()
2003// )
2004// }
2005
2006// // check noise in Auto key
2007// if false {
2008// let mut check = Stats { samples: vec![] };
2009
2010// let mut neg_s_poly =
2011//
2012// Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe().values(), rlwe_q);
2013// rlwe_modop.elwise_neg_mut(neg_s_poly.as_mut_slice());
2014
2015// let g = bool_evaluator.pbs_info.g();
2016// let br_q = bool_evaluator.pbs_info.br_q();
2017// let auto_element_dlogs =
2018// bool_evaluator.pbs_info.parameters.auto_element_dlogs(); for
2019// i in auto_element_dlogs.into_iter() { let g_pow = if i ==
2020// 0 { -g
2021// } else {
2022// (((g as usize).pow(i as u32)) % br_q) as isize
2023// };
2024
2025// // -s[X^k]
2026// let (auto_indices, auto_sign) = generate_auto_map(rlwe_n,
2027// g_pow); let mut neg_s_poly_auto_i = vec![0u64; rlwe_n];
2028// izip!(neg_s_poly.iter(), auto_indices.iter(),
2029// auto_sign.iter()).for_each( |(v, to_i, to_sign)| {
2030// if !to_sign {
2031// neg_s_poly_auto_i[*to_i] = rlwe_modop.neg(v);
2032// } else {
2033// neg_s_poly_auto_i[*to_i] = *v;
2034// }
2035// },
2036// );
2037
2038// let mut auto_key_i =
2039// server_key_eval_domain.galois_key_for_auto(i).clone(); //
2040// send i^th auto key to coefficient domain auto_key_i
2041// .iter_mut()
2042// .for_each(|r| rlwe_nttop.backward(r.as_mut_slice()));
2043// auto_gadget.iter().enumerate().for_each(|(i, b_i)| {
2044// // B^i * -s[X^k]
2045// let mut m_ideal = neg_s_poly_auto_i.clone();
2046//
2047// rlwe_modop.elwise_scalar_mul_mut(m_ideal.as_mut_slice(), b_i);
2048
2049// let mut m_out = vec![0u64; rlwe_n];
2050// let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2051// rlwe_ct[0].copy_from_slice(&auto_key_i[i]);
2052// rlwe_ct[1].copy_from_slice(
2053// &auto_key_i[auto_decomposer.decomposition_count()
2054// + i], ); decrypt_rlwe( &rlwe_ct,
2055// ideal_client_key.sk_rlwe().values(), &mut m_out, rlwe_nttop, rlwe_modop, );
2056
2057// // diff
2058// rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(),
2059// m_ideal.as_slice());
2060
2061// check.add_more(&Vec::<i64>::try_convert_from(&m_out,
2062// rlwe_q)); });
2063// }
2064
2065// println!("Auto key noise std dev: {}",
2066// check.std_dev().abs().log2()); }
2067
2068// // check noise in RLWE(X^k) after sending RLWE(X) -> RLWE(X^k)
2069// using collective // auto key
2070// if true {
2071// let mut check = Stats { samples: vec![] };
2072// let br_q = bool_evaluator.pbs_info.br_q();
2073// let g = bool_evaluator.pbs_info.g();
2074// let auto_element_dlogs =
2075// bool_evaluator.pbs_info.parameters.auto_element_dlogs(); for
2076// i in auto_element_dlogs.into_iter() { for _ in 0..10 {
2077// let mut m = vec![0u64; rlwe_n];
2078// RandomFillUniformInModulus::random_fill(&mut rng,
2079// rlwe_q, m.as_mut_slice()); let mut rlwe_ct =
2080// RlweCiphertext::<_, DefaultSecureRng> { data:
2081// vec![vec![0u64; rlwe_n]; 2], is_trivial: false,
2082// _phatom: PhantomData,
2083// };
2084// public_key_encrypt_rlwe::<_, _, _, _, i32, _>(
2085// &mut rlwe_ct,
2086// collective_pk.key(),
2087// &m,
2088// rlwe_modop,
2089// rlwe_nttop,
2090// &mut rng,
2091// );
2092
2093// // We're only interested in noise increased as a
2094// result of automorphism. // Hence, we take m+e as the
2095// bench. let mut m_plus_e = vec![0u64; rlwe_n];
2096// decrypt_rlwe(
2097// &rlwe_ct,
2098// ideal_client_key.sk_rlwe().values(),
2099// &mut m_plus_e,
2100// rlwe_nttop,
2101// rlwe_modop,
2102// );
2103
2104// let auto_key =
2105// server_key_eval_domain.galois_key_for_auto(i); let
2106// (auto_map_index, auto_map_sign) =
2107// bool_evaluator.pbs_info.rlwe_auto_map(i); let mut
2108// scratch = vec![vec![0u64; rlwe_n];
2109// auto_decomposer.decomposition_count() + 2];
2110// galois_auto( &mut rlwe_ct,
2111// auto_key,
2112// &mut scratch,
2113// &auto_map_index,
2114// &auto_map_sign,
2115// rlwe_modop,
2116// rlwe_nttop,
2117// auto_decomposer,
2118// );
2119
2120// // send m+e from X to X^k
2121// let mut m_plus_e_auto = vec![0u64; rlwe_n];
2122// izip!(m_plus_e.iter(), auto_map_index.iter(),
2123// auto_map_sign.iter()) .for_each(|(v, to_index,
2124// to_sign)| { if !to_sign {
2125// m_plus_e_auto[*to_index] =
2126// rlwe_modop.neg(v); } else {
2127// m_plus_e_auto[*to_index] = *v
2128// }
2129// });
2130
2131// let mut m_out = vec![0u64; rlwe_n];
2132// decrypt_rlwe(
2133// &rlwe_ct,
2134// ideal_client_key.sk_rlwe().values(),
2135// &mut m_out,
2136// rlwe_nttop,
2137// rlwe_modop,
2138// );
2139
2140// // diff
2141// rlwe_modop.elwise_sub_mut(m_out.as_mut_slice(),
2142// m_plus_e_auto.as_slice());
2143
2144//
2145// check.add_more(&Vec::<i64>::try_convert_from(m_out.as_slice(), rlwe_q));
2146// }
2147// }
2148
2149// println!("Rlwe Auto Noise Std: {}",
2150// check.std_dev().abs().log2()); }
2151
2152// // Check noise growth in ksk
2153// // TODO check in LWE key switching keys
2154// if true {
2155// // 1. encrypt LWE ciphertext
2156// // 2. Key switching
2157// // 3.
2158// let mut check = Stats { samples: vec![] };
2159
2160// for _ in 0..1024 {
2161// // Encrypt m \in Q_{ks} using RLWE sk
2162// let mut lwe_in_ct = vec![0u64; rlwe_n + 1];
2163// let m = RandomElementInModulus::random(&mut rng,
2164// &lwe_q.q().unwrap()); encrypt_lwe(
2165// &mut lwe_in_ct,
2166// &m,
2167// ideal_client_key.sk_rlwe().values(),
2168// lwe_modop,
2169// &mut rng,
2170// );
2171
2172// // Key switch
2173// let mut lwe_out = vec![0u64; lwe_n + 1];
2174// lwe_key_switch(
2175// &mut lwe_out,
2176// &lwe_in_ct,
2177// server_key_eval_domain.lwe_ksk(),
2178// lwe_modop,
2179// bool_evaluator.pbs_info.lwe_decomposer(),
2180// );
2181
2182// // We only care about noise added by LWE key switch
2183// // m+e
2184// let m_plus_e =
2185// decrypt_lwe(&lwe_in_ct,
2186// ideal_client_key.sk_rlwe().values(), lwe_modop);
2187
2188// let m_plus_e_plus_lwe_ksk_noise =
2189// decrypt_lwe(&lwe_out,
2190// ideal_client_key.sk_lwe().values(), lwe_modop);
2191
2192// let diff = lwe_modop.sub(&m_plus_e_plus_lwe_ksk_noise,
2193// &m_plus_e);
2194
2195// check.add_more(&vec![lwe_q.map_element_to_i64(&diff)]);
2196// }
2197
2198// println!("Lwe ksk std dev: {}",
2199// check.std_dev().abs().log2()); }
2200// }
2201
2202// // Check noise in fresh RGSW ciphertexts, ie X^{s_j[i]}, must equal
2203// noise in // fresh RLWE ciphertext
2204// if true {}
2205// // test LWE ksk from RLWE -> LWE
2206// // if false {
2207// // let logp = 2;
2208// // let mut rng = DefaultSecureRng::new();
2209
2210// // let m = 1;
2211// // let encoded_m = m << (lwe_logq - logp);
2212
2213// // // Encrypt
2214// // let mut lwe_ct = vec![0u64; rlwe_n + 1];
2215// // encrypt_lwe(
2216// // &mut lwe_ct,
2217// // &encoded_m,
2218// // ideal_client_key.sk_rlwe.values(),
2219// // lwe_modop,
2220// // &mut rng,
2221// // );
2222
2223// // // key switch
2224// // let lwe_decomposer = &bool_evaluator.decomposer_lwe;
2225// // let mut lwe_out = vec![0u64; lwe_n + 1];
2226// // lwe_key_switch(
2227// // &mut lwe_out,
2228// // &lwe_ct,
2229// // &server_key_eval.lwe_ksk,
2230// // lwe_modop,
2231// // lwe_decomposer,
2232// // );
2233
2234// // let encoded_m_back = decrypt_lwe(&lwe_out,
2235// // ideal_client_key.sk_lwe.values(), lwe_modop); let m_back
2236// // = ((encoded_m_back as f64 * (1 << logp) as f64) /
2237// // (lwe_q as f64)).round() as u64; dbg!(m_back, m);
2238
2239// // let noise = measure_noise_lwe(
2240// // &lwe_out,
2241// // ideal_client_key.sk_lwe.values(),
2242// // lwe_modop,
2243// // &encoded_m,
2244// // );
2245
2246// // println!("Noise: {noise}");
2247// // }
2248
2249// // Measure noise in RGSW ciphertexts of ideal LWE secrets
2250// // if true {
2251// // let gadget_vec = gadget_vector(
2252// // bool_evaluator.parameters.rlwe_logq,
2253// // bool_evaluator.parameters.logb_rgsw,
2254// // bool_evaluator.parameters.d_rgsw,
2255// // );
2256
2257// // for i in 0..20 {
2258// // // measure noise in RGSW(s[i])
2259// // let si =
2260// // ideal_client_key.sk_lwe.values[i] *
2261// // (bool_evaluator.embedding_factor as i32); let mut
2262// // si_poly = vec![0u64; rlwe_n]; if si < 0 {
2263// // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2264// // } else {
2265// // si_poly[(si.abs() as usize)] = 1;
2266// // }
2267
2268// // let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
2269// // rgsw_si
2270// // .iter_mut()
2271// // .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
2272
2273// // println!("####### Noise in RGSW(X^s_{i}) #######");
2274// // _measure_noise_rgsw(
2275// // &rgsw_si,
2276// // &si_poly,
2277// // ideal_client_key.sk_rlwe.values(),
2278// // &gadget_vec,
2279// // rlwe_q,
2280// // );
2281// // println!("####### ##################### #######");
2282// // }
2283// // }
2284
2285// // // measure noise grwoth in RLWExRGSW
2286// // if true {
2287// // let mut rng = DefaultSecureRng::new();
2288// // let mut carry_m = vec![0u64; rlwe_n];
2289// // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
2290// // carry_m.as_mut_slice());
2291
2292// // // RGSW(carrym)
2293// // let trivial_rlwect = vec![vec![0u64; rlwe_n],
2294// carry_m.clone()]; // let mut rlwe_ct = RlweCiphertext::<_,
2295// // DefaultSecureRng>::from_raw(trivial_rlwect, true);
2296
2297// // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
2298// // d_rgsw + 2]; let mul_mod =
2299// // |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) %
2300// (rlwe_q as u128)) as u64);
2301
2302// // for i in 0..bool_evaluator.parameters.lwe_n {
2303// // rlwe_by_rgsw(
2304// // &mut rlwe_ct,
2305// // server_key_eval.rgsw_ct_lwe_si(i),
2306// // &mut scratch_matrix_dplus2_ring,
2307// // rlwe_decomposer,
2308// // rlwe_nttop,
2309// // rlwe_modop,
2310// // );
2311
2312// // // carry_m[X] * s_i[X]
2313// // let si =
2314// // ideal_client_key.sk_lwe.values[i] *
2315// // (bool_evaluator.embedding_factor as i32); let mut
2316// // si_poly = vec![0u64; rlwe_n]; if si < 0 {
2317// // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2318// // } else {
2319// // si_poly[(si.abs() as usize)] = 1;
2320// // }
2321// // carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod,
2322// // rlwe_q);
2323
2324// // let noise = measure_noise(
2325// // &rlwe_ct,
2326// // &carry_m,
2327// // rlwe_nttop,
2328// // rlwe_modop,
2329// // ideal_client_key.sk_rlwe.values(),
2330// // );
2331// // println!("Noise RLWE(carry_m) accumulating {i}^th secret
2332// // monomial: {noise}"); }
2333// // }
2334
2335// // // Check galois keys
2336// // if false {
2337// // let g = bool_evaluator.g() as isize;
2338// // let mut rng = DefaultSecureRng::new();
2339// // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
2340// // d_rgsw + 2]; for i in [g, -g] {
2341// // let mut m = vec![0u64; rlwe_n];
2342// // RandomUniformDist1::random_fill(&mut rng, &rlwe_q,
2343// // m.as_mut_slice()); let mut rlwe_ct = {
2344// // let mut data = vec![vec![0u64; rlwe_n]; 2];
2345// // public_key_encrypt_rlwe(
2346// // &mut data,
2347// // &collective_pk.key,
2348// // &m,
2349// // rlwe_modop,
2350// // rlwe_nttop,
2351// // &mut rng,
2352// // );
2353// // RlweCiphertext::<_, DefaultSecureRng>::from_raw(data,
2354// // false) };
2355
2356// // let auto_key = server_key_eval.galois_key_for_auto(i);
2357// // let (auto_map_index, auto_map_sign) =
2358// // generate_auto_map(rlwe_n, i); galois_auto(
2359// // &mut rlwe_ct,
2360// // auto_key,
2361// // &mut scratch_matrix_dplus2_ring,
2362// // &auto_map_index,
2363// // &auto_map_sign,
2364// // rlwe_modop,
2365// // rlwe_nttop,
2366// // rlwe_decomposer,
2367// // );
2368
2369// // // send m(X) -> m(X^i)
2370// // let mut m_k = vec![0u64; rlwe_n];
2371// // izip!(m.iter(), auto_map_index.iter(),
2372// // auto_map_sign.iter()).for_each( |(mi, to_index,
2373// to_sign)| // { if !to_sign {
2374// // m_k[*to_index] = rlwe_q - *mi;
2375// // } else {
2376// // m_k[*to_index] = *mi;
2377// // }
2378// // },
2379// // );
2380
2381// // // measure noise
2382// // let noise = measure_noise(
2383// // &rlwe_ct,
2384// // &m_k,
2385// // rlwe_nttop,
2386// // rlwe_modop,
2387// // ideal_client_key.sk_rlwe.values(),
2388// // );
2389
2390// // println!("Noise after auto k={i}: {noise}");
2391// // }
2392// // }
2393// }
2394// }