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