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