phantom-zone/src/bool/evaluator.rs
src/bool/evaluator.rsRaw
1use std::{
2 cell::RefCell,
3 collections::HashMap,
4 fmt::{Debug, Display},
5 hash::Hash,
6 marker::PhantomData,
7 thread::panicking,
8};
9
10use itertools::{izip, partition, Itertools};
11use num_traits::{FromPrimitive, Num, One, PrimInt, ToPrimitive, WrappingSub, Zero};
12
13use crate::{
14 backend::{ArithmeticOps, ModInit, ModularOpsU64, VectorOps},
15 decomposer::{gadget_vector, Decomposer, DefaultDecomposer, NumInfo},
16 lwe::{decrypt_lwe, encrypt_lwe, lwe_key_switch, lwe_ksk_keygen, measure_noise_lwe, LweSecret},
17 multi_party::public_key_share,
18 ntt::{self, Ntt, NttBackendU64, NttInit},
19 random::{DefaultSecureRng, NewWithSeed, RandomGaussianDist, RandomUniformDist},
20 rgsw::{
21 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, public_key_encrypt_rgsw,
22 rgsw_by_rgsw_inplace, rlwe_by_rgsw, secret_key_encrypt_rgsw, IsTrivial, RlweCiphertext,
23 RlweSecret,
24 },
25 utils::{
26 fill_random_ternary_secret_with_hamming_weight, generate_prime, mod_exponent,
27 TryConvertFrom, WithLocal,
28 },
29 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut, Secret,
30};
31
32use super::parameters::{self, BoolParameters};
33
34// thread_local! {
35// pub(crate) static CLIENT_KEY: RefCell<ClientKey> =
36// RefCell::new(ClientKey::random()); }
37
38trait PbsKey {
39 type M: Matrix;
40
41 /// RGSW ciphertext of LWE secret elements
42 fn rgsw_ct_lwe_si(&self, si: usize) -> &Self::M;
43 /// Key for automorphism
44 fn galois_key_for_auto(&self, k: isize) -> &Self::M;
45 /// LWE ksk to key switch from RLWE secret to LWE secret
46 fn lwe_ksk(&self) -> &Self::M;
47}
48trait PbsParameters {
49 type Element;
50 type D: Decomposer<Element = Self::Element>;
51 fn rlwe_q(&self) -> Self::Element;
52 fn lwe_q(&self) -> Self::Element;
53 fn br_q(&self) -> usize;
54 fn d_rgsw(&self) -> usize;
55 fn d_lwe(&self) -> usize;
56 fn rlwe_n(&self) -> usize;
57 fn lwe_n(&self) -> usize;
58 /// Embedding fator for ring X^{q}+1 inside
59 fn embedding_factor(&self) -> usize;
60 /// generator g
61 fn g(&self) -> isize;
62 fn decomoposer_lwe(&self) -> &Self::D;
63 fn decomoposer_rlwe(&self) -> &Self::D;
64
65 /// Maps a \in Z^*_{q} to discrete log k, with generator g (i.e. g^k =
66 /// a). Returned vector is of size q that stores dlog of a at `vec[a]`.
67 /// For any a, if k is s.t. a = g^{k}, then k is expressed as k. If k is s.t
68 /// a = -g^{k}, then k is expressed as k=k+q/2
69 fn g_k_dlog_map(&self) -> &[usize];
70 fn rlwe_auto_map(&self, k: isize) -> &(Vec<usize>, Vec<bool>);
71}
72
73#[derive(Clone)]
74struct ClientKey {
75 sk_rlwe: RlweSecret,
76 sk_lwe: LweSecret,
77}
78
79impl ClientKey {
80 fn random() -> Self {
81 let sk_rlwe = RlweSecret::random(0, 0);
82 let sk_lwe = LweSecret::random(0, 0);
83 Self { sk_rlwe, sk_lwe }
84 }
85}
86
87// impl WithLocal for ClientKey {
88// fn with_local<F, R>(func: F) -> R
89// where
90// F: Fn(&Self) -> R,
91// {
92// CLIENT_KEY.with_borrow(|client_key| func(client_key))
93// }
94
95// fn with_local_mut<F, R>(func: F) -> R
96// where
97// F: Fn(&mut Self) -> R,
98// {
99// CLIENT_KEY.with_borrow_mut(|client_key| func(client_key))
100// }
101// }
102
103// fn set_client_key(key: &ClientKey) {
104// ClientKey::with_local_mut(|k| *k = key.clone())
105// }
106
107struct MultiPartyDecryptionShare<E> {
108 share: E,
109}
110
111struct CommonReferenceSeededCollectivePublicKeyShare<R, S, P> {
112 share: R,
113 cr_seed: S,
114 parameters: P,
115}
116
117struct PublicKey<M, R, O> {
118 key: M,
119 _phantom: PhantomData<(R, O)>,
120}
121
122impl<
123 M: MatrixMut + MatrixEntity,
124 Rng: NewWithSeed + RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
125 ModOp: VectorOps<Element = M::MatElement> + ModInit<Element = M::MatElement>,
126 >
127 From<
128 &[CommonReferenceSeededCollectivePublicKeyShare<
129 M::R,
130 Rng::Seed,
131 BoolParameters<M::MatElement>,
132 >],
133 > for PublicKey<M, Rng, ModOp>
134where
135 <M as Matrix>::R: RowMut,
136 Rng::Seed: Copy + PartialEq,
137 M::MatElement: PartialEq + Copy,
138{
139 fn from(
140 value: &[CommonReferenceSeededCollectivePublicKeyShare<
141 M::R,
142 Rng::Seed,
143 BoolParameters<M::MatElement>,
144 >],
145 ) -> Self {
146 assert!(value.len() > 0);
147
148 let parameters = &value[0].parameters;
149 let mut key = M::zeros(2, parameters.rlwe_n);
150
151 // sample A
152 let seed = value[0].cr_seed;
153 let mut main_rng = Rng::new_with_seed(seed);
154 RandomUniformDist::random_fill(&mut main_rng, ¶meters.rlwe_q, key.get_row_mut(0));
155
156 // Sum all Bs
157 let rlweq_modop = ModOp::new(parameters.rlwe_q);
158 value.iter().for_each(|share_i| {
159 assert!(share_i.cr_seed == seed);
160 assert!(&share_i.parameters == parameters);
161
162 rlweq_modop.elwise_add_mut(key.get_row_mut(1), share_i.share.as_ref());
163 });
164
165 PublicKey {
166 key,
167 _phantom: PhantomData,
168 }
169 }
170}
171
172struct CommonReferenceSeededMultiPartyServerKeyShare<M: Matrix, P, S> {
173 rgsw_cts: Vec<M>,
174 auto_keys: HashMap<isize, M>,
175 lwe_ksk: M::R,
176 /// Common reference seed
177 cr_seed: S,
178 parameters: P,
179}
180struct SeededMultiPartyServerKey<M: Matrix, S, P> {
181 rgsw_cts: Vec<M>,
182 auto_keys: HashMap<isize, M>,
183 lwe_ksk: M::R,
184 cr_seed: S,
185 parameters: P,
186}
187
188fn aggregate_multi_party_server_key_shares<
189 M: MatrixMut + MatrixEntity,
190 S: Copy + PartialEq,
191 D: Decomposer<Element = M::MatElement>,
192 ModOp: VectorOps<Element = M::MatElement> + ModInit<Element = M::MatElement>,
193 NttOp: Ntt<Element = M::MatElement> + NttInit<Element = M::MatElement>,
194>(
195 mut shares: &[CommonReferenceSeededMultiPartyServerKeyShare<
196 M,
197 BoolParameters<M::MatElement>,
198 S,
199 >],
200 d_rgsw_decomposer: &D,
201) -> SeededMultiPartyServerKey<M, S, BoolParameters<M::MatElement>>
202where
203 <M as Matrix>::R: RowMut + RowEntity,
204 M::MatElement: Copy + PartialEq + Zero,
205 M: Clone,
206{
207 assert!(shares.len() > 0);
208 let parameters = shares[0].parameters.clone();
209 let cr_seed = shares[0].cr_seed;
210
211 let rlwe_n = parameters.rlwe_n;
212 let g = parameters.g as isize;
213 let d_rgsw = parameters.d_rgsw;
214 let d_lwe = parameters.d_lwe;
215 let rlwe_q = parameters.rlwe_q;
216 let lwe_q = parameters.lwe_q;
217
218 // sanity checks
219 shares.iter().skip(1).for_each(|s| {
220 assert!(s.parameters == parameters);
221 assert!(s.cr_seed == cr_seed);
222 });
223
224 let rlweq_modop = ModOp::new(rlwe_q);
225 let rlweq_nttop = NttOp::new(rlwe_q, rlwe_n);
226
227 // auto keys
228 let mut auto_keys = HashMap::new();
229 for i in [g, -g] {
230 let mut key = M::zeros(d_rgsw, rlwe_n);
231
232 shares.iter().for_each(|s| {
233 let auto_key_share_i = s.auto_keys.get(&i).expect("Auto key {i} missing");
234 assert!(auto_key_share_i.dimension() == (d_rgsw, rlwe_n));
235 izip!(key.iter_rows_mut(), auto_key_share_i.iter_rows()).for_each(
236 |(partb_out, partb_share)| {
237 rlweq_modop.elwise_add_mut(partb_out.as_mut(), partb_share.as_ref());
238 },
239 );
240 });
241
242 auto_keys.insert(i, key);
243 }
244
245 // rgsw ciphertext (most expensive part!)
246 let lwe_n = parameters.lwe_n;
247 let mut scratch_d_plus_rgsw_by_ring = M::zeros(d_rgsw + (d_rgsw * 4), rlwe_n);
248 let mut tmp_rgsw = M::zeros(d_rgsw * 2 * 2, rlwe_n);
249 let rgsw_cts = (0..lwe_n)
250 .into_iter()
251 .map(|index| {
252 // copy over rgsw ciphertext for index^th secret element from first share and
253 // treat it as accumulating rgsw ciphertext
254 let mut rgsw_i = shares[0].rgsw_cts[index].clone();
255
256 shares.iter().skip(1).for_each(|si| {
257 // copy over si's RGSW[index] ciphertext and send to evaluation domain
258 izip!(tmp_rgsw.iter_rows_mut(), si.rgsw_cts[index].iter_rows()).for_each(
259 |(to_ri, from_ri)| {
260 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
261 rlweq_nttop.forward(to_ri.as_mut())
262 },
263 );
264
265 rgsw_by_rgsw_inplace(
266 &mut rgsw_i,
267 &tmp_rgsw,
268 d_rgsw_decomposer,
269 &mut scratch_d_plus_rgsw_by_ring,
270 &rlweq_nttop,
271 &rlweq_modop,
272 );
273 });
274
275 rgsw_i
276 })
277 .collect_vec();
278
279 // LWE ksks
280 let mut lwe_ksk = M::R::zeros(rlwe_n * d_lwe);
281 let lweq_modop = ModOp::new(lwe_q);
282 shares.iter().for_each(|si| {
283 assert!(si.lwe_ksk.as_ref().len() == rlwe_n * d_lwe);
284 lweq_modop.elwise_add_mut(lwe_ksk.as_mut(), si.lwe_ksk.as_ref())
285 });
286
287 SeededMultiPartyServerKey {
288 rgsw_cts,
289 auto_keys,
290 lwe_ksk,
291 cr_seed,
292 parameters: parameters,
293 }
294}
295
296struct SeededServerKey<M: Matrix, P, S> {
297 /// Rgsw cts of LWE secret elements
298 rgsw_cts: Vec<M>,
299 /// Auto keys
300 auto_keys: HashMap<isize, M>,
301 /// LWE ksk to key switching LWE ciphertext from RLWE secret to LWE secret
302 lwe_ksk: M::R,
303 /// Parameters
304 parameters: P,
305 /// Main seed
306 seed: S,
307}
308
309impl<M: Matrix, S> SeededServerKey<M, BoolParameters<M::MatElement>, S> {
310 pub(crate) fn from_raw(
311 auto_keys: HashMap<isize, M>,
312 rgsw_cts: Vec<M>,
313 lwe_ksk: M::R,
314 parameters: BoolParameters<M::MatElement>,
315 seed: S,
316 ) -> Self {
317 // sanity checks
318 auto_keys
319 .iter()
320 .for_each(|v| assert!(v.1.dimension() == (parameters.d_rgsw, parameters.rlwe_n)));
321 rgsw_cts
322 .iter()
323 .for_each(|v| assert!(v.dimension() == (parameters.d_rgsw * 3, parameters.rlwe_n)));
324 assert!(lwe_ksk.as_ref().len() == (parameters.d_lwe * parameters.rlwe_n));
325
326 SeededServerKey {
327 rgsw_cts,
328 auto_keys,
329 lwe_ksk,
330 parameters,
331 seed,
332 }
333 }
334}
335
336struct ServerKeyEvaluationDomain<M, R, N> {
337 /// Rgsw cts of LWE secret elements
338 rgsw_cts: Vec<M>,
339 /// Galois keys
340 galois_keys: HashMap<isize, M>,
341 /// LWE ksk to key switching LWE ciphertext from RLWE secret to LWE secret
342 lwe_ksk: M,
343 _phanton: PhantomData<(R, N)>,
344}
345
346impl<
347 M: MatrixMut + MatrixEntity,
348 R: RandomUniformDist<[M::MatElement], Parameters = M::MatElement> + NewWithSeed,
349 N: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement>,
350 > From<&SeededServerKey<M, BoolParameters<M::MatElement>, R::Seed>>
351 for ServerKeyEvaluationDomain<M, R, N>
352where
353 <M as Matrix>::R: RowMut,
354 M::MatElement: Copy,
355 R::Seed: Clone,
356{
357 fn from(value: &SeededServerKey<M, BoolParameters<M::MatElement>, R::Seed>) -> Self {
358 let mut main_prng = R::new_with_seed(value.seed.clone());
359
360 let g = value.parameters.g as isize;
361 let ring_size = value.parameters.rlwe_n;
362 let lwe_n = value.parameters.lwe_n;
363 let d_rgsw = value.parameters.d_rgsw;
364 let d_lwe = value.parameters.d_lwe;
365 let rlwe_q = value.parameters.rlwe_q;
366 let lwq_q = value.parameters.lwe_q;
367
368 let nttop = N::new(rlwe_q, ring_size);
369
370 // galois keys
371 let mut auto_keys = HashMap::new();
372 for i in [g, -g] {
373 let seeded_auto_key = value.auto_keys.get(&i).unwrap();
374 assert!(seeded_auto_key.dimension() == (d_rgsw, ring_size));
375
376 let mut data = M::zeros(d_rgsw * 2, ring_size);
377
378 // sample RLWE'_A(-s(X^k))
379 data.iter_rows_mut().take(d_rgsw).for_each(|ri| {
380 RandomUniformDist::random_fill(&mut main_prng, &rlwe_q, ri.as_mut())
381 });
382
383 // copy over RLWE'B_(-s(X^k))
384 izip!(
385 data.iter_rows_mut().skip(d_rgsw),
386 seeded_auto_key.iter_rows()
387 )
388 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
389
390 // Send to Evaluation domain
391 data.iter_rows_mut()
392 .for_each(|ri| nttop.forward(ri.as_mut()));
393
394 auto_keys.insert(i, data);
395 }
396
397 // RGSW ciphertexts
398 let rgsw_cts = value
399 .rgsw_cts
400 .iter()
401 .map(|seeded_rgsw_si| {
402 assert!(seeded_rgsw_si.dimension() == (3 * d_rgsw, ring_size));
403
404 let mut data = M::zeros(d_rgsw * 4, ring_size);
405
406 // copy over RLWE'(-sm)
407 izip!(
408 data.iter_rows_mut().take(d_rgsw * 2),
409 seeded_rgsw_si.iter_rows().take(d_rgsw * 2)
410 )
411 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
412
413 // sample RLWE'_A(m)
414 data.iter_rows_mut()
415 .skip(2 * d_rgsw)
416 .take(d_rgsw)
417 .for_each(|ri| {
418 RandomUniformDist::random_fill(&mut main_prng, &rlwe_q, ri.as_mut())
419 });
420
421 // copy over RLWE'_B(m)
422 izip!(
423 data.iter_rows_mut().skip(d_rgsw * 3),
424 seeded_rgsw_si.iter_rows().skip(d_rgsw * 2)
425 )
426 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
427
428 // send polynomials to evaluation domain
429 data.iter_rows_mut()
430 .for_each(|ri| nttop.forward(ri.as_mut()));
431
432 data
433 })
434 .collect_vec();
435
436 // LWE ksk
437 let lwe_ksk = {
438 assert!(value.lwe_ksk.as_ref().len() == d_lwe * ring_size);
439
440 let mut data = M::zeros(d_lwe * ring_size, lwe_n + 1);
441 izip!(data.iter_rows_mut(), value.lwe_ksk.as_ref().iter()).for_each(|(lwe_i, bi)| {
442 RandomUniformDist::random_fill(&mut main_prng, &lwq_q, &mut lwe_i.as_mut()[1..]);
443 lwe_i.as_mut()[0] = *bi;
444 });
445
446 data
447 };
448
449 ServerKeyEvaluationDomain {
450 rgsw_cts,
451 galois_keys: auto_keys,
452 lwe_ksk,
453 _phanton: PhantomData,
454 }
455 }
456}
457
458impl<
459 M: MatrixMut + MatrixEntity,
460 Rng: NewWithSeed,
461 N: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement>,
462 > From<&SeededMultiPartyServerKey<M, Rng::Seed, BoolParameters<M::MatElement>>>
463 for ServerKeyEvaluationDomain<M, Rng, N>
464where
465 <M as Matrix>::R: RowMut,
466 Rng::Seed: Copy,
467 Rng: RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
468 M::MatElement: Copy,
469{
470 fn from(
471 value: &SeededMultiPartyServerKey<M, Rng::Seed, BoolParameters<M::MatElement>>,
472 ) -> Self {
473 let g = value.parameters.g as isize;
474 let rlwe_n = value.parameters.rlwe_n;
475 let lwe_n = value.parameters.lwe_n;
476 let rlwe_q = value.parameters.rlwe_q;
477 let lwe_q = value.parameters.lwe_q;
478 let d_rgsw = value.parameters.d_rgsw;
479
480 let mut main_prng = Rng::new_with_seed(value.cr_seed);
481
482 let rlwe_nttop = N::new(rlwe_q, rlwe_n);
483
484 // auto keys
485 let mut auto_keys = HashMap::new();
486 for i in [g, -g] {
487 let mut key = M::zeros(value.parameters.d_rgsw * 2, rlwe_n);
488
489 // sample a
490 key.iter_rows_mut().take(d_rgsw).for_each(|ri| {
491 RandomUniformDist::random_fill(&mut main_prng, &rlwe_q, ri.as_mut())
492 });
493
494 let key_part_b = value.auto_keys.get(&i).unwrap();
495 assert!(key_part_b.dimension() == (d_rgsw, rlwe_n));
496 izip!(key.iter_rows_mut().skip(d_rgsw), key_part_b.iter_rows()).for_each(
497 |(to_ri, from_ri)| {
498 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
499 },
500 );
501
502 // send to evaluation domain
503 key.iter_rows_mut()
504 .for_each(|ri| rlwe_nttop.forward(ri.as_mut()));
505
506 auto_keys.insert(i, key);
507 }
508
509 // rgsw cts
510 let rgsw_cts = value
511 .rgsw_cts
512 .iter()
513 .map(|ct_i| {
514 let mut eval_ct_i = M::zeros(d_rgsw * 4, rlwe_n);
515
516 izip!(eval_ct_i.iter_rows_mut(), ct_i.iter_rows()).for_each(|(to_ri, from_ri)| {
517 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
518 rlwe_nttop.forward(to_ri.as_mut());
519 });
520
521 eval_ct_i
522 })
523 .collect_vec();
524
525 // lwe ksk
526 let d_lwe = value.parameters.d_lwe;
527 let mut lwe_ksk = M::zeros(rlwe_n * d_lwe, lwe_n + 1);
528 izip!(lwe_ksk.iter_rows_mut(), value.lwe_ksk.as_ref().iter()).for_each(|(lwe_i, bi)| {
529 RandomUniformDist::random_fill(&mut main_prng, &lwe_q, &mut lwe_i.as_mut()[1..]);
530 lwe_i.as_mut()[0] = *bi;
531 });
532
533 ServerKeyEvaluationDomain {
534 rgsw_cts,
535 galois_keys: auto_keys,
536 lwe_ksk,
537 _phanton: PhantomData,
538 }
539 }
540}
541
542//FIXME(Jay): Figure out a way for BoolEvaluator to have access to ServerKey
543// via a pointer and implement PbsKey for BoolEvaluator instead of ServerKey
544// directly
545impl<M: Matrix, R, N> PbsKey for ServerKeyEvaluationDomain<M, R, N> {
546 type M = M;
547 fn galois_key_for_auto(&self, k: isize) -> &Self::M {
548 self.galois_keys.get(&k).unwrap()
549 }
550 fn rgsw_ct_lwe_si(&self, si: usize) -> &Self::M {
551 &self.rgsw_cts[si]
552 }
553
554 fn lwe_ksk(&self) -> &Self::M {
555 &self.lwe_ksk
556 }
557}
558
559struct BoolEvaluator<M, E, Ntt, ModOp>
560where
561 M: Matrix,
562{
563 parameters: BoolParameters<E>,
564 decomposer_rlwe: DefaultDecomposer<E>,
565 decomposer_lwe: DefaultDecomposer<E>,
566 g_k_dlog_map: Vec<usize>,
567 rlwe_nttop: Ntt,
568 rlwe_modop: ModOp,
569 lwe_modop: ModOp,
570 embedding_factor: usize,
571 nand_test_vec: M::R,
572 rlweq_by8: M::MatElement,
573 rlwe_auto_maps: Vec<(Vec<usize>, Vec<bool>)>,
574 _phantom: PhantomData<M>,
575}
576
577impl<M, NttOp, ModOp> BoolEvaluator<M, M::MatElement, NttOp, ModOp>
578where
579 NttOp: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement>,
580 ModOp: ModInit<Element = M::MatElement>
581 + ArithmeticOps<Element = M::MatElement>
582 + VectorOps<Element = M::MatElement>,
583 M::MatElement: PrimInt + Debug + Display + NumInfo + FromPrimitive + WrappingSub,
584 M: MatrixEntity + MatrixMut,
585 M::R: TryConvertFrom<[i32], Parameters = M::MatElement> + RowEntity,
586 M: TryConvertFrom<[i32], Parameters = M::MatElement>,
587 <M as Matrix>::R: RowMut,
588 DefaultSecureRng: RandomGaussianDist<[M::MatElement], Parameters = M::MatElement>
589 + RandomGaussianDist<M::MatElement, Parameters = M::MatElement>
590 + RandomUniformDist<[M::MatElement], Parameters = M::MatElement>
591 + NewWithSeed,
592{
593 fn new(parameters: BoolParameters<M::MatElement>) -> Self {
594 //TODO(Jay): Run sanity checks for modulus values in parameters
595 assert!(parameters.br_q.is_power_of_two());
596
597 let decomposer_rlwe =
598 DefaultDecomposer::new(parameters.rlwe_q, parameters.logb_rgsw, parameters.d_rgsw);
599 let decomposer_lwe =
600 DefaultDecomposer::new(parameters.lwe_q, parameters.logb_lwe, parameters.d_lwe);
601
602 // generatr dlog map s.t. g^{k} % q = a, for all a \in Z*_{q}
603 let g = parameters.g;
604 let q = parameters.br_q;
605 let mut g_k_dlog_map = vec![0usize; q];
606 for i in 0..q / 2 {
607 let v = mod_exponent(g as u64, i as u64, q as u64) as usize;
608 // g^i
609 g_k_dlog_map[v] = i;
610 // -(g^i)
611 g_k_dlog_map[q - v] = i + (q / 2);
612 }
613
614 let embedding_factor = (2 * parameters.rlwe_n) / q;
615
616 let rlwe_nttop = NttOp::new(parameters.rlwe_q, parameters.rlwe_n);
617 let rlwe_modop = ModInit::new(parameters.rlwe_q);
618 let lwe_modop = ModInit::new(parameters.lwe_q);
619
620 // set test vectors
621 let el_one = M::MatElement::one();
622 let nand_map = |index: usize, qby8: usize| {
623 if index < (3 * qby8) {
624 true
625 } else {
626 false
627 }
628 };
629
630 let q = parameters.br_q;
631 let qby2 = q >> 1;
632 let qby8 = q >> 3;
633 let qby16 = q >> 4;
634 let mut nand_test_vec = M::R::zeros(qby2);
635 // Q/8 (Q: rlwe_q)
636 let rlwe_qby8 =
637 M::MatElement::from_f64((parameters.rlwe_q.to_f64().unwrap() / 8.0).round()).unwrap();
638 let true_m_el = rlwe_qby8;
639 // -Q/8
640 let false_m_el = parameters.rlwe_q - rlwe_qby8;
641 for i in 0..qby2 {
642 let v = nand_map(i, qby8);
643 if v {
644 nand_test_vec.as_mut()[i] = true_m_el;
645 } else {
646 nand_test_vec.as_mut()[i] = false_m_el;
647 }
648 }
649 // Rotate and negate by q/16
650 let mut tmp = M::R::zeros(qby2);
651 tmp.as_mut()[..qby2 - qby16].copy_from_slice(&nand_test_vec.as_ref()[qby16..]);
652 tmp.as_mut()[qby2 - qby16..].copy_from_slice(&nand_test_vec.as_ref()[..qby16]);
653 tmp.as_mut()[qby2 - qby16..].iter_mut().for_each(|v| {
654 *v = parameters.rlwe_q - *v;
655 });
656 let nand_test_vec = tmp;
657
658 // v(X) -> v(X^{-g})
659 let (auto_map_index, auto_map_sign) = generate_auto_map(qby2, -(g as isize));
660 let mut nand_test_vec_autog = M::R::zeros(qby2);
661 izip!(
662 nand_test_vec.as_ref().iter(),
663 auto_map_index.iter(),
664 auto_map_sign.iter()
665 )
666 .for_each(|(v, to_index, to_sign)| {
667 if !to_sign {
668 // negate
669 nand_test_vec_autog.as_mut()[*to_index] = parameters.rlwe_q - *v;
670 } else {
671 nand_test_vec_autog.as_mut()[*to_index] = *v;
672 }
673 });
674
675 // auto map indices and sign
676 let mut rlwe_auto_maps = vec![];
677 let ring_size = parameters.rlwe_n;
678 let g = parameters.g as isize;
679 for i in [g, -g] {
680 rlwe_auto_maps.push(generate_auto_map(ring_size, i))
681 }
682
683 BoolEvaluator {
684 parameters: parameters,
685 decomposer_lwe,
686 decomposer_rlwe,
687 g_k_dlog_map,
688 embedding_factor,
689 lwe_modop,
690 rlwe_modop,
691 rlwe_nttop,
692 nand_test_vec: nand_test_vec_autog,
693 rlweq_by8: rlwe_qby8,
694 rlwe_auto_maps,
695
696 _phantom: PhantomData,
697 }
698 }
699
700 fn client_key(&self) -> ClientKey {
701 let sk_lwe = LweSecret::random(self.parameters.lwe_n >> 1, self.parameters.lwe_n);
702 let sk_rlwe = RlweSecret::random(self.parameters.rlwe_n >> 1, self.parameters.rlwe_n);
703 ClientKey { sk_rlwe, sk_lwe }
704 }
705
706 fn server_key(
707 &self,
708 client_key: &ClientKey,
709 ) -> SeededServerKey<M, BoolParameters<M::MatElement>, [u8; 32]> {
710 DefaultSecureRng::with_local_mut(|rng| {
711 let mut main_seed = [0u8; 32];
712 rng.fill_bytes(&mut main_seed);
713
714 let mut main_prng = DefaultSecureRng::new_seeded(main_seed);
715
716 let sk_rlwe = &client_key.sk_rlwe;
717 let sk_lwe = &client_key.sk_lwe;
718
719 let d_rgsw_gadget_vec = gadget_vector(
720 self.parameters.rlwe_logq,
721 self.parameters.logb_rgsw,
722 self.parameters.d_rgsw,
723 );
724
725 // generate auto keys -g, g
726 let mut auto_keys = HashMap::new();
727 let g = self.parameters.g as isize;
728 for i in [g, -g] {
729 let mut gk = M::zeros(self.parameters.d_rgsw, self.parameters.rlwe_n);
730 galois_key_gen(
731 &mut gk,
732 sk_rlwe.values(),
733 i,
734 &d_rgsw_gadget_vec,
735 &self.rlwe_modop,
736 &self.rlwe_nttop,
737 &mut main_prng,
738 rng,
739 );
740 auto_keys.insert(i, gk);
741 }
742
743 // generate rgsw ciphertexts RGSW(si) where si is i^th LWE secret element
744 let ring_size = self.parameters.rlwe_n;
745 let rlwe_q = self.parameters.rlwe_q;
746 let rgsw_cts = sk_lwe
747 .values()
748 .iter()
749 .map(|si| {
750 // X^{si}; assume |emebedding_factor * si| < N
751 let mut m = M::R::zeros(ring_size);
752 let si = (self.embedding_factor as i32) * si;
753 // dbg!(si);
754 if si < 0 {
755 // X^{-i} = X^{2N - i} = -X^{N-i}
756 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q - M::MatElement::one();
757 } else {
758 // X^{i}
759 m.as_mut()[si.abs() as usize] = M::MatElement::one();
760 }
761
762 let mut rgsw_si = M::zeros(self.parameters.d_rgsw * 3, ring_size);
763 secret_key_encrypt_rgsw(
764 &mut rgsw_si,
765 m.as_ref(),
766 &d_rgsw_gadget_vec,
767 sk_rlwe.values(),
768 &self.rlwe_modop,
769 &self.rlwe_nttop,
770 &mut main_prng,
771 rng,
772 );
773
774 rgsw_si
775 })
776 .collect_vec();
777
778 // LWE KSK from RLWE secret s -> LWE secret z
779 let d_lwe_gadget = gadget_vector(
780 self.parameters.lwe_logq,
781 self.parameters.logb_lwe,
782 self.parameters.d_lwe,
783 );
784
785 let mut lwe_ksk = M::R::zeros(self.parameters.d_lwe * ring_size);
786 lwe_ksk_keygen(
787 &sk_rlwe.values(),
788 &sk_lwe.values(),
789 &mut lwe_ksk,
790 &d_lwe_gadget,
791 &self.lwe_modop,
792 &mut main_prng,
793 rng,
794 );
795
796 SeededServerKey::from_raw(
797 auto_keys,
798 rgsw_cts,
799 lwe_ksk,
800 self.parameters.clone(),
801 main_seed,
802 )
803 })
804 }
805
806 fn multi_party_sever_key_share(
807 &self,
808 cr_seed: [u8; 32],
809 collective_pk: &M,
810 client_key: &ClientKey,
811 ) -> CommonReferenceSeededMultiPartyServerKeyShare<M, BoolParameters<M::MatElement>, [u8; 32]>
812 {
813 DefaultSecureRng::with_local_mut(|rng| {
814 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
815
816 let sk_rlwe = &client_key.sk_rlwe;
817 let sk_lwe = &client_key.sk_lwe;
818
819 let g = self.parameters.g as isize;
820 let ring_size = self.parameters.rlwe_n;
821 let d_rgsw = self.parameters.d_rgsw;
822 let d_lwe = self.parameters.d_lwe;
823 let rlwe_q = self.parameters.rlwe_q;
824 let lwe_q = self.parameters.lwe_q;
825
826 let d_rgsw_gadget_vec =
827 gadget_vector(self.parameters.rlwe_logq, self.parameters.logb_rgsw, d_rgsw);
828
829 let rlweq_modop = ModOp::new(rlwe_q);
830 let rlweq_nttop = NttOp::new(rlwe_q, ring_size);
831
832 // sanity check
833 assert!(sk_rlwe.values().len() == ring_size);
834 assert!(sk_lwe.values().len() == self.parameters.lwe_n);
835
836 // auto keys
837 let mut auto_keys = HashMap::new();
838 for i in [g, -g] {
839 let mut ksk_out = M::zeros(d_rgsw, ring_size);
840 galois_key_gen(
841 &mut ksk_out,
842 sk_rlwe.values(),
843 i,
844 &d_rgsw_gadget_vec,
845 &rlweq_modop,
846 &rlweq_nttop,
847 &mut main_prng,
848 rng,
849 );
850 auto_keys.insert(i, ksk_out);
851 }
852
853 // rgsw ciphertexts of lwe secret elements
854 let rgsw_cts = sk_lwe
855 .values()
856 .iter()
857 .map(|si| {
858 let mut m = M::R::zeros(ring_size);
859
860 if *si < 0 {
861 // X^{-si} = X^{2N-si} = -X^{N-si}, assuming abs(si) < N
862 // (which it is given si is secret element)
863 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q - M::MatElement::one();
864 } else {
865 m.as_mut()[*si as usize] = M::MatElement::one();
866 }
867
868 // public key RGSW encryption has no part that can be seeded, unlike secret key
869 // RGSW encryption where RLWE'_A(m) is seeded
870 let mut out_rgsw = M::zeros(d_rgsw * 4, ring_size);
871 public_key_encrypt_rgsw(
872 &mut out_rgsw,
873 &m.as_ref(),
874 collective_pk,
875 &d_rgsw_gadget_vec,
876 &rlweq_modop,
877 &rlweq_nttop,
878 rng,
879 );
880
881 out_rgsw
882 })
883 .collect_vec();
884
885 // LWE ksk
886 let mut lwe_ksk = M::R::zeros(d_lwe * ring_size);
887 let lwe_modop = ModOp::new(lwe_q);
888 let d_lwe_gadget_vec =
889 gadget_vector(self.parameters.lwe_logq, self.parameters.logb_lwe, d_lwe);
890 lwe_ksk_keygen(
891 sk_rlwe.values(),
892 sk_lwe.values(),
893 &mut lwe_ksk,
894 &d_lwe_gadget_vec,
895 &lwe_modop,
896 &mut main_prng,
897 rng,
898 );
899
900 CommonReferenceSeededMultiPartyServerKeyShare {
901 auto_keys,
902 rgsw_cts,
903 lwe_ksk,
904 cr_seed,
905 parameters: self.parameters.clone(),
906 }
907 })
908 }
909
910 fn multi_party_public_key_share(
911 &self,
912 cr_seed: [u8; 32],
913 client_key: &ClientKey,
914 ) -> CommonReferenceSeededCollectivePublicKeyShare<
915 <M as Matrix>::R,
916 [u8; 32],
917 BoolParameters<<M as Matrix>::MatElement>,
918 > {
919 DefaultSecureRng::with_local_mut(|rng| {
920 let mut share_out = M::R::zeros(self.parameters.rlwe_n);
921 let modop = ModOp::new(self.parameters.rlwe_q);
922 let nttop = NttOp::new(self.parameters.rlwe_q, self.parameters.rlwe_n);
923 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
924 public_key_share(
925 &mut share_out,
926 client_key.sk_rlwe.values(),
927 &modop,
928 &nttop,
929 &mut main_prng,
930 rng,
931 );
932
933 CommonReferenceSeededCollectivePublicKeyShare {
934 share: share_out,
935 cr_seed: cr_seed,
936 parameters: self.parameters.clone(),
937 }
938 })
939 }
940
941 fn multi_party_decryption_share(
942 &self,
943 lwe_ct: &M::R,
944 client_key: &ClientKey,
945 ) -> MultiPartyDecryptionShare<<M as Matrix>::MatElement> {
946 assert!(lwe_ct.as_ref().len() == self.parameters.rlwe_n + 1);
947 let modop = &self.rlwe_modop;
948 let mut neg_s =
949 M::R::try_convert_from(client_key.sk_rlwe.values(), &self.parameters.rlwe_q);
950 modop.elwise_neg_mut(neg_s.as_mut());
951
952 let mut neg_sa = M::MatElement::zero();
953 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
954 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
955 });
956
957 let e = DefaultSecureRng::with_local_mut(|rng| {
958 let mut e = M::MatElement::zero();
959 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, &mut e);
960 e
961 });
962 let share = modop.add(&neg_sa, &e);
963
964 MultiPartyDecryptionShare { share }
965 }
966
967 pub(crate) fn multi_party_decrypt(
968 &self,
969 shares: &[MultiPartyDecryptionShare<M::MatElement>],
970 lwe_ct: &M::R,
971 ) -> bool {
972 let modop = &self.rlwe_modop;
973 let mut sum_a = M::MatElement::zero();
974 shares
975 .iter()
976 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i.share));
977
978 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
979
980 let m = (((encoded_m + self.rlweq_by8).to_f64().unwrap() * 4f64)
981 / self.parameters.rlwe_q.to_f64().unwrap())
982 .round() as usize
983 % 4usize;
984
985 if m == 0 {
986 return false;
987 } else if m == 1 {
988 return true;
989 } else {
990 panic!("Bool decryption failure. Expected m to be either 1 or 0, but m={m} ");
991 }
992 }
993
994 /// First encrypt as RLWE(m) with m as constant polynomial and extract it as
995 /// LWE ciphertext
996 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
997 DefaultSecureRng::with_local_mut(|rng| {
998 let modop = &self.rlwe_modop;
999 let nttop = &self.rlwe_nttop;
1000
1001 // RLWE(0)
1002 // sample ephemeral key u
1003 let ring_size = self.parameters.rlwe_n;
1004 let mut u = vec![0i32; ring_size];
1005 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1006 let mut u = M::R::try_convert_from(&u, &self.parameters.rlwe_q);
1007 nttop.forward(u.as_mut());
1008
1009 let mut ua = M::R::zeros(ring_size);
1010 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1011 let mut ub = M::R::zeros(ring_size);
1012 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1013
1014 // a*u
1015 nttop.forward(ua.as_mut());
1016 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
1017 nttop.backward(ua.as_mut());
1018
1019 // b*u
1020 nttop.forward(ub.as_mut());
1021 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
1022 nttop.backward(ub.as_mut());
1023
1024 let mut rlwe = M::zeros(2, ring_size);
1025 // sample error
1026 rlwe.iter_rows_mut().for_each(|ri| {
1027 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, ri.as_mut());
1028 });
1029
1030 // a*u + e0
1031 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
1032 // b*u + e1
1033 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
1034
1035 let m = if m {
1036 // Q/8
1037 self.rlweq_by8
1038 } else {
1039 // -Q/8
1040 self.parameters.rlwe_q - self.rlweq_by8
1041 };
1042
1043 // b*u + e1 + m, where m is constant polynomial
1044 rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
1045
1046 // sample extract index 0
1047 let mut lwe_out = M::R::zeros(ring_size + 1);
1048 sample_extract(&mut lwe_out, &rlwe, modop, 0);
1049
1050 lwe_out
1051 })
1052 }
1053
1054 /// TODO(Jay): Fetch client key from thread local
1055 pub fn sk_encrypt(&self, m: bool, client_key: &ClientKey) -> M::R {
1056 let m = if m {
1057 // Q/8
1058 self.rlweq_by8
1059 } else {
1060 // -Q/8
1061 self.parameters.rlwe_q - self.rlweq_by8
1062 };
1063
1064 DefaultSecureRng::with_local_mut(|rng| {
1065 let mut lwe_out = M::R::zeros(self.parameters.rlwe_n + 1);
1066 encrypt_lwe(
1067 &mut lwe_out,
1068 &m,
1069 client_key.sk_rlwe.values(),
1070 &self.rlwe_modop,
1071 rng,
1072 );
1073 lwe_out
1074 })
1075 }
1076
1077 pub fn sk_decrypt(&self, lwe_ct: &M::R, client_key: &ClientKey) -> bool {
1078 let m = decrypt_lwe(lwe_ct, client_key.sk_rlwe.values(), &self.rlwe_modop);
1079 let m = {
1080 // m + q/8 => {0,q/4 1}
1081 (((m + self.rlweq_by8).to_f64().unwrap() * 4.0)
1082 / self.parameters.rlwe_q.to_f64().unwrap())
1083 .round()
1084 .to_usize()
1085 .unwrap()
1086 % 4
1087 };
1088
1089 if m == 0 {
1090 false
1091 } else if m == 1 {
1092 true
1093 } else {
1094 panic!("Incorrect bool decryption. Got m={m} but expected m to be 0 or 1")
1095 }
1096 }
1097
1098 // TODO(Jay): scratch spaces must be thread local. Don't pass them as arguments
1099 pub fn nand(
1100 &self,
1101 c0: &M::R,
1102 c1: &M::R,
1103 server_key: &ServerKeyEvaluationDomain<M, DefaultSecureRng, NttOp>,
1104 scratch_lwen_plus1: &mut M::R,
1105 scratch_matrix_dplus2_ring: &mut M,
1106 ) -> M::R {
1107 // ClientKey::with_local(|ck| {
1108 // let c0_noise = measure_noise_lwe(
1109 // c0,
1110 // ck.sk_rlwe.values(),
1111 // &self.rlwe_modop,
1112 // &(self.rlwe_q() - self.rlweq_by8),
1113 // );
1114 // let c1_noise =
1115 // measure_noise_lwe(c1, ck.sk_rlwe.values(), &self.rlwe_modop,
1116 // &(self.rlweq_by8)); println!("c0 noise: {c0_noise}; c1 noise:
1117 // {c1_noise}"); });
1118
1119 let mut c_out = M::R::zeros(c0.as_ref().len());
1120 let modop = &self.rlwe_modop;
1121 izip!(
1122 c_out.as_mut().iter_mut(),
1123 c0.as_ref().iter(),
1124 c1.as_ref().iter()
1125 )
1126 .for_each(|(o, i0, i1)| {
1127 *o = modop.add(i0, i1);
1128 });
1129 // +Q/8
1130 c_out.as_mut()[0] = modop.add(&c_out.as_ref()[0], &self.rlweq_by8);
1131
1132 // ClientKey::with_local(|ck| {
1133 // let noise = measure_noise_lwe(
1134 // &c_out,
1135 // ck.sk_rlwe.values(),
1136 // &self.rlwe_modop,
1137 // &(self.rlweq_by8),
1138 // );
1139 // println!("cout_noise: {noise}");
1140 // });
1141
1142 // PBS
1143 pbs(
1144 self,
1145 &self.nand_test_vec,
1146 &mut c_out,
1147 scratch_lwen_plus1,
1148 scratch_matrix_dplus2_ring,
1149 &self.lwe_modop,
1150 &self.rlwe_modop,
1151 &self.rlwe_nttop,
1152 server_key,
1153 );
1154
1155 c_out
1156 }
1157}
1158
1159impl<M: Matrix, NttOp, ModOp> PbsParameters for BoolEvaluator<M, M::MatElement, NttOp, ModOp>
1160where
1161 M::MatElement: PrimInt + WrappingSub + Debug,
1162{
1163 type Element = M::MatElement;
1164 type D = DefaultDecomposer<M::MatElement>;
1165 fn rlwe_auto_map(&self, k: isize) -> &(Vec<usize>, Vec<bool>) {
1166 let g = self.parameters.g as isize;
1167 if k == g {
1168 &self.rlwe_auto_maps[0]
1169 } else if k == -g {
1170 &self.rlwe_auto_maps[1]
1171 } else {
1172 panic!("RLWE auto map only supports k in [-g, g], but got k={k}");
1173 }
1174 }
1175
1176 fn br_q(&self) -> usize {
1177 self.parameters.br_q
1178 }
1179 fn d_lwe(&self) -> usize {
1180 self.parameters.d_lwe
1181 }
1182 fn d_rgsw(&self) -> usize {
1183 self.parameters.d_rgsw
1184 }
1185 fn decomoposer_lwe(&self) -> &Self::D {
1186 &self.decomposer_lwe
1187 }
1188 fn decomoposer_rlwe(&self) -> &Self::D {
1189 &self.decomposer_rlwe
1190 }
1191 fn embedding_factor(&self) -> usize {
1192 self.embedding_factor
1193 }
1194 fn g(&self) -> isize {
1195 self.parameters.g as isize
1196 }
1197 fn g_k_dlog_map(&self) -> &[usize] {
1198 &self.g_k_dlog_map
1199 }
1200 fn lwe_n(&self) -> usize {
1201 self.parameters.lwe_n
1202 }
1203 fn lwe_q(&self) -> Self::Element {
1204 self.parameters.lwe_q
1205 }
1206 fn rlwe_n(&self) -> usize {
1207 self.parameters.rlwe_n
1208 }
1209 fn rlwe_q(&self) -> Self::Element {
1210 self.parameters.rlwe_q
1211 }
1212}
1213
1214/// LMKCY+ Blind rotation
1215///
1216/// gk_to_si: [-g^0, -g^1, .., -g^{q/2-1}, g^0, ..., g^{q/2-1}]
1217fn blind_rotation<
1218 MT: IsTrivial + MatrixMut,
1219 Mmut: MatrixMut<MatElement = MT::MatElement> + Matrix,
1220 D: Decomposer<Element = MT::MatElement>,
1221 NttOp: Ntt<Element = MT::MatElement>,
1222 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
1223 K: PbsKey<M = Mmut>,
1224 P: PbsParameters<Element = MT::MatElement>,
1225>(
1226 trivial_rlwe_test_poly: &mut MT,
1227 scratch_matrix_dplus2_ring: &mut Mmut,
1228 g: isize,
1229 w: usize,
1230 q: usize,
1231 gk_to_si: &[Vec<usize>],
1232 decomposer: &D,
1233 ntt_op: &NttOp,
1234 mod_op: &ModOp,
1235 parameters: &P,
1236 pbs_key: &K,
1237) where
1238 <Mmut as Matrix>::R: RowMut,
1239 Mmut::MatElement: Copy + Zero,
1240 <MT as Matrix>::R: RowMut,
1241{
1242 let q_by_2 = q / 2;
1243
1244 // -(g^k)
1245 for i in (1..q_by_2).rev() {
1246 gk_to_si[q_by_2 + i].iter().for_each(|s_index| {
1247 rlwe_by_rgsw(
1248 trivial_rlwe_test_poly,
1249 pbs_key.rgsw_ct_lwe_si(*s_index),
1250 scratch_matrix_dplus2_ring,
1251 decomposer,
1252 ntt_op,
1253 mod_op,
1254 );
1255 });
1256
1257 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1258 galois_auto(
1259 trivial_rlwe_test_poly,
1260 pbs_key.galois_key_for_auto(g),
1261 scratch_matrix_dplus2_ring,
1262 &auto_map_index,
1263 &auto_map_sign,
1264 mod_op,
1265 ntt_op,
1266 decomposer,
1267 );
1268 }
1269
1270 // -(g^0)
1271 gk_to_si[q_by_2].iter().for_each(|s_index| {
1272 rlwe_by_rgsw(
1273 trivial_rlwe_test_poly,
1274 pbs_key.rgsw_ct_lwe_si(*s_index),
1275 scratch_matrix_dplus2_ring,
1276 decomposer,
1277 ntt_op,
1278 mod_op,
1279 );
1280 });
1281 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(-g);
1282 galois_auto(
1283 trivial_rlwe_test_poly,
1284 pbs_key.galois_key_for_auto(-g),
1285 scratch_matrix_dplus2_ring,
1286 &auto_map_index,
1287 &auto_map_sign,
1288 mod_op,
1289 ntt_op,
1290 decomposer,
1291 );
1292
1293 // +(g^k)
1294 for i in (1..q_by_2).rev() {
1295 gk_to_si[i].iter().for_each(|s_index| {
1296 rlwe_by_rgsw(
1297 trivial_rlwe_test_poly,
1298 pbs_key.rgsw_ct_lwe_si(*s_index),
1299 scratch_matrix_dplus2_ring,
1300 decomposer,
1301 ntt_op,
1302 mod_op,
1303 );
1304 });
1305
1306 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1307 galois_auto(
1308 trivial_rlwe_test_poly,
1309 pbs_key.galois_key_for_auto(g),
1310 scratch_matrix_dplus2_ring,
1311 &auto_map_index,
1312 &auto_map_sign,
1313 mod_op,
1314 ntt_op,
1315 decomposer,
1316 );
1317 }
1318
1319 // +(g^0)
1320 gk_to_si[0].iter().for_each(|s_index| {
1321 rlwe_by_rgsw(
1322 trivial_rlwe_test_poly,
1323 pbs_key.rgsw_ct_lwe_si(gk_to_si[q_by_2][*s_index]),
1324 scratch_matrix_dplus2_ring,
1325 decomposer,
1326 ntt_op,
1327 mod_op,
1328 );
1329 });
1330}
1331
1332/// - Mod down
1333/// - key switching
1334/// - mod down
1335/// - blind rotate
1336fn pbs<
1337 M: Matrix + MatrixMut + MatrixEntity,
1338 P: PbsParameters<Element = M::MatElement>,
1339 NttOp: Ntt<Element = M::MatElement>,
1340 ModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
1341 K: PbsKey<M = M>,
1342>(
1343 parameters: &P,
1344 test_vec: &M::R,
1345 lwe_in: &mut M::R,
1346 scratch_lwen_plus1: &mut M::R,
1347 scratch_matrix_dplus2_ring: &mut M,
1348 modop_lweq: &ModOp,
1349 modop_rlweq: &ModOp,
1350 nttop_rlweq: &NttOp,
1351 pbs_key: &K,
1352) where
1353 <M as Matrix>::R: RowMut,
1354 M::MatElement: PrimInt + ToPrimitive + FromPrimitive + One + Copy + Zero + Display,
1355{
1356 let rlwe_q = parameters.rlwe_q();
1357 let lwe_q = parameters.lwe_q();
1358 let br_q = parameters.br_q();
1359 let rlwe_qf64 = rlwe_q.to_f64().unwrap();
1360 let lwe_qf64 = lwe_q.to_f64().unwrap();
1361 let br_qf64 = br_q.to_f64().unwrap();
1362 let rlwe_n = parameters.rlwe_n();
1363
1364 // moddown Q -> Q_ks
1365 lwe_in.as_mut().iter_mut().for_each(|v| {
1366 *v =
1367 M::MatElement::from_f64(((v.to_f64().unwrap() * lwe_qf64) / rlwe_qf64).round()).unwrap()
1368 });
1369
1370 PBSTracer::with_local_mut(|t| {
1371 let out = lwe_in
1372 .as_ref()
1373 .iter()
1374 .map(|v| v.to_u64().unwrap())
1375 .collect_vec();
1376 t.ct_lwe_q_mod = out;
1377 });
1378
1379 // key switch RLWE secret to LWE secret
1380 scratch_lwen_plus1.as_mut().fill(M::MatElement::zero());
1381 lwe_key_switch(
1382 scratch_lwen_plus1,
1383 lwe_in,
1384 pbs_key.lwe_ksk(),
1385 modop_lweq,
1386 parameters.decomoposer_lwe(),
1387 );
1388
1389 PBSTracer::with_local_mut(|t| {
1390 let out = scratch_lwen_plus1
1391 .as_ref()
1392 .iter()
1393 .map(|v| v.to_u64().unwrap())
1394 .collect_vec();
1395 t.ct_lwe_q_mod_after_ksk = out;
1396 });
1397
1398 // odd mowdown Q_ks -> q
1399 let g_k_dlog_map = parameters.g_k_dlog_map();
1400 let mut g_k_si = vec![vec![]; br_q];
1401 scratch_lwen_plus1
1402 .as_ref()
1403 .iter()
1404 .skip(1)
1405 .enumerate()
1406 .for_each(|(index, v)| {
1407 let odd_v = mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64);
1408 let k = g_k_dlog_map[odd_v];
1409 g_k_si[k].push(index);
1410 });
1411
1412 PBSTracer::with_local_mut(|t| {
1413 let out = scratch_lwen_plus1
1414 .as_ref()
1415 .iter()
1416 .map(|v| mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64) as u64)
1417 .collect_vec();
1418 t.ct_br_q_mod = out;
1419 });
1420
1421 // handle b and set trivial test RLWE
1422 let g = parameters.g() as usize;
1423 let g_times_b = (g * mod_switch_odd(
1424 scratch_lwen_plus1.as_ref()[0].to_f64().unwrap(),
1425 lwe_qf64,
1426 br_qf64,
1427 )) % (br_q);
1428 // v = (v(X) * X^{g*b}) mod X^{q/2}+1
1429 let br_qby2 = br_q / 2;
1430 let mut gb_monomial_sign = true;
1431 let mut gb_monomial_exp = g_times_b;
1432 // X^{g*b} mod X^{q/2}+1
1433 if gb_monomial_exp > br_qby2 {
1434 gb_monomial_exp -= br_qby2;
1435 gb_monomial_sign = false
1436 }
1437 // monomial mul
1438 let mut trivial_rlwe_test_poly =
1439 RlweCiphertext::<_, DefaultSecureRng>::from_raw(M::zeros(2, rlwe_n), true);
1440 if parameters.embedding_factor() == 1 {
1441 monomial_mul(
1442 test_vec.as_ref(),
1443 trivial_rlwe_test_poly.get_row_mut(1).as_mut(),
1444 gb_monomial_exp,
1445 gb_monomial_sign,
1446 br_qby2,
1447 modop_rlweq,
1448 );
1449 } else {
1450 // use lwe_in to store the `t = v(X) * X^{g*2} mod X^{q/2}+1` temporarily. This
1451 // works because q/2 <= N (where N is lwe_in LWE dimension) always.
1452 monomial_mul(
1453 test_vec.as_ref(),
1454 &mut lwe_in.as_mut()[..br_qby2],
1455 gb_monomial_exp,
1456 gb_monomial_sign,
1457 br_qby2,
1458 modop_rlweq,
1459 );
1460
1461 // emebed poly `t` in ring X^{q/2}+1 inside the bigger ring X^{N}+1
1462 let embed_factor = parameters.embedding_factor();
1463 let partb_trivial_rlwe = trivial_rlwe_test_poly.get_row_mut(1);
1464 lwe_in.as_ref()[..br_qby2]
1465 .iter()
1466 .enumerate()
1467 .for_each(|(index, v)| {
1468 partb_trivial_rlwe[embed_factor * index] = *v;
1469 });
1470 }
1471
1472 // blind rotate
1473 blind_rotation(
1474 &mut trivial_rlwe_test_poly,
1475 scratch_matrix_dplus2_ring,
1476 parameters.g(),
1477 1,
1478 br_q,
1479 &g_k_si,
1480 parameters.decomoposer_rlwe(),
1481 nttop_rlweq,
1482 modop_rlweq,
1483 parameters,
1484 pbs_key,
1485 );
1486
1487 // ClientKey::with_local(|ck| {
1488 // let ring_size = parameters.rlwe_n();
1489 // let mut rlwe_ct = vec![vec![0u64; ring_size]; 2];
1490 // izip!(
1491 // rlwe_ct[0].iter_mut(),
1492 // trivial_rlwe_test_poly.0.get_row_slice(0)
1493 // )
1494 // .for_each(|(t, f)| {
1495 // *t = f.to_u64().unwrap();
1496 // });
1497 // izip!(
1498 // rlwe_ct[1].iter_mut(),
1499 // trivial_rlwe_test_poly.0.get_row_slice(1)
1500 // )
1501 // .for_each(|(t, f)| {
1502 // *t = f.to_u64().unwrap();
1503 // });
1504 // let mut m_out = vec![vec![0u64; ring_size]];
1505 // let modop = ModularOpsU64::new(rlwe_q.to_u64().unwrap());
1506 // let nttop = NttBackendU64::new(rlwe_q.to_u64().unwrap(), ring_size);
1507 // decrypt_rlwe(&rlwe_ct, ck.sk_rlwe.values(), &mut m_out, &nttop, &modop);
1508
1509 // println!("RLWE post PBS message: {:?}", m_out[0]);
1510 // });
1511
1512 // sample extract
1513 sample_extract(lwe_in, &trivial_rlwe_test_poly, modop_rlweq, 0);
1514}
1515
1516fn mod_switch_odd(v: f64, from_q: f64, to_q: f64) -> usize {
1517 let odd_v = (((v * to_q) / (from_q)).floor()).to_usize().unwrap();
1518 //TODO(Jay): check correctness of this
1519 odd_v + ((odd_v & 1) ^ 1)
1520}
1521
1522// TODO(Jay): Add tests for sample extract
1523fn sample_extract<M: Matrix + MatrixMut, ModOp: ArithmeticOps<Element = M::MatElement>>(
1524 lwe_out: &mut M::R,
1525 rlwe_in: &M,
1526 mod_op: &ModOp,
1527 index: usize,
1528) where
1529 <M as Matrix>::R: RowMut,
1530 M::MatElement: Copy,
1531{
1532 let ring_size = rlwe_in.dimension().1;
1533
1534 // index..=0
1535 let to = &mut lwe_out.as_mut()[1..];
1536 let from = rlwe_in.get_row_slice(0);
1537 for i in 0..index + 1 {
1538 to[i] = from[index - i];
1539 }
1540
1541 // -(N..index)
1542 for i in index + 1..ring_size {
1543 to[i] = mod_op.neg(&from[ring_size + index - i]);
1544 }
1545
1546 // set b
1547 lwe_out.as_mut()[0] = *rlwe_in.get(1, index);
1548}
1549
1550/// TODO(Jay): Write tests for monomial mul
1551fn monomial_mul<El, ModOp: ArithmeticOps<Element = El>>(
1552 p_in: &[El],
1553 p_out: &mut [El],
1554 mon_exp: usize,
1555 mon_sign: bool,
1556 ring_size: usize,
1557 mod_op: &ModOp,
1558) where
1559 El: Copy,
1560{
1561 debug_assert!(p_in.as_ref().len() == ring_size);
1562 debug_assert!(p_in.as_ref().len() == p_out.as_ref().len());
1563 debug_assert!(mon_exp < ring_size);
1564
1565 p_in.as_ref().iter().enumerate().for_each(|(index, v)| {
1566 let mut to_index = index + mon_exp;
1567 let mut to_sign = mon_sign;
1568 if to_index >= ring_size {
1569 to_index = to_index - ring_size;
1570 to_sign = !to_sign;
1571 }
1572
1573 if !to_sign {
1574 p_out.as_mut()[to_index] = mod_op.neg(v);
1575 } else {
1576 p_out.as_mut()[to_index] = *v;
1577 }
1578 });
1579}
1580
1581thread_local! {
1582 static PBS_TRACER: RefCell<PBSTracer<Vec<Vec<u64>>>> = RefCell::new(PBSTracer::default());
1583}
1584
1585#[derive(Default)]
1586struct PBSTracer<M>
1587where
1588 M: Matrix + Default,
1589{
1590 pub(crate) ct_lwe_q_mod: M::R,
1591 pub(crate) ct_lwe_q_mod_after_ksk: M::R,
1592 pub(crate) ct_br_q_mod: Vec<u64>,
1593}
1594
1595impl PBSTracer<Vec<Vec<u64>>> {
1596 fn trace(&self, parameters: &BoolParameters<u64>, sk_lwe: &[i32], sk_rlwe: &[i32]) {
1597 assert!(parameters.rlwe_n == sk_rlwe.len());
1598 assert!(parameters.lwe_n == sk_lwe.len());
1599
1600 let modop_lweq = ModularOpsU64::new(parameters.lwe_q as u64);
1601 // noise after mod down Q -> Q_ks
1602 let m_back0 = decrypt_lwe(&self.ct_lwe_q_mod, sk_rlwe, &modop_lweq);
1603 // noise after key switch from RLWE -> LWE
1604 let m_back1 = decrypt_lwe(&self.ct_lwe_q_mod_after_ksk, sk_lwe, &modop_lweq);
1605
1606 // noise after mod down odd from Q_ks -> q
1607 let modop_br_q = ModularOpsU64::new(parameters.br_q as u64);
1608 let m_back2 = decrypt_lwe(&self.ct_br_q_mod, sk_lwe, &modop_br_q);
1609
1610 println!(
1611 "
1612 M after mod down Q -> Q_ks: {m_back0},
1613 M after key switch from RLWE -> LWE: {m_back1},
1614 M after mod dwon Q_ks -> q: {m_back2}
1615 "
1616 );
1617 }
1618}
1619
1620impl WithLocal for PBSTracer<Vec<Vec<u64>>> {
1621 fn with_local<F, R>(func: F) -> R
1622 where
1623 F: Fn(&Self) -> R,
1624 {
1625 PBS_TRACER.with_borrow(|t| func(t))
1626 }
1627
1628 fn with_local_mut<F, R>(func: F) -> R
1629 where
1630 F: Fn(&mut Self) -> R,
1631 {
1632 PBS_TRACER.with_borrow_mut(|t| func(t))
1633 }
1634}
1635
1636#[cfg(test)]
1637mod tests {
1638 use rand::{thread_rng, Rng};
1639
1640 use crate::{
1641 backend::ModularOpsU64,
1642 bool,
1643 ntt::NttBackendU64,
1644 random::DEFAULT_RNG,
1645 rgsw::{
1646 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
1647 tests::_measure_noise_rgsw, RgswCiphertext, RgswCiphertextEvaluationDomain,
1648 SeededRgswCiphertext, SeededRlweCiphertext,
1649 },
1650 utils::negacyclic_mul,
1651 };
1652
1653 use self::parameters::{MP_BOOL_PARAMS, SP_BOOL_PARAMS};
1654
1655 use super::*;
1656
1657 // #[test]
1658 // fn trial() {
1659 // dbg!(generate_prime(28, 1 << 11, 1 << 28));
1660 // }
1661
1662 #[test]
1663 fn bool_encrypt_decrypt_works() {
1664 // let prime = generate_prime(32, 2 * 1024, 1 << 32);
1665 // dbg!(prime);
1666 let bool_evaluator =
1667 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1668 let client_key = bool_evaluator.client_key();
1669 // let sever_key = bool_evaluator.server_key(&client_key);
1670
1671 let mut m = true;
1672 for _ in 0..1000 {
1673 let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
1674 let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
1675 assert_eq!(m, m_back);
1676 m = !m;
1677 }
1678 }
1679
1680 #[test]
1681 fn bool_nand() {
1682 DefaultSecureRng::with_local_mut(|r| {
1683 let rng = DefaultSecureRng::new_seeded([19u8; 32]);
1684 *r = rng;
1685 });
1686
1687 let bool_evaluator =
1688 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1689
1690 // println!("{:?}", bool_evaluator.nand_test_vec);
1691 let client_key = bool_evaluator.client_key();
1692 let seeded_server_key = bool_evaluator.server_key(&client_key);
1693 let server_key_eval_domain =
1694 ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1695 &seeded_server_key,
1696 );
1697
1698 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
1699 let mut scratch_matrix_dplus2_ring = vec![
1700 vec![0u64; bool_evaluator.parameters.rlwe_n];
1701 bool_evaluator.parameters.d_rgsw + 2
1702 ];
1703
1704 let mut m0 = false;
1705 let mut m1 = true;
1706 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
1707 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
1708 for _ in 0..1000 {
1709 let ct_back = bool_evaluator.nand(
1710 &ct0,
1711 &ct1,
1712 &server_key_eval_domain,
1713 &mut scratch_lwen_plus1,
1714 &mut scratch_matrix_dplus2_ring,
1715 );
1716
1717 let m_out = !(m0 && m1);
1718
1719 // Trace and measure PBS noise
1720 {
1721 // Trace PBS
1722 PBSTracer::with_local(|t| {
1723 t.trace(
1724 &SP_BOOL_PARAMS,
1725 &client_key.sk_lwe.values(),
1726 client_key.sk_rlwe.values(),
1727 )
1728 });
1729
1730 // Calculate noise in ciphertext post PBS
1731 let ideal = if m_out {
1732 bool_evaluator.rlweq_by8
1733 } else {
1734 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1735 };
1736 let noise = measure_noise_lwe(
1737 &ct_back,
1738 client_key.sk_rlwe.values(),
1739 &bool_evaluator.rlwe_modop,
1740 &ideal,
1741 );
1742 println!("PBS noise: {noise}");
1743 }
1744 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
1745 assert_eq!(m_out, m_back);
1746 println!("----------");
1747
1748 m1 = m0;
1749 m0 = m_out;
1750
1751 ct1 = ct0;
1752 ct0 = ct_back;
1753 }
1754 }
1755
1756 #[test]
1757 fn multi_party_encryption_decryption() {
1758 let bool_evaluator =
1759 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
1760
1761 let no_of_parties = 5;
1762 let parties = (0..no_of_parties)
1763 .map(|_| bool_evaluator.client_key())
1764 .collect_vec();
1765
1766 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
1767 parties.iter().for_each(|k| {
1768 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
1769 *ideal_i = *ideal_i + s_i;
1770 });
1771 });
1772
1773 let mut m = true;
1774 for i in 0..100 {
1775 let pk_cr_seed = [0u8; 32];
1776
1777 let public_key_share = parties
1778 .iter()
1779 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1780 .collect_vec();
1781
1782 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
1783 public_key_share.as_slice(),
1784 );
1785 let lwe_ct = bool_evaluator.pk_encrypt(&collective_pk.key, m);
1786
1787 let decryption_shares = parties
1788 .iter()
1789 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct, k))
1790 .collect_vec();
1791
1792 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
1793
1794 {
1795 let ideal_m = if m {
1796 bool_evaluator.rlweq_by8
1797 } else {
1798 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
1799 };
1800 let noise = measure_noise_lwe(
1801 &lwe_ct,
1802 &ideal_rlwe_sk,
1803 &bool_evaluator.rlwe_modop,
1804 &ideal_m,
1805 );
1806 println!("Noise: {noise}");
1807 }
1808
1809 assert_eq!(m_back, m);
1810 m = !m;
1811 }
1812 }
1813
1814 #[test]
1815 fn mp_key_correcntess() {
1816 let bool_evaluator =
1817 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
1818
1819 let no_of_parties = 10;
1820 let parties = (0..no_of_parties)
1821 .map(|_| bool_evaluator.client_key())
1822 .collect_vec();
1823
1824 // Collective public key
1825 let pk_cr_seed = [0u8; 32];
1826 let public_key_share = parties
1827 .iter()
1828 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1829 .collect_vec();
1830 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
1831 public_key_share.as_slice(),
1832 );
1833
1834 // Server key
1835 let pbs_cr_seed = [1u8; 32];
1836 let server_key_shares = parties
1837 .iter()
1838 .map(|k| bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k))
1839 .collect_vec();
1840 let seeded_server_key =
1841 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
1842 &server_key_shares,
1843 &bool_evaluator.decomposer_rlwe,
1844 );
1845 let server_key_eval = ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1846 &seeded_server_key,
1847 );
1848
1849 // construct ideal rlwe sk for meauring noise
1850 let ideal_client_key = {
1851 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
1852 parties.iter().for_each(|k| {
1853 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
1854 *ideal_i = *ideal_i + s_i;
1855 });
1856 });
1857 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
1858 parties.iter().for_each(|k| {
1859 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
1860 *ideal_i = *ideal_i + s_i;
1861 });
1862 });
1863
1864 ClientKey {
1865 sk_lwe: LweSecret {
1866 values: ideal_lwe_sk,
1867 },
1868 sk_rlwe: RlweSecret {
1869 values: ideal_rlwe_sk,
1870 },
1871 }
1872 };
1873
1874 let lwe_q = bool_evaluator.parameters.lwe_q;
1875 let rlwe_q = bool_evaluator.parameters.rlwe_q;
1876 let d_rgsw = bool_evaluator.parameters.d_rgsw;
1877 let lwe_logq = bool_evaluator.parameters.lwe_logq;
1878 let lwe_n = bool_evaluator.parameters.lwe_n;
1879 let rlwe_n = bool_evaluator.parameters.rlwe_n;
1880 let lwe_modop = &bool_evaluator.lwe_modop;
1881 let rlwe_nttop = &bool_evaluator.rlwe_nttop;
1882 let rlwe_modop = &bool_evaluator.rlwe_modop;
1883 let rlwe_decomposer = &bool_evaluator.decomposer_rlwe;
1884
1885 // test LWE ksk from RLWE -> LWE
1886 if true {
1887 let logp = 2;
1888 let mut rng = DefaultSecureRng::new();
1889
1890 let m = 1;
1891 let encoded_m = m << (lwe_logq - logp);
1892
1893 // Encrypt
1894 let mut lwe_ct = vec![0u64; rlwe_n + 1];
1895 encrypt_lwe(
1896 &mut lwe_ct,
1897 &encoded_m,
1898 ideal_client_key.sk_rlwe.values(),
1899 lwe_modop,
1900 &mut rng,
1901 );
1902
1903 // key switch
1904 let lwe_decomposer = &bool_evaluator.decomposer_lwe;
1905 let mut lwe_out = vec![0u64; lwe_n + 1];
1906 lwe_key_switch(
1907 &mut lwe_out,
1908 &lwe_ct,
1909 &server_key_eval.lwe_ksk,
1910 lwe_modop,
1911 lwe_decomposer,
1912 );
1913
1914 let encoded_m_back = decrypt_lwe(&lwe_out, ideal_client_key.sk_lwe.values(), lwe_modop);
1915 let m_back =
1916 ((encoded_m_back as f64 * (1 << logp) as f64) / (lwe_q as f64)).round() as u64;
1917 dbg!(m_back, m);
1918
1919 let noise = measure_noise_lwe(
1920 &lwe_out,
1921 ideal_client_key.sk_lwe.values(),
1922 lwe_modop,
1923 &encoded_m,
1924 );
1925
1926 println!("Noise: {noise}");
1927 }
1928
1929 // Measure noise in RGSW ciphertexts of ideal LWE secrets
1930 if false {
1931 let gadget_vec = gadget_vector(
1932 bool_evaluator.parameters.rlwe_logq,
1933 bool_evaluator.parameters.logb_rgsw,
1934 bool_evaluator.parameters.d_rgsw,
1935 );
1936
1937 for i in 0..20 {
1938 // measure noise in RGSW(s[i])
1939 let si = ideal_client_key.sk_lwe.values[i];
1940 let mut si_poly = vec![0u64; rlwe_n];
1941 if si < 0 {
1942 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
1943 } else {
1944 si_poly[(si.abs() as usize)] = 1;
1945 }
1946
1947 let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
1948 rgsw_si
1949 .iter_mut()
1950 .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
1951
1952 println!("####### Noise in RGSW(X^s_{i}) #######");
1953 _measure_noise_rgsw(
1954 &rgsw_si,
1955 &si_poly,
1956 ideal_client_key.sk_rlwe.values(),
1957 &gadget_vec,
1958 rlwe_q,
1959 );
1960 println!("####### ##################### #######");
1961 }
1962 }
1963
1964 // measure noise grwoth in RLWExRGSW
1965 if false {
1966 let mut rng = DefaultSecureRng::new();
1967 let mut carry_m = vec![0u64; rlwe_n];
1968 RandomUniformDist::random_fill(&mut rng, &rlwe_q, carry_m.as_mut_slice());
1969
1970 // RGSW(carrym)
1971 let trivial_rlwect = vec![vec![0u64; rlwe_n], carry_m.clone()];
1972 let mut rlwe_ct = RlweCiphertext::<_, DefaultSecureRng>::from_raw(trivial_rlwect, true);
1973
1974 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
1975 let mul_mod =
1976 |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
1977
1978 for i in 0..450 {
1979 rlwe_by_rgsw(
1980 &mut rlwe_ct,
1981 server_key_eval.rgsw_ct_lwe_si(i),
1982 &mut scratch_matrix_dplus2_ring,
1983 rlwe_decomposer,
1984 rlwe_nttop,
1985 rlwe_modop,
1986 );
1987
1988 // carry_m[X] * s_i[X]
1989 let si = ideal_client_key.sk_lwe.values[i];
1990 let mut si_poly = vec![0u64; rlwe_n];
1991 if si < 0 {
1992 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
1993 } else {
1994 si_poly[(si.abs() as usize)] = 1;
1995 }
1996 carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod, rlwe_q);
1997
1998 let noise = measure_noise(
1999 &rlwe_ct,
2000 &carry_m,
2001 rlwe_nttop,
2002 rlwe_modop,
2003 ideal_client_key.sk_rlwe.values(),
2004 );
2005 println!("Noise RLWE(carry_m) accumulating {i}^th secret monomial: {noise}");
2006 }
2007 }
2008
2009 // Check galois keys
2010 if false {
2011 let g = bool_evaluator.g() as isize;
2012 let mut rng = DefaultSecureRng::new();
2013 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
2014 for i in [g, -g] {
2015 let mut m = vec![0u64; rlwe_n];
2016 RandomUniformDist::random_fill(&mut rng, &rlwe_q, m.as_mut_slice());
2017 let mut rlwe_ct = {
2018 let mut data = vec![vec![0u64; rlwe_n]; 2];
2019 public_key_encrypt_rlwe(
2020 &mut data,
2021 &collective_pk.key,
2022 &m,
2023 rlwe_modop,
2024 rlwe_nttop,
2025 &mut rng,
2026 );
2027 RlweCiphertext::<_, DefaultSecureRng>::from_raw(data, false)
2028 };
2029
2030 let auto_key = server_key_eval.galois_key_for_auto(i);
2031 let (auto_map_index, auto_map_sign) = generate_auto_map(rlwe_n, i);
2032 galois_auto(
2033 &mut rlwe_ct,
2034 auto_key,
2035 &mut scratch_matrix_dplus2_ring,
2036 &auto_map_index,
2037 &auto_map_sign,
2038 rlwe_modop,
2039 rlwe_nttop,
2040 rlwe_decomposer,
2041 );
2042
2043 // send m(X) -> m(X^i)
2044 let mut m_k = vec![0u64; rlwe_n];
2045 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
2046 |(mi, to_index, to_sign)| {
2047 if !to_sign {
2048 m_k[*to_index] = rlwe_q - *mi;
2049 } else {
2050 m_k[*to_index] = *mi;
2051 }
2052 },
2053 );
2054
2055 // measure noise
2056 let noise = measure_noise(
2057 &rlwe_ct,
2058 &m_k,
2059 rlwe_nttop,
2060 rlwe_modop,
2061 ideal_client_key.sk_rlwe.values(),
2062 );
2063
2064 println!("Noise after auto k={i}: {noise}");
2065 }
2066 }
2067 }
2068
2069 #[test]
2070 fn trial12() {
2071 let bool_evaluator =
2072 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2073
2074 let no_of_parties = 2;
2075 let parties = (0..no_of_parties)
2076 .map(|_| bool_evaluator.client_key())
2077 .collect_vec();
2078
2079 // Collective public key
2080 let pk_cr_seed = [0u8; 32];
2081 let public_key_share = parties
2082 .iter()
2083 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2084 .collect_vec();
2085 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2086 public_key_share.as_slice(),
2087 );
2088
2089 // Server key
2090 let pbs_cr_seed = [1u8; 32];
2091 let server_key_shares = parties
2092 .iter()
2093 .map(|k| bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k))
2094 .collect_vec();
2095 let seeded_server_key =
2096 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
2097 &server_key_shares,
2098 &bool_evaluator.decomposer_rlwe,
2099 );
2100 let server_key_eval = ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2101 &seeded_server_key,
2102 );
2103
2104 // construct ideal rlwe sk for meauring noise
2105 let ideal_client_key = {
2106 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
2107 parties.iter().for_each(|k| {
2108 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
2109 *ideal_i = *ideal_i + s_i;
2110 });
2111 });
2112 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
2113 parties.iter().for_each(|k| {
2114 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
2115 *ideal_i = *ideal_i + s_i;
2116 });
2117 });
2118
2119 ClientKey {
2120 sk_lwe: LweSecret {
2121 values: ideal_lwe_sk,
2122 },
2123 sk_rlwe: RlweSecret {
2124 values: ideal_rlwe_sk,
2125 },
2126 }
2127 };
2128
2129 // PBS
2130 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
2131 let mut scratch_matrix_dplus2_ring = vec![
2132 vec![0u64; bool_evaluator.parameters.rlwe_n];
2133 bool_evaluator.parameters.d_rgsw + 2
2134 ];
2135
2136 let mut m0 = true;
2137 let mut m1 = false;
2138
2139 for _ in 0..500 {
2140 let lwe0 = bool_evaluator.pk_encrypt(&collective_pk.key, m0);
2141 let lwe1 = bool_evaluator.pk_encrypt(&collective_pk.key, m1);
2142
2143 let lwe_out = bool_evaluator.nand(
2144 &lwe0,
2145 &lwe1,
2146 &server_key_eval,
2147 &mut scratch_lwen_plus1,
2148 &mut scratch_matrix_dplus2_ring,
2149 );
2150
2151 let m_expected = !(m0 & m1);
2152
2153 // measure noise
2154 {
2155 // Trace PBS
2156 PBSTracer::with_local(|t| {
2157 t.trace(
2158 &MP_BOOL_PARAMS,
2159 &ideal_client_key.sk_lwe.values(),
2160 &ideal_client_key.sk_rlwe.values(),
2161 )
2162 });
2163
2164 let ideal_m = if m_expected {
2165 bool_evaluator.rlweq_by8
2166 } else {
2167 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
2168 };
2169 let noise = measure_noise_lwe(
2170 &lwe_out,
2171 ideal_client_key.sk_rlwe.values(),
2172 &bool_evaluator.rlwe_modop,
2173 &ideal_m,
2174 );
2175 println!("Noise: {noise}");
2176 }
2177
2178 // multi-party decrypt
2179 let decryption_shares = parties
2180 .iter()
2181 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_out, k))
2182 .collect_vec();
2183 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
2184
2185 // let m_back = bool_evaluator.sk_decrypt(&lwe_out, &ideal_client_key);
2186
2187 assert_eq!(m_expected, m_back);
2188 m1 = m0;
2189 m0 = m_expected;
2190 }
2191 }
2192}