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