1use std::collections::BTreeMap;
8use std::error::Error;
9use std::fmt;
10
11#[derive(Clone, Debug, PartialEq, Eq)]
13pub enum NtruError {
14 InvalidModulus,
16 Shape,
18 NotInvertible,
20 InvalidParameters(String),
22 Backend(String),
24}
25
26impl fmt::Display for NtruError {
27 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
28 match self {
29 Self::InvalidModulus => write!(f, "invalid modulus"),
30 Self::Shape => write!(f, "shape mismatch"),
31 Self::NotInvertible => write!(f, "element is not invertible"),
32 Self::InvalidParameters(message) => write!(f, "invalid parameters: {message}"),
33 Self::Backend(message) => write!(f, "backend error: {message}"),
34 }
35 }
36}
37
38impl Error for NtruError {}
39
40#[derive(Clone, Debug)]
43pub struct Lcg {
44 state: u64,
45}
46
47impl Lcg {
48 pub fn new(seed: u64) -> Self {
50 Self { state: seed }
51 }
52
53 pub fn next_u64(&mut self) -> u64 {
55 self.state = self
56 .state
57 .wrapping_mul(6_364_136_223_846_793_005)
58 .wrapping_add(1_442_695_040_888_963_407);
59 self.state
60 }
61
62 pub fn gen_range(&mut self, upper: usize) -> usize {
64 assert!(upper > 0);
65 (self.next_u64() as usize) % upper
66 }
67}
68
69#[derive(Clone, Debug, PartialEq, Eq)]
71pub enum GroupKind {
72 Cyclic,
74 Dihedral,
76 Symmetric,
78}
79
80#[derive(Clone, Debug)]
82pub struct FiniteGroup {
83 kind: GroupKind,
84 n: usize,
85 name: String,
86 elements: Vec<Vec<usize>>,
87}
88
89impl FiniteGroup {
90 pub fn cyclic(n: usize) -> Result<Self, NtruError> {
92 if n == 0 {
93 return Err(NtruError::InvalidParameters("n must be positive".into()));
94 }
95 Ok(Self {
96 kind: GroupKind::Cyclic,
97 n,
98 name: format!("C{n}"),
99 elements: (0..n).map(|i| vec![i]).collect(),
100 })
101 }
102
103 pub fn dihedral(n: usize) -> Result<Self, NtruError> {
105 if n < 3 {
106 return Err(NtruError::InvalidParameters(
107 "dihedral rotation order must be at least 3".into(),
108 ));
109 }
110 Ok(Self {
111 kind: GroupKind::Dihedral,
112 n,
113 name: format!("D{n} (order {})", 2 * n),
114 elements: (0..2 * n).map(|i| vec![i]).collect(),
115 })
116 }
117
118 pub fn symmetric(n: usize) -> Result<Self, NtruError> {
120 if n == 0 {
121 return Err(NtruError::InvalidParameters("n must be positive".into()));
122 }
123 let elements = all_permutations(n);
124 Ok(Self {
125 kind: GroupKind::Symmetric,
126 n,
127 name: format!("S{n}"),
128 elements,
129 })
130 }
131
132 pub fn kind(&self) -> &GroupKind {
134 &self.kind
135 }
136
137 pub fn n(&self) -> usize {
139 self.n
140 }
141
142 pub fn name(&self) -> &str {
144 &self.name
145 }
146
147 pub fn order(&self) -> usize {
149 self.elements.len()
150 }
151
152 pub fn elements(&self) -> &[Vec<usize>] {
154 &self.elements
155 }
156
157 pub fn multiply_index(&self, lhs: usize, rhs: usize) -> usize {
159 match self.kind {
160 GroupKind::Cyclic => (lhs + rhs) % self.n,
161 GroupKind::Dihedral => self.multiply_dihedral(lhs, rhs),
162 GroupKind::Symmetric => self.multiply_symmetric(lhs, rhs),
163 }
164 }
165
166 fn multiply_dihedral(&self, lhs: usize, rhs: usize) -> usize {
167 let n = self.n;
168 let lhs_reflection = lhs >= n;
169 let rhs_reflection = rhs >= n;
170 let lhs_k = if lhs_reflection { lhs - n } else { lhs };
171 let rhs_k = if rhs_reflection { rhs - n } else { rhs };
172
173 match (lhs_reflection, rhs_reflection) {
174 (false, false) => (lhs_k + rhs_k) % n,
175 (false, true) => n + ((rhs_k + n - lhs_k) % n),
176 (true, false) => n + ((lhs_k + rhs_k) % n),
177 (true, true) => (rhs_k + n - lhs_k) % n,
178 }
179 }
180
181 fn multiply_symmetric(&self, lhs: usize, rhs: usize) -> usize {
182 let lhs_images = &self.elements[lhs];
183 let rhs_images = &self.elements[rhs];
184 let product: Vec<_> = rhs_images.iter().map(|image| lhs_images[*image]).collect();
185 self.elements
186 .iter()
187 .position(|candidate| *candidate == product)
188 .expect("product permutation is in S_n")
189 }
190}
191
192fn all_permutations(n: usize) -> Vec<Vec<usize>> {
193 let mut current: Vec<_> = (0..n).collect();
194 let mut out = vec![current.clone()];
195 while next_permutation(&mut current) {
196 out.push(current.clone());
197 }
198 out
199}
200
201fn next_permutation(values: &mut [usize]) -> bool {
202 if values.len() < 2 {
203 return false;
204 }
205 let mut pivot = values.len() - 2;
206 while values[pivot] >= values[pivot + 1] {
207 if pivot == 0 {
208 values.reverse();
209 return false;
210 }
211 pivot -= 1;
212 }
213 let mut successor = values.len() - 1;
214 while values[successor] <= values[pivot] {
215 successor -= 1;
216 }
217 values.swap(pivot, successor);
218 values[pivot + 1..].reverse();
219 true
220}
221
222#[derive(Clone, Debug, Default, PartialEq, Eq)]
224pub struct BackendStats {
225 counts: BTreeMap<String, usize>,
226}
227
228impl BackendStats {
229 fn record(&mut self, name: &str) {
230 *self.counts.entry(name.to_string()).or_insert(0) += 1;
231 }
232
233 pub fn counts(&self) -> &BTreeMap<String, usize> {
235 &self.counts
236 }
237
238 pub fn format(&self) -> String {
240 self.counts
241 .iter()
242 .map(|(name, count)| format!("{name}={count}"))
243 .collect::<Vec<_>>()
244 .join(", ")
245 }
246}
247
248#[derive(Clone, Debug)]
250pub struct PrivateKey {
251 pub f: Vec<i64>,
253 pub f_p: Vec<u64>,
255 pub f_q: Vec<u64>,
257 pub attempts: usize,
259}
260
261#[derive(Clone, Debug)]
263pub struct TrialResult {
264 pub success: bool,
266 pub no_wrap: bool,
268 pub key_attempts: usize,
270}
271
272#[derive(Clone, Debug)]
274pub struct TrialSummary {
275 pub requested_trials: usize,
277 pub completed_trials: usize,
279 pub successes: usize,
281 pub no_wraps: usize,
283 pub keygen_failures: usize,
285 pub avg_key_attempts: Option<f64>,
287 pub max_key_attempts: Option<usize>,
289 pub backend_stats: BackendStats,
291}
292
293#[derive(Clone, Debug)]
295pub struct GroupAlgebraNtru {
296 group: FiniteGroup,
297 p: u64,
298 q: u64,
299 d: usize,
300 stats: BackendStats,
301}
302
303impl GroupAlgebraNtru {
304 pub fn new(group: FiniteGroup, p: u64, q: u64, d: usize) -> Result<Self, NtruError> {
306 if !is_prime(p) {
307 return Err(NtruError::InvalidParameters("p must be prime".into()));
308 }
309 if q <= 1 {
310 return Err(NtruError::InvalidParameters(
311 "q must be greater than 1".into(),
312 ));
313 }
314 if gcd(p, q) != 1 {
315 return Err(NtruError::InvalidParameters(
316 "p and q must be coprime".into(),
317 ));
318 }
319 if group.order() < 2 * d + 1 {
320 return Err(NtruError::InvalidParameters(
321 "group is too small for the requested ternary density".into(),
322 ));
323 }
324 Ok(Self {
325 group,
326 p,
327 q,
328 d,
329 stats: BackendStats::default(),
330 })
331 }
332
333 pub fn group(&self) -> &FiniteGroup {
335 &self.group
336 }
337
338 pub fn p(&self) -> u64 {
340 self.p
341 }
342
343 pub fn q(&self) -> u64 {
345 self.q
346 }
347
348 pub fn d(&self) -> usize {
350 self.d
351 }
352
353 pub fn backend_stats(&self) -> &BackendStats {
355 &self.stats
356 }
357
358 pub fn one_mod(&self, modulus: u64) -> Vec<u64> {
360 let mut out = vec![0; self.group.order()];
361 out[0] = 1 % modulus;
362 out
363 }
364
365 pub fn random_ternary(
367 &self,
368 rng: &mut Lcg,
369 d1: usize,
370 d2: usize,
371 ) -> Result<Vec<i64>, NtruError> {
372 let support = d1 + d2;
373 if support > self.group.order() {
374 return Err(NtruError::InvalidParameters(
375 "ternary support too large".into(),
376 ));
377 }
378 let mut positions: Vec<_> = (0..self.group.order()).collect();
379 for i in 0..support {
380 let j = i + rng.gen_range(self.group.order() - i);
381 positions.swap(i, j);
382 }
383 let mut out = vec![0; self.group.order()];
384 for &idx in &positions[..d1] {
385 out[idx] = 1;
386 }
387 for &idx in &positions[d1..support] {
388 out[idx] = -1;
389 }
390 Ok(out)
391 }
392
393 pub fn random_plaintext(&self, rng: &mut Lcg) -> Vec<i64> {
395 let half_width = ((self.p - 1) / 2) as i64;
396 (0..self.group.order())
397 .map(|_| rng.gen_range((2 * half_width + 1) as usize) as i64 - half_width)
398 .collect()
399 }
400
401 pub fn multiply_mod(
403 &mut self,
404 lhs: &[u64],
405 rhs: &[u64],
406 modulus: u64,
407 ) -> Result<Vec<u64>, NtruError> {
408 if lhs.len() != self.group.order() || rhs.len() != self.group.order() || modulus == 0 {
409 return Err(NtruError::Shape);
410 }
411
412 if let Some(product) = self.try_fft_multiply(lhs, rhs, modulus)? {
413 return Ok(product);
414 }
415
416 self.stats.record("naive:multiply");
417 self.naive_multiply_mod(lhs, rhs, modulus)
418 }
419
420 pub fn inverse_mod(&mut self, element: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
422 if element.len() != self.group.order() || modulus == 0 {
423 return Err(NtruError::Shape);
424 }
425
426 if let Some(inverse) = self.try_fft_inverse(element, modulus)? {
427 return Ok(inverse);
428 }
429
430 match self.group.kind() {
431 GroupKind::Cyclic => {
432 let inverse = cyclic_inverse_mod(element, modulus)?;
433 self.stats.record("cyclic:invert");
434 self.verify_inverse(element, &inverse, modulus)?;
435 Ok(inverse)
436 }
437 GroupKind::Dihedral => {
438 match dihedral_inverse_via_cyclic(element, self.group.n(), modulus) {
439 Ok(inverse) => {
440 self.stats.record("dihedral-cyclic:invert");
441 self.verify_inverse(element, &inverse, modulus)?;
442 Ok(inverse)
443 }
444 Err(error) => {
445 if is_prime(modulus) && gcd(2 * self.group.n() as u64, modulus) == 1 {
446 return Err(error);
447 }
448 let inverse = self.linear_solve_inverse(element, modulus)?;
449 self.stats.record("linear-solve:invert");
450 self.verify_inverse(element, &inverse, modulus)?;
451 Ok(inverse)
452 }
453 }
454 }
455 GroupKind::Symmetric => {
456 let inverse = self.linear_solve_inverse(element, modulus)?;
457 self.stats.record("linear-solve:invert");
458 self.verify_inverse(element, &inverse, modulus)?;
459 Ok(inverse)
460 }
461 }
462 }
463
464 pub fn try_inverse_mod(&mut self, element: &[u64], modulus: u64) -> Option<Vec<u64>> {
466 self.inverse_mod(element, modulus).ok()
467 }
468
469 pub fn random_private_key(
471 &mut self,
472 rng: &mut Lcg,
473 max_tries: usize,
474 ) -> Result<PrivateKey, NtruError> {
475 for attempts in 1..=max_tries {
476 let f = self.random_ternary(rng, self.d + 1, self.d)?;
477 let f_mod_p = signed_to_mod(&f, self.p);
478 let f_p = match self.try_inverse_mod(&f_mod_p, self.p) {
479 Some(inverse) => inverse,
480 None => continue,
481 };
482 let f_mod_q = signed_to_mod(&f, self.q);
483 let f_q = match self.try_inverse_mod(&f_mod_q, self.q) {
484 Some(inverse) => inverse,
485 None => continue,
486 };
487 return Ok(PrivateKey {
488 f,
489 f_p,
490 f_q,
491 attempts,
492 });
493 }
494 Err(NtruError::NotInvertible)
495 }
496
497 pub fn public_key(&mut self, f_q: &[u64], g: &[i64]) -> Result<Vec<u64>, NtruError> {
499 self.multiply_mod(f_q, &signed_to_mod(g, self.q), self.q)
500 }
501
502 pub fn encrypt(&mut self, m: &[i64], h: &[u64], r: &[i64]) -> Result<Vec<u64>, NtruError> {
504 let hr = self.multiply_mod(h, &signed_to_mod(r, self.q), self.q)?;
505 let m_mod_q = signed_to_mod(m, self.q);
506 Ok(hr
507 .iter()
508 .zip(m_mod_q.iter())
509 .map(|(value, message)| {
510 add_mod(mul_mod(self.p % self.q, *value, self.q), *message, self.q)
511 })
512 .collect())
513 }
514
515 pub fn decrypt(&mut self, e: &[u64], f: &[i64], f_p: &[u64]) -> Result<Vec<i64>, NtruError> {
517 let a_q = self.multiply_mod(&signed_to_mod(f, self.q), e, self.q)?;
518 let a_lift = center_lift_vector(&a_q, self.q);
519 let b_p = self.multiply_mod(f_p, &signed_to_mod(&a_lift, self.p), self.p)?;
520 Ok(center_lift_vector(&b_p, self.p))
521 }
522
523 pub fn trial(&mut self, rng: &mut Lcg, max_key_tries: usize) -> Result<TrialResult, NtruError> {
525 let private = self.random_private_key(rng, max_key_tries)?;
526 let g = self.random_ternary(rng, self.d, self.d)?;
527 let r = self.random_ternary(rng, self.d, self.d)?;
528 let m = self.random_plaintext(rng);
529 let h = self.public_key(&private.f_q, &g)?;
530 let e = self.encrypt(&m, &h, &r)?;
531 let decrypted = self.decrypt(&e, &private.f, &private.f_p)?;
532
533 let a_q = self.multiply_mod(&signed_to_mod(&private.f, self.q), &e, self.q)?;
534 let a_lift = center_lift_vector(&a_q, self.q);
535 let expected = add_i64_vectors(
536 &scalar_mul_i64(self.p as i64, &self.multiply_integer(&g, &r)),
537 &self.multiply_integer(&private.f, &m),
538 );
539
540 Ok(TrialResult {
541 success: decrypted == m,
542 no_wrap: a_lift == expected,
543 key_attempts: private.attempts,
544 })
545 }
546
547 pub fn run_trials(&mut self, trials: usize, max_key_tries: usize, seed: u64) -> TrialSummary {
549 let mut rng = Lcg::new(seed);
550 let mut results = Vec::new();
551 let mut keygen_failures = 0;
552 for _ in 0..trials {
553 match self.trial(&mut rng, max_key_tries) {
554 Ok(result) => results.push(result),
555 Err(NtruError::NotInvertible) => keygen_failures += 1,
556 Err(_) => keygen_failures += 1,
557 }
558 }
559 let successes = results.iter().filter(|result| result.success).count();
560 let no_wraps = results.iter().filter(|result| result.no_wrap).count();
561 let attempts: Vec<_> = results.iter().map(|result| result.key_attempts).collect();
562 let avg_key_attempts = if attempts.is_empty() {
563 None
564 } else {
565 Some(attempts.iter().sum::<usize>() as f64 / attempts.len() as f64)
566 };
567 let max_key_attempts = attempts.into_iter().max();
568 TrialSummary {
569 requested_trials: trials,
570 completed_trials: results.len(),
571 successes,
572 no_wraps,
573 keygen_failures,
574 avg_key_attempts,
575 max_key_attempts,
576 backend_stats: self.stats.clone(),
577 }
578 }
579
580 pub fn multiply_integer(&self, lhs: &[i64], rhs: &[i64]) -> Vec<i64> {
582 let mut out = vec![0; self.group.order()];
583 for (lhs_index, lhs_value) in lhs.iter().enumerate() {
584 if *lhs_value == 0 {
585 continue;
586 }
587 for (rhs_index, rhs_value) in rhs.iter().enumerate() {
588 if *rhs_value == 0 {
589 continue;
590 }
591 let product_index = self.group.multiply_index(lhs_index, rhs_index);
592 out[product_index] += lhs_value * rhs_value;
593 }
594 }
595 out
596 }
597
598 fn naive_multiply_mod(
599 &self,
600 lhs: &[u64],
601 rhs: &[u64],
602 modulus: u64,
603 ) -> Result<Vec<u64>, NtruError> {
604 let mut out = vec![0; self.group.order()];
605 for (lhs_index, lhs_value) in lhs.iter().enumerate() {
606 let lhs_value = *lhs_value % modulus;
607 if lhs_value == 0 {
608 continue;
609 }
610 for (rhs_index, rhs_value) in rhs.iter().enumerate() {
611 let rhs_value = *rhs_value % modulus;
612 if rhs_value == 0 {
613 continue;
614 }
615 let product_index = self.group.multiply_index(lhs_index, rhs_index);
616 out[product_index] = add_mod(
617 out[product_index],
618 mul_mod(lhs_value, rhs_value, modulus),
619 modulus,
620 );
621 }
622 }
623 Ok(out)
624 }
625
626 fn try_fft_multiply(
627 &mut self,
628 lhs: &[u64],
629 rhs: &[u64],
630 modulus: u64,
631 ) -> Result<Option<Vec<u64>>, NtruError> {
632 match self.group.kind() {
633 GroupKind::Dihedral => self.try_dihedral_fft_multiply(lhs, rhs, modulus),
634 GroupKind::Symmetric => self.try_symmetric_fft_multiply(lhs, rhs, modulus),
635 GroupKind::Cyclic => Ok(None),
636 }
637 }
638
639 fn try_fft_inverse(
640 &mut self,
641 element: &[u64],
642 modulus: u64,
643 ) -> Result<Option<Vec<u64>>, NtruError> {
644 match self.group.kind() {
645 GroupKind::Dihedral => self.try_dihedral_fft_inverse(element, modulus),
646 GroupKind::Symmetric => self.try_symmetric_fft_inverse(element, modulus),
647 GroupKind::Cyclic => Ok(None),
648 }
649 }
650
651 #[cfg(feature = "fft")]
652 fn try_dihedral_fft_multiply(
653 &mut self,
654 lhs: &[u64],
655 rhs: &[u64],
656 modulus: u64,
657 ) -> Result<Option<Vec<u64>>, NtruError> {
658 if self.group.n() < 3
659 || !self.group.n().is_power_of_two()
660 || gcd(2 * self.group.n() as u64, modulus) != 1
661 {
662 return Ok(None);
663 }
664 if is_prime(modulus) && !(modulus - 1).is_multiple_of(self.group.n() as u64) {
665 return Ok(None);
666 }
667 let omega = match fft_dihedral::root_of_unity(self.group.n(), modulus) {
668 Ok(root) => root,
669 Err(_) => return Ok(None),
670 };
671 let n = self.group.n();
672 match fft_dihedral::dihedral_multiply_fft(
673 &lhs[..n],
674 &lhs[n..],
675 &rhs[..n],
676 &rhs[n..],
677 modulus,
678 omega,
679 ) {
680 Ok((rotations, reflections)) => {
681 self.stats.record("fft-dihedral:multiply");
682 Ok(Some(rotations.into_iter().chain(reflections).collect()))
683 }
684 Err(_) => Ok(None),
685 }
686 }
687
688 #[cfg(not(feature = "fft"))]
689 fn try_dihedral_fft_multiply(
690 &mut self,
691 _lhs: &[u64],
692 _rhs: &[u64],
693 _modulus: u64,
694 ) -> Result<Option<Vec<u64>>, NtruError> {
695 Ok(None)
696 }
697
698 #[cfg(feature = "fft")]
699 fn try_dihedral_fft_inverse(
700 &mut self,
701 element: &[u64],
702 modulus: u64,
703 ) -> Result<Option<Vec<u64>>, NtruError> {
704 if self.group.n() < 3
705 || !self.group.n().is_power_of_two()
706 || gcd(2 * self.group.n() as u64, modulus) != 1
707 {
708 return Ok(None);
709 }
710 if is_prime(modulus) && !(modulus - 1).is_multiple_of(self.group.n() as u64) {
711 return Ok(None);
712 }
713 let omega = match fft_dihedral::root_of_unity(self.group.n(), modulus) {
714 Ok(root) => root,
715 Err(_) => return Ok(None),
716 };
717 let n = self.group.n();
718 match fft_dihedral::dihedral_invert_fft(&element[..n], &element[n..], modulus, omega) {
719 Ok((rotations, reflections)) => {
720 let inverse: Vec<_> = rotations.into_iter().chain(reflections).collect();
721 self.stats.record("fft-dihedral:invert");
722 self.verify_inverse(element, &inverse, modulus)?;
723 Ok(Some(inverse))
724 }
725 Err(_) if is_prime(modulus) => Err(NtruError::NotInvertible),
726 Err(_) => Ok(None),
727 }
728 }
729
730 #[cfg(not(feature = "fft"))]
731 fn try_dihedral_fft_inverse(
732 &mut self,
733 _element: &[u64],
734 _modulus: u64,
735 ) -> Result<Option<Vec<u64>>, NtruError> {
736 Ok(None)
737 }
738
739 #[cfg(feature = "fft")]
740 fn try_symmetric_fft_multiply(
741 &mut self,
742 lhs: &[u64],
743 rhs: &[u64],
744 modulus: u64,
745 ) -> Result<Option<Vec<u64>>, NtruError> {
746 if !is_prime(modulus) || modulus <= self.group.n() as u64 {
747 return Ok(None);
748 }
749 let plan = match fft_symmetric::SymmetricFft::new(self.group.n(), modulus) {
750 Ok(plan) => plan,
751 Err(_) => return Ok(None),
752 };
753 match plan.multiply(lhs, rhs) {
754 Ok(product) => {
755 self.stats.record("fft-symmetric:multiply");
756 Ok(Some(product))
757 }
758 Err(_) => Ok(None),
759 }
760 }
761
762 #[cfg(not(feature = "fft"))]
763 fn try_symmetric_fft_multiply(
764 &mut self,
765 _lhs: &[u64],
766 _rhs: &[u64],
767 _modulus: u64,
768 ) -> Result<Option<Vec<u64>>, NtruError> {
769 Ok(None)
770 }
771
772 #[cfg(feature = "fft")]
773 fn try_symmetric_fft_inverse(
774 &mut self,
775 element: &[u64],
776 modulus: u64,
777 ) -> Result<Option<Vec<u64>>, NtruError> {
778 if !is_prime(modulus) || modulus <= self.group.n() as u64 {
779 return Ok(None);
780 }
781 let plan = match fft_symmetric::SymmetricFft::new(self.group.n(), modulus) {
782 Ok(plan) => plan,
783 Err(_) => return Ok(None),
784 };
785 match plan.invert(element) {
786 Ok(inverse) => {
787 self.stats.record("fft-symmetric:invert");
788 self.verify_inverse(element, &inverse, modulus)?;
789 Ok(Some(inverse))
790 }
791 Err(_) => Err(NtruError::NotInvertible),
792 }
793 }
794
795 #[cfg(not(feature = "fft"))]
796 fn try_symmetric_fft_inverse(
797 &mut self,
798 _element: &[u64],
799 _modulus: u64,
800 ) -> Result<Option<Vec<u64>>, NtruError> {
801 Ok(None)
802 }
803
804 fn linear_solve_inverse(&self, element: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
805 let matrix = self.left_multiplication_matrix(element, modulus);
806 solve_modular_linear_system(&matrix, &self.one_mod(modulus), modulus)
807 }
808
809 fn left_multiplication_matrix(&self, element: &[u64], modulus: u64) -> Vec<Vec<u64>> {
810 let mut matrix = vec![vec![0; self.group.order()]; self.group.order()];
811 for (column, _) in self.group.elements().iter().enumerate() {
812 for (index, coeff) in element.iter().enumerate() {
813 let coeff = *coeff % modulus;
814 if coeff == 0 {
815 continue;
816 }
817 let row = self.group.multiply_index(index, column);
818 matrix[row][column] = add_mod(matrix[row][column], coeff, modulus);
819 }
820 }
821 matrix
822 }
823
824 fn verify_inverse(
825 &mut self,
826 element: &[u64],
827 inverse: &[u64],
828 modulus: u64,
829 ) -> Result<(), NtruError> {
830 let identity = self.one_mod(modulus);
831 if self.multiply_mod(element, inverse, modulus)? != identity {
832 return Err(NtruError::NotInvertible);
833 }
834 if self.multiply_mod(inverse, element, modulus)? != identity {
835 return Err(NtruError::NotInvertible);
836 }
837 Ok(())
838 }
839}
840
841pub fn is_prime(value: u64) -> bool {
843 if value < 2 {
844 return false;
845 }
846 const SMALL: [u64; 12] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
847 for prime in SMALL {
848 if value == prime {
849 return true;
850 }
851 if value.is_multiple_of(prime) {
852 return false;
853 }
854 }
855 let mut d = value - 1;
856 let mut s = 0;
857 while d.is_multiple_of(2) {
858 s += 1;
859 d /= 2;
860 }
861 for base in SMALL {
862 if base >= value {
863 continue;
864 }
865 let mut x = pow_mod(base, d, value);
866 if x == 1 || x == value - 1 {
867 continue;
868 }
869 let mut probably_prime = false;
870 for _ in 0..s - 1 {
871 x = mul_mod(x, x, value);
872 if x == value - 1 {
873 probably_prime = true;
874 break;
875 }
876 }
877 if !probably_prime {
878 return false;
879 }
880 }
881 true
882}
883
884pub fn gcd(mut a: u64, mut b: u64) -> u64 {
886 while b != 0 {
887 let r = a % b;
888 a = b;
889 b = r;
890 }
891 a
892}
893
894pub fn add_mod(lhs: u64, rhs: u64, modulus: u64) -> u64 {
896 ((lhs as u128 + rhs as u128) % modulus as u128) as u64
897}
898
899pub fn sub_mod(lhs: u64, rhs: u64, modulus: u64) -> u64 {
901 ((lhs as u128 + modulus as u128 - rhs as u128) % modulus as u128) as u64
902}
903
904pub fn mul_mod(lhs: u64, rhs: u64, modulus: u64) -> u64 {
906 ((lhs as u128 * rhs as u128) % modulus as u128) as u64
907}
908
909pub fn pow_mod(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
911 let mut acc = 1 % modulus;
912 base %= modulus;
913 while exp > 0 {
914 if exp & 1 == 1 {
915 acc = mul_mod(acc, base, modulus);
916 }
917 base = mul_mod(base, base, modulus);
918 exp >>= 1;
919 }
920 acc
921}
922
923fn extended_gcd(a: i128, b: i128) -> (i128, i128, i128) {
924 if b == 0 {
925 (a, 1, 0)
926 } else {
927 let (g, x, y) = extended_gcd(b, a % b);
928 (g, y, x - (a / b) * y)
929 }
930}
931
932pub fn inv_mod(value: u64, modulus: u64) -> Option<u64> {
934 let (g, x, _) = extended_gcd(value as i128, modulus as i128);
935 if g != 1 {
936 None
937 } else {
938 Some(x.rem_euclid(modulus as i128) as u64)
939 }
940}
941
942pub fn center_lift(value: u64, modulus: u64) -> i64 {
944 let residue = value % modulus;
945 if residue > modulus / 2 {
946 residue as i64 - modulus as i64
947 } else {
948 residue as i64
949 }
950}
951
952pub fn center_lift_vector(values: &[u64], modulus: u64) -> Vec<i64> {
954 values
955 .iter()
956 .map(|value| center_lift(*value, modulus))
957 .collect()
958}
959
960pub fn signed_to_mod(values: &[i64], modulus: u64) -> Vec<u64> {
962 values
963 .iter()
964 .map(|value| (*value as i128).rem_euclid(modulus as i128) as u64)
965 .collect()
966}
967
968fn add_i64_vectors(lhs: &[i64], rhs: &[i64]) -> Vec<i64> {
969 lhs.iter().zip(rhs.iter()).map(|(a, b)| a + b).collect()
970}
971
972fn scalar_mul_i64(scalar: i64, values: &[i64]) -> Vec<i64> {
973 values.iter().map(|value| scalar * value).collect()
974}
975
976pub fn solve_modular_linear_system(
978 matrix: &[Vec<u64>],
979 rhs: &[u64],
980 modulus: u64,
981) -> Result<Vec<u64>, NtruError> {
982 let size = rhs.len();
983 if matrix.len() != size || matrix.iter().any(|row| row.len() != size) || modulus <= 1 {
984 return Err(NtruError::Shape);
985 }
986 let mut rows: Vec<Vec<u64>> = matrix
987 .iter()
988 .zip(rhs.iter())
989 .map(|(row, rhs)| {
990 let mut augmented: Vec<_> = row.iter().map(|value| value % modulus).collect();
991 augmented.push(*rhs % modulus);
992 augmented
993 })
994 .collect();
995
996 for col in 0..size {
997 let pivot_row = (col..size).find(|row| gcd(rows[*row][col], modulus) == 1);
998 let Some(pivot_row) = pivot_row else {
999 return Err(NtruError::NotInvertible);
1000 };
1001 if pivot_row != col {
1002 rows.swap(col, pivot_row);
1003 }
1004 let pivot_inv = inv_mod(rows[col][col], modulus).ok_or(NtruError::NotInvertible)?;
1005 for entry in &mut rows[col] {
1006 *entry = mul_mod(*entry, pivot_inv, modulus);
1007 }
1008 let pivot = rows[col].clone();
1009 for (row_index, row) in rows.iter_mut().enumerate() {
1010 if row_index == col {
1011 continue;
1012 }
1013 let factor = row[col];
1014 if factor == 0 {
1015 continue;
1016 }
1017 for (idx, entry) in row.iter_mut().enumerate().take(size + 1) {
1018 *entry = sub_mod(*entry, mul_mod(factor, pivot[idx], modulus), modulus);
1019 }
1020 }
1021 }
1022
1023 Ok(rows.into_iter().map(|row| row[size] % modulus).collect())
1024}
1025
1026pub fn cyclic_convolution_mod(
1028 lhs: &[u64],
1029 rhs: &[u64],
1030 modulus: u64,
1031) -> Result<Vec<u64>, NtruError> {
1032 if lhs.len() != rhs.len() || modulus == 0 {
1033 return Err(NtruError::Shape);
1034 }
1035 let n = lhs.len();
1036 let mut out = vec![0; n];
1037 for (i, lhs_value) in lhs.iter().enumerate() {
1038 let lhs_value = *lhs_value % modulus;
1039 if lhs_value == 0 {
1040 continue;
1041 }
1042 for (j, rhs_value) in rhs.iter().enumerate() {
1043 let rhs_value = *rhs_value % modulus;
1044 if rhs_value == 0 {
1045 continue;
1046 }
1047 out[(i + j) % n] = add_mod(
1048 out[(i + j) % n],
1049 mul_mod(lhs_value, rhs_value, modulus),
1050 modulus,
1051 );
1052 }
1053 }
1054 Ok(out)
1055}
1056
1057pub fn cyclic_involution(values: &[u64], modulus: u64) -> Vec<u64> {
1059 let n = values.len();
1060 let mut out = vec![0; n];
1061 for (index, value) in values.iter().enumerate() {
1062 out[(n - index) % n] = *value % modulus;
1063 }
1064 out
1065}
1066
1067pub fn cyclic_inverse_mod(values: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
1069 if values.is_empty() || modulus <= 1 {
1070 return Err(NtruError::Shape);
1071 }
1072 let normalized: Vec<_> = values.iter().map(|value| value % modulus).collect();
1073 if is_prime(modulus) {
1074 cyclic_inverse_prime_field(&normalized, modulus)
1075 } else {
1076 cyclic_inverse_linear_solve(&normalized, modulus)
1077 }
1078}
1079
1080fn cyclic_inverse_linear_solve(values: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
1081 let n = values.len();
1082 let mut matrix = vec![vec![0; n]; n];
1083 for row in 0..n {
1084 for col in 0..n {
1085 matrix[row][col] = values[(row + n - col) % n] % modulus;
1086 }
1087 }
1088 let mut rhs = vec![0; n];
1089 rhs[0] = 1 % modulus;
1090 solve_modular_linear_system(&matrix, &rhs, modulus)
1091}
1092
1093fn cyclic_inverse_prime_field(values: &[u64], modulus: u64) -> Result<Vec<u64>, NtruError> {
1094 let n = values.len();
1095 let mut modulus_poly = vec![0; n + 1];
1096 modulus_poly[0] = (modulus - 1) % modulus;
1097 modulus_poly[n] = 1;
1098 let inverse = polynomial_inverse_mod(values, &modulus_poly, modulus)?;
1099 Ok(polynomial_mod_xn_minus_1(&inverse, n, modulus))
1100}
1101
1102fn polynomial_inverse_mod(
1103 values: &[u64],
1104 modulus_poly: &[u64],
1105 modulus: u64,
1106) -> Result<Vec<u64>, NtruError> {
1107 let mut old_r = trim_polynomial(modulus_poly, modulus);
1108 let mut r = trim_polynomial(values, modulus);
1109 let mut old_t = Vec::new();
1110 let mut t = vec![1];
1111 while !r.is_empty() {
1112 let (quotient, remainder) = polynomial_divmod(&old_r, &r, modulus)?;
1113 old_r = r;
1114 r = remainder;
1115 let next_t = polynomial_sub(&old_t, &polynomial_mul("ient, &t, modulus), modulus);
1116 old_t = t;
1117 t = next_t;
1118 }
1119 if old_r.len() != 1 || old_r[0] == 0 {
1120 return Err(NtruError::NotInvertible);
1121 }
1122 let scale = inv_mod(old_r[0], modulus).ok_or(NtruError::NotInvertible)?;
1123 Ok(old_t
1124 .into_iter()
1125 .map(|coeff| mul_mod(scale, coeff, modulus))
1126 .collect())
1127}
1128
1129fn polynomial_divmod(
1130 numerator: &[u64],
1131 denominator: &[u64],
1132 modulus: u64,
1133) -> Result<(Vec<u64>, Vec<u64>), NtruError> {
1134 let mut remainder = trim_polynomial(numerator, modulus);
1135 let denominator = trim_polynomial(denominator, modulus);
1136 if denominator.is_empty() {
1137 return Err(NtruError::Shape);
1138 }
1139 if remainder.len() < denominator.len() {
1140 return Ok((Vec::new(), remainder));
1141 }
1142 let mut quotient = vec![0; remainder.len() - denominator.len() + 1];
1143 let denominator_lead_inv =
1144 inv_mod(*denominator.last().unwrap(), modulus).ok_or(NtruError::NotInvertible)?;
1145 while !remainder.is_empty() && remainder.len() >= denominator.len() {
1146 let shift = remainder.len() - denominator.len();
1147 let coeff = mul_mod(*remainder.last().unwrap(), denominator_lead_inv, modulus);
1148 quotient[shift] = coeff;
1149 for (index, denominator_coeff) in denominator.iter().enumerate() {
1150 remainder[shift + index] = sub_mod(
1151 remainder[shift + index],
1152 mul_mod(coeff, *denominator_coeff, modulus),
1153 modulus,
1154 );
1155 }
1156 remainder = trim_polynomial(&remainder, modulus);
1157 }
1158 Ok((trim_polynomial("ient, modulus), remainder))
1159}
1160
1161fn polynomial_mul(lhs: &[u64], rhs: &[u64], modulus: u64) -> Vec<u64> {
1162 if lhs.is_empty() || rhs.is_empty() {
1163 return Vec::new();
1164 }
1165 let mut out = vec![0; lhs.len() + rhs.len() - 1];
1166 for (i, lhs_value) in lhs.iter().enumerate() {
1167 let lhs_value = *lhs_value % modulus;
1168 if lhs_value == 0 {
1169 continue;
1170 }
1171 for (j, rhs_value) in rhs.iter().enumerate() {
1172 let rhs_value = *rhs_value % modulus;
1173 if rhs_value == 0 {
1174 continue;
1175 }
1176 out[i + j] = add_mod(out[i + j], mul_mod(lhs_value, rhs_value, modulus), modulus);
1177 }
1178 }
1179 trim_polynomial(&out, modulus)
1180}
1181
1182fn polynomial_sub(lhs: &[u64], rhs: &[u64], modulus: u64) -> Vec<u64> {
1183 let size = lhs.len().max(rhs.len());
1184 let mut out = vec![0; size];
1185 for (index, entry) in out.iter_mut().enumerate() {
1186 let lhs_value = lhs.get(index).copied().unwrap_or(0);
1187 let rhs_value = rhs.get(index).copied().unwrap_or(0);
1188 *entry = sub_mod(lhs_value, rhs_value, modulus);
1189 }
1190 trim_polynomial(&out, modulus)
1191}
1192
1193fn polynomial_mod_xn_minus_1(values: &[u64], n: usize, modulus: u64) -> Vec<u64> {
1194 let mut out = vec![0; n];
1195 for (index, coeff) in values.iter().enumerate() {
1196 out[index % n] = add_mod(out[index % n], *coeff % modulus, modulus);
1197 }
1198 out
1199}
1200
1201fn trim_polynomial(values: &[u64], modulus: u64) -> Vec<u64> {
1202 let mut out: Vec<_> = values.iter().map(|value| value % modulus).collect();
1203 while out.last() == Some(&0) {
1204 out.pop();
1205 }
1206 out
1207}
1208
1209pub fn dihedral_inverse_via_cyclic(
1211 element: &[u64],
1212 n: usize,
1213 modulus: u64,
1214) -> Result<Vec<u64>, NtruError> {
1215 if element.len() != 2 * n || n < 3 || modulus <= 1 {
1216 return Err(NtruError::Shape);
1217 }
1218 let rotations: Vec<_> = element[..n].iter().map(|value| value % modulus).collect();
1219 let reflections: Vec<_> = element[n..].iter().map(|value| value % modulus).collect();
1220 let rotation_bar = cyclic_involution(&rotations, modulus);
1221 let reflection_bar = cyclic_involution(&reflections, modulus);
1222 let rotation_norm = cyclic_convolution_mod(&rotations, &rotation_bar, modulus)?;
1223 let reflection_norm = cyclic_convolution_mod(&reflection_bar, &reflections, modulus)?;
1224 let determinant: Vec<_> = rotation_norm
1225 .iter()
1226 .zip(reflection_norm.iter())
1227 .map(|(lhs, rhs)| sub_mod(*lhs, *rhs, modulus))
1228 .collect();
1229 let determinant_inverse = cyclic_inverse_mod(&determinant, modulus)?;
1230 let inverse_rotations = cyclic_convolution_mod(&rotation_bar, &determinant_inverse, modulus)?;
1231 let neg_reflections: Vec<_> = reflections
1232 .iter()
1233 .map(|value| if *value == 0 { 0 } else { modulus - *value })
1234 .collect();
1235 let inverse_reflections =
1236 cyclic_convolution_mod(&neg_reflections, &determinant_inverse, modulus)?;
1237 Ok(inverse_rotations
1238 .into_iter()
1239 .chain(inverse_reflections)
1240 .collect())
1241}
1242
1243pub fn verify_cyclic_group_algebra_model(n: usize) -> Result<bool, NtruError> {
1245 let group = FiniteGroup::cyclic(n)?;
1246 let scheme = GroupAlgebraNtru::new(group, 3, 41, 2)?;
1247 for i in 0..n {
1248 for j in 0..n {
1249 if scheme.group.multiply_index(i, j) != (i + j) % n {
1250 return Ok(false);
1251 }
1252 }
1253 }
1254 Ok(true)
1255}
1256
1257#[cfg(test)]
1258mod tests {
1259 use super::*;
1260
1261 #[test]
1262 fn cyclic_model_matches_quotient_ring() {
1263 assert!(verify_cyclic_group_algebra_model(7).unwrap());
1264 }
1265
1266 #[test]
1267 fn dihedral_cyclic_inverse_handles_small_fields() {
1268 let group = FiniteGroup::dihedral(16).unwrap();
1269 let mut fast = GroupAlgebraNtru::new(group.clone(), 3, 97, 3).unwrap();
1270 let dense = GroupAlgebraNtru::new(group, 3, 97, 3).unwrap();
1271 let mut rng = Lcg::new(20260506);
1272 for _ in 0..100 {
1273 let element = fast.random_ternary(&mut rng, 4, 3).unwrap();
1274 let element_mod = signed_to_mod(&element, 3);
1275 let dense_inverse = dense.linear_solve_inverse(&element_mod, 3);
1276 if let Ok(expected) = dense_inverse {
1277 let inverse = fast.inverse_mod(&element_mod, 3).unwrap();
1278 assert_eq!(inverse, expected);
1279 assert!(fast
1280 .backend_stats()
1281 .counts()
1282 .contains_key("dihedral-cyclic:invert"));
1283 return;
1284 }
1285 }
1286 panic!("could not find an invertible sample");
1287 }
1288
1289 #[cfg(feature = "fft")]
1290 #[test]
1291 fn dihedral_fft_inverse_backend_is_used_when_compatible() {
1292 let group = FiniteGroup::dihedral(8).unwrap();
1293 let mut scheme = GroupAlgebraNtru::new(group, 3, 97, 2).unwrap();
1294 let mut element = vec![0; scheme.group().order()];
1295 element[0] = 5;
1296
1297 let inverse = scheme.inverse_mod(&element, 97).unwrap();
1298 assert_eq!(
1299 scheme.multiply_mod(&element, &inverse, 97).unwrap(),
1300 scheme.one_mod(97)
1301 );
1302 assert!(scheme
1303 .backend_stats()
1304 .counts()
1305 .contains_key("fft-dihedral:invert"));
1306 }
1307
1308 #[cfg(feature = "fft")]
1309 #[test]
1310 fn symmetric_fft_inverse_backend_is_used_when_compatible() {
1311 let group = FiniteGroup::symmetric(3).unwrap();
1312 let mut scheme = GroupAlgebraNtru::new(group, 5, 67, 2).unwrap();
1313 let mut element = vec![0; scheme.group().order()];
1314 element[0] = 2;
1315
1316 let inverse = scheme.inverse_mod(&element, 5).unwrap();
1317 assert_eq!(
1318 scheme.multiply_mod(&element, &inverse, 5).unwrap(),
1319 scheme.one_mod(5)
1320 );
1321 assert!(scheme
1322 .backend_stats()
1323 .counts()
1324 .contains_key("fft-symmetric:invert"));
1325 }
1326
1327 #[test]
1328 fn symmetric_s3_round_trips() {
1329 let group = FiniteGroup::symmetric(3).unwrap();
1330 let mut scheme = GroupAlgebraNtru::new(group, 5, 67, 2).unwrap();
1331 let summary = scheme.run_trials(3, 50, 20260506);
1332 assert_eq!(summary.completed_trials, 3);
1333 assert_eq!(summary.successes, 3);
1334 assert_eq!(summary.no_wraps, 3);
1335 }
1336
1337 #[test]
1338 fn dihedral_trials_round_trip() {
1339 let group = FiniteGroup::dihedral(8).unwrap();
1340 let mut scheme = GroupAlgebraNtru::new(group, 3, 97, 2).unwrap();
1341 let summary = scheme.run_trials(2, 100, 20260506);
1342 assert_eq!(summary.completed_trials, 2);
1343 assert_eq!(summary.successes, 2);
1344 }
1345}