quantica/ml_dsa/decompose.rs
1//! Decomposition algorithms for ML-DSA (FIPS 204, Algorithms 35-40).
2//!
3//! Implements the Decompose, HighBits, LowBits, MakeHint, and UseHint
4//! functions used during signing and verification to split polynomial
5//! coefficients into high-order and low-order parts with respect to
6//! `alpha = 2 * gamma2`.
7//!
8//! All vector functions operate on slices and fixed arrays -- no heap
9//! allocations.
10
11use super::params::{MAX_K, N, Q};
12
13/// Decompose a coefficient into high and low parts.
14///
15/// Implements Algorithm 36 of FIPS 204 (Decompose). Given `r` in [0, q-1]
16/// and `gamma2`, computes `(r1, r0)` such that `r = r1 * alpha + r0` where
17/// `alpha = 2 * gamma2` and `r0` lies in the centered range
18/// `(-alpha/2, alpha/2]`. A special case handles `r1 * alpha == q - 1` to
19/// keep r1 in the valid range.
20///
21/// - `r`: coefficient to decompose (should be in [0, q-1]).
22/// - `gamma2`: half the decomposition modulus (parameter-set dependent).
23///
24/// Returns `(r1, r0)`.
25pub fn decompose(r: i32, gamma2: i32) -> (i32, i32) {
26 let alpha = 2 * gamma2;
27 let rp = r % Q + ((r >> 31) & Q); // ensure positive
28 let mut r0 = rp % alpha; // [0, alpha-1]
29 if r0 > alpha / 2 {
30 r0 -= alpha;
31 }
32 if rp - r0 == Q - 1 {
33 (0, r0 - 1)
34 } else {
35 ((rp - r0) / alpha, r0)
36 }
37}
38
39/// Extract the high-order representative of a coefficient.
40///
41/// Implements Algorithm 37 of FIPS 204 (HighBits). Returns the r1 component
42/// from [`decompose`]. This is used to compute the commitment w1 during
43/// signing and verification.
44pub fn high_bits(r: i32, gamma2: i32) -> i32 {
45 decompose(r, gamma2).0
46}
47
48/// Extract the low-order representative of a coefficient.
49///
50/// Implements Algorithm 38 of FIPS 204 (LowBits). Returns the r0 component
51/// from [`decompose`]. The norm of r0 is checked during signing to decide
52/// whether to accept or reject a candidate signature.
53pub fn low_bits(r: i32, gamma2: i32) -> i32 {
54 decompose(r, gamma2).1
55}
56
57/// Compute a single hint bit.
58///
59/// Implements Algorithm 39 of FIPS 204 (MakeHint). Returns 1 if adding `z`
60/// to `r` changes the high bits (i.e., `HighBits(r + z) != HighBits(r)`),
61/// and 0 otherwise. The hint allows the verifier to recover w1 without
62/// knowing the secret low-order information.
63///
64/// - `z`: perturbation value (typically `-ct0[i][j]`).
65/// - `r`: base value (typically `(w - cs2 + ct0)[i][j]`).
66/// - `gamma2`: decomposition parameter.
67pub fn make_hint(z: i32, r: i32, gamma2: i32) -> i32 {
68 let r1 = high_bits(r, gamma2);
69 let v1 = high_bits((r + z) % Q + (((r + z) >> 31) & Q), gamma2);
70 if r1 != v1 { 1 } else { 0 }
71}
72
73/// Use a hint bit to recover the correct high bits.
74///
75/// Implements Algorithm 40 of FIPS 204 (UseHint). When `h == 0`, returns
76/// `HighBits(r)` directly. When `h == 1`, adjusts the high-bits value by
77/// +/-1 (modulo m = (q-1)/alpha) depending on the sign of the low bits.
78///
79/// - `h`: hint bit (0 or 1).
80/// - `r`: the approximate value to round.
81/// - `gamma2`: decomposition parameter.
82///
83/// Returns the corrected high-order representative.
84pub fn use_hint(h: i32, r: i32, gamma2: i32) -> i32 {
85 let alpha = 2 * gamma2;
86 let (r1, r0) = decompose(r, gamma2);
87 if h == 0 {
88 return r1;
89 }
90 // m = (q-1) / alpha
91 let m = (Q - 1) / alpha;
92 if r0 > 0 { (r1 + 1) % m } else { (r1 - 1 + m) % m }
93}
94
95/// Apply [`high_bits`] to every coefficient of a polynomial vector.
96///
97/// Writes the high-order parts into `out`. Only the first `len` polynomials
98/// are processed.
99pub fn high_bits_vec(w: &[[i32; N]], gamma2: i32, out: &mut [[i32; N]], len: usize) {
100 for i in 0..len {
101 for j in 0..N {
102 out[i][j] = high_bits(w[i][j], gamma2);
103 }
104 }
105}
106
107/// Apply [`low_bits`] to every coefficient of a polynomial vector.
108///
109/// Writes the low-order parts into `out`. Only the first `len` polynomials
110/// are processed.
111pub fn low_bits_vec(w: &[[i32; N]], gamma2: i32, out: &mut [[i32; N]], len: usize) {
112 for i in 0..len {
113 for j in 0..N {
114 out[i][j] = low_bits(w[i][j], gamma2);
115 }
116 }
117}
118
119/// Apply [`make_hint`] to every coefficient of two polynomial vectors.
120///
121/// Returns `(h, count)` where `h` is the fixed array of hint polynomials and
122/// `count` is the total number of 1-bits across all polynomials. The count
123/// is compared against `omega` to decide whether to accept the signature.
124pub fn make_hint_vec(z: &[[i32; N]], r: &[[i32; N]], gamma2: i32, len: usize) -> ([[i32; N]; MAX_K], usize) {
125 let mut h = [[0i32; N]; MAX_K];
126 let mut count = 0usize;
127 for i in 0..len {
128 for j in 0..N {
129 h[i][j] = make_hint(z[i][j], r[i][j], gamma2);
130 count += h[i][j] as usize;
131 }
132 }
133 (h, count)
134}
135
136/// Apply [`use_hint`] to every coefficient of a hint vector and an approximate vector.
137///
138/// Returns the corrected w1 vector used during verification.
139pub fn use_hint_vec(h: &[[i32; N]], r: &[[i32; N]], gamma2: i32, len: usize) -> [[i32; N]; MAX_K] {
140 let mut w1 = [[0i32; N]; MAX_K];
141 for i in 0..len {
142 for j in 0..N {
143 w1[i][j] = use_hint(h[i][j], r[i][j], gamma2);
144 }
145 }
146 w1
147}
148
149#[cfg(test)]
150mod tests {
151 use super::*;
152
153 #[test]
154 fn test_decompose_roundtrip() {
155 let gamma2 = (Q - 1) / 88;
156 let alpha = 2 * gamma2;
157 for r in [0, 1, 100000, Q / 2, Q - 1] {
158 let (r1, r0) = decompose(r, gamma2);
159 let reconstructed = (r1 * alpha + r0) % Q + (((r1 * alpha + r0) >> 31) & Q);
160 assert_eq!(reconstructed, r, "decompose roundtrip failed for r={}", r);
161 }
162 }
163
164 #[test]
165 fn test_use_hint_consistency() {
166 let gamma2 = (Q - 1) / 88;
167 let r = 1234567;
168 let r1 = high_bits(r, gamma2);
169 // With hint=0, use_hint should return r1
170 assert_eq!(use_hint(0, r, gamma2), r1);
171 }
172}