phantom-zone/src/bool/parameters.rs
src/bool/parameters.rsRaw
1use num_traits::{ConstZero, FromPrimitive, PrimInt};
2
3use crate::{
4 backend::Modulus,
5 decomposer::{Decomposer, NumInfo},
6 utils::log2,
7};
8
9pub(crate) trait DoubleDecomposerCount {
10 type Count;
11 fn a(&self) -> Self::Count;
12 fn b(&self) -> Self::Count;
13}
14
15pub(crate) trait DoubleDecomposerParams {
16 type Base;
17 type Count;
18
19 fn decomposition_base(&self) -> Self::Base;
20 fn decomposition_count_a(&self) -> Self::Count;
21 fn decomposition_count_b(&self) -> Self::Count;
22}
23
24pub(crate) trait SingleDecomposerParams {
25 type Base;
26 type Count;
27
28 // fn new(base: Self::Base, count: Self::Count) -> Self;
29 fn decomposition_base(&self) -> Self::Base;
30 fn decomposition_count(&self) -> Self::Count;
31}
32
33impl DoubleDecomposerParams
34 for (
35 DecompostionLogBase,
36 // Assume (Decomposition count for A, Decomposition count for B)
37 (DecompositionCount, DecompositionCount),
38 )
39{
40 type Base = DecompostionLogBase;
41 type Count = DecompositionCount;
42
43 // fn new(
44 // base: DecompostionLogBase,
45 // count_a: DecompositionCount,
46 // count_b: DecompositionCount,
47 // ) -> Self {
48 // (base, (count_a, count_b))
49 // }
50
51 fn decomposition_base(&self) -> Self::Base {
52 self.0
53 }
54
55 fn decomposition_count_a(&self) -> Self::Count {
56 self.1 .0
57 }
58
59 fn decomposition_count_b(&self) -> Self::Count {
60 self.1 .1
61 }
62}
63
64impl SingleDecomposerParams for (DecompostionLogBase, DecompositionCount) {
65 type Base = DecompostionLogBase;
66 type Count = DecompositionCount;
67
68 // fn new(base: DecompostionLogBase, count: DecompositionCount) -> Self {
69 // (base, count)
70 // }
71
72 fn decomposition_base(&self) -> Self::Base {
73 self.0
74 }
75
76 fn decomposition_count(&self) -> Self::Count {
77 self.1
78 }
79}
80
81#[derive(Clone, PartialEq, Debug)]
82pub(crate) enum ParameterVariant {
83 SingleParty,
84 MultiParty,
85 NonInteractiveMultiParty,
86}
87#[derive(Clone, PartialEq)]
88pub struct BoolParameters<El> {
89 /// RLWE ciphertext modulus Q
90 rlwe_q: CiphertextModulus<El>,
91 /// LWE ciphertext modulus q (usually referred to as Q_{ks})
92 lwe_q: CiphertextModulus<El>,
93 /// Blind rotation modulus. It is the modulus to which we switch before
94 /// blind rotation.
95 ///
96 /// Since blind rotation decrypts LWE ciphertext in the exponent of a ring
97 /// polynomial, which is a ring mod 2N, blind rotation modulus is
98 /// always <= 2N.
99 br_q: usize,
100 /// Ring dimension `N` for 2N^{th} cyclotomic polynomial ring
101 rlwe_n: PolynomialSize,
102 /// LWE dimension `n`
103 lwe_n: LweDimension,
104 /// LWE key switch decompositon params
105 lwe_decomposer_params: (DecompostionLogBase, DecompositionCount),
106 /// Decompostion parameters for RLWE x RGSW.
107 ///
108 /// We restrict decomposition for RLWE'(-sm) and RLWE'(m) to have same base
109 /// but can have different decomposition count. We refer to this
110 /// DoubleDecomposer / RlweDecomposer
111 ///
112 /// Decomposition count `d_a` (i.e. for SignedDecompose(RLWE_A(m)) x
113 /// RLWE'(-sm)) and `d_b` (i.e. for SignedDecompose(RLWE_B(m)) x RLWE'(m))
114 /// are always stored as `(d_a, d_b)`
115 rlrg_decomposer_params: (
116 DecompostionLogBase,
117 (DecompositionCount, DecompositionCount),
118 ),
119 /// Decomposition parameters for RLWE automorphism
120 auto_decomposer_params: (DecompostionLogBase, DecompositionCount),
121 /// Decomposition parameters for RGSW0 x RGSW1
122 ///
123 /// `0` and `1` indicate that RGSW0 and RGSW1 may not use same decomposition
124 /// parameters.
125 ///
126 /// In RGSW0 x RGSW1, decomposition parameters for RGSW1 are required.
127 /// Hence, the parameters we store are decomposition parameters of RGSW1.
128 ///
129 /// Like RLWE x RGSW decomposition parameters (1) we restrict to same base
130 /// but can have different decomposition counts `d_a` and `d_b` and (2)
131 /// decomposition count `d_a` and `d_b` are always stored as `(d_a, d_b)`
132 ///
133 /// RGSW0 x RGSW1 are optional because they only necessary to be supplied in
134 /// multi-party setting.
135 rgrg_decomposer_params: Option<(
136 DecompostionLogBase,
137 (DecompositionCount, DecompositionCount),
138 )>,
139 /// Decomposition parameters for non-interactive key switching from u_j to
140 /// s, hwere u_j is RLWE secret `u` of party `j` and `s` is the ideal RLWE
141 /// secret key.
142 ///
143 /// Decomposition parameters for non-interactive key switching are optional
144 /// and must be supplied only for non-interactive multi-party
145 non_interactive_ui_to_s_key_switch_decomposer:
146 Option<(DecompostionLogBase, DecompositionCount)>,
147 /// Group generator for Z^*_{br_q}
148 g: usize,
149 /// Window size parameter for LMKC++ blind rotation
150 w: usize,
151 /// Parameter variant
152 variant: ParameterVariant,
153}
154
155impl<El> BoolParameters<El> {
156 pub(crate) fn rlwe_q(&self) -> &CiphertextModulus<El> {
157 &self.rlwe_q
158 }
159
160 pub(crate) fn lwe_q(&self) -> &CiphertextModulus<El> {
161 &self.lwe_q
162 }
163
164 pub(crate) fn br_q(&self) -> &usize {
165 &self.br_q
166 }
167
168 pub(crate) fn rlwe_n(&self) -> &PolynomialSize {
169 &self.rlwe_n
170 }
171
172 pub(crate) fn lwe_n(&self) -> &LweDimension {
173 &self.lwe_n
174 }
175
176 pub(crate) fn g(&self) -> usize {
177 self.g
178 }
179
180 pub(crate) fn w(&self) -> usize {
181 self.w
182 }
183
184 pub(crate) fn rlwe_by_rgsw_decomposition_params(
185 &self,
186 ) -> &(
187 DecompostionLogBase,
188 (DecompositionCount, DecompositionCount),
189 ) {
190 &self.rlrg_decomposer_params
191 }
192
193 pub(crate) fn rgsw_by_rgsw_decomposition_params(
194 &self,
195 ) -> (
196 DecompostionLogBase,
197 (DecompositionCount, DecompositionCount),
198 ) {
199 self.rgrg_decomposer_params.expect(&format!(
200 "Parameter variant {:?} does not support RGSWxRGSW",
201 self.variant
202 ))
203 }
204
205 pub(crate) fn rlwe_rgsw_decomposition_base(&self) -> DecompostionLogBase {
206 self.rlrg_decomposer_params.0
207 }
208
209 pub(crate) fn rlwe_rgsw_decomposition_count(&self) -> (DecompositionCount, DecompositionCount) {
210 self.rlrg_decomposer_params.1
211 }
212
213 pub(crate) fn rgsw_rgsw_decomposition_count(&self) -> (DecompositionCount, DecompositionCount) {
214 let params = self.rgrg_decomposer_params.expect(&format!(
215 "Parameter variant {:?} does not support RGSW x RGSW",
216 self.variant
217 ));
218 params.1
219 }
220
221 pub(crate) fn auto_decomposition_param(&self) -> &(DecompostionLogBase, DecompositionCount) {
222 &self.auto_decomposer_params
223 }
224
225 pub(crate) fn auto_decomposition_base(&self) -> DecompostionLogBase {
226 self.auto_decomposer_params.decomposition_base()
227 }
228
229 pub(crate) fn auto_decomposition_count(&self) -> DecompositionCount {
230 self.auto_decomposer_params.decomposition_count()
231 }
232
233 pub(crate) fn lwe_decomposition_base(&self) -> DecompostionLogBase {
234 self.lwe_decomposer_params.decomposition_base()
235 }
236
237 pub(crate) fn lwe_decomposition_count(&self) -> DecompositionCount {
238 self.lwe_decomposer_params.decomposition_count()
239 }
240
241 pub(crate) fn non_interactive_ui_to_s_key_switch_decomposition_count(
242 &self,
243 ) -> DecompositionCount {
244 let params = self
245 .non_interactive_ui_to_s_key_switch_decomposer
246 .expect(&format!(
247 "Parameter variant {:?} does not support non-interactive",
248 self.variant
249 ));
250 params.decomposition_count()
251 }
252
253 pub(crate) fn rgsw_rgsw_decomposer<D: Decomposer<Element = El>>(&self) -> (D, D)
254 where
255 El: Copy,
256 {
257 let params = self.rgrg_decomposer_params.expect(&format!(
258 "Parameter variant {:?} does not support RGSW x RGSW",
259 self.variant
260 ));
261 (
262 // A
263 D::new(
264 self.rlwe_q.0,
265 params.decomposition_base().0,
266 params.decomposition_count_a().0,
267 ),
268 // B
269 D::new(
270 self.rlwe_q.0,
271 params.decomposition_base().0,
272 params.decomposition_count_b().0,
273 ),
274 )
275 }
276
277 pub(crate) fn auto_decomposer<D: Decomposer<Element = El>>(&self) -> D
278 where
279 El: Copy,
280 {
281 D::new(
282 self.rlwe_q.0,
283 self.auto_decomposer_params.decomposition_base().0,
284 self.auto_decomposer_params.decomposition_count().0,
285 )
286 }
287
288 pub(crate) fn lwe_decomposer<D: Decomposer<Element = El>>(&self) -> D
289 where
290 El: Copy,
291 {
292 D::new(
293 self.lwe_q.0,
294 self.lwe_decomposer_params.decomposition_base().0,
295 self.lwe_decomposer_params.decomposition_count().0,
296 )
297 }
298
299 pub(crate) fn rlwe_rgsw_decomposer<D: Decomposer<Element = El>>(&self) -> (D, D)
300 where
301 El: Copy,
302 {
303 (
304 // A
305 D::new(
306 self.rlwe_q.0,
307 self.rlrg_decomposer_params.decomposition_base().0,
308 self.rlrg_decomposer_params.decomposition_count_a().0,
309 ),
310 // B
311 D::new(
312 self.rlwe_q.0,
313 self.rlrg_decomposer_params.decomposition_base().0,
314 self.rlrg_decomposer_params.decomposition_count_b().0,
315 ),
316 )
317 }
318
319 pub(crate) fn non_interactive_ui_to_s_key_switch_decomposer<D: Decomposer<Element = El>>(
320 &self,
321 ) -> D
322 where
323 El: Copy,
324 {
325 let params = self
326 .non_interactive_ui_to_s_key_switch_decomposer
327 .expect(&format!(
328 "Parameter variant {:?} does not support non-interactive",
329 self.variant
330 ));
331 D::new(
332 self.rlwe_q.0,
333 params.decomposition_base().0,
334 params.decomposition_count().0,
335 )
336 }
337
338 /// Returns dlogs of `g` for which auto keys are required as
339 /// per the parameter. Given that autos are required for [-g, g, g^2, ...,
340 /// g^w] function returns the following [0, 1, 2, ..., w] where `w` is
341 /// the window size. Note that although g^0 = 1, we use 0 for -g.
342 pub(crate) fn auto_element_dlogs(&self) -> Vec<usize> {
343 let mut els = vec![0];
344 (1..self.w + 1).into_iter().for_each(|e| {
345 els.push(e);
346 });
347 els
348 }
349
350 pub(crate) fn variant(&self) -> &ParameterVariant {
351 &self.variant
352 }
353}
354
355#[derive(Clone, Copy, PartialEq)]
356pub struct DecompostionLogBase(pub(crate) usize);
357impl AsRef<usize> for DecompostionLogBase {
358 fn as_ref(&self) -> &usize {
359 &self.0
360 }
361}
362#[derive(Clone, Copy, PartialEq)]
363pub struct DecompositionCount(pub(crate) usize);
364impl AsRef<usize> for DecompositionCount {
365 fn as_ref(&self) -> &usize {
366 &self.0
367 }
368}
369
370#[derive(Clone, Copy, PartialEq)]
371pub(crate) struct LweDimension(pub(crate) usize);
372#[derive(Clone, Copy, PartialEq)]
373pub(crate) struct PolynomialSize(pub(crate) usize);
374#[derive(Clone, Copy, PartialEq, Debug)]
375
376/// T equals modulus when modulus is non-native. Otherwise T equals 0. bool is
377/// true when modulus is native, false otherwise.
378pub struct CiphertextModulus<T>(T, bool);
379
380impl<T: ConstZero> CiphertextModulus<T> {
381 const fn new_native() -> Self {
382 // T::zero is stored only for convenience. It has no use when modulus
383 // is native. That is, either u128,u64,u32,u16
384 Self(T::ZERO, true)
385 }
386
387 const fn new_non_native(q: T) -> Self {
388 Self(q, false)
389 }
390}
391
392impl<T> CiphertextModulus<T>
393where
394 T: PrimInt + NumInfo,
395{
396 fn _bits() -> usize {
397 T::BITS as usize
398 }
399
400 fn _native(&self) -> bool {
401 self.1
402 }
403
404 fn _half_q(&self) -> T {
405 if self._native() {
406 T::one() << (Self::_bits() - 1)
407 } else {
408 self.0 >> 1
409 }
410 }
411
412 fn _q(&self) -> Option<T> {
413 if self._native() {
414 None
415 } else {
416 Some(self.0)
417 }
418 }
419}
420
421impl<T> Modulus for CiphertextModulus<T>
422where
423 T: PrimInt + FromPrimitive + NumInfo,
424{
425 type Element = T;
426 fn is_native(&self) -> bool {
427 self._native()
428 }
429 fn largest_unsigned_value(&self) -> Self::Element {
430 if self._native() {
431 T::max_value()
432 } else {
433 self.0 - T::one()
434 }
435 }
436 fn neg_one(&self) -> Self::Element {
437 if self._native() {
438 T::max_value()
439 } else {
440 self.0 - T::one()
441 }
442 }
443 // fn signed_max(&self) -> Self::Element {}
444 // fn signed_min(&self) -> Self::Element {}
445 fn smallest_unsigned_value(&self) -> Self::Element {
446 T::zero()
447 }
448
449 fn map_element_to_i64(&self, v: &Self::Element) -> i64 {
450 assert!(*v <= self.largest_unsigned_value());
451 if *v > self._half_q() {
452 -((self.largest_unsigned_value() - *v) + T::one())
453 .to_i64()
454 .unwrap()
455 } else {
456 v.to_i64().unwrap()
457 }
458 }
459
460 fn map_element_from_f64(&self, v: f64) -> Self::Element {
461 let v = v.round();
462
463 let v_el = T::from_f64(v.abs()).unwrap();
464 assert!(v_el <= self.largest_unsigned_value());
465
466 if v < 0.0 {
467 self.largest_unsigned_value() - v_el + T::one()
468 } else {
469 v_el
470 }
471 }
472
473 fn map_element_from_i64(&self, v: i64) -> Self::Element {
474 let v_el = T::from_i64(v.abs()).unwrap();
475 assert!(v_el <= self.largest_unsigned_value());
476 if v < 0 {
477 self.largest_unsigned_value() - v_el + T::one()
478 } else {
479 v_el
480 }
481 }
482
483 fn q(&self) -> Option<Self::Element> {
484 self._q()
485 }
486
487 fn q_as_f64(&self) -> Option<f64> {
488 if self._native() {
489 Some(T::max_value().to_f64().unwrap() + 1.0)
490 } else {
491 self.0.to_f64()
492 }
493 }
494
495 fn log_q(&self) -> usize {
496 if self.is_native() {
497 Self::_bits()
498 } else {
499 log2(&self.q().unwrap())
500 }
501 }
502}
503
504pub(crate) const MP_BOOL_PARAMS: BoolParameters<u64> = BoolParameters::<u64> {
505 rlwe_q: CiphertextModulus::new_non_native(1152921504606830593),
506 lwe_q: CiphertextModulus::new_non_native(1 << 20),
507 br_q: 1 << 11,
508 rlwe_n: PolynomialSize(1 << 11),
509 lwe_n: LweDimension(500),
510 lwe_decomposer_params: (DecompostionLogBase(4), DecompositionCount(5)),
511 rlrg_decomposer_params: (
512 DecompostionLogBase(12),
513 (DecompositionCount(5), DecompositionCount(5)),
514 ),
515 rgrg_decomposer_params: Some((
516 DecompostionLogBase(12),
517 (DecompositionCount(5), DecompositionCount(5)),
518 )),
519 auto_decomposer_params: (DecompostionLogBase(12), DecompositionCount(5)),
520 non_interactive_ui_to_s_key_switch_decomposer: None,
521 g: 5,
522 w: 10,
523 variant: ParameterVariant::MultiParty,
524};
525
526pub(crate) const SMALL_MP_BOOL_PARAMS: BoolParameters<u64> = BoolParameters::<u64> {
527 rlwe_q: CiphertextModulus::new_non_native(36028797018820609),
528 lwe_q: CiphertextModulus::new_non_native(1 << 20),
529 br_q: 1 << 11,
530 rlwe_n: PolynomialSize(1 << 11),
531 lwe_n: LweDimension(600),
532 lwe_decomposer_params: (DecompostionLogBase(4), DecompositionCount(5)),
533 rlrg_decomposer_params: (
534 DecompostionLogBase(11),
535 (DecompositionCount(2), DecompositionCount(1)),
536 ),
537 rgrg_decomposer_params: Some((
538 DecompostionLogBase(11),
539 (DecompositionCount(5), DecompositionCount(4)),
540 )),
541 auto_decomposer_params: (DecompostionLogBase(11), DecompositionCount(2)),
542 non_interactive_ui_to_s_key_switch_decomposer: None,
543 g: 5,
544 w: 10,
545 variant: ParameterVariant::MultiParty,
546};
547
548pub(crate) const I_2P: BoolParameters<u64> = BoolParameters::<u64> {
549 rlwe_q: CiphertextModulus::new_non_native(18014398509404161),
550 lwe_q: CiphertextModulus::new_non_native(1 << 15),
551 br_q: 1 << 11,
552 rlwe_n: PolynomialSize(1 << 11),
553 lwe_n: LweDimension(480),
554 lwe_decomposer_params: (DecompostionLogBase(1), DecompositionCount(11)),
555 rlrg_decomposer_params: (
556 DecompostionLogBase(16),
557 (DecompositionCount(1), DecompositionCount(1)),
558 ),
559 rgrg_decomposer_params: Some((
560 DecompostionLogBase(8),
561 (DecompositionCount(6), DecompositionCount(6)),
562 )),
563 auto_decomposer_params: (DecompostionLogBase(24), DecompositionCount(1)),
564 non_interactive_ui_to_s_key_switch_decomposer: None,
565 g: 5,
566 w: 10,
567 variant: ParameterVariant::MultiParty,
568};
569
570pub(crate) const NI_2P: BoolParameters<u64> = BoolParameters::<u64> {
571 rlwe_q: CiphertextModulus::new_non_native(18014398509404161),
572 lwe_q: CiphertextModulus::new_non_native(1 << 15),
573 br_q: 1 << 11,
574 rlwe_n: PolynomialSize(1 << 11),
575 lwe_n: LweDimension(480),
576 lwe_decomposer_params: (DecompostionLogBase(1), DecompositionCount(12)),
577 rlrg_decomposer_params: (
578 DecompostionLogBase(16),
579 (DecompositionCount(1), DecompositionCount(1)),
580 ),
581 rgrg_decomposer_params: Some((
582 DecompostionLogBase(6),
583 (DecompositionCount(7), DecompositionCount(7)),
584 )),
585 auto_decomposer_params: (DecompostionLogBase(24), DecompositionCount(1)),
586 non_interactive_ui_to_s_key_switch_decomposer: Some((
587 DecompostionLogBase(1),
588 DecompositionCount(50),
589 )),
590 g: 5,
591 w: 10,
592 variant: ParameterVariant::NonInteractiveMultiParty,
593};
594
595pub(crate) const NI_4P: BoolParameters<u64> = BoolParameters::<u64> {
596 rlwe_q: CiphertextModulus::new_non_native(18014398509404161),
597 lwe_q: CiphertextModulus::new_non_native(1 << 16),
598 br_q: 1 << 11,
599 rlwe_n: PolynomialSize(1 << 11),
600 lwe_n: LweDimension(510),
601 lwe_decomposer_params: (DecompostionLogBase(1), DecompositionCount(12)),
602 rlrg_decomposer_params: (
603 DecompostionLogBase(17),
604 (DecompositionCount(1), DecompositionCount(1)),
605 ),
606 rgrg_decomposer_params: Some((
607 DecompostionLogBase(4),
608 (DecompositionCount(10), DecompositionCount(9)),
609 )),
610 auto_decomposer_params: (DecompostionLogBase(24), DecompositionCount(1)),
611 non_interactive_ui_to_s_key_switch_decomposer: Some((
612 DecompostionLogBase(1),
613 DecompositionCount(50),
614 )),
615 g: 5,
616 w: 10,
617 variant: ParameterVariant::NonInteractiveMultiParty,
618};
619
620#[cfg(test)]
621pub(crate) const SP_TEST_BOOL_PARAMS: BoolParameters<u64> = BoolParameters::<u64> {
622 rlwe_q: CiphertextModulus::new_non_native(268369921u64),
623 lwe_q: CiphertextModulus::new_non_native(1 << 16),
624 br_q: 1 << 9,
625 rlwe_n: PolynomialSize(1 << 9),
626 lwe_n: LweDimension(100),
627 lwe_decomposer_params: (DecompostionLogBase(4), DecompositionCount(4)),
628 rlrg_decomposer_params: (
629 DecompostionLogBase(7),
630 (DecompositionCount(4), DecompositionCount(4)),
631 ),
632 rgrg_decomposer_params: None,
633 auto_decomposer_params: (DecompostionLogBase(7), DecompositionCount(4)),
634 non_interactive_ui_to_s_key_switch_decomposer: None,
635 g: 5,
636 w: 5,
637 variant: ParameterVariant::SingleParty,
638};
639
640#[cfg(test)]
641mod tests {
642
643 impl BoolParameters<u64> {
644 pub(crate) fn default_rlwe_modop(&self) -> ModularOpsU64<CiphertextModulus<u64>> {
645 ModularOpsU64::new(self.rlwe_q)
646 }
647 pub(crate) fn default_rlwe_nttop(&self) -> NttBackendU64 {
648 NttBackendU64::new(&self.rlwe_q, self.rlwe_n.0)
649 }
650 }
651
652 use crate::{utils::generate_prime, ModInit, ModularOpsU64, Ntt, NttBackendU64, NttInit};
653
654 use super::{BoolParameters, CiphertextModulus};
655
656 #[test]
657 fn find_prime() {
658 let bits = 60;
659 let ring_size = 1 << 11;
660 let prime = generate_prime(bits, ring_size * 2, 1 << bits).unwrap();
661 dbg!(prime);
662 }
663}