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