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