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