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::{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 = self.decomposer_rlwe.gadget_vector();
719
720 // generate auto keys -g, g
721 let mut auto_keys = HashMap::new();
722 let g = self.parameters.g as isize;
723 for i in [g, -g] {
724 let mut gk = M::zeros(self.parameters.d_rgsw, self.parameters.rlwe_n);
725 galois_key_gen(
726 &mut gk,
727 sk_rlwe.values(),
728 i,
729 &d_rgsw_gadget_vec,
730 &self.rlwe_modop,
731 &self.rlwe_nttop,
732 &mut main_prng,
733 rng,
734 );
735 auto_keys.insert(i, gk);
736 }
737
738 // generate rgsw ciphertexts RGSW(si) where si is i^th LWE secret element
739 let ring_size = self.parameters.rlwe_n;
740 let rlwe_q = self.parameters.rlwe_q;
741 let rgsw_cts = sk_lwe
742 .values()
743 .iter()
744 .map(|si| {
745 // X^{si}; assume |emebedding_factor * si| < N
746 let mut m = M::R::zeros(ring_size);
747 let si = (self.embedding_factor as i32) * si;
748 // dbg!(si);
749 if si < 0 {
750 // X^{-i} = X^{2N - i} = -X^{N-i}
751 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q - M::MatElement::one();
752 } else {
753 // X^{i}
754 m.as_mut()[si.abs() as usize] = M::MatElement::one();
755 }
756
757 let mut rgsw_si = M::zeros(self.parameters.d_rgsw * 3, ring_size);
758 secret_key_encrypt_rgsw(
759 &mut rgsw_si,
760 m.as_ref(),
761 &d_rgsw_gadget_vec,
762 sk_rlwe.values(),
763 &self.rlwe_modop,
764 &self.rlwe_nttop,
765 &mut main_prng,
766 rng,
767 );
768
769 rgsw_si
770 })
771 .collect_vec();
772
773 // LWE KSK from RLWE secret s -> LWE secret z
774 let d_lwe_gadget = self.decomposer_lwe.gadget_vector();
775
776 let mut lwe_ksk = M::R::zeros(self.parameters.d_lwe * ring_size);
777 lwe_ksk_keygen(
778 &sk_rlwe.values(),
779 &sk_lwe.values(),
780 &mut lwe_ksk,
781 &d_lwe_gadget,
782 &self.lwe_modop,
783 &mut main_prng,
784 rng,
785 );
786
787 SeededServerKey::from_raw(
788 auto_keys,
789 rgsw_cts,
790 lwe_ksk,
791 self.parameters.clone(),
792 main_seed,
793 )
794 })
795 }
796
797 fn multi_party_sever_key_share(
798 &self,
799 cr_seed: [u8; 32],
800 collective_pk: &M,
801 client_key: &ClientKey,
802 ) -> CommonReferenceSeededMultiPartyServerKeyShare<M, BoolParameters<M::MatElement>, [u8; 32]>
803 {
804 DefaultSecureRng::with_local_mut(|rng| {
805 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
806
807 let sk_rlwe = &client_key.sk_rlwe;
808 let sk_lwe = &client_key.sk_lwe;
809
810 let g = self.parameters.g as isize;
811 let ring_size = self.parameters.rlwe_n;
812 let d_rgsw = self.parameters.d_rgsw;
813 let d_lwe = self.parameters.d_lwe;
814 let rlwe_q = self.parameters.rlwe_q;
815 let lwe_q = self.parameters.lwe_q;
816
817 let d_rgsw_gadget_vec = self.decomposer_rlwe.gadget_vector();
818
819 let rlweq_modop = ModOp::new(rlwe_q);
820 let rlweq_nttop = NttOp::new(rlwe_q, ring_size);
821
822 // sanity check
823 assert!(sk_rlwe.values().len() == ring_size);
824 assert!(sk_lwe.values().len() == self.parameters.lwe_n);
825
826 // auto keys
827 let mut auto_keys = HashMap::new();
828 for i in [g, -g] {
829 let mut ksk_out = M::zeros(d_rgsw, ring_size);
830 galois_key_gen(
831 &mut ksk_out,
832 sk_rlwe.values(),
833 i,
834 &d_rgsw_gadget_vec,
835 &rlweq_modop,
836 &rlweq_nttop,
837 &mut main_prng,
838 rng,
839 );
840 auto_keys.insert(i, ksk_out);
841 }
842
843 // rgsw ciphertexts of lwe secret elements
844 let rgsw_cts = sk_lwe
845 .values()
846 .iter()
847 .map(|si| {
848 let mut m = M::R::zeros(ring_size);
849 //TODO(Jay): It will be nice to have a function that returns polynomial
850 // (monomial infact!) corresponding to secret element embedded in ring X^{2N+1}.
851 // Save lots of mistakes where one forgest to emebed si in bigger ring.
852 let si = *si * (self.embedding_factor as i32);
853 if si < 0 {
854 // X^{-si} = X^{2N-si} = -X^{N-si}, assuming abs(si) < N
855 // (which it is given si is secret element)
856 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q - M::MatElement::one();
857 } else {
858 m.as_mut()[si as usize] = M::MatElement::one();
859 }
860
861 // public key RGSW encryption has no part that can be seeded, unlike secret key
862 // RGSW encryption where RLWE'_A(m) is seeded
863 let mut out_rgsw = M::zeros(d_rgsw * 4, ring_size);
864 public_key_encrypt_rgsw(
865 &mut out_rgsw,
866 &m.as_ref(),
867 collective_pk,
868 &d_rgsw_gadget_vec,
869 &rlweq_modop,
870 &rlweq_nttop,
871 rng,
872 );
873
874 out_rgsw
875 })
876 .collect_vec();
877
878 // LWE ksk
879 let mut lwe_ksk = M::R::zeros(d_lwe * ring_size);
880 let lwe_modop = ModOp::new(lwe_q);
881 let d_lwe_gadget_vec = self.decomposer_lwe.gadget_vector();
882 lwe_ksk_keygen(
883 sk_rlwe.values(),
884 sk_lwe.values(),
885 &mut lwe_ksk,
886 &d_lwe_gadget_vec,
887 &lwe_modop,
888 &mut main_prng,
889 rng,
890 );
891
892 CommonReferenceSeededMultiPartyServerKeyShare {
893 auto_keys,
894 rgsw_cts,
895 lwe_ksk,
896 cr_seed,
897 parameters: self.parameters.clone(),
898 }
899 })
900 }
901
902 fn multi_party_public_key_share(
903 &self,
904 cr_seed: [u8; 32],
905 client_key: &ClientKey,
906 ) -> CommonReferenceSeededCollectivePublicKeyShare<
907 <M as Matrix>::R,
908 [u8; 32],
909 BoolParameters<<M as Matrix>::MatElement>,
910 > {
911 DefaultSecureRng::with_local_mut(|rng| {
912 let mut share_out = M::R::zeros(self.parameters.rlwe_n);
913 let modop = ModOp::new(self.parameters.rlwe_q);
914 let nttop = NttOp::new(self.parameters.rlwe_q, self.parameters.rlwe_n);
915 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
916 public_key_share(
917 &mut share_out,
918 client_key.sk_rlwe.values(),
919 &modop,
920 &nttop,
921 &mut main_prng,
922 rng,
923 );
924
925 CommonReferenceSeededCollectivePublicKeyShare {
926 share: share_out,
927 cr_seed: cr_seed,
928 parameters: self.parameters.clone(),
929 }
930 })
931 }
932
933 fn multi_party_decryption_share(
934 &self,
935 lwe_ct: &M::R,
936 client_key: &ClientKey,
937 ) -> MultiPartyDecryptionShare<<M as Matrix>::MatElement> {
938 assert!(lwe_ct.as_ref().len() == self.parameters.rlwe_n + 1);
939 let modop = &self.rlwe_modop;
940 let mut neg_s =
941 M::R::try_convert_from(client_key.sk_rlwe.values(), &self.parameters.rlwe_q);
942 modop.elwise_neg_mut(neg_s.as_mut());
943
944 let mut neg_sa = M::MatElement::zero();
945 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
946 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
947 });
948
949 let e = DefaultSecureRng::with_local_mut(|rng| {
950 let mut e = M::MatElement::zero();
951 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, &mut e);
952 e
953 });
954 let share = modop.add(&neg_sa, &e);
955
956 MultiPartyDecryptionShare { share }
957 }
958
959 pub(crate) fn multi_party_decrypt(
960 &self,
961 shares: &[MultiPartyDecryptionShare<M::MatElement>],
962 lwe_ct: &M::R,
963 ) -> bool {
964 let modop = &self.rlwe_modop;
965 let mut sum_a = M::MatElement::zero();
966 shares
967 .iter()
968 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i.share));
969
970 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
971
972 let m = (((encoded_m + self.rlweq_by8).to_f64().unwrap() * 4f64)
973 / self.parameters.rlwe_q.to_f64().unwrap())
974 .round() as usize
975 % 4usize;
976
977 if m == 0 {
978 return false;
979 } else if m == 1 {
980 return true;
981 } else {
982 panic!("Bool decryption failure. Expected m to be either 1 or 0, but m={m} ");
983 }
984 }
985
986 /// First encrypt as RLWE(m) with m as constant polynomial and extract it as
987 /// LWE ciphertext
988 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
989 DefaultSecureRng::with_local_mut(|rng| {
990 let modop = &self.rlwe_modop;
991 let nttop = &self.rlwe_nttop;
992
993 // RLWE(0)
994 // sample ephemeral key u
995 let ring_size = self.parameters.rlwe_n;
996 let mut u = vec![0i32; ring_size];
997 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
998 let mut u = M::R::try_convert_from(&u, &self.parameters.rlwe_q);
999 nttop.forward(u.as_mut());
1000
1001 let mut ua = M::R::zeros(ring_size);
1002 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1003 let mut ub = M::R::zeros(ring_size);
1004 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1005
1006 // a*u
1007 nttop.forward(ua.as_mut());
1008 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
1009 nttop.backward(ua.as_mut());
1010
1011 // b*u
1012 nttop.forward(ub.as_mut());
1013 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
1014 nttop.backward(ub.as_mut());
1015
1016 let mut rlwe = M::zeros(2, ring_size);
1017 // sample error
1018 rlwe.iter_rows_mut().for_each(|ri| {
1019 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, ri.as_mut());
1020 });
1021
1022 // a*u + e0
1023 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
1024 // b*u + e1
1025 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
1026
1027 let m = if m {
1028 // Q/8
1029 self.rlweq_by8
1030 } else {
1031 // -Q/8
1032 self.parameters.rlwe_q - self.rlweq_by8
1033 };
1034
1035 // b*u + e1 + m, where m is constant polynomial
1036 rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
1037
1038 // sample extract index 0
1039 let mut lwe_out = M::R::zeros(ring_size + 1);
1040 sample_extract(&mut lwe_out, &rlwe, modop, 0);
1041
1042 lwe_out
1043 })
1044 }
1045
1046 /// TODO(Jay): Fetch client key from thread local
1047 pub fn sk_encrypt(&self, m: bool, client_key: &ClientKey) -> M::R {
1048 let m = if m {
1049 // Q/8
1050 self.rlweq_by8
1051 } else {
1052 // -Q/8
1053 self.parameters.rlwe_q - self.rlweq_by8
1054 };
1055
1056 DefaultSecureRng::with_local_mut(|rng| {
1057 let mut lwe_out = M::R::zeros(self.parameters.rlwe_n + 1);
1058 encrypt_lwe(
1059 &mut lwe_out,
1060 &m,
1061 client_key.sk_rlwe.values(),
1062 &self.rlwe_modop,
1063 rng,
1064 );
1065 lwe_out
1066 })
1067 }
1068
1069 pub fn sk_decrypt(&self, lwe_ct: &M::R, client_key: &ClientKey) -> bool {
1070 let m = decrypt_lwe(lwe_ct, client_key.sk_rlwe.values(), &self.rlwe_modop);
1071 let m = {
1072 // m + q/8 => {0,q/4 1}
1073 (((m + self.rlweq_by8).to_f64().unwrap() * 4.0)
1074 / self.parameters.rlwe_q.to_f64().unwrap())
1075 .round()
1076 .to_usize()
1077 .unwrap()
1078 % 4
1079 };
1080
1081 if m == 0 {
1082 false
1083 } else if m == 1 {
1084 true
1085 } else {
1086 panic!("Incorrect bool decryption. Got m={m} but expected m to be 0 or 1")
1087 }
1088 }
1089
1090 // TODO(Jay): scratch spaces must be thread local. Don't pass them as arguments
1091 pub fn nand(
1092 &self,
1093 c0: &M::R,
1094 c1: &M::R,
1095 server_key: &ServerKeyEvaluationDomain<M, DefaultSecureRng, NttOp>,
1096 scratch_lwen_plus1: &mut M::R,
1097 scratch_matrix_dplus2_ring: &mut M,
1098 ) -> M::R {
1099 // ClientKey::with_local(|ck| {
1100 // let c0_noise = measure_noise_lwe(
1101 // c0,
1102 // ck.sk_rlwe.values(),
1103 // &self.rlwe_modop,
1104 // &(self.rlwe_q() - self.rlweq_by8),
1105 // );
1106 // let c1_noise =
1107 // measure_noise_lwe(c1, ck.sk_rlwe.values(), &self.rlwe_modop,
1108 // &(self.rlweq_by8)); println!(
1109 // "c0 noise: {c0_noise}; c1 noise:
1110 // {c1_noise}"
1111 // );
1112 // });
1113
1114 let mut c_out = M::R::zeros(c0.as_ref().len());
1115 let modop = &self.rlwe_modop;
1116 izip!(
1117 c_out.as_mut().iter_mut(),
1118 c0.as_ref().iter(),
1119 c1.as_ref().iter()
1120 )
1121 .for_each(|(o, i0, i1)| {
1122 *o = modop.add(i0, i1);
1123 });
1124 // +Q/8
1125 c_out.as_mut()[0] = modop.add(&c_out.as_ref()[0], &self.rlwe_qby4);
1126
1127 // ClientKey::with_local(|ck| {
1128 // let noise = measure_noise_lwe(
1129 // &c_out,
1130 // ck.sk_rlwe.values(),
1131 // &self.rlwe_modop,
1132 // &(self.rlweq_by8),
1133 // );
1134 // println!("cout_noise: {noise}");
1135 // });
1136
1137 // PBS
1138 pbs(
1139 self,
1140 &self.nand_test_vec,
1141 &mut c_out,
1142 scratch_lwen_plus1,
1143 scratch_matrix_dplus2_ring,
1144 &self.lwe_modop,
1145 &self.rlwe_modop,
1146 &self.rlwe_nttop,
1147 server_key,
1148 );
1149
1150 c_out
1151 }
1152}
1153
1154impl<M: Matrix, NttOp, ModOp> PbsParameters for BoolEvaluator<M, M::MatElement, NttOp, ModOp>
1155where
1156 M::MatElement: PrimInt + WrappingSub + Debug,
1157{
1158 type Element = M::MatElement;
1159 type D = DefaultDecomposer<M::MatElement>;
1160 fn rlwe_auto_map(&self, k: isize) -> &(Vec<usize>, Vec<bool>) {
1161 let g = self.parameters.g as isize;
1162 if k == g {
1163 &self.rlwe_auto_maps[0]
1164 } else if k == -g {
1165 &self.rlwe_auto_maps[1]
1166 } else {
1167 panic!("RLWE auto map only supports k in [-g, g], but got k={k}");
1168 }
1169 }
1170
1171 fn br_q(&self) -> usize {
1172 self.parameters.br_q
1173 }
1174 fn d_lwe(&self) -> usize {
1175 self.parameters.d_lwe
1176 }
1177 fn d_rgsw(&self) -> usize {
1178 self.parameters.d_rgsw
1179 }
1180 fn decomoposer_lwe(&self) -> &Self::D {
1181 &self.decomposer_lwe
1182 }
1183 fn decomoposer_rlwe(&self) -> &Self::D {
1184 &self.decomposer_rlwe
1185 }
1186 fn embedding_factor(&self) -> usize {
1187 self.embedding_factor
1188 }
1189 fn g(&self) -> isize {
1190 self.parameters.g as isize
1191 }
1192 fn g_k_dlog_map(&self) -> &[usize] {
1193 &self.g_k_dlog_map
1194 }
1195 fn lwe_n(&self) -> usize {
1196 self.parameters.lwe_n
1197 }
1198 fn lwe_q(&self) -> Self::Element {
1199 self.parameters.lwe_q
1200 }
1201 fn rlwe_n(&self) -> usize {
1202 self.parameters.rlwe_n
1203 }
1204 fn rlwe_q(&self) -> Self::Element {
1205 self.parameters.rlwe_q
1206 }
1207}
1208
1209/// LMKCY+ Blind rotation
1210///
1211/// gk_to_si: [-g^0, -g^1, .., -g^{q/2-1}, g^0, ..., g^{q/2-1}]
1212fn blind_rotation<
1213 MT: IsTrivial + MatrixMut,
1214 Mmut: MatrixMut<MatElement = MT::MatElement> + Matrix,
1215 D: Decomposer<Element = MT::MatElement>,
1216 NttOp: Ntt<Element = MT::MatElement>,
1217 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
1218 K: PbsKey<M = Mmut>,
1219 P: PbsParameters<Element = MT::MatElement>,
1220>(
1221 trivial_rlwe_test_poly: &mut MT,
1222 scratch_matrix_dplus2_ring: &mut Mmut,
1223 g: isize,
1224 w: usize,
1225 q: usize,
1226 gk_to_si: &[Vec<usize>],
1227 decomposer: &D,
1228 ntt_op: &NttOp,
1229 mod_op: &ModOp,
1230 parameters: &P,
1231 pbs_key: &K,
1232) where
1233 <Mmut as Matrix>::R: RowMut,
1234 Mmut::MatElement: Copy + Zero,
1235 <MT as Matrix>::R: RowMut,
1236{
1237 let q_by_2 = q / 2;
1238
1239 // -(g^k)
1240 for i in (1..q_by_2).rev() {
1241 gk_to_si[q_by_2 + i].iter().for_each(|s_index| {
1242 rlwe_by_rgsw(
1243 trivial_rlwe_test_poly,
1244 pbs_key.rgsw_ct_lwe_si(*s_index),
1245 scratch_matrix_dplus2_ring,
1246 decomposer,
1247 ntt_op,
1248 mod_op,
1249 );
1250 });
1251
1252 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1253 galois_auto(
1254 trivial_rlwe_test_poly,
1255 pbs_key.galois_key_for_auto(g),
1256 scratch_matrix_dplus2_ring,
1257 &auto_map_index,
1258 &auto_map_sign,
1259 mod_op,
1260 ntt_op,
1261 decomposer,
1262 );
1263 }
1264
1265 // -(g^0)
1266 gk_to_si[q_by_2].iter().for_each(|s_index| {
1267 rlwe_by_rgsw(
1268 trivial_rlwe_test_poly,
1269 pbs_key.rgsw_ct_lwe_si(*s_index),
1270 scratch_matrix_dplus2_ring,
1271 decomposer,
1272 ntt_op,
1273 mod_op,
1274 );
1275 });
1276 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(-g);
1277 galois_auto(
1278 trivial_rlwe_test_poly,
1279 pbs_key.galois_key_for_auto(-g),
1280 scratch_matrix_dplus2_ring,
1281 &auto_map_index,
1282 &auto_map_sign,
1283 mod_op,
1284 ntt_op,
1285 decomposer,
1286 );
1287
1288 // +(g^k)
1289 for i in (1..q_by_2).rev() {
1290 gk_to_si[i].iter().for_each(|s_index| {
1291 rlwe_by_rgsw(
1292 trivial_rlwe_test_poly,
1293 pbs_key.rgsw_ct_lwe_si(*s_index),
1294 scratch_matrix_dplus2_ring,
1295 decomposer,
1296 ntt_op,
1297 mod_op,
1298 );
1299 });
1300
1301 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1302 galois_auto(
1303 trivial_rlwe_test_poly,
1304 pbs_key.galois_key_for_auto(g),
1305 scratch_matrix_dplus2_ring,
1306 &auto_map_index,
1307 &auto_map_sign,
1308 mod_op,
1309 ntt_op,
1310 decomposer,
1311 );
1312 }
1313
1314 // +(g^0)
1315 gk_to_si[0].iter().for_each(|s_index| {
1316 rlwe_by_rgsw(
1317 trivial_rlwe_test_poly,
1318 pbs_key.rgsw_ct_lwe_si(gk_to_si[q_by_2][*s_index]),
1319 scratch_matrix_dplus2_ring,
1320 decomposer,
1321 ntt_op,
1322 mod_op,
1323 );
1324 });
1325}
1326
1327/// - Mod down
1328/// - key switching
1329/// - mod down
1330/// - blind rotate
1331fn pbs<
1332 M: Matrix + MatrixMut + MatrixEntity,
1333 P: PbsParameters<Element = M::MatElement>,
1334 NttOp: Ntt<Element = M::MatElement>,
1335 ModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
1336 K: PbsKey<M = M>,
1337>(
1338 parameters: &P,
1339 test_vec: &M::R,
1340 lwe_in: &mut M::R,
1341 scratch_lwen_plus1: &mut M::R,
1342 scratch_matrix_dplus2_ring: &mut M,
1343 modop_lweq: &ModOp,
1344 modop_rlweq: &ModOp,
1345 nttop_rlweq: &NttOp,
1346 pbs_key: &K,
1347) where
1348 <M as Matrix>::R: RowMut,
1349 M::MatElement: PrimInt + ToPrimitive + FromPrimitive + One + Copy + Zero + Display,
1350{
1351 let rlwe_q = parameters.rlwe_q();
1352 let lwe_q = parameters.lwe_q();
1353 let br_q = parameters.br_q();
1354 let rlwe_qf64 = rlwe_q.to_f64().unwrap();
1355 let lwe_qf64 = lwe_q.to_f64().unwrap();
1356 let br_qf64 = br_q.to_f64().unwrap();
1357 let rlwe_n = parameters.rlwe_n();
1358
1359 PBSTracer::with_local_mut(|t| {
1360 let out = lwe_in
1361 .as_ref()
1362 .iter()
1363 .map(|v| v.to_u64().unwrap())
1364 .collect_vec();
1365 t.ct_rlwe_q_mod = out;
1366 });
1367
1368 // moddown Q -> Q_ks
1369 lwe_in.as_mut().iter_mut().for_each(|v| {
1370 *v =
1371 M::MatElement::from_f64(((v.to_f64().unwrap() * lwe_qf64) / rlwe_qf64).round()).unwrap()
1372 });
1373
1374 PBSTracer::with_local_mut(|t| {
1375 let out = lwe_in
1376 .as_ref()
1377 .iter()
1378 .map(|v| v.to_u64().unwrap())
1379 .collect_vec();
1380 t.ct_lwe_q_mod = out;
1381 });
1382
1383 // key switch RLWE secret to LWE secret
1384 scratch_lwen_plus1.as_mut().fill(M::MatElement::zero());
1385 lwe_key_switch(
1386 scratch_lwen_plus1,
1387 lwe_in,
1388 pbs_key.lwe_ksk(),
1389 modop_lweq,
1390 parameters.decomoposer_lwe(),
1391 );
1392
1393 PBSTracer::with_local_mut(|t| {
1394 let out = scratch_lwen_plus1
1395 .as_ref()
1396 .iter()
1397 .map(|v| v.to_u64().unwrap())
1398 .collect_vec();
1399 t.ct_lwe_q_mod_after_ksk = out;
1400 });
1401
1402 // odd mowdown Q_ks -> q
1403 let g_k_dlog_map = parameters.g_k_dlog_map();
1404 let mut g_k_si = vec![vec![]; br_q];
1405 scratch_lwen_plus1
1406 .as_ref()
1407 .iter()
1408 .skip(1)
1409 .enumerate()
1410 .for_each(|(index, v)| {
1411 let odd_v = mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64);
1412 let k = g_k_dlog_map[odd_v];
1413 g_k_si[k].push(index);
1414 });
1415
1416 PBSTracer::with_local_mut(|t| {
1417 let out = scratch_lwen_plus1
1418 .as_ref()
1419 .iter()
1420 .map(|v| mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64) as u64)
1421 .collect_vec();
1422 t.ct_br_q_mod = out;
1423 });
1424
1425 // handle b and set trivial test RLWE
1426 let g = parameters.g() as usize;
1427 let g_times_b = (g * mod_switch_odd(
1428 scratch_lwen_plus1.as_ref()[0].to_f64().unwrap(),
1429 lwe_qf64,
1430 br_qf64,
1431 )) % (br_q);
1432 // v = (v(X) * X^{g*b}) mod X^{q/2}+1
1433 let br_qby2 = br_q / 2;
1434 let mut gb_monomial_sign = true;
1435 let mut gb_monomial_exp = g_times_b;
1436 // X^{g*b} mod X^{q/2}+1
1437 if gb_monomial_exp > br_qby2 {
1438 gb_monomial_exp -= br_qby2;
1439 gb_monomial_sign = false
1440 }
1441 // monomial mul
1442 let mut trivial_rlwe_test_poly =
1443 RlweCiphertext::<_, DefaultSecureRng>::from_raw(M::zeros(2, rlwe_n), true);
1444 if parameters.embedding_factor() == 1 {
1445 monomial_mul(
1446 test_vec.as_ref(),
1447 trivial_rlwe_test_poly.get_row_mut(1).as_mut(),
1448 gb_monomial_exp,
1449 gb_monomial_sign,
1450 br_qby2,
1451 modop_rlweq,
1452 );
1453 } else {
1454 // use lwe_in to store the `t = v(X) * X^{g*2} mod X^{q/2}+1` temporarily. This
1455 // works because q/2 <= N (where N is lwe_in LWE dimension) always.
1456 monomial_mul(
1457 test_vec.as_ref(),
1458 &mut lwe_in.as_mut()[..br_qby2],
1459 gb_monomial_exp,
1460 gb_monomial_sign,
1461 br_qby2,
1462 modop_rlweq,
1463 );
1464
1465 // emebed poly `t` in ring X^{q/2}+1 inside the bigger ring X^{N}+1
1466 let embed_factor = parameters.embedding_factor();
1467 let partb_trivial_rlwe = trivial_rlwe_test_poly.get_row_mut(1);
1468 lwe_in.as_ref()[..br_qby2]
1469 .iter()
1470 .enumerate()
1471 .for_each(|(index, v)| {
1472 partb_trivial_rlwe[embed_factor * index] = *v;
1473 });
1474 }
1475
1476 // blind rotate
1477 blind_rotation(
1478 &mut trivial_rlwe_test_poly,
1479 scratch_matrix_dplus2_ring,
1480 parameters.g(),
1481 1,
1482 br_q,
1483 &g_k_si,
1484 parameters.decomoposer_rlwe(),
1485 nttop_rlweq,
1486 modop_rlweq,
1487 parameters,
1488 pbs_key,
1489 );
1490
1491 // ClientKey::with_local(|ck| {
1492 // let ring_size = parameters.rlwe_n();
1493 // let mut rlwe_ct = vec![vec![0u64; ring_size]; 2];
1494 // izip!(
1495 // rlwe_ct[0].iter_mut(),
1496 // trivial_rlwe_test_poly.0.get_row_slice(0)
1497 // )
1498 // .for_each(|(t, f)| {
1499 // *t = f.to_u64().unwrap();
1500 // });
1501 // izip!(
1502 // rlwe_ct[1].iter_mut(),
1503 // trivial_rlwe_test_poly.0.get_row_slice(1)
1504 // )
1505 // .for_each(|(t, f)| {
1506 // *t = f.to_u64().unwrap();
1507 // });
1508 // let mut m_out = vec![vec![0u64; ring_size]];
1509 // let modop = ModularOpsU64::new(rlwe_q.to_u64().unwrap());
1510 // let nttop = NttBackendU64::new(rlwe_q.to_u64().unwrap(), ring_size);
1511 // decrypt_rlwe(&rlwe_ct, ck.sk_rlwe.values(), &mut m_out, &nttop, &modop);
1512
1513 // println!("RLWE post PBS message: {:?}", m_out[0]);
1514 // });
1515
1516 // sample extract
1517 sample_extract(lwe_in, &trivial_rlwe_test_poly, modop_rlweq, 0);
1518}
1519
1520fn mod_switch_odd(v: f64, from_q: f64, to_q: f64) -> usize {
1521 let odd_v = (((v * to_q) / (from_q)).floor()).to_usize().unwrap();
1522 //TODO(Jay): check correctness of this
1523 odd_v + ((odd_v & 1) ^ 1)
1524}
1525
1526// TODO(Jay): Add tests for sample extract
1527fn sample_extract<M: Matrix + MatrixMut, ModOp: ArithmeticOps<Element = M::MatElement>>(
1528 lwe_out: &mut M::R,
1529 rlwe_in: &M,
1530 mod_op: &ModOp,
1531 index: usize,
1532) where
1533 <M as Matrix>::R: RowMut,
1534 M::MatElement: Copy,
1535{
1536 let ring_size = rlwe_in.dimension().1;
1537
1538 // index..=0
1539 let to = &mut lwe_out.as_mut()[1..];
1540 let from = rlwe_in.get_row_slice(0);
1541 for i in 0..index + 1 {
1542 to[i] = from[index - i];
1543 }
1544
1545 // -(N..index)
1546 for i in index + 1..ring_size {
1547 to[i] = mod_op.neg(&from[ring_size + index - i]);
1548 }
1549
1550 // set b
1551 lwe_out.as_mut()[0] = *rlwe_in.get(1, index);
1552}
1553
1554/// TODO(Jay): Write tests for monomial mul
1555fn monomial_mul<El, ModOp: ArithmeticOps<Element = El>>(
1556 p_in: &[El],
1557 p_out: &mut [El],
1558 mon_exp: usize,
1559 mon_sign: bool,
1560 ring_size: usize,
1561 mod_op: &ModOp,
1562) where
1563 El: Copy,
1564{
1565 debug_assert!(p_in.as_ref().len() == ring_size);
1566 debug_assert!(p_in.as_ref().len() == p_out.as_ref().len());
1567 debug_assert!(mon_exp < ring_size);
1568
1569 p_in.as_ref().iter().enumerate().for_each(|(index, v)| {
1570 let mut to_index = index + mon_exp;
1571 let mut to_sign = mon_sign;
1572 if to_index >= ring_size {
1573 to_index = to_index - ring_size;
1574 to_sign = !to_sign;
1575 }
1576
1577 if !to_sign {
1578 p_out.as_mut()[to_index] = mod_op.neg(v);
1579 } else {
1580 p_out.as_mut()[to_index] = *v;
1581 }
1582 });
1583}
1584
1585thread_local! {
1586 static PBS_TRACER: RefCell<PBSTracer<Vec<Vec<u64>>>> = RefCell::new(PBSTracer::default());
1587}
1588
1589#[derive(Default)]
1590struct PBSTracer<M>
1591where
1592 M: Matrix + Default,
1593{
1594 pub(crate) ct_rlwe_q_mod: M::R,
1595 pub(crate) ct_lwe_q_mod: M::R,
1596 pub(crate) ct_lwe_q_mod_after_ksk: M::R,
1597 pub(crate) ct_br_q_mod: Vec<u64>,
1598}
1599
1600impl PBSTracer<Vec<Vec<u64>>> {
1601 fn trace(&self, parameters: &BoolParameters<u64>, sk_lwe: &[i32], sk_rlwe: &[i32]) {
1602 assert!(parameters.rlwe_n == sk_rlwe.len());
1603 assert!(parameters.lwe_n == sk_lwe.len());
1604
1605 let modop_rlweq = ModularOpsU64::new(parameters.rlwe_q as u64);
1606 // noise after mod down Q -> Q_ks
1607 let m_back0 = decrypt_lwe(&self.ct_rlwe_q_mod, sk_rlwe, &modop_rlweq);
1608
1609 let modop_lweq = ModularOpsU64::new(parameters.lwe_q as u64);
1610 // noise after mod down Q -> Q_ks
1611 let m_back1 = decrypt_lwe(&self.ct_lwe_q_mod, sk_rlwe, &modop_lweq);
1612 // noise after key switch from RLWE -> LWE
1613 let m_back2 = decrypt_lwe(&self.ct_lwe_q_mod_after_ksk, sk_lwe, &modop_lweq);
1614
1615 // noise after mod down odd from Q_ks -> q
1616 let modop_br_q = ModularOpsU64::new(parameters.br_q as u64);
1617 let m_back3 = decrypt_lwe(&self.ct_br_q_mod, sk_lwe, &modop_br_q);
1618
1619 println!(
1620 "
1621 M initial mod Q: {m_back0},
1622 M after mod down Q -> Q_ks: {m_back1},
1623 M after key switch from RLWE -> LWE: {m_back2},
1624 M after mod dwon Q_ks -> q: {m_back3}
1625 "
1626 );
1627 }
1628}
1629
1630impl WithLocal for PBSTracer<Vec<Vec<u64>>> {
1631 fn with_local<F, R>(func: F) -> R
1632 where
1633 F: Fn(&Self) -> R,
1634 {
1635 PBS_TRACER.with_borrow(|t| func(t))
1636 }
1637
1638 fn with_local_mut<F, R>(func: F) -> R
1639 where
1640 F: Fn(&mut Self) -> R,
1641 {
1642 PBS_TRACER.with_borrow_mut(|t| func(t))
1643 }
1644}
1645
1646#[cfg(test)]
1647mod tests {
1648 use std::iter::Sum;
1649
1650 use rand::{thread_rng, Rng};
1651 use rand_distr::Uniform;
1652
1653 use crate::{
1654 backend::ModularOpsU64,
1655 bool,
1656 ntt::NttBackendU64,
1657 random::DEFAULT_RNG,
1658 rgsw::{
1659 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
1660 tests::{_measure_noise_rgsw, _secret_encrypt_rlwe},
1661 RgswCiphertext, RgswCiphertextEvaluationDomain, SeededRgswCiphertext,
1662 SeededRlweCiphertext,
1663 },
1664 utils::negacyclic_mul,
1665 };
1666
1667 use self::parameters::{MP_BOOL_PARAMS, SP_BOOL_PARAMS};
1668
1669 use super::*;
1670
1671 // #[test]
1672 // fn trial() {
1673 // dbg!(generate_prime(28, 1 << 11, 1 << 28));
1674 // }
1675
1676 #[test]
1677 fn bool_encrypt_decrypt_works() {
1678 // let prime = generate_prime(32, 2 * 1024, 1 << 32);
1679 // dbg!(prime);
1680 let bool_evaluator =
1681 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1682 let client_key = bool_evaluator.client_key();
1683 // let sever_key = bool_evaluator.server_key(&client_key);
1684
1685 let mut m = true;
1686 for _ in 0..1000 {
1687 let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
1688 let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
1689 assert_eq!(m, m_back);
1690 m = !m;
1691 }
1692 }
1693
1694 #[test]
1695 fn bool_nand() {
1696 DefaultSecureRng::with_local_mut(|r| {
1697 let rng = DefaultSecureRng::new_seeded([19u8; 32]);
1698 *r = rng;
1699 });
1700
1701 let bool_evaluator =
1702 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1703
1704 // println!("{:?}", bool_evaluator.nand_test_vec);
1705 let client_key = bool_evaluator.client_key();
1706 let seeded_server_key = bool_evaluator.server_key(&client_key);
1707 let server_key_eval_domain =
1708 ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1709 &seeded_server_key,
1710 );
1711
1712 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
1713 let mut scratch_matrix_dplus2_ring = vec![
1714 vec![0u64; bool_evaluator.parameters.rlwe_n];
1715 bool_evaluator.parameters.d_rgsw + 2
1716 ];
1717
1718 let mut m0 = false;
1719 let mut m1 = true;
1720 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
1721 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
1722
1723 for _ in 0..1000 {
1724 let ct_back = bool_evaluator.nand(
1725 &ct0,
1726 &ct1,
1727 &server_key_eval_domain,
1728 &mut scratch_lwen_plus1,
1729 &mut scratch_matrix_dplus2_ring,
1730 );
1731
1732 let m_out = !(m0 && m1);
1733
1734 // Trace and measure PBS noise
1735 {
1736 let noise0 = {
1737 let ideal = if m0 {
1738 bool_evaluator.rlweq_by8
1739 } else {
1740 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1741 };
1742 let n = measure_noise_lwe(
1743 &ct0,
1744 client_key.sk_rlwe.values(),
1745 &bool_evaluator.rlwe_modop,
1746 &ideal,
1747 );
1748 let v = decrypt_lwe(
1749 &ct0,
1750 client_key.sk_rlwe.values(),
1751 &bool_evaluator.rlwe_modop,
1752 );
1753 (n, v)
1754 };
1755 let noise1 = {
1756 let ideal = if m1 {
1757 bool_evaluator.rlweq_by8
1758 } else {
1759 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1760 };
1761 let n = measure_noise_lwe(
1762 &ct1,
1763 client_key.sk_rlwe.values(),
1764 &bool_evaluator.rlwe_modop,
1765 &ideal,
1766 );
1767 let v = decrypt_lwe(
1768 &ct1,
1769 client_key.sk_rlwe.values(),
1770 &bool_evaluator.rlwe_modop,
1771 );
1772 (n, v)
1773 };
1774
1775 // Trace PBS
1776 PBSTracer::with_local(|t| {
1777 t.trace(
1778 &SP_BOOL_PARAMS,
1779 &client_key.sk_lwe.values(),
1780 client_key.sk_rlwe.values(),
1781 )
1782 });
1783
1784 // Calculate noise in ciphertext post PBS
1785 let noise_out = {
1786 let ideal = if m_out {
1787 bool_evaluator.rlweq_by8
1788 } else {
1789 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1790 };
1791 let n = measure_noise_lwe(
1792 &ct_back,
1793 client_key.sk_rlwe.values(),
1794 &bool_evaluator.rlwe_modop,
1795 &ideal,
1796 );
1797 let v = decrypt_lwe(
1798 &ct_back,
1799 client_key.sk_rlwe.values(),
1800 &bool_evaluator.rlwe_modop,
1801 );
1802 (n, v)
1803 };
1804 dbg!(m0, m1, m_out);
1805 println!(
1806 "ct0 (noise, message): {:?} \n ct1 (noise, message): {:?} \n PBS (noise, message): {:?}", noise0, noise1, noise_out
1807 );
1808 }
1809 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
1810 assert!(m_out == m_back, "Expected {m_out}, got {m_back}");
1811 println!("----------");
1812
1813 m1 = m0;
1814 m0 = m_out;
1815
1816 ct1 = ct0;
1817 ct0 = ct_back;
1818 }
1819 }
1820
1821 #[test]
1822 fn multi_party_encryption_decryption() {
1823 let bool_evaluator =
1824 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
1825
1826 let no_of_parties = 500;
1827 let parties = (0..no_of_parties)
1828 .map(|_| bool_evaluator.client_key())
1829 .collect_vec();
1830
1831 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
1832 parties.iter().for_each(|k| {
1833 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
1834 *ideal_i = *ideal_i + s_i;
1835 });
1836 });
1837
1838 println!("{:?}", &ideal_rlwe_sk);
1839
1840 let mut m = true;
1841 for i in 0..100 {
1842 let pk_cr_seed = [0u8; 32];
1843
1844 let public_key_share = parties
1845 .iter()
1846 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1847 .collect_vec();
1848
1849 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
1850 public_key_share.as_slice(),
1851 );
1852 let lwe_ct = bool_evaluator.pk_encrypt(&collective_pk.key, m);
1853
1854 let decryption_shares = parties
1855 .iter()
1856 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct, k))
1857 .collect_vec();
1858
1859 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
1860
1861 {
1862 let ideal_m = if m {
1863 bool_evaluator.rlweq_by8
1864 } else {
1865 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
1866 };
1867 let noise = measure_noise_lwe(
1868 &lwe_ct,
1869 &ideal_rlwe_sk,
1870 &bool_evaluator.rlwe_modop,
1871 &ideal_m,
1872 );
1873 println!("Noise: {noise}");
1874 }
1875
1876 assert_eq!(m_back, m);
1877 m = !m;
1878 }
1879 }
1880
1881 #[test]
1882 fn ms() {
1883 let logbig_q = 50;
1884 let logsmall_q = 20;
1885 let big_q = 1 << logbig_q;
1886 let small_q = 1 << logsmall_q;
1887 let lwe_n = 493;
1888
1889 let no_of_parties = 10;
1890 let parties_lwe_sk = (0..no_of_parties)
1891 .map(|_| LweSecret::random(lwe_n >> 1, lwe_n))
1892 .collect_vec();
1893
1894 // Ideal secrets
1895 let mut ideal_lwe_sk = vec![0i32; lwe_n];
1896 parties_lwe_sk.iter().for_each(|k| {
1897 izip!(ideal_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1898 *ideal_i = *ideal_i + s_i;
1899 });
1900 });
1901
1902 let mut rng = DefaultSecureRng::new();
1903
1904 let logp = 3;
1905 let modop_bigq = ModularOpsU64::new(big_q);
1906 let modop_smallq = ModularOpsU64::new(small_q);
1907
1908 for i in 0..100 {
1909 let m = thread_rng().sample(Uniform::new(0u64, (1u64 << logp)));
1910 let bigq_m = m << (logbig_q - logp);
1911 let smallq_m = m << (logsmall_q - logp);
1912
1913 // encrypt
1914 let mut lwe_ct = vec![0u64; lwe_n + 1];
1915 encrypt_lwe(&mut lwe_ct, &bigq_m, &ideal_lwe_sk, &modop_bigq, &mut rng);
1916
1917 let noise = measure_noise_lwe(&lwe_ct, &ideal_lwe_sk, &modop_bigq, &bigq_m);
1918 println!("Noise Before: {noise}");
1919
1920 // mod switch
1921 let lwe_ct_ms = lwe_ct
1922 .iter()
1923 .map(|v| (((*v as f64) * small_q as f64) / (big_q as f64)).round() as u64)
1924 .collect_vec();
1925
1926 let noise = measure_noise_lwe(&lwe_ct_ms, &ideal_lwe_sk, &modop_smallq, &smallq_m);
1927 println!("Noise After: {noise}");
1928 }
1929 }
1930
1931 #[test]
1932 fn multi_party_lwe_keyswitch() {
1933 let lwe_logq = 18;
1934 let lwe_q = 1 << lwe_logq;
1935 let d_lwe = 1;
1936 let logb_lwe = 6;
1937 let lweq_modop = ModularOpsU64::new(lwe_q);
1938
1939 let decomposer = DefaultDecomposer::new(lwe_q, logb_lwe, d_lwe);
1940 let lwe_gadgect_vec = decomposer.gadget_vector();
1941 let logp = 2;
1942
1943 let from_lwe_n = 2048;
1944 let to_lwe_n = 500;
1945
1946 let no_of_parties = 10;
1947 let parties_from_lwe_sk = (0..no_of_parties)
1948 .map(|_| LweSecret::random(from_lwe_n >> 1, from_lwe_n))
1949 .collect_vec();
1950 let parties_to_lwe_sk = (0..no_of_parties)
1951 .map(|_| LweSecret::random(to_lwe_n >> 1, to_lwe_n))
1952 .collect_vec();
1953
1954 // Ideal secrets
1955 let mut ideal_from_lwe_sk = vec![0i32; from_lwe_n];
1956 parties_from_lwe_sk.iter().for_each(|k| {
1957 izip!(ideal_from_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1958 *ideal_i = *ideal_i + s_i;
1959 });
1960 });
1961 let mut ideal_to_lwe_sk = vec![0i32; to_lwe_n];
1962 parties_to_lwe_sk.iter().for_each(|k| {
1963 izip!(ideal_to_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1964 *ideal_i = *ideal_i + s_i;
1965 });
1966 });
1967
1968 // Generate Lwe KSK share
1969 let mut rng = DefaultSecureRng::new();
1970 let mut ksk_seed = [0u8; 32];
1971 rng.fill_bytes(&mut ksk_seed);
1972 let lwe_ksk_shares = izip!(parties_from_lwe_sk.iter(), parties_to_lwe_sk.iter())
1973 .map(|(from_sk, to_sk)| {
1974 let mut ksk_out = vec![0u64; from_lwe_n * d_lwe];
1975 let mut p_rng = DefaultSecureRng::new_seeded(ksk_seed);
1976 lwe_ksk_keygen(
1977 from_sk.values(),
1978 to_sk.values(),
1979 &mut ksk_out,
1980 &lwe_gadgect_vec,
1981 &lweq_modop,
1982 &mut p_rng,
1983 &mut rng,
1984 );
1985 ksk_out
1986 })
1987 .collect_vec();
1988
1989 // Create collective LWE ksk
1990 let mut sum_partb = vec![0u64; d_lwe * from_lwe_n];
1991 lwe_ksk_shares.iter().for_each(|share| {
1992 lweq_modop.elwise_add_mut(sum_partb.as_mut_slice(), share.as_slice())
1993 });
1994 let mut lwe_ksk = vec![vec![0u64; to_lwe_n + 1]; d_lwe * from_lwe_n];
1995 let mut p_rng = DefaultSecureRng::new_seeded(ksk_seed);
1996 izip!(lwe_ksk.iter_mut(), sum_partb.iter()).for_each(|(lwe_i, part_bi)| {
1997 RandomUniformDist::random_fill(&mut p_rng, &lwe_q, &mut lwe_i.as_mut_slice()[1..]);
1998 lwe_i[0] = *part_bi;
1999 });
2000
2001 for i in 0..128 {
2002 println!("############## ITERATION {i} ##############");
2003
2004 // Encrypt m
2005 let m = 1;
2006 let mut lwe_ct = vec![0u64; from_lwe_n + 1];
2007 encrypt_lwe(&mut lwe_ct, &m, &ideal_from_lwe_sk, &lweq_modop, &mut rng);
2008
2009 let noise = measure_noise_lwe(&lwe_ct, &ideal_from_lwe_sk, &lweq_modop, &m);
2010 println!("Noise before key switch: {noise}");
2011
2012 // Key switch
2013 let lwe_ct_key_switched = {
2014 let mut lwe_ct_key_switched = vec![0u64; to_lwe_n + 1];
2015 lwe_key_switch(
2016 &mut lwe_ct_key_switched,
2017 &lwe_ct,
2018 &lwe_ksk,
2019 &lweq_modop,
2020 &decomposer,
2021 );
2022 lwe_ct_key_switched
2023 };
2024
2025 let noise = measure_noise_lwe(&lwe_ct_key_switched, &ideal_to_lwe_sk, &lweq_modop, &m);
2026 println!("Noise after key switch: {noise}");
2027 }
2028 }
2029
2030 fn _collecitve_public_key_gen(rlwe_q: u64, parties_rlwe_sk: &[RlweSecret]) -> Vec<Vec<u64>> {
2031 let ring_size = parties_rlwe_sk[0].values.len();
2032 assert!(ring_size.is_power_of_two());
2033 let mut rng = DefaultSecureRng::new();
2034 let nttop = NttBackendU64::new(rlwe_q, ring_size);
2035 let modop = ModularOpsU64::new(rlwe_q);
2036
2037 // Generate Pk shares
2038 let pk_seed = [0u8; 32];
2039 let pk_shares = parties_rlwe_sk.iter().map(|sk| {
2040 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2041 let mut share_out = vec![0u64; ring_size];
2042 public_key_share(
2043 &mut share_out,
2044 sk.values(),
2045 &modop,
2046 &nttop,
2047 &mut p_rng,
2048 &mut rng,
2049 );
2050 share_out
2051 });
2052
2053 let mut pk_part_b = vec![0u64; ring_size];
2054 pk_shares.for_each(|share| modop.elwise_add_mut(&mut pk_part_b, &share));
2055 let mut pk_part_a = vec![0u64; ring_size];
2056 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
2057 RandomUniformDist::random_fill(&mut p_rng, &rlwe_q, pk_part_a.as_mut_slice());
2058
2059 vec![pk_part_a, pk_part_b]
2060 }
2061
2062 fn _multi_party_all_keygen(
2063 bool_evaluator: &BoolEvaluator<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>,
2064 no_of_parties: usize,
2065 ) -> (
2066 Vec<ClientKey>,
2067 PublicKey<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>,
2068 Vec<
2069 CommonReferenceSeededMultiPartyServerKeyShare<
2070 Vec<Vec<u64>>,
2071 BoolParameters<u64>,
2072 [u8; 32],
2073 >,
2074 >,
2075 SeededMultiPartyServerKey<Vec<Vec<u64>>, [u8; 32], BoolParameters<u64>>,
2076 ServerKeyEvaluationDomain<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>,
2077 ClientKey,
2078 ) {
2079 let parties = (0..no_of_parties)
2080 .map(|_| bool_evaluator.client_key())
2081 .collect_vec();
2082
2083 // Collective public key
2084 let pk_cr_seed = [0u8; 32];
2085 let public_key_share = parties
2086 .iter()
2087 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2088 .collect_vec();
2089 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2090 public_key_share.as_slice(),
2091 );
2092
2093 // Server key
2094 let pbs_cr_seed = [1u8; 32];
2095 let server_key_shares = parties
2096 .iter()
2097 .map(|k| bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k))
2098 .collect_vec();
2099 let seeded_server_key =
2100 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
2101 &server_key_shares,
2102 &bool_evaluator.decomposer_rlwe,
2103 );
2104 let server_key_eval = ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2105 &seeded_server_key,
2106 );
2107
2108 // construct ideal rlwe sk for meauring noise
2109 let ideal_client_key = {
2110 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
2111 parties.iter().for_each(|k| {
2112 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
2113 *ideal_i = *ideal_i + s_i;
2114 });
2115 });
2116 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
2117 parties.iter().for_each(|k| {
2118 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
2119 *ideal_i = *ideal_i + s_i;
2120 });
2121 });
2122
2123 ClientKey {
2124 sk_lwe: LweSecret {
2125 values: ideal_lwe_sk,
2126 },
2127 sk_rlwe: RlweSecret {
2128 values: ideal_rlwe_sk,
2129 },
2130 }
2131 };
2132
2133 (
2134 parties,
2135 collective_pk,
2136 server_key_shares,
2137 seeded_server_key,
2138 server_key_eval,
2139 ideal_client_key,
2140 )
2141 }
2142
2143 #[test]
2144 fn mp_key_correcntess() {
2145 let bool_evaluator =
2146 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2147
2148 let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2149 _multi_party_all_keygen(&bool_evaluator, 20);
2150
2151 let lwe_q = bool_evaluator.parameters.lwe_q;
2152 let rlwe_q = bool_evaluator.parameters.rlwe_q;
2153 let d_rgsw = bool_evaluator.parameters.d_rgsw;
2154 let lwe_logq = bool_evaluator.parameters.lwe_logq;
2155 let lwe_n = bool_evaluator.parameters.lwe_n;
2156 let rlwe_n = bool_evaluator.parameters.rlwe_n;
2157 let lwe_modop = &bool_evaluator.lwe_modop;
2158 let rlwe_nttop = &bool_evaluator.rlwe_nttop;
2159 let rlwe_modop = &bool_evaluator.rlwe_modop;
2160 let rlwe_decomposer = &bool_evaluator.decomposer_rlwe;
2161
2162 // test LWE ksk from RLWE -> LWE
2163 if false {
2164 let logp = 2;
2165 let mut rng = DefaultSecureRng::new();
2166
2167 let m = 1;
2168 let encoded_m = m << (lwe_logq - logp);
2169
2170 // Encrypt
2171 let mut lwe_ct = vec![0u64; rlwe_n + 1];
2172 encrypt_lwe(
2173 &mut lwe_ct,
2174 &encoded_m,
2175 ideal_client_key.sk_rlwe.values(),
2176 lwe_modop,
2177 &mut rng,
2178 );
2179
2180 // key switch
2181 let lwe_decomposer = &bool_evaluator.decomposer_lwe;
2182 let mut lwe_out = vec![0u64; lwe_n + 1];
2183 lwe_key_switch(
2184 &mut lwe_out,
2185 &lwe_ct,
2186 &server_key_eval.lwe_ksk,
2187 lwe_modop,
2188 lwe_decomposer,
2189 );
2190
2191 let encoded_m_back = decrypt_lwe(&lwe_out, ideal_client_key.sk_lwe.values(), lwe_modop);
2192 let m_back =
2193 ((encoded_m_back as f64 * (1 << logp) as f64) / (lwe_q as f64)).round() as u64;
2194 dbg!(m_back, m);
2195
2196 let noise = measure_noise_lwe(
2197 &lwe_out,
2198 ideal_client_key.sk_lwe.values(),
2199 lwe_modop,
2200 &encoded_m,
2201 );
2202
2203 println!("Noise: {noise}");
2204 }
2205
2206 // Measure noise in RGSW ciphertexts of ideal LWE secrets
2207 if true {
2208 let gadget_vec = rlwe_decomposer.gadget_vector();
2209 for i in 0..20 {
2210 // measure noise in RGSW(s[i])
2211 let si =
2212 ideal_client_key.sk_lwe.values[i] * (bool_evaluator.embedding_factor as i32);
2213 let mut si_poly = vec![0u64; rlwe_n];
2214 if si < 0 {
2215 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2216 } else {
2217 si_poly[(si.abs() as usize)] = 1;
2218 }
2219
2220 let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
2221 rgsw_si
2222 .iter_mut()
2223 .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
2224
2225 println!("####### Noise in RGSW(X^s_{i}) #######");
2226 _measure_noise_rgsw(
2227 &rgsw_si,
2228 &si_poly,
2229 ideal_client_key.sk_rlwe.values(),
2230 &gadget_vec,
2231 rlwe_q,
2232 );
2233 println!("####### ##################### #######");
2234 }
2235 }
2236
2237 // measure noise grwoth in RLWExRGSW
2238 if true {
2239 let mut rng = DefaultSecureRng::new();
2240 let mut carry_m = vec![0u64; rlwe_n];
2241 RandomUniformDist::random_fill(&mut rng, &rlwe_q, carry_m.as_mut_slice());
2242
2243 // RGSW(carrym)
2244 let trivial_rlwect = vec![vec![0u64; rlwe_n], carry_m.clone()];
2245 let mut rlwe_ct = RlweCiphertext::<_, DefaultSecureRng>::from_raw(trivial_rlwect, true);
2246
2247 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
2248 let mul_mod =
2249 |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
2250
2251 for i in 0..bool_evaluator.parameters.lwe_n {
2252 rlwe_by_rgsw(
2253 &mut rlwe_ct,
2254 server_key_eval.rgsw_ct_lwe_si(i),
2255 &mut scratch_matrix_dplus2_ring,
2256 rlwe_decomposer,
2257 rlwe_nttop,
2258 rlwe_modop,
2259 );
2260
2261 // carry_m[X] * s_i[X]
2262 let si =
2263 ideal_client_key.sk_lwe.values[i] * (bool_evaluator.embedding_factor as i32);
2264 let mut si_poly = vec![0u64; rlwe_n];
2265 if si < 0 {
2266 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2267 } else {
2268 si_poly[(si.abs() as usize)] = 1;
2269 }
2270 carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod, rlwe_q);
2271
2272 let noise = measure_noise(
2273 &rlwe_ct,
2274 &carry_m,
2275 rlwe_nttop,
2276 rlwe_modop,
2277 ideal_client_key.sk_rlwe.values(),
2278 );
2279 println!("Noise RLWE(carry_m) accumulating {i}^th secret monomial: {noise}");
2280 }
2281 }
2282
2283 // Check galois keys
2284 if false {
2285 let g = bool_evaluator.g() as isize;
2286 let mut rng = DefaultSecureRng::new();
2287 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
2288 for i in [g, -g] {
2289 let mut m = vec![0u64; rlwe_n];
2290 RandomUniformDist::random_fill(&mut rng, &rlwe_q, m.as_mut_slice());
2291 let mut rlwe_ct = {
2292 let mut data = vec![vec![0u64; rlwe_n]; 2];
2293 public_key_encrypt_rlwe(
2294 &mut data,
2295 &collective_pk.key,
2296 &m,
2297 rlwe_modop,
2298 rlwe_nttop,
2299 &mut rng,
2300 );
2301 RlweCiphertext::<_, DefaultSecureRng>::from_raw(data, false)
2302 };
2303
2304 let auto_key = server_key_eval.galois_key_for_auto(i);
2305 let (auto_map_index, auto_map_sign) = generate_auto_map(rlwe_n, i);
2306 galois_auto(
2307 &mut rlwe_ct,
2308 auto_key,
2309 &mut scratch_matrix_dplus2_ring,
2310 &auto_map_index,
2311 &auto_map_sign,
2312 rlwe_modop,
2313 rlwe_nttop,
2314 rlwe_decomposer,
2315 );
2316
2317 // send m(X) -> m(X^i)
2318 let mut m_k = vec![0u64; rlwe_n];
2319 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
2320 |(mi, to_index, to_sign)| {
2321 if !to_sign {
2322 m_k[*to_index] = rlwe_q - *mi;
2323 } else {
2324 m_k[*to_index] = *mi;
2325 }
2326 },
2327 );
2328
2329 // measure noise
2330 let noise = measure_noise(
2331 &rlwe_ct,
2332 &m_k,
2333 rlwe_nttop,
2334 rlwe_modop,
2335 ideal_client_key.sk_rlwe.values(),
2336 );
2337
2338 println!("Noise after auto k={i}: {noise}");
2339 }
2340 }
2341 }
2342
2343 #[test]
2344 fn multi_party_nand() {
2345 let bool_evaluator =
2346 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2347
2348 let (parties, collective_pk, _, _, server_key_eval, ideal_client_key) =
2349 _multi_party_all_keygen(&bool_evaluator, 50);
2350
2351 // PBS
2352 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
2353 let mut scratch_matrix_dplus2_ring = vec![
2354 vec![0u64; bool_evaluator.parameters.rlwe_n];
2355 bool_evaluator.parameters.d_rgsw + 2
2356 ];
2357
2358 let mut m0 = true;
2359 let mut m1 = false;
2360
2361 let mut lwe0 = bool_evaluator.pk_encrypt(&collective_pk.key, m0);
2362 let mut lwe1 = bool_evaluator.pk_encrypt(&collective_pk.key, m1);
2363
2364 for _ in 0..2000 {
2365 let lwe_out = bool_evaluator.nand(
2366 &lwe0,
2367 &lwe1,
2368 &server_key_eval,
2369 &mut scratch_lwen_plus1,
2370 &mut scratch_matrix_dplus2_ring,
2371 );
2372
2373 let m_expected = !(m0 & m1);
2374
2375 // measure noise
2376 {
2377 let noise0 = {
2378 let ideal = if m0 {
2379 bool_evaluator.rlweq_by8
2380 } else {
2381 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
2382 };
2383 let n = measure_noise_lwe(
2384 &lwe0,
2385 ideal_client_key.sk_rlwe.values(),
2386 &bool_evaluator.rlwe_modop,
2387 &ideal,
2388 );
2389 let v = decrypt_lwe(
2390 &lwe0,
2391 ideal_client_key.sk_rlwe.values(),
2392 &bool_evaluator.rlwe_modop,
2393 );
2394 (n, v)
2395 };
2396 let noise1 = {
2397 let ideal = if m1 {
2398 bool_evaluator.rlweq_by8
2399 } else {
2400 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
2401 };
2402 let n = measure_noise_lwe(
2403 &lwe1,
2404 ideal_client_key.sk_rlwe.values(),
2405 &bool_evaluator.rlwe_modop,
2406 &ideal,
2407 );
2408 let v = decrypt_lwe(
2409 &lwe1,
2410 ideal_client_key.sk_rlwe.values(),
2411 &bool_evaluator.rlwe_modop,
2412 );
2413 (n, v)
2414 };
2415
2416 // Trace PBS
2417 PBSTracer::with_local(|t| {
2418 t.trace(
2419 &MP_BOOL_PARAMS,
2420 &ideal_client_key.sk_lwe.values(),
2421 &ideal_client_key.sk_rlwe.values(),
2422 )
2423 });
2424
2425 let noise_out = {
2426 let ideal_m = if m_expected {
2427 bool_evaluator.rlweq_by8
2428 } else {
2429 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
2430 };
2431 let n = measure_noise_lwe(
2432 &lwe_out,
2433 ideal_client_key.sk_rlwe.values(),
2434 &bool_evaluator.rlwe_modop,
2435 &ideal_m,
2436 );
2437 let v = decrypt_lwe(
2438 &lwe_out,
2439 ideal_client_key.sk_rlwe.values(),
2440 &bool_evaluator.rlwe_modop,
2441 );
2442 (n, v)
2443 };
2444 dbg!(m0, m1, m_expected);
2445 println!(
2446 "ct0 (noise, message): {:?} \n ct1 (noise, message): {:?} \n PBS (noise, message): {:?}", noise0, noise1, noise_out
2447 );
2448 }
2449
2450 // multi-party decrypt
2451 let decryption_shares = parties
2452 .iter()
2453 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_out, k))
2454 .collect_vec();
2455 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
2456
2457 // let m_back = bool_evaluator.sk_decrypt(&lwe_out, &ideal_client_key);
2458
2459 assert!(m_expected == m_back, "Expected {m_expected}, got {m_back}");
2460 m1 = m0;
2461 m0 = m_expected;
2462
2463 lwe1 = lwe0;
2464 lwe0 = lwe_out;
2465 }
2466 }
2467
2468 struct Stats<T> {
2469 samples: Vec<T>,
2470 }
2471
2472 impl<T: PrimInt + FromPrimitive + Debug> Stats<T>
2473 where
2474 // T: for<'a> Sum<&'a T>,
2475 T: for<'a> std::iter::Sum<&'a T> + std::iter::Sum<T>,
2476 {
2477 fn mean(&self) -> f64 {
2478 self.samples.iter().sum::<T>().to_f64().unwrap() / (self.samples.len() as f64)
2479 }
2480
2481 fn std_dev(&self) -> f64 {
2482 let mean = self.mean();
2483
2484 // diff
2485 let diff_sq = self
2486 .samples
2487 .iter()
2488 .map(|v| {
2489 let t = v.to_f64().unwrap() - mean;
2490 t * t
2491 })
2492 .into_iter()
2493 .sum::<f64>();
2494
2495 (diff_sq / (self.samples.len() as f64)).sqrt()
2496 }
2497
2498 fn add_more(&mut self, values: &[T]) {
2499 self.samples.extend(values.iter());
2500 }
2501 }
2502
2503 #[test]
2504 fn tester() {
2505 // pub(super) const TEST_MP_BOOL_PARAMS: BoolParameters<u64> =
2506 // BoolParameters::<u64> { rlwe_q: 1152921504606830593,
2507 // rlwe_logq: 60,
2508 // lwe_q: 1 << 20,
2509 // lwe_logq: 20,
2510 // br_q: 1 << 11,
2511 // rlwe_n: 1 << 11,
2512 // lwe_n: 500,
2513 // d_rgsw: 4,
2514 // logb_rgsw: 12,
2515 // d_lwe: 5,
2516 // logb_lwe: 4,
2517 // g: 5,
2518 // w: 1,
2519 // };
2520
2521 let bool_evaluator =
2522 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2523
2524 // let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2525 // _multi_party_all_keygen(&bool_evaluator, 20);
2526 let no_of_parties = 2;
2527 let lwe_q = bool_evaluator.parameters.lwe_q;
2528 let rlwe_q = bool_evaluator.parameters.rlwe_q;
2529 let d_rgsw = bool_evaluator.parameters.d_rgsw;
2530 let lwe_logq = bool_evaluator.parameters.lwe_logq;
2531 let lwe_n = bool_evaluator.parameters.lwe_n;
2532 let rlwe_n = bool_evaluator.parameters.rlwe_n;
2533 let lwe_modop = &bool_evaluator.lwe_modop;
2534 let rlwe_nttop = &bool_evaluator.rlwe_nttop;
2535 let rlwe_modop = &bool_evaluator.rlwe_modop;
2536 let rlwe_decomposer = &bool_evaluator.decomposer_rlwe;
2537 let rlwe_gadget_vector = rlwe_decomposer.gadget_vector();
2538
2539 let parties = (0..no_of_parties)
2540 .map(|_| bool_evaluator.client_key())
2541 .collect_vec();
2542
2543 let ideal_client_key = {
2544 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
2545 parties.iter().for_each(|k| {
2546 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
2547 *ideal_i = *ideal_i + s_i;
2548 });
2549 });
2550 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
2551 parties.iter().for_each(|k| {
2552 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
2553 *ideal_i = *ideal_i + s_i;
2554 });
2555 });
2556
2557 ClientKey {
2558 sk_lwe: LweSecret {
2559 values: ideal_lwe_sk,
2560 },
2561 sk_rlwe: RlweSecret {
2562 values: ideal_rlwe_sk,
2563 },
2564 }
2565 };
2566
2567 // check noise in freshly encrypted RLWE ciphertext (ie var_fresh)
2568 if false {
2569 let mut rng = DefaultSecureRng::new();
2570 let mut check = Stats { samples: vec![] };
2571 for _ in 0..10 {
2572 // generate a new collective public key
2573 let mut pk_cr_seed = [0u8; 32];
2574 rng.fill_bytes(&mut pk_cr_seed);
2575 let public_key_share = parties
2576 .iter()
2577 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2578 .collect_vec();
2579 let collective_pk =
2580 PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2581 public_key_share.as_slice(),
2582 );
2583
2584 let m = vec![0u64; rlwe_n];
2585 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2586 public_key_encrypt_rlwe(
2587 &mut rlwe_ct,
2588 &collective_pk.key,
2589 &m,
2590 rlwe_modop,
2591 rlwe_nttop,
2592 &mut rng,
2593 );
2594
2595 let mut m_back = vec![0u64; rlwe_n];
2596 decrypt_rlwe(
2597 &rlwe_ct,
2598 ideal_client_key.sk_rlwe.values(),
2599 &mut m_back,
2600 rlwe_nttop,
2601 rlwe_modop,
2602 );
2603
2604 rlwe_modop.elwise_sub_mut(m_back.as_mut_slice(), m.as_slice());
2605
2606 check.add_more(Vec::<i64>::try_convert_from(&m_back, &rlwe_q).as_slice());
2607 }
2608
2609 println!("Public key Std: {}", check.std_dev().abs().log2());
2610 }
2611
2612 if true {
2613 // Generate server key shares
2614 let mut rng = DefaultSecureRng::new();
2615 let mut pk_cr_seed = [0u8; 32];
2616 rng.fill_bytes(&mut pk_cr_seed);
2617 let public_key_share = parties
2618 .iter()
2619 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2620 .collect_vec();
2621 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2622 public_key_share.as_slice(),
2623 );
2624 let pbs_cr_seed = [0u8; 32];
2625 rng.fill_bytes(&mut pk_cr_seed);
2626 let server_key_shares = parties
2627 .iter()
2628 .map(|k| {
2629 bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k)
2630 })
2631 .collect_vec();
2632
2633 let seeded_server_key =
2634 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
2635 &server_key_shares,
2636 rlwe_decomposer,
2637 );
2638
2639 // Check noise in RGSW ciphertexts of ideal LWE secret elements
2640 if true {
2641 let mut check = Stats { samples: vec![] };
2642 izip!(
2643 ideal_client_key.sk_lwe.values.iter(),
2644 seeded_server_key.rgsw_cts.iter()
2645 )
2646 .for_each(|(s_i, rgsw_ct_i)| {
2647 // X^{s[i]}
2648 let mut m_si = vec![0u64; rlwe_n];
2649 let s_i = *s_i * (bool_evaluator.embedding_factor as i32);
2650 if s_i < 0 {
2651 m_si[rlwe_n - (s_i.abs() as usize)] = rlwe_q - 1;
2652 } else {
2653 m_si[s_i as usize] = 1;
2654 }
2655
2656 _measure_noise_rgsw(
2657 &rgsw_ct_i,
2658 &m_si,
2659 ideal_client_key.sk_rlwe.values(),
2660 &rlwe_gadget_vector,
2661 rlwe_q,
2662 );
2663
2664 // RLWE(-sm)
2665 let mut neg_s_eval =
2666 Vec::<u64>::try_convert_from(ideal_client_key.sk_rlwe.values(), &rlwe_q);
2667 rlwe_modop.elwise_neg_mut(&mut neg_s_eval);
2668 rlwe_nttop.forward(&mut neg_s_eval);
2669 for j in 0..rlwe_decomposer.d() {
2670 // -s[X]*X^{s_lwe[i]}*B_j
2671 let mut m_ideal = m_si.clone();
2672 rlwe_nttop.forward(m_ideal.as_mut_slice());
2673 rlwe_modop.elwise_mul_mut(m_ideal.as_mut_slice(), neg_s_eval.as_slice());
2674 rlwe_nttop.backward(m_ideal.as_mut_slice());
2675 rlwe_modop
2676 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_gadget_vector[j]);
2677
2678 // RLWE(-s*X^{s_lwe[i]}*B_j)
2679 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2680 rlwe_ct[0].copy_from_slice(&rgsw_ct_i[j]);
2681 rlwe_ct[1].copy_from_slice(&rgsw_ct_i[j + rlwe_decomposer.d()]);
2682
2683 let mut m_back = vec![0u64; rlwe_n];
2684 decrypt_rlwe(
2685 &rlwe_ct,
2686 ideal_client_key.sk_rlwe.values(),
2687 &mut m_back,
2688 rlwe_nttop,
2689 rlwe_modop,
2690 );
2691
2692 // diff
2693 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2694 check.add_more(&Vec::<i64>::try_convert_from(&m_back, &rlwe_q));
2695 }
2696
2697 // RLWE'(m)
2698 for j in 0..rlwe_decomposer.d() {
2699 // X^{s_lwe[i]}*B_j
2700 let mut m_ideal = m_si.clone();
2701 rlwe_modop
2702 .elwise_scalar_mul_mut(m_ideal.as_mut_slice(), &rlwe_gadget_vector[j]);
2703
2704 // RLWE(X^{s_lwe[i]}*B_j)
2705 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2706 rlwe_ct[0].copy_from_slice(&rgsw_ct_i[j + (2 * rlwe_decomposer.d())]);
2707 rlwe_ct[1].copy_from_slice(&rgsw_ct_i[j + (3 * rlwe_decomposer.d())]);
2708
2709 let mut m_back = vec![0u64; rlwe_n];
2710 decrypt_rlwe(
2711 &rlwe_ct,
2712 ideal_client_key.sk_rlwe.values(),
2713 &mut m_back,
2714 rlwe_nttop,
2715 rlwe_modop,
2716 );
2717
2718 // diff
2719 rlwe_modop.elwise_sub_mut(&mut m_back, &m_ideal);
2720 check.add_more(&Vec::<i64>::try_convert_from(&m_back, &rlwe_q));
2721 }
2722 });
2723 println!(
2724 "RGSW Std: {} {} ;; max={}",
2725 check.mean(),
2726 check.std_dev().abs().log2(),
2727 check.samples.iter().max().unwrap()
2728 );
2729 }
2730
2731 // check noise in RLWE x RGSW(X^{s_i}) where RGSW is accunulated RGSW ciphertext
2732 if false {
2733 let mut check = Stats { samples: vec![] };
2734 // server key in Evaluation domain
2735 let server_key_eval_domain =
2736 ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2737 &seeded_server_key,
2738 );
2739 izip!(
2740 ideal_client_key.sk_lwe.values(),
2741 seeded_server_key.rgsw_cts.iter()
2742 )
2743 .for_each(|(s_i, rgsw_ct_i)| {
2744 let mut rgsw_ct_i = rgsw_ct_i.clone();
2745 rgsw_ct_i
2746 .iter_mut()
2747 .for_each(|ri| rlwe_nttop.forward(ri.as_mut()));
2748
2749 let mut m = vec![0u64; rlwe_n];
2750 RandomUniformDist::random_fill(&mut rng, &rlwe_q, m.as_mut_slice());
2751 let mut rlwe_ct = vec![vec![0u64; rlwe_n]; 2];
2752 public_key_encrypt_rlwe(
2753 &mut rlwe_ct,
2754 &collective_pk.key,
2755 &m,
2756 rlwe_modop,
2757 rlwe_nttop,
2758 &mut rng,
2759 );
2760
2761 // RLWE(m*X^{s[i]}) = RLWE(m) x RGSW(X^{s[i]})
2762 let mut rlwe_after = RlweCiphertext::<_, DefaultSecureRng>::from_raw(
2763 vec![vec![0u64; rlwe_n], m.clone()],
2764 true,
2765 );
2766 // let mut rlwe_after =
2767 // RlweCiphertext::<_, DefaultSecureRng>::from_raw(rlwe_ct.clone(), false);
2768 let mut scratch = vec![vec![0u64; rlwe_n]; rlwe_decomposer.d() + 2];
2769 rlwe_by_rgsw(
2770 &mut rlwe_after,
2771 &rgsw_ct_i,
2772 &mut scratch,
2773 rlwe_decomposer,
2774 rlwe_nttop,
2775 rlwe_modop,
2776 );
2777
2778 // m1 = X^{s[i]}
2779 let mut m1 = vec![0u64; rlwe_n];
2780 let s_i = *s_i * (bool_evaluator.embedding_factor as i32);
2781 if s_i < 0 {
2782 m1[rlwe_n - (s_i.abs() as usize)] = rlwe_q - 1;
2783 } else {
2784 m1[s_i as usize] = 1;
2785 }
2786
2787 // (m+e) * m1
2788 let mut m_plus_e_times_m1 = m.clone();
2789 // decrypt_rlwe(
2790 // &rlwe_ct,
2791 // ideal_client_key.sk_rlwe.values(),
2792 // &mut m_plus_e_times_m1,
2793 // rlwe_nttop,
2794 // rlwe_modop,
2795 // );
2796 rlwe_nttop.forward(m_plus_e_times_m1.as_mut_slice());
2797 rlwe_nttop.forward(m1.as_mut_slice());
2798 rlwe_modop.elwise_mul_mut(m_plus_e_times_m1.as_mut_slice(), m1.as_slice());
2799 rlwe_nttop.backward(m_plus_e_times_m1.as_mut_slice());
2800
2801 // Resulting RLWE ciphertext will equal: (m0m1 + em1) + e_{rlsw x rgsw}.
2802 // Hence, resulting rlwe ciphertext will have error em1 + e_{rlwe x rgsw}.
2803 // Here we're only concerned with e_{rlwe x rgsw}, that is noise caused due to
2804 // RLWExRGSW. Also note, in practice m1 is a monomial, for ex, X^{s_{i}}, for
2805 // some i and var(em1) = var(e).
2806 let mut m_plus_e_times_m1_more_e = vec![0u64; rlwe_n];
2807 decrypt_rlwe(
2808 &rlwe_after,
2809 ideal_client_key.sk_rlwe.values(),
2810 &mut m_plus_e_times_m1_more_e,
2811 rlwe_nttop,
2812 rlwe_modop,
2813 );
2814
2815 // diff
2816 rlwe_modop.elwise_sub_mut(
2817 m_plus_e_times_m1_more_e.as_mut_slice(),
2818 m_plus_e_times_m1.as_slice(),
2819 );
2820
2821 let noise = measure_noise(
2822 &rlwe_after,
2823 &m_plus_e_times_m1,
2824 rlwe_nttop,
2825 rlwe_modop,
2826 ideal_client_key.sk_rlwe.values(),
2827 );
2828 print!("NOISE: {}", noise);
2829
2830 check.add_more(&Vec::<i64>::try_convert_from(
2831 &m_plus_e_times_m1_more_e,
2832 &rlwe_q,
2833 ));
2834 });
2835 println!(
2836 "RLWE x RGSW, where RGSW has noise var_brk, std: {} {}",
2837 check.std_dev(),
2838 check.std_dev().abs().log2()
2839 )
2840 }
2841 }
2842
2843 // Check noise in fresh RGSW ciphertexts, ie X^{s_j[i]}, must equal noise in
2844 // fresh RLWE ciphertext
2845 if true {}
2846 // test LWE ksk from RLWE -> LWE
2847 // if false {
2848 // let logp = 2;
2849 // let mut rng = DefaultSecureRng::new();
2850
2851 // let m = 1;
2852 // let encoded_m = m << (lwe_logq - logp);
2853
2854 // // Encrypt
2855 // let mut lwe_ct = vec![0u64; rlwe_n + 1];
2856 // encrypt_lwe(
2857 // &mut lwe_ct,
2858 // &encoded_m,
2859 // ideal_client_key.sk_rlwe.values(),
2860 // lwe_modop,
2861 // &mut rng,
2862 // );
2863
2864 // // key switch
2865 // let lwe_decomposer = &bool_evaluator.decomposer_lwe;
2866 // let mut lwe_out = vec![0u64; lwe_n + 1];
2867 // lwe_key_switch(
2868 // &mut lwe_out,
2869 // &lwe_ct,
2870 // &server_key_eval.lwe_ksk,
2871 // lwe_modop,
2872 // lwe_decomposer,
2873 // );
2874
2875 // let encoded_m_back = decrypt_lwe(&lwe_out,
2876 // ideal_client_key.sk_lwe.values(), lwe_modop); let m_back
2877 // = ((encoded_m_back as f64 * (1 << logp) as f64) /
2878 // (lwe_q as f64)).round() as u64; dbg!(m_back, m);
2879
2880 // let noise = measure_noise_lwe(
2881 // &lwe_out,
2882 // ideal_client_key.sk_lwe.values(),
2883 // lwe_modop,
2884 // &encoded_m,
2885 // );
2886
2887 // println!("Noise: {noise}");
2888 // }
2889
2890 // Measure noise in RGSW ciphertexts of ideal LWE secrets
2891 // if true {
2892 // let gadget_vec = gadget_vector(
2893 // bool_evaluator.parameters.rlwe_logq,
2894 // bool_evaluator.parameters.logb_rgsw,
2895 // bool_evaluator.parameters.d_rgsw,
2896 // );
2897
2898 // for i in 0..20 {
2899 // // measure noise in RGSW(s[i])
2900 // let si =
2901 // ideal_client_key.sk_lwe.values[i] *
2902 // (bool_evaluator.embedding_factor as i32); let mut
2903 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
2904 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2905 // } else {
2906 // si_poly[(si.abs() as usize)] = 1;
2907 // }
2908
2909 // let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
2910 // rgsw_si
2911 // .iter_mut()
2912 // .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
2913
2914 // println!("####### Noise in RGSW(X^s_{i}) #######");
2915 // _measure_noise_rgsw(
2916 // &rgsw_si,
2917 // &si_poly,
2918 // ideal_client_key.sk_rlwe.values(),
2919 // &gadget_vec,
2920 // rlwe_q,
2921 // );
2922 // println!("####### ##################### #######");
2923 // }
2924 // }
2925
2926 // // measure noise grwoth in RLWExRGSW
2927 // if true {
2928 // let mut rng = DefaultSecureRng::new();
2929 // let mut carry_m = vec![0u64; rlwe_n];
2930 // RandomUniformDist::random_fill(&mut rng, &rlwe_q,
2931 // carry_m.as_mut_slice());
2932
2933 // // RGSW(carrym)
2934 // let trivial_rlwect = vec![vec![0u64; rlwe_n], carry_m.clone()];
2935 // let mut rlwe_ct = RlweCiphertext::<_,
2936 // DefaultSecureRng>::from_raw(trivial_rlwect, true);
2937
2938 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
2939 // d_rgsw + 2]; let mul_mod =
2940 // |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
2941
2942 // for i in 0..bool_evaluator.parameters.lwe_n {
2943 // rlwe_by_rgsw(
2944 // &mut rlwe_ct,
2945 // server_key_eval.rgsw_ct_lwe_si(i),
2946 // &mut scratch_matrix_dplus2_ring,
2947 // rlwe_decomposer,
2948 // rlwe_nttop,
2949 // rlwe_modop,
2950 // );
2951
2952 // // carry_m[X] * s_i[X]
2953 // let si =
2954 // ideal_client_key.sk_lwe.values[i] *
2955 // (bool_evaluator.embedding_factor as i32); let mut
2956 // si_poly = vec![0u64; rlwe_n]; if si < 0 {
2957 // si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2958 // } else {
2959 // si_poly[(si.abs() as usize)] = 1;
2960 // }
2961 // carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod,
2962 // rlwe_q);
2963
2964 // let noise = measure_noise(
2965 // &rlwe_ct,
2966 // &carry_m,
2967 // rlwe_nttop,
2968 // rlwe_modop,
2969 // ideal_client_key.sk_rlwe.values(),
2970 // );
2971 // println!("Noise RLWE(carry_m) accumulating {i}^th secret
2972 // monomial: {noise}"); }
2973 // }
2974
2975 // // Check galois keys
2976 // if false {
2977 // let g = bool_evaluator.g() as isize;
2978 // let mut rng = DefaultSecureRng::new();
2979 // let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n];
2980 // d_rgsw + 2]; for i in [g, -g] {
2981 // let mut m = vec![0u64; rlwe_n];
2982 // RandomUniformDist::random_fill(&mut rng, &rlwe_q,
2983 // m.as_mut_slice()); let mut rlwe_ct = {
2984 // let mut data = vec![vec![0u64; rlwe_n]; 2];
2985 // public_key_encrypt_rlwe(
2986 // &mut data,
2987 // &collective_pk.key,
2988 // &m,
2989 // rlwe_modop,
2990 // rlwe_nttop,
2991 // &mut rng,
2992 // );
2993 // RlweCiphertext::<_, DefaultSecureRng>::from_raw(data,
2994 // false) };
2995
2996 // let auto_key = server_key_eval.galois_key_for_auto(i);
2997 // let (auto_map_index, auto_map_sign) =
2998 // generate_auto_map(rlwe_n, i); galois_auto(
2999 // &mut rlwe_ct,
3000 // auto_key,
3001 // &mut scratch_matrix_dplus2_ring,
3002 // &auto_map_index,
3003 // &auto_map_sign,
3004 // rlwe_modop,
3005 // rlwe_nttop,
3006 // rlwe_decomposer,
3007 // );
3008
3009 // // send m(X) -> m(X^i)
3010 // let mut m_k = vec![0u64; rlwe_n];
3011 // izip!(m.iter(), auto_map_index.iter(),
3012 // auto_map_sign.iter()).for_each( |(mi, to_index, to_sign)|
3013 // { if !to_sign {
3014 // m_k[*to_index] = rlwe_q - *mi;
3015 // } else {
3016 // m_k[*to_index] = *mi;
3017 // }
3018 // },
3019 // );
3020
3021 // // measure noise
3022 // let noise = measure_noise(
3023 // &rlwe_ct,
3024 // &m_k,
3025 // rlwe_nttop,
3026 // rlwe_modop,
3027 // ideal_client_key.sk_rlwe.values(),
3028 // );
3029
3030 // println!("Noise after auto k={i}: {noise}");
3031 // }
3032 // }
3033 }
3034
3035 fn test_2() {
3036 let bool_evaluator =
3037 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
3038 }
3039}