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 //TODO(Jay): It will be nice to have a function that returns polynomial
860 // (monomial infact!) corresponding to secret element embedded in ring X^{2N+1}.
861 // Save lots of mistakes where one forgest to emebed si in bigger ring.
862 let si = *si * (self.embedding_factor as i32);
863 if si < 0 {
864 // X^{-si} = X^{2N-si} = -X^{N-si}, assuming abs(si) < N
865 // (which it is given si is secret element)
866 m.as_mut()[ring_size - (si.abs() as usize)] = rlwe_q - M::MatElement::one();
867 } else {
868 m.as_mut()[si as usize] = M::MatElement::one();
869 }
870
871 // public key RGSW encryption has no part that can be seeded, unlike secret key
872 // RGSW encryption where RLWE'_A(m) is seeded
873 let mut out_rgsw = M::zeros(d_rgsw * 4, ring_size);
874 public_key_encrypt_rgsw(
875 &mut out_rgsw,
876 &m.as_ref(),
877 collective_pk,
878 &d_rgsw_gadget_vec,
879 &rlweq_modop,
880 &rlweq_nttop,
881 rng,
882 );
883
884 out_rgsw
885 })
886 .collect_vec();
887
888 // LWE ksk
889 let mut lwe_ksk = M::R::zeros(d_lwe * ring_size);
890 let lwe_modop = ModOp::new(lwe_q);
891 let d_lwe_gadget_vec =
892 gadget_vector(self.parameters.lwe_logq, self.parameters.logb_lwe, d_lwe);
893 lwe_ksk_keygen(
894 sk_rlwe.values(),
895 sk_lwe.values(),
896 &mut lwe_ksk,
897 &d_lwe_gadget_vec,
898 &lwe_modop,
899 &mut main_prng,
900 rng,
901 );
902
903 CommonReferenceSeededMultiPartyServerKeyShare {
904 auto_keys,
905 rgsw_cts,
906 lwe_ksk,
907 cr_seed,
908 parameters: self.parameters.clone(),
909 }
910 })
911 }
912
913 fn multi_party_public_key_share(
914 &self,
915 cr_seed: [u8; 32],
916 client_key: &ClientKey,
917 ) -> CommonReferenceSeededCollectivePublicKeyShare<
918 <M as Matrix>::R,
919 [u8; 32],
920 BoolParameters<<M as Matrix>::MatElement>,
921 > {
922 DefaultSecureRng::with_local_mut(|rng| {
923 let mut share_out = M::R::zeros(self.parameters.rlwe_n);
924 let modop = ModOp::new(self.parameters.rlwe_q);
925 let nttop = NttOp::new(self.parameters.rlwe_q, self.parameters.rlwe_n);
926 let mut main_prng = DefaultSecureRng::new_seeded(cr_seed);
927 public_key_share(
928 &mut share_out,
929 client_key.sk_rlwe.values(),
930 &modop,
931 &nttop,
932 &mut main_prng,
933 rng,
934 );
935
936 CommonReferenceSeededCollectivePublicKeyShare {
937 share: share_out,
938 cr_seed: cr_seed,
939 parameters: self.parameters.clone(),
940 }
941 })
942 }
943
944 fn multi_party_decryption_share(
945 &self,
946 lwe_ct: &M::R,
947 client_key: &ClientKey,
948 ) -> MultiPartyDecryptionShare<<M as Matrix>::MatElement> {
949 assert!(lwe_ct.as_ref().len() == self.parameters.rlwe_n + 1);
950 let modop = &self.rlwe_modop;
951 let mut neg_s =
952 M::R::try_convert_from(client_key.sk_rlwe.values(), &self.parameters.rlwe_q);
953 modop.elwise_neg_mut(neg_s.as_mut());
954
955 let mut neg_sa = M::MatElement::zero();
956 izip!(lwe_ct.as_ref().iter().skip(1), neg_s.as_ref().iter()).for_each(|(ai, nsi)| {
957 neg_sa = modop.add(&neg_sa, &modop.mul(ai, nsi));
958 });
959
960 let e = DefaultSecureRng::with_local_mut(|rng| {
961 let mut e = M::MatElement::zero();
962 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, &mut e);
963 e
964 });
965 let share = modop.add(&neg_sa, &e);
966
967 MultiPartyDecryptionShare { share }
968 }
969
970 pub(crate) fn multi_party_decrypt(
971 &self,
972 shares: &[MultiPartyDecryptionShare<M::MatElement>],
973 lwe_ct: &M::R,
974 ) -> bool {
975 let modop = &self.rlwe_modop;
976 let mut sum_a = M::MatElement::zero();
977 shares
978 .iter()
979 .for_each(|share_i| sum_a = modop.add(&sum_a, &share_i.share));
980
981 let encoded_m = modop.add(&lwe_ct.as_ref()[0], &sum_a);
982
983 let m = (((encoded_m + self.rlweq_by8).to_f64().unwrap() * 4f64)
984 / self.parameters.rlwe_q.to_f64().unwrap())
985 .round() as usize
986 % 4usize;
987
988 if m == 0 {
989 return false;
990 } else if m == 1 {
991 return true;
992 } else {
993 panic!("Bool decryption failure. Expected m to be either 1 or 0, but m={m} ");
994 }
995 }
996
997 /// First encrypt as RLWE(m) with m as constant polynomial and extract it as
998 /// LWE ciphertext
999 pub(crate) fn pk_encrypt(&self, pk: &M, m: bool) -> M::R {
1000 DefaultSecureRng::with_local_mut(|rng| {
1001 let modop = &self.rlwe_modop;
1002 let nttop = &self.rlwe_nttop;
1003
1004 // RLWE(0)
1005 // sample ephemeral key u
1006 let ring_size = self.parameters.rlwe_n;
1007 let mut u = vec![0i32; ring_size];
1008 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1009 let mut u = M::R::try_convert_from(&u, &self.parameters.rlwe_q);
1010 nttop.forward(u.as_mut());
1011
1012 let mut ua = M::R::zeros(ring_size);
1013 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1014 let mut ub = M::R::zeros(ring_size);
1015 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1016
1017 // a*u
1018 nttop.forward(ua.as_mut());
1019 modop.elwise_mul_mut(ua.as_mut(), u.as_ref());
1020 nttop.backward(ua.as_mut());
1021
1022 // b*u
1023 nttop.forward(ub.as_mut());
1024 modop.elwise_mul_mut(ub.as_mut(), u.as_ref());
1025 nttop.backward(ub.as_mut());
1026
1027 let mut rlwe = M::zeros(2, ring_size);
1028 // sample error
1029 rlwe.iter_rows_mut().for_each(|ri| {
1030 RandomGaussianDist::random_fill(rng, &self.parameters.rlwe_q, ri.as_mut());
1031 });
1032
1033 // a*u + e0
1034 modop.elwise_add_mut(rlwe.get_row_mut(0), ua.as_ref());
1035 // b*u + e1
1036 modop.elwise_add_mut(rlwe.get_row_mut(1), ub.as_ref());
1037
1038 let m = if m {
1039 // Q/8
1040 self.rlweq_by8
1041 } else {
1042 // -Q/8
1043 self.parameters.rlwe_q - self.rlweq_by8
1044 };
1045
1046 // b*u + e1 + m, where m is constant polynomial
1047 rlwe.set(1, 0, modop.add(rlwe.get(1, 0), &m));
1048
1049 // sample extract index 0
1050 let mut lwe_out = M::R::zeros(ring_size + 1);
1051 sample_extract(&mut lwe_out, &rlwe, modop, 0);
1052
1053 lwe_out
1054 })
1055 }
1056
1057 /// TODO(Jay): Fetch client key from thread local
1058 pub fn sk_encrypt(&self, m: bool, client_key: &ClientKey) -> M::R {
1059 let m = if m {
1060 // Q/8
1061 self.rlweq_by8
1062 } else {
1063 // -Q/8
1064 self.parameters.rlwe_q - self.rlweq_by8
1065 };
1066
1067 DefaultSecureRng::with_local_mut(|rng| {
1068 let mut lwe_out = M::R::zeros(self.parameters.rlwe_n + 1);
1069 encrypt_lwe(
1070 &mut lwe_out,
1071 &m,
1072 client_key.sk_rlwe.values(),
1073 &self.rlwe_modop,
1074 rng,
1075 );
1076 lwe_out
1077 })
1078 }
1079
1080 pub fn sk_decrypt(&self, lwe_ct: &M::R, client_key: &ClientKey) -> bool {
1081 let m = decrypt_lwe(lwe_ct, client_key.sk_rlwe.values(), &self.rlwe_modop);
1082 let m = {
1083 // m + q/8 => {0,q/4 1}
1084 (((m + self.rlweq_by8).to_f64().unwrap() * 4.0)
1085 / self.parameters.rlwe_q.to_f64().unwrap())
1086 .round()
1087 .to_usize()
1088 .unwrap()
1089 % 4
1090 };
1091
1092 if m == 0 {
1093 false
1094 } else if m == 1 {
1095 true
1096 } else {
1097 panic!("Incorrect bool decryption. Got m={m} but expected m to be 0 or 1")
1098 }
1099 }
1100
1101 // TODO(Jay): scratch spaces must be thread local. Don't pass them as arguments
1102 pub fn nand(
1103 &self,
1104 c0: &M::R,
1105 c1: &M::R,
1106 server_key: &ServerKeyEvaluationDomain<M, DefaultSecureRng, NttOp>,
1107 scratch_lwen_plus1: &mut M::R,
1108 scratch_matrix_dplus2_ring: &mut M,
1109 ) -> M::R {
1110 // ClientKey::with_local(|ck| {
1111 // let c0_noise = measure_noise_lwe(
1112 // c0,
1113 // ck.sk_rlwe.values(),
1114 // &self.rlwe_modop,
1115 // &(self.rlwe_q() - self.rlweq_by8),
1116 // );
1117 // let c1_noise =
1118 // measure_noise_lwe(c1, ck.sk_rlwe.values(), &self.rlwe_modop,
1119 // &(self.rlweq_by8)); println!("c0 noise: {c0_noise}; c1 noise:
1120 // {c1_noise}"); });
1121
1122 let mut c_out = M::R::zeros(c0.as_ref().len());
1123 let modop = &self.rlwe_modop;
1124 izip!(
1125 c_out.as_mut().iter_mut(),
1126 c0.as_ref().iter(),
1127 c1.as_ref().iter()
1128 )
1129 .for_each(|(o, i0, i1)| {
1130 *o = modop.add(i0, i1);
1131 });
1132 // +Q/8
1133 c_out.as_mut()[0] = modop.add(&c_out.as_ref()[0], &self.rlweq_by8);
1134
1135 // ClientKey::with_local(|ck| {
1136 // let noise = measure_noise_lwe(
1137 // &c_out,
1138 // ck.sk_rlwe.values(),
1139 // &self.rlwe_modop,
1140 // &(self.rlweq_by8),
1141 // );
1142 // println!("cout_noise: {noise}");
1143 // });
1144
1145 // PBS
1146 pbs(
1147 self,
1148 &self.nand_test_vec,
1149 &mut c_out,
1150 scratch_lwen_plus1,
1151 scratch_matrix_dplus2_ring,
1152 &self.lwe_modop,
1153 &self.rlwe_modop,
1154 &self.rlwe_nttop,
1155 server_key,
1156 );
1157
1158 c_out
1159 }
1160}
1161
1162impl<M: Matrix, NttOp, ModOp> PbsParameters for BoolEvaluator<M, M::MatElement, NttOp, ModOp>
1163where
1164 M::MatElement: PrimInt + WrappingSub + Debug,
1165{
1166 type Element = M::MatElement;
1167 type D = DefaultDecomposer<M::MatElement>;
1168 fn rlwe_auto_map(&self, k: isize) -> &(Vec<usize>, Vec<bool>) {
1169 let g = self.parameters.g as isize;
1170 if k == g {
1171 &self.rlwe_auto_maps[0]
1172 } else if k == -g {
1173 &self.rlwe_auto_maps[1]
1174 } else {
1175 panic!("RLWE auto map only supports k in [-g, g], but got k={k}");
1176 }
1177 }
1178
1179 fn br_q(&self) -> usize {
1180 self.parameters.br_q
1181 }
1182 fn d_lwe(&self) -> usize {
1183 self.parameters.d_lwe
1184 }
1185 fn d_rgsw(&self) -> usize {
1186 self.parameters.d_rgsw
1187 }
1188 fn decomoposer_lwe(&self) -> &Self::D {
1189 &self.decomposer_lwe
1190 }
1191 fn decomoposer_rlwe(&self) -> &Self::D {
1192 &self.decomposer_rlwe
1193 }
1194 fn embedding_factor(&self) -> usize {
1195 self.embedding_factor
1196 }
1197 fn g(&self) -> isize {
1198 self.parameters.g as isize
1199 }
1200 fn g_k_dlog_map(&self) -> &[usize] {
1201 &self.g_k_dlog_map
1202 }
1203 fn lwe_n(&self) -> usize {
1204 self.parameters.lwe_n
1205 }
1206 fn lwe_q(&self) -> Self::Element {
1207 self.parameters.lwe_q
1208 }
1209 fn rlwe_n(&self) -> usize {
1210 self.parameters.rlwe_n
1211 }
1212 fn rlwe_q(&self) -> Self::Element {
1213 self.parameters.rlwe_q
1214 }
1215}
1216
1217/// LMKCY+ Blind rotation
1218///
1219/// gk_to_si: [-g^0, -g^1, .., -g^{q/2-1}, g^0, ..., g^{q/2-1}]
1220fn blind_rotation<
1221 MT: IsTrivial + MatrixMut,
1222 Mmut: MatrixMut<MatElement = MT::MatElement> + Matrix,
1223 D: Decomposer<Element = MT::MatElement>,
1224 NttOp: Ntt<Element = MT::MatElement>,
1225 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
1226 K: PbsKey<M = Mmut>,
1227 P: PbsParameters<Element = MT::MatElement>,
1228>(
1229 trivial_rlwe_test_poly: &mut MT,
1230 scratch_matrix_dplus2_ring: &mut Mmut,
1231 g: isize,
1232 w: usize,
1233 q: usize,
1234 gk_to_si: &[Vec<usize>],
1235 decomposer: &D,
1236 ntt_op: &NttOp,
1237 mod_op: &ModOp,
1238 parameters: &P,
1239 pbs_key: &K,
1240) where
1241 <Mmut as Matrix>::R: RowMut,
1242 Mmut::MatElement: Copy + Zero,
1243 <MT as Matrix>::R: RowMut,
1244{
1245 let q_by_2 = q / 2;
1246
1247 // -(g^k)
1248 for i in (1..q_by_2).rev() {
1249 gk_to_si[q_by_2 + i].iter().for_each(|s_index| {
1250 rlwe_by_rgsw(
1251 trivial_rlwe_test_poly,
1252 pbs_key.rgsw_ct_lwe_si(*s_index),
1253 scratch_matrix_dplus2_ring,
1254 decomposer,
1255 ntt_op,
1256 mod_op,
1257 );
1258 });
1259
1260 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1261 galois_auto(
1262 trivial_rlwe_test_poly,
1263 pbs_key.galois_key_for_auto(g),
1264 scratch_matrix_dplus2_ring,
1265 &auto_map_index,
1266 &auto_map_sign,
1267 mod_op,
1268 ntt_op,
1269 decomposer,
1270 );
1271 }
1272
1273 // -(g^0)
1274 gk_to_si[q_by_2].iter().for_each(|s_index| {
1275 rlwe_by_rgsw(
1276 trivial_rlwe_test_poly,
1277 pbs_key.rgsw_ct_lwe_si(*s_index),
1278 scratch_matrix_dplus2_ring,
1279 decomposer,
1280 ntt_op,
1281 mod_op,
1282 );
1283 });
1284 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(-g);
1285 galois_auto(
1286 trivial_rlwe_test_poly,
1287 pbs_key.galois_key_for_auto(-g),
1288 scratch_matrix_dplus2_ring,
1289 &auto_map_index,
1290 &auto_map_sign,
1291 mod_op,
1292 ntt_op,
1293 decomposer,
1294 );
1295
1296 // +(g^k)
1297 for i in (1..q_by_2).rev() {
1298 gk_to_si[i].iter().for_each(|s_index| {
1299 rlwe_by_rgsw(
1300 trivial_rlwe_test_poly,
1301 pbs_key.rgsw_ct_lwe_si(*s_index),
1302 scratch_matrix_dplus2_ring,
1303 decomposer,
1304 ntt_op,
1305 mod_op,
1306 );
1307 });
1308
1309 let (auto_map_index, auto_map_sign) = parameters.rlwe_auto_map(g);
1310 galois_auto(
1311 trivial_rlwe_test_poly,
1312 pbs_key.galois_key_for_auto(g),
1313 scratch_matrix_dplus2_ring,
1314 &auto_map_index,
1315 &auto_map_sign,
1316 mod_op,
1317 ntt_op,
1318 decomposer,
1319 );
1320 }
1321
1322 // +(g^0)
1323 gk_to_si[0].iter().for_each(|s_index| {
1324 rlwe_by_rgsw(
1325 trivial_rlwe_test_poly,
1326 pbs_key.rgsw_ct_lwe_si(gk_to_si[q_by_2][*s_index]),
1327 scratch_matrix_dplus2_ring,
1328 decomposer,
1329 ntt_op,
1330 mod_op,
1331 );
1332 });
1333}
1334
1335/// - Mod down
1336/// - key switching
1337/// - mod down
1338/// - blind rotate
1339fn pbs<
1340 M: Matrix + MatrixMut + MatrixEntity,
1341 P: PbsParameters<Element = M::MatElement>,
1342 NttOp: Ntt<Element = M::MatElement>,
1343 ModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
1344 K: PbsKey<M = M>,
1345>(
1346 parameters: &P,
1347 test_vec: &M::R,
1348 lwe_in: &mut M::R,
1349 scratch_lwen_plus1: &mut M::R,
1350 scratch_matrix_dplus2_ring: &mut M,
1351 modop_lweq: &ModOp,
1352 modop_rlweq: &ModOp,
1353 nttop_rlweq: &NttOp,
1354 pbs_key: &K,
1355) where
1356 <M as Matrix>::R: RowMut,
1357 M::MatElement: PrimInt + ToPrimitive + FromPrimitive + One + Copy + Zero + Display,
1358{
1359 let rlwe_q = parameters.rlwe_q();
1360 let lwe_q = parameters.lwe_q();
1361 let br_q = parameters.br_q();
1362 let rlwe_qf64 = rlwe_q.to_f64().unwrap();
1363 let lwe_qf64 = lwe_q.to_f64().unwrap();
1364 let br_qf64 = br_q.to_f64().unwrap();
1365 let rlwe_n = parameters.rlwe_n();
1366
1367 // moddown Q -> Q_ks
1368 lwe_in.as_mut().iter_mut().for_each(|v| {
1369 *v =
1370 M::MatElement::from_f64(((v.to_f64().unwrap() * lwe_qf64) / rlwe_qf64).round()).unwrap()
1371 });
1372
1373 PBSTracer::with_local_mut(|t| {
1374 let out = lwe_in
1375 .as_ref()
1376 .iter()
1377 .map(|v| v.to_u64().unwrap())
1378 .collect_vec();
1379 t.ct_lwe_q_mod = out;
1380 });
1381
1382 // key switch RLWE secret to LWE secret
1383 scratch_lwen_plus1.as_mut().fill(M::MatElement::zero());
1384 lwe_key_switch(
1385 scratch_lwen_plus1,
1386 lwe_in,
1387 pbs_key.lwe_ksk(),
1388 modop_lweq,
1389 parameters.decomoposer_lwe(),
1390 );
1391
1392 PBSTracer::with_local_mut(|t| {
1393 let out = scratch_lwen_plus1
1394 .as_ref()
1395 .iter()
1396 .map(|v| v.to_u64().unwrap())
1397 .collect_vec();
1398 t.ct_lwe_q_mod_after_ksk = out;
1399 });
1400
1401 // odd mowdown Q_ks -> q
1402 let g_k_dlog_map = parameters.g_k_dlog_map();
1403 let mut g_k_si = vec![vec![]; br_q];
1404 scratch_lwen_plus1
1405 .as_ref()
1406 .iter()
1407 .skip(1)
1408 .enumerate()
1409 .for_each(|(index, v)| {
1410 let odd_v = mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64);
1411 let k = g_k_dlog_map[odd_v];
1412 g_k_si[k].push(index);
1413 });
1414
1415 PBSTracer::with_local_mut(|t| {
1416 let out = scratch_lwen_plus1
1417 .as_ref()
1418 .iter()
1419 .map(|v| mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64) as u64)
1420 .collect_vec();
1421 t.ct_br_q_mod = out;
1422 });
1423
1424 // handle b and set trivial test RLWE
1425 let g = parameters.g() as usize;
1426 let g_times_b = (g * mod_switch_odd(
1427 scratch_lwen_plus1.as_ref()[0].to_f64().unwrap(),
1428 lwe_qf64,
1429 br_qf64,
1430 )) % (br_q);
1431 // v = (v(X) * X^{g*b}) mod X^{q/2}+1
1432 let br_qby2 = br_q / 2;
1433 let mut gb_monomial_sign = true;
1434 let mut gb_monomial_exp = g_times_b;
1435 // X^{g*b} mod X^{q/2}+1
1436 if gb_monomial_exp > br_qby2 {
1437 gb_monomial_exp -= br_qby2;
1438 gb_monomial_sign = false
1439 }
1440 // monomial mul
1441 let mut trivial_rlwe_test_poly =
1442 RlweCiphertext::<_, DefaultSecureRng>::from_raw(M::zeros(2, rlwe_n), true);
1443 if parameters.embedding_factor() == 1 {
1444 monomial_mul(
1445 test_vec.as_ref(),
1446 trivial_rlwe_test_poly.get_row_mut(1).as_mut(),
1447 gb_monomial_exp,
1448 gb_monomial_sign,
1449 br_qby2,
1450 modop_rlweq,
1451 );
1452 } else {
1453 // use lwe_in to store the `t = v(X) * X^{g*2} mod X^{q/2}+1` temporarily. This
1454 // works because q/2 <= N (where N is lwe_in LWE dimension) always.
1455 monomial_mul(
1456 test_vec.as_ref(),
1457 &mut lwe_in.as_mut()[..br_qby2],
1458 gb_monomial_exp,
1459 gb_monomial_sign,
1460 br_qby2,
1461 modop_rlweq,
1462 );
1463
1464 // emebed poly `t` in ring X^{q/2}+1 inside the bigger ring X^{N}+1
1465 let embed_factor = parameters.embedding_factor();
1466 let partb_trivial_rlwe = trivial_rlwe_test_poly.get_row_mut(1);
1467 lwe_in.as_ref()[..br_qby2]
1468 .iter()
1469 .enumerate()
1470 .for_each(|(index, v)| {
1471 partb_trivial_rlwe[embed_factor * index] = *v;
1472 });
1473 }
1474
1475 // blind rotate
1476 blind_rotation(
1477 &mut trivial_rlwe_test_poly,
1478 scratch_matrix_dplus2_ring,
1479 parameters.g(),
1480 1,
1481 br_q,
1482 &g_k_si,
1483 parameters.decomoposer_rlwe(),
1484 nttop_rlweq,
1485 modop_rlweq,
1486 parameters,
1487 pbs_key,
1488 );
1489
1490 // ClientKey::with_local(|ck| {
1491 // let ring_size = parameters.rlwe_n();
1492 // let mut rlwe_ct = vec![vec![0u64; ring_size]; 2];
1493 // izip!(
1494 // rlwe_ct[0].iter_mut(),
1495 // trivial_rlwe_test_poly.0.get_row_slice(0)
1496 // )
1497 // .for_each(|(t, f)| {
1498 // *t = f.to_u64().unwrap();
1499 // });
1500 // izip!(
1501 // rlwe_ct[1].iter_mut(),
1502 // trivial_rlwe_test_poly.0.get_row_slice(1)
1503 // )
1504 // .for_each(|(t, f)| {
1505 // *t = f.to_u64().unwrap();
1506 // });
1507 // let mut m_out = vec![vec![0u64; ring_size]];
1508 // let modop = ModularOpsU64::new(rlwe_q.to_u64().unwrap());
1509 // let nttop = NttBackendU64::new(rlwe_q.to_u64().unwrap(), ring_size);
1510 // decrypt_rlwe(&rlwe_ct, ck.sk_rlwe.values(), &mut m_out, &nttop, &modop);
1511
1512 // println!("RLWE post PBS message: {:?}", m_out[0]);
1513 // });
1514
1515 // sample extract
1516 sample_extract(lwe_in, &trivial_rlwe_test_poly, modop_rlweq, 0);
1517}
1518
1519fn mod_switch_odd(v: f64, from_q: f64, to_q: f64) -> usize {
1520 let odd_v = (((v * to_q) / (from_q)).floor()).to_usize().unwrap();
1521 //TODO(Jay): check correctness of this
1522 odd_v + ((odd_v & 1) ^ 1)
1523}
1524
1525// TODO(Jay): Add tests for sample extract
1526fn sample_extract<M: Matrix + MatrixMut, ModOp: ArithmeticOps<Element = M::MatElement>>(
1527 lwe_out: &mut M::R,
1528 rlwe_in: &M,
1529 mod_op: &ModOp,
1530 index: usize,
1531) where
1532 <M as Matrix>::R: RowMut,
1533 M::MatElement: Copy,
1534{
1535 let ring_size = rlwe_in.dimension().1;
1536
1537 // index..=0
1538 let to = &mut lwe_out.as_mut()[1..];
1539 let from = rlwe_in.get_row_slice(0);
1540 for i in 0..index + 1 {
1541 to[i] = from[index - i];
1542 }
1543
1544 // -(N..index)
1545 for i in index + 1..ring_size {
1546 to[i] = mod_op.neg(&from[ring_size + index - i]);
1547 }
1548
1549 // set b
1550 lwe_out.as_mut()[0] = *rlwe_in.get(1, index);
1551}
1552
1553/// TODO(Jay): Write tests for monomial mul
1554fn monomial_mul<El, ModOp: ArithmeticOps<Element = El>>(
1555 p_in: &[El],
1556 p_out: &mut [El],
1557 mon_exp: usize,
1558 mon_sign: bool,
1559 ring_size: usize,
1560 mod_op: &ModOp,
1561) where
1562 El: Copy,
1563{
1564 debug_assert!(p_in.as_ref().len() == ring_size);
1565 debug_assert!(p_in.as_ref().len() == p_out.as_ref().len());
1566 debug_assert!(mon_exp < ring_size);
1567
1568 p_in.as_ref().iter().enumerate().for_each(|(index, v)| {
1569 let mut to_index = index + mon_exp;
1570 let mut to_sign = mon_sign;
1571 if to_index >= ring_size {
1572 to_index = to_index - ring_size;
1573 to_sign = !to_sign;
1574 }
1575
1576 if !to_sign {
1577 p_out.as_mut()[to_index] = mod_op.neg(v);
1578 } else {
1579 p_out.as_mut()[to_index] = *v;
1580 }
1581 });
1582}
1583
1584thread_local! {
1585 static PBS_TRACER: RefCell<PBSTracer<Vec<Vec<u64>>>> = RefCell::new(PBSTracer::default());
1586}
1587
1588#[derive(Default)]
1589struct PBSTracer<M>
1590where
1591 M: Matrix + Default,
1592{
1593 pub(crate) ct_lwe_q_mod: M::R,
1594 pub(crate) ct_lwe_q_mod_after_ksk: M::R,
1595 pub(crate) ct_br_q_mod: Vec<u64>,
1596}
1597
1598impl PBSTracer<Vec<Vec<u64>>> {
1599 fn trace(&self, parameters: &BoolParameters<u64>, sk_lwe: &[i32], sk_rlwe: &[i32]) {
1600 assert!(parameters.rlwe_n == sk_rlwe.len());
1601 assert!(parameters.lwe_n == sk_lwe.len());
1602
1603 let modop_lweq = ModularOpsU64::new(parameters.lwe_q as u64);
1604 // noise after mod down Q -> Q_ks
1605 let m_back0 = decrypt_lwe(&self.ct_lwe_q_mod, sk_rlwe, &modop_lweq);
1606 // noise after key switch from RLWE -> LWE
1607 let m_back1 = decrypt_lwe(&self.ct_lwe_q_mod_after_ksk, sk_lwe, &modop_lweq);
1608
1609 // noise after mod down odd from Q_ks -> q
1610 let modop_br_q = ModularOpsU64::new(parameters.br_q as u64);
1611 let m_back2 = decrypt_lwe(&self.ct_br_q_mod, sk_lwe, &modop_br_q);
1612
1613 println!(
1614 "
1615 M after mod down Q -> Q_ks: {m_back0},
1616 M after key switch from RLWE -> LWE: {m_back1},
1617 M after mod dwon Q_ks -> q: {m_back2}
1618 "
1619 );
1620 }
1621}
1622
1623impl WithLocal for PBSTracer<Vec<Vec<u64>>> {
1624 fn with_local<F, R>(func: F) -> R
1625 where
1626 F: Fn(&Self) -> R,
1627 {
1628 PBS_TRACER.with_borrow(|t| func(t))
1629 }
1630
1631 fn with_local_mut<F, R>(func: F) -> R
1632 where
1633 F: Fn(&mut Self) -> R,
1634 {
1635 PBS_TRACER.with_borrow_mut(|t| func(t))
1636 }
1637}
1638
1639#[cfg(test)]
1640mod tests {
1641 use rand::{thread_rng, Rng};
1642
1643 use crate::{
1644 backend::ModularOpsU64,
1645 bool,
1646 ntt::NttBackendU64,
1647 random::DEFAULT_RNG,
1648 rgsw::{
1649 self, measure_noise, public_key_encrypt_rlwe, secret_key_encrypt_rlwe,
1650 tests::_measure_noise_rgsw, RgswCiphertext, RgswCiphertextEvaluationDomain,
1651 SeededRgswCiphertext, SeededRlweCiphertext,
1652 },
1653 utils::negacyclic_mul,
1654 };
1655
1656 use self::parameters::{MP_BOOL_PARAMS, SP_BOOL_PARAMS};
1657
1658 use super::*;
1659
1660 // #[test]
1661 // fn trial() {
1662 // dbg!(generate_prime(28, 1 << 11, 1 << 28));
1663 // }
1664
1665 #[test]
1666 fn bool_encrypt_decrypt_works() {
1667 // let prime = generate_prime(32, 2 * 1024, 1 << 32);
1668 // dbg!(prime);
1669 let bool_evaluator =
1670 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1671 let client_key = bool_evaluator.client_key();
1672 // let sever_key = bool_evaluator.server_key(&client_key);
1673
1674 let mut m = true;
1675 for _ in 0..1000 {
1676 let lwe_ct = bool_evaluator.sk_encrypt(m, &client_key);
1677 let m_back = bool_evaluator.sk_decrypt(&lwe_ct, &client_key);
1678 assert_eq!(m, m_back);
1679 m = !m;
1680 }
1681 }
1682
1683 #[test]
1684 fn bool_nand() {
1685 DefaultSecureRng::with_local_mut(|r| {
1686 let rng = DefaultSecureRng::new_seeded([19u8; 32]);
1687 *r = rng;
1688 });
1689
1690 let bool_evaluator =
1691 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(SP_BOOL_PARAMS);
1692
1693 // println!("{:?}", bool_evaluator.nand_test_vec);
1694 let client_key = bool_evaluator.client_key();
1695 let seeded_server_key = bool_evaluator.server_key(&client_key);
1696 let server_key_eval_domain =
1697 ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1698 &seeded_server_key,
1699 );
1700
1701 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
1702 let mut scratch_matrix_dplus2_ring = vec![
1703 vec![0u64; bool_evaluator.parameters.rlwe_n];
1704 bool_evaluator.parameters.d_rgsw + 2
1705 ];
1706
1707 let mut m0 = false;
1708 let mut m1 = true;
1709 let mut ct0 = bool_evaluator.sk_encrypt(m0, &client_key);
1710 let mut ct1 = bool_evaluator.sk_encrypt(m1, &client_key);
1711 for _ in 0..1000 {
1712 let ct_back = bool_evaluator.nand(
1713 &ct0,
1714 &ct1,
1715 &server_key_eval_domain,
1716 &mut scratch_lwen_plus1,
1717 &mut scratch_matrix_dplus2_ring,
1718 );
1719
1720 let m_out = !(m0 && m1);
1721
1722 // Trace and measure PBS noise
1723 {
1724 // Trace PBS
1725 PBSTracer::with_local(|t| {
1726 t.trace(
1727 &SP_BOOL_PARAMS,
1728 &client_key.sk_lwe.values(),
1729 client_key.sk_rlwe.values(),
1730 )
1731 });
1732
1733 // Calculate noise in ciphertext post PBS
1734 let ideal = if m_out {
1735 bool_evaluator.rlweq_by8
1736 } else {
1737 bool_evaluator.rlwe_q() - bool_evaluator.rlweq_by8
1738 };
1739 let noise = measure_noise_lwe(
1740 &ct_back,
1741 client_key.sk_rlwe.values(),
1742 &bool_evaluator.rlwe_modop,
1743 &ideal,
1744 );
1745 println!("PBS noise: {noise}");
1746 }
1747 let m_back = bool_evaluator.sk_decrypt(&ct_back, &client_key);
1748 assert_eq!(m_out, m_back);
1749 println!("----------");
1750
1751 m1 = m0;
1752 m0 = m_out;
1753
1754 ct1 = ct0;
1755 ct0 = ct_back;
1756 }
1757 }
1758
1759 #[test]
1760 fn multi_party_encryption_decryption() {
1761 let bool_evaluator =
1762 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
1763
1764 let no_of_parties = 5;
1765 let parties = (0..no_of_parties)
1766 .map(|_| bool_evaluator.client_key())
1767 .collect_vec();
1768
1769 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
1770 parties.iter().for_each(|k| {
1771 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
1772 *ideal_i = *ideal_i + s_i;
1773 });
1774 });
1775
1776 let mut m = true;
1777 for i in 0..100 {
1778 let pk_cr_seed = [0u8; 32];
1779
1780 let public_key_share = parties
1781 .iter()
1782 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1783 .collect_vec();
1784
1785 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
1786 public_key_share.as_slice(),
1787 );
1788 let lwe_ct = bool_evaluator.pk_encrypt(&collective_pk.key, m);
1789
1790 let decryption_shares = parties
1791 .iter()
1792 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_ct, k))
1793 .collect_vec();
1794
1795 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_ct);
1796
1797 {
1798 let ideal_m = if m {
1799 bool_evaluator.rlweq_by8
1800 } else {
1801 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
1802 };
1803 let noise = measure_noise_lwe(
1804 &lwe_ct,
1805 &ideal_rlwe_sk,
1806 &bool_evaluator.rlwe_modop,
1807 &ideal_m,
1808 );
1809 println!("Noise: {noise}");
1810 }
1811
1812 assert_eq!(m_back, m);
1813 m = !m;
1814 }
1815 }
1816
1817 #[test]
1818 fn multi_party_lwe_keyswitch() {
1819 let lwe_logq = 18;
1820 let lwe_q = 1 << lwe_logq;
1821 let d_lwe = 4;
1822 let logb_lwe = 4;
1823 let lwe_gadgect_vec = gadget_vector(lwe_logq, logb_lwe, d_lwe);
1824 let lweq_modop = ModularOpsU64::new(lwe_q);
1825 let logp = 2;
1826
1827 let from_lwe_n = 2048;
1828 let to_lwe_n = 583;
1829
1830 let no_of_parties = 10;
1831 let parties_from_lwe_sk = (0..no_of_parties)
1832 .map(|_| LweSecret::random(from_lwe_n >> 1, from_lwe_n))
1833 .collect_vec();
1834 let parties_to_lwe_sk = (0..no_of_parties)
1835 .map(|_| LweSecret::random(to_lwe_n >> 1, to_lwe_n))
1836 .collect_vec();
1837
1838 // Generate Lwe KSK share
1839 let mut rng = DefaultSecureRng::new();
1840 let mut ksk_seed = [0u8; 32];
1841 rng.fill_bytes(&mut ksk_seed);
1842 let lwe_ksk_shares =
1843 izip!(parties_from_lwe_sk.iter(), parties_to_lwe_sk.iter()).map(|(from_sk, to_sk)| {
1844 let mut ksk_out = vec![0u64; from_lwe_n * d_lwe];
1845 let mut p_rng = DefaultSecureRng::new_seeded(ksk_seed);
1846 lwe_ksk_keygen(
1847 from_sk.values(),
1848 to_sk.values(),
1849 &mut ksk_out,
1850 &lwe_gadgect_vec,
1851 &lweq_modop,
1852 &mut p_rng,
1853 &mut rng,
1854 );
1855 ksk_out
1856 });
1857
1858 // Create collective LWE ksk
1859 let mut sum_partb = vec![0u64; d_lwe * from_lwe_n];
1860 lwe_ksk_shares.for_each(|share| {
1861 lweq_modop.elwise_add_mut(sum_partb.as_mut_slice(), share.as_slice())
1862 });
1863 let mut lwe_ksk = vec![vec![0u64; to_lwe_n + 1]; d_lwe * from_lwe_n];
1864 let mut p_rng = DefaultSecureRng::new_seeded(ksk_seed);
1865 izip!(lwe_ksk.iter_mut(), sum_partb.iter()).for_each(|(lwe_i, part_bi)| {
1866 RandomUniformDist::random_fill(&mut p_rng, &lwe_q, &mut lwe_i.as_mut_slice()[1..]);
1867 lwe_i[0] = *part_bi;
1868 });
1869
1870 // Collective pk
1871 // let collective_pk = _collecitve_public_key_gen(
1872 // lwe_q,
1873 // &parties_from_lwe_sk
1874 // .iter()
1875 // .map(|s| RlweSecret {
1876 // values: s.values.clone(),
1877 // })
1878 // .collect_vec(),
1879 // );
1880
1881 // // Encrypt m as LWE ciphertext
1882 // let m = 1;
1883 // let lwe_ct = {
1884 // let nttop = NttBackendU64::new(lwe_q, from_lwe_n);
1885 // let modop = ModularOpsU64::new(lwe_q);
1886 // let mut rlwe_out = vec![vec![0u64]; from_lwe_n];
1887 // let mut m_vec = vec![0u64; from_lwe_n];
1888 // m_vec[0] = m;
1889 // public_key_encrypt_rlwe(
1890 // &mut rlwe_out,
1891 // &collective_pk,
1892 // &m_vec,
1893 // &modop,
1894 // &nttop,
1895 // &mut rng,
1896 // );
1897 // let mut lwe_ct = vec![0u64; from_lwe_n + 1];
1898 // sample_extract(&mut lwe_ct, &rlwe_out, &modop, 0);
1899 // lwe_ct
1900 // };
1901 // Encrypt m
1902 let m = 1;
1903 let mut ideal_from_lwe_sk = vec![0i32; from_lwe_n];
1904 parties_from_lwe_sk.iter().for_each(|k| {
1905 izip!(ideal_from_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1906 *ideal_i = *ideal_i + s_i;
1907 });
1908 });
1909 let mut lwe_ct = vec![0u64; from_lwe_n + 1];
1910 encrypt_lwe(&mut lwe_ct, &m, &ideal_from_lwe_sk, &lweq_modop, &mut rng);
1911
1912 // Key switch
1913 let lwe_ct_key_switched = {
1914 let mut lwe_ct_key_switched = vec![0u64; to_lwe_n + 1];
1915 let decomposer = DefaultDecomposer::new(lwe_q, logb_lwe, d_lwe);
1916 lwe_key_switch(
1917 &mut lwe_ct_key_switched,
1918 &lwe_ct,
1919 &lwe_ksk,
1920 &lweq_modop,
1921 &decomposer,
1922 );
1923 lwe_ct_key_switched
1924 };
1925
1926 // Measure noise
1927 let mut ideal_to_lwe_sk = vec![0i32; to_lwe_n];
1928 parties_to_lwe_sk.iter().for_each(|k| {
1929 izip!(ideal_to_lwe_sk.iter_mut(), k.values()).for_each(|(ideal_i, s_i)| {
1930 *ideal_i = *ideal_i + s_i;
1931 });
1932 });
1933 let noise = measure_noise_lwe(&lwe_ct_key_switched, &ideal_to_lwe_sk, &lweq_modop, &m);
1934 println!("Noise: {noise}");
1935 }
1936
1937 fn _collecitve_public_key_gen(rlwe_q: u64, parties_rlwe_sk: &[RlweSecret]) -> Vec<Vec<u64>> {
1938 let ring_size = parties_rlwe_sk[0].values.len();
1939 assert!(ring_size.is_power_of_two());
1940 let mut rng = DefaultSecureRng::new();
1941 let nttop = NttBackendU64::new(rlwe_q, ring_size);
1942 let modop = ModularOpsU64::new(rlwe_q);
1943
1944 // Generate Pk shares
1945 let pk_seed = [0u8; 32];
1946 let pk_shares = parties_rlwe_sk.iter().map(|sk| {
1947 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
1948 let mut share_out = vec![0u64; ring_size];
1949 public_key_share(
1950 &mut share_out,
1951 sk.values(),
1952 &modop,
1953 &nttop,
1954 &mut p_rng,
1955 &mut rng,
1956 );
1957 share_out
1958 });
1959
1960 let mut pk_part_b = vec![0u64; ring_size];
1961 pk_shares.for_each(|share| modop.elwise_add_mut(&mut pk_part_b, &share));
1962 let mut pk_part_a = vec![0u64; ring_size];
1963 let mut p_rng = DefaultSecureRng::new_seeded(pk_seed);
1964 RandomUniformDist::random_fill(&mut p_rng, &rlwe_q, pk_part_a.as_mut_slice());
1965
1966 vec![pk_part_a, pk_part_b]
1967 }
1968
1969 fn _multi_party_keygen(
1970 bool_evaluator: &BoolEvaluator<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>,
1971 no_of_parties: usize,
1972 ) -> (
1973 Vec<ClientKey>,
1974 PublicKey<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>,
1975 Vec<
1976 CommonReferenceSeededMultiPartyServerKeyShare<
1977 Vec<Vec<u64>>,
1978 BoolParameters<u64>,
1979 [u8; 32],
1980 >,
1981 >,
1982 SeededMultiPartyServerKey<Vec<Vec<u64>>, [u8; 32], BoolParameters<u64>>,
1983 ServerKeyEvaluationDomain<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>,
1984 ClientKey,
1985 ) {
1986 let parties = (0..no_of_parties)
1987 .map(|_| bool_evaluator.client_key())
1988 .collect_vec();
1989
1990 // Collective public key
1991 let pk_cr_seed = [0u8; 32];
1992 let public_key_share = parties
1993 .iter()
1994 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
1995 .collect_vec();
1996 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
1997 public_key_share.as_slice(),
1998 );
1999
2000 // Server key
2001 let pbs_cr_seed = [1u8; 32];
2002 let server_key_shares = parties
2003 .iter()
2004 .map(|k| bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k))
2005 .collect_vec();
2006 let seeded_server_key =
2007 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
2008 &server_key_shares,
2009 &bool_evaluator.decomposer_rlwe,
2010 );
2011 let server_key_eval = ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2012 &seeded_server_key,
2013 );
2014
2015 // construct ideal rlwe sk for meauring noise
2016 let ideal_client_key = {
2017 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
2018 parties.iter().for_each(|k| {
2019 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
2020 *ideal_i = *ideal_i + s_i;
2021 });
2022 });
2023 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
2024 parties.iter().for_each(|k| {
2025 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
2026 *ideal_i = *ideal_i + s_i;
2027 });
2028 });
2029
2030 ClientKey {
2031 sk_lwe: LweSecret {
2032 values: ideal_lwe_sk,
2033 },
2034 sk_rlwe: RlweSecret {
2035 values: ideal_rlwe_sk,
2036 },
2037 }
2038 };
2039
2040 (
2041 parties,
2042 collective_pk,
2043 server_key_shares,
2044 seeded_server_key,
2045 server_key_eval,
2046 ideal_client_key,
2047 )
2048 }
2049
2050 #[test]
2051 fn mp_key_correcntess() {
2052 let bool_evaluator =
2053 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2054
2055 let (_, collective_pk, _, _, server_key_eval, ideal_client_key) =
2056 _multi_party_keygen(&bool_evaluator, 2);
2057
2058 let lwe_q = bool_evaluator.parameters.lwe_q;
2059 let rlwe_q = bool_evaluator.parameters.rlwe_q;
2060 let d_rgsw = bool_evaluator.parameters.d_rgsw;
2061 let lwe_logq = bool_evaluator.parameters.lwe_logq;
2062 let lwe_n = bool_evaluator.parameters.lwe_n;
2063 let rlwe_n = bool_evaluator.parameters.rlwe_n;
2064 let lwe_modop = &bool_evaluator.lwe_modop;
2065 let rlwe_nttop = &bool_evaluator.rlwe_nttop;
2066 let rlwe_modop = &bool_evaluator.rlwe_modop;
2067 let rlwe_decomposer = &bool_evaluator.decomposer_rlwe;
2068
2069 // test LWE ksk from RLWE -> LWE
2070 if true {
2071 let logp = 2;
2072 let mut rng = DefaultSecureRng::new();
2073
2074 let m = 1;
2075 let encoded_m = m << (lwe_logq - logp);
2076
2077 // Encrypt
2078 let mut lwe_ct = vec![0u64; rlwe_n + 1];
2079 encrypt_lwe(
2080 &mut lwe_ct,
2081 &encoded_m,
2082 ideal_client_key.sk_rlwe.values(),
2083 lwe_modop,
2084 &mut rng,
2085 );
2086
2087 // key switch
2088 let lwe_decomposer = &bool_evaluator.decomposer_lwe;
2089 let mut lwe_out = vec![0u64; lwe_n + 1];
2090 lwe_key_switch(
2091 &mut lwe_out,
2092 &lwe_ct,
2093 &server_key_eval.lwe_ksk,
2094 lwe_modop,
2095 lwe_decomposer,
2096 );
2097
2098 let encoded_m_back = decrypt_lwe(&lwe_out, ideal_client_key.sk_lwe.values(), lwe_modop);
2099 let m_back =
2100 ((encoded_m_back as f64 * (1 << logp) as f64) / (lwe_q as f64)).round() as u64;
2101 dbg!(m_back, m);
2102
2103 let noise = measure_noise_lwe(
2104 &lwe_out,
2105 ideal_client_key.sk_lwe.values(),
2106 lwe_modop,
2107 &encoded_m,
2108 );
2109
2110 println!("Noise: {noise}");
2111 }
2112
2113 // Measure noise in RGSW ciphertexts of ideal LWE secrets
2114 if false {
2115 let gadget_vec = gadget_vector(
2116 bool_evaluator.parameters.rlwe_logq,
2117 bool_evaluator.parameters.logb_rgsw,
2118 bool_evaluator.parameters.d_rgsw,
2119 );
2120
2121 for i in 0..20 {
2122 // measure noise in RGSW(s[i])
2123 let si =
2124 ideal_client_key.sk_lwe.values[i] * (bool_evaluator.embedding_factor as i32);
2125 let mut si_poly = vec![0u64; rlwe_n];
2126 if si < 0 {
2127 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2128 } else {
2129 si_poly[(si.abs() as usize)] = 1;
2130 }
2131
2132 let mut rgsw_si = server_key_eval.rgsw_cts[i].clone();
2133 rgsw_si
2134 .iter_mut()
2135 .for_each(|ri| rlwe_nttop.backward(ri.as_mut()));
2136
2137 println!("####### Noise in RGSW(X^s_{i}) #######");
2138 _measure_noise_rgsw(
2139 &rgsw_si,
2140 &si_poly,
2141 ideal_client_key.sk_rlwe.values(),
2142 &gadget_vec,
2143 rlwe_q,
2144 );
2145 println!("####### ##################### #######");
2146 }
2147 }
2148
2149 // measure noise grwoth in RLWExRGSW
2150 if false {
2151 let mut rng = DefaultSecureRng::new();
2152 let mut carry_m = vec![0u64; rlwe_n];
2153 RandomUniformDist::random_fill(&mut rng, &rlwe_q, carry_m.as_mut_slice());
2154
2155 // RGSW(carrym)
2156 let trivial_rlwect = vec![vec![0u64; rlwe_n], carry_m.clone()];
2157 let mut rlwe_ct = RlweCiphertext::<_, DefaultSecureRng>::from_raw(trivial_rlwect, true);
2158
2159 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
2160 let mul_mod =
2161 |v0: &u64, v1: &u64| (((*v0 as u128 * *v1 as u128) % (rlwe_q as u128)) as u64);
2162
2163 for i in 0..450 {
2164 rlwe_by_rgsw(
2165 &mut rlwe_ct,
2166 server_key_eval.rgsw_ct_lwe_si(i),
2167 &mut scratch_matrix_dplus2_ring,
2168 rlwe_decomposer,
2169 rlwe_nttop,
2170 rlwe_modop,
2171 );
2172
2173 // carry_m[X] * s_i[X]
2174 let si =
2175 ideal_client_key.sk_lwe.values[i] * (bool_evaluator.embedding_factor as i32);
2176 let mut si_poly = vec![0u64; rlwe_n];
2177 if si < 0 {
2178 si_poly[rlwe_n - (si.abs() as usize)] = rlwe_q - 1;
2179 } else {
2180 si_poly[(si.abs() as usize)] = 1;
2181 }
2182 carry_m = negacyclic_mul(&carry_m, &si_poly, mul_mod, rlwe_q);
2183
2184 let noise = measure_noise(
2185 &rlwe_ct,
2186 &carry_m,
2187 rlwe_nttop,
2188 rlwe_modop,
2189 ideal_client_key.sk_rlwe.values(),
2190 );
2191 println!("Noise RLWE(carry_m) accumulating {i}^th secret monomial: {noise}");
2192 }
2193 }
2194
2195 // Check galois keys
2196 if false {
2197 let g = bool_evaluator.g() as isize;
2198 let mut rng = DefaultSecureRng::new();
2199 let mut scratch_matrix_dplus2_ring = vec![vec![0u64; rlwe_n]; d_rgsw + 2];
2200 for i in [g, -g] {
2201 let mut m = vec![0u64; rlwe_n];
2202 RandomUniformDist::random_fill(&mut rng, &rlwe_q, m.as_mut_slice());
2203 let mut rlwe_ct = {
2204 let mut data = vec![vec![0u64; rlwe_n]; 2];
2205 public_key_encrypt_rlwe(
2206 &mut data,
2207 &collective_pk.key,
2208 &m,
2209 rlwe_modop,
2210 rlwe_nttop,
2211 &mut rng,
2212 );
2213 RlweCiphertext::<_, DefaultSecureRng>::from_raw(data, false)
2214 };
2215
2216 let auto_key = server_key_eval.galois_key_for_auto(i);
2217 let (auto_map_index, auto_map_sign) = generate_auto_map(rlwe_n, i);
2218 galois_auto(
2219 &mut rlwe_ct,
2220 auto_key,
2221 &mut scratch_matrix_dplus2_ring,
2222 &auto_map_index,
2223 &auto_map_sign,
2224 rlwe_modop,
2225 rlwe_nttop,
2226 rlwe_decomposer,
2227 );
2228
2229 // send m(X) -> m(X^i)
2230 let mut m_k = vec![0u64; rlwe_n];
2231 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
2232 |(mi, to_index, to_sign)| {
2233 if !to_sign {
2234 m_k[*to_index] = rlwe_q - *mi;
2235 } else {
2236 m_k[*to_index] = *mi;
2237 }
2238 },
2239 );
2240
2241 // measure noise
2242 let noise = measure_noise(
2243 &rlwe_ct,
2244 &m_k,
2245 rlwe_nttop,
2246 rlwe_modop,
2247 ideal_client_key.sk_rlwe.values(),
2248 );
2249
2250 println!("Noise after auto k={i}: {noise}");
2251 }
2252 }
2253 }
2254
2255 #[test]
2256 fn multi_party_nand() {
2257 let bool_evaluator =
2258 BoolEvaluator::<Vec<Vec<u64>>, u64, NttBackendU64, ModularOpsU64>::new(MP_BOOL_PARAMS);
2259
2260 let no_of_parties = 20;
2261 let parties = (0..no_of_parties)
2262 .map(|_| bool_evaluator.client_key())
2263 .collect_vec();
2264
2265 // Collective public key
2266 let pk_cr_seed = [0u8; 32];
2267 let public_key_share = parties
2268 .iter()
2269 .map(|k| bool_evaluator.multi_party_public_key_share(pk_cr_seed, k))
2270 .collect_vec();
2271 let collective_pk = PublicKey::<Vec<Vec<u64>>, DefaultSecureRng, ModularOpsU64>::from(
2272 public_key_share.as_slice(),
2273 );
2274
2275 // Server key
2276 let pbs_cr_seed = [1u8; 32];
2277 let server_key_shares = parties
2278 .iter()
2279 .map(|k| bool_evaluator.multi_party_sever_key_share(pbs_cr_seed, &collective_pk.key, k))
2280 .collect_vec();
2281 let seeded_server_key =
2282 aggregate_multi_party_server_key_shares::<_, _, _, ModularOpsU64, NttBackendU64>(
2283 &server_key_shares,
2284 &bool_evaluator.decomposer_rlwe,
2285 );
2286 let server_key_eval = ServerKeyEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2287 &seeded_server_key,
2288 );
2289
2290 // construct ideal rlwe sk for meauring noise
2291 let ideal_client_key = {
2292 let mut ideal_rlwe_sk = vec![0i32; bool_evaluator.rlwe_n()];
2293 parties.iter().for_each(|k| {
2294 izip!(ideal_rlwe_sk.iter_mut(), k.sk_rlwe.values()).for_each(|(ideal_i, s_i)| {
2295 *ideal_i = *ideal_i + s_i;
2296 });
2297 });
2298 let mut ideal_lwe_sk = vec![0i32; bool_evaluator.lwe_n()];
2299 parties.iter().for_each(|k| {
2300 izip!(ideal_lwe_sk.iter_mut(), k.sk_lwe.values()).for_each(|(ideal_i, s_i)| {
2301 *ideal_i = *ideal_i + s_i;
2302 });
2303 });
2304
2305 ClientKey {
2306 sk_lwe: LweSecret {
2307 values: ideal_lwe_sk,
2308 },
2309 sk_rlwe: RlweSecret {
2310 values: ideal_rlwe_sk,
2311 },
2312 }
2313 };
2314
2315 // PBS
2316 let mut scratch_lwen_plus1 = vec![0u64; bool_evaluator.parameters.lwe_n + 1];
2317 let mut scratch_matrix_dplus2_ring = vec![
2318 vec![0u64; bool_evaluator.parameters.rlwe_n];
2319 bool_evaluator.parameters.d_rgsw + 2
2320 ];
2321
2322 let mut m0 = true;
2323 let mut m1 = false;
2324
2325 for _ in 0..500 {
2326 let lwe0 = bool_evaluator.pk_encrypt(&collective_pk.key, m0);
2327 let lwe1 = bool_evaluator.pk_encrypt(&collective_pk.key, m1);
2328
2329 let lwe_out = bool_evaluator.nand(
2330 &lwe0,
2331 &lwe1,
2332 &server_key_eval,
2333 &mut scratch_lwen_plus1,
2334 &mut scratch_matrix_dplus2_ring,
2335 );
2336
2337 let m_expected = !(m0 & m1);
2338
2339 // measure noise
2340 {
2341 // Trace PBS
2342 PBSTracer::with_local(|t| {
2343 t.trace(
2344 &MP_BOOL_PARAMS,
2345 &ideal_client_key.sk_lwe.values(),
2346 &ideal_client_key.sk_rlwe.values(),
2347 )
2348 });
2349
2350 let ideal_m = if m_expected {
2351 bool_evaluator.rlweq_by8
2352 } else {
2353 bool_evaluator.parameters.rlwe_q - bool_evaluator.rlweq_by8
2354 };
2355 let noise = measure_noise_lwe(
2356 &lwe_out,
2357 ideal_client_key.sk_rlwe.values(),
2358 &bool_evaluator.rlwe_modop,
2359 &ideal_m,
2360 );
2361 println!("Noise: {noise}");
2362 }
2363
2364 // multi-party decrypt
2365 let decryption_shares = parties
2366 .iter()
2367 .map(|k| bool_evaluator.multi_party_decryption_share(&lwe_out, k))
2368 .collect_vec();
2369 let m_back = bool_evaluator.multi_party_decrypt(&decryption_shares, &lwe_out);
2370
2371 // let m_back = bool_evaluator.sk_decrypt(&lwe_out, &ideal_client_key);
2372
2373 assert!(m_expected == m_back, "Expected {m_expected}, got {m_back}");
2374 m1 = m0;
2375 m0 = m_expected;
2376 }
2377 }
2378}