Skip to main content

logicaffeine_proof/
cyclotomic.rs

1//! # Power-of-two cyclotomic ring `R = ℤ[X]/(Xⁿ + 1)`, `n = 2ᵏ`
2//!
3//! When `n` is a power of two, `Xⁿ + 1 = Φ_{2n}(X)` is the `2n`-th cyclotomic polynomial, so `R` is the ring
4//! of integers `𝒪_K` of the cyclotomic field `K = ℚ(ζ_{2n})` (`ζ_{2n}` a primitive `2n`-th root of unity,
5//! played by `X`). This is the algebraic substrate of **Module-LWE** — ML-KEM/Kyber live over `R_q` with
6//! `n = 256`. Multiplication is **negacyclic** (`Xⁿ ≡ −1`).
7//!
8//! The field's **Galois group** is `Gal(K/ℚ) ≅ (ℤ/2n)^×` — the ring automorphisms `σ_t : X ↦ X^t` for odd
9//! `t`, of which there are exactly `φ(2n) = n`. This rigid, fully-known symmetry group is precisely what
10//! structure-exploiting cryptanalysis (the log-unit lattice, the Principal Ideal Problem) rides on: two
11//! generators of an ideal differ by a unit, and the units are governed by these automorphisms. It is the
12//! lattice analogue of the `Aut(E₀)`-orbit collapse in the isogeny keyspace — **symmetry = compression**.
13//!
14//! This module builds the ring and its Galois action honestly. It does **not** break Module-LWE: it is the
15//! substrate on which the (short-generator) attacks that *do* work are expressed, and the lens that measures
16//! where they stop.
17
18use logicaffeine_base::BigInt;
19use std::f64::consts::PI;
20
21#[inline]
22fn zero() -> BigInt {
23    BigInt::from_i64(0)
24}
25
26/// An element of `R = ℤ[X]/(Xⁿ + 1)`: the coefficient vector `[a₀, …, a_{n−1}]` of `Σ aᵢ Xⁱ`, with `n` a
27/// power of two.
28#[derive(Clone, Debug, PartialEq, Eq)]
29pub struct Cyclo {
30    pub n: usize,
31    pub coeffs: Vec<BigInt>,
32}
33
34impl Cyclo {
35    /// An element from a coefficient vector (padded/verified to length `n`). `n` must be a power of two.
36    pub fn new(n: usize, mut coeffs: Vec<BigInt>) -> Cyclo {
37        assert!(
38            n.is_power_of_two(),
39            "R = ℤ[X]/(Xⁿ+1) requires n a power of two"
40        );
41        assert!(coeffs.len() <= n, "an element of R has degree < n");
42        coeffs.resize(n, zero());
43        Cyclo { n, coeffs }
44    }
45
46    /// Convenience constructor from small integers.
47    pub fn from_ints(n: usize, v: &[i64]) -> Cyclo {
48        Cyclo::new(n, v.iter().map(|&x| BigInt::from_i64(x)).collect())
49    }
50
51    pub fn zero(n: usize) -> Cyclo {
52        Cyclo::new(n, vec![])
53    }
54
55    pub fn one(n: usize) -> Cyclo {
56        Cyclo::from_ints(n, &[1])
57    }
58
59    /// `coeff · Xⁱ` reduced into `R` (any `i ≥ 0`): `Xⁱ = (−1)^{⌊i/n⌋} · X^{i mod n}`.
60    pub fn monomial(n: usize, i: usize, coeff: BigInt) -> Cyclo {
61        let mut c = vec![zero(); n];
62        let signed = if (i / n) % 2 == 0 {
63            coeff
64        } else {
65            zero().sub(&coeff)
66        };
67        c[i % n] = signed;
68        Cyclo { n, coeffs: c }
69    }
70
71    pub fn add(&self, o: &Cyclo) -> Cyclo {
72        Cyclo {
73            n: self.n,
74            coeffs: (0..self.n)
75                .map(|i| self.coeffs[i].add(&o.coeffs[i]))
76                .collect(),
77        }
78    }
79
80    pub fn sub(&self, o: &Cyclo) -> Cyclo {
81        Cyclo {
82            n: self.n,
83            coeffs: (0..self.n)
84                .map(|i| self.coeffs[i].sub(&o.coeffs[i]))
85                .collect(),
86        }
87    }
88
89    pub fn neg(&self) -> Cyclo {
90        Cyclo {
91            n: self.n,
92            coeffs: self.coeffs.iter().map(|c| zero().sub(c)).collect(),
93        }
94    }
95
96    /// Negacyclic product: multiply as polynomials, then reduce `Xⁿ ≡ −1`.
97    pub fn mul(&self, o: &Cyclo) -> Cyclo {
98        let n = self.n;
99        let mut c = vec![zero(); n];
100        for i in 0..n {
101            if self.coeffs[i].is_zero() {
102                continue;
103            }
104            for j in 0..n {
105                let prod = self.coeffs[i].mul(&o.coeffs[j]);
106                let k = i + j;
107                if k < n {
108                    c[k] = c[k].add(&prod); // Xᵏ, k < n
109                } else {
110                    c[k - n] = c[k - n].sub(&prod); // Xᵏ = −X^{k−n}
111                }
112            }
113        }
114        Cyclo { n, coeffs: c }
115    }
116
117    /// The Galois automorphism `σ_t : X ↦ X^t` (`t` odd, i.e. a unit of `ℤ/2n`). On monomials
118    /// `σ_t(Xⁱ) = X^{it}`, reduced by `Xⁿ ≡ −1`. A ring automorphism of `R`.
119    pub fn galois(&self, t: u64) -> Cyclo {
120        let n = self.n;
121        let twon = 2 * n as u64;
122        let t = t % twon;
123        assert!(
124            t % 2 == 1,
125            "Galois automorphisms σ_t require t odd (a unit mod 2n)"
126        );
127        let mut c = vec![zero(); n];
128        for i in 0..n {
129            let m = ((i as u64) * t) % twon;
130            let (idx, neg) = if (m as usize) < n {
131                (m as usize, false)
132            } else {
133                (m as usize - n, true)
134            };
135            c[idx] = if neg {
136                c[idx].sub(&self.coeffs[i])
137            } else {
138                c[idx].add(&self.coeffs[i])
139            };
140        }
141        Cyclo { n, coeffs: c }
142    }
143
144    /// Complex conjugation `σ_{−1} : X ↦ X^{−1} = X^{2n−1}` — the order-two element of the Galois group.
145    pub fn conjugate(&self) -> Cyclo {
146        self.galois((2 * self.n - 1) as u64)
147    }
148
149    /// The product `∏_{σ ∈ Gal} σ(a)` as a ring element — Galois-invariant, hence a rational integer times
150    /// `1`. Used by [`norm`](Cyclo::norm); exposed so callers can confirm the higher coefficients vanish.
151    fn galois_product(&self) -> Cyclo {
152        galois_group(self.n)
153            .into_iter()
154            .fold(Cyclo::one(self.n), |acc, t| acc.mul(&self.galois(t)))
155    }
156
157    /// The field **norm** `N(a) = ∏_{σ ∈ Gal} σ(a) ∈ ℤ` — multiplicative, and `±1` exactly on the units.
158    pub fn norm(&self) -> BigInt {
159        self.galois_product().coeffs[0].clone()
160    }
161
162    /// The field **trace** `Tr(a) = Σ_{σ ∈ Gal} σ(a) ∈ ℤ` — additive; `Tr(1) = n`.
163    pub fn trace(&self) -> BigInt {
164        let sum = galois_group(self.n)
165            .into_iter()
166            .fold(Cyclo::zero(self.n), |acc, t| acc.add(&self.galois(t)));
167        sum.coeffs[0].clone()
168    }
169
170    /// Whether `a` is a unit of `R` — equivalently `N(a) = ±1`.
171    pub fn is_unit(&self) -> bool {
172        let nrm = self.norm();
173        nrm == BigInt::from_i64(1) || nrm == BigInt::from_i64(-1)
174    }
175
176    /// The exact ring inverse of a **unit**, with no field division: since `N(u) = u·∏_{t≠1}σ_t(u) = ±1`, we
177    /// have `u⁻¹ = N(u)·∏_{t≠1}σ_t(u)`. `None` for a non-unit.
178    pub fn unit_inverse(&self) -> Option<Cyclo> {
179        let nrm = self.norm();
180        let one = BigInt::from_i64(1);
181        let neg = BigInt::from_i64(-1);
182        let sign_neg = if nrm == one {
183            false
184        } else if nrm == neg {
185            true
186        } else {
187            return None;
188        };
189        let prod = galois_group(self.n)
190            .into_iter()
191            .filter(|&t| t != 1)
192            .fold(Cyclo::one(self.n), |acc, t| acc.mul(&self.galois(t)));
193        Some(if sign_neg { prod.neg() } else { prod })
194    }
195
196    /// The sum of absolute values of the coefficients — a coarse length used to recognize a *short* generator.
197    pub fn coeff_norm(&self) -> i64 {
198        self.coeffs
199            .iter()
200            .map(|c| c.to_i64().unwrap_or(i64::MAX / 2).abs())
201            .sum()
202    }
203}
204
205// ---- The log-unit lattice and CDPR short-generator recovery -----------------------------------------
206//
207// The canonical embedding sends a ∈ K to (a(ζ^j))_{j odd} ∈ ℂⁿ (the n complex places), and the log embedding
208// to (log|a(ζ^j)|)_j ∈ ℝⁿ. The units map to a lattice Λ = Log(units); the cyclotomic units b_j = (Xʲ−1)/(X−1)
209// give an explicit basis. A short generator g of a principal ideal sits *close to the origin* in this picture,
210// so a generator h = g·u differs from it by the lattice vector Log(u); rounding Log(h) into Λ strips the unit.
211// This is the AutOrbitClosure move — quotient out the units, collapse the space — for structured lattices.
212
213/// `a(ζ^j)` in ℂ, `ζ = exp(2πi/2n)` — the `j`-th canonical embedding.
214fn embed_at(a: &Cyclo, j: usize) -> (f64, f64) {
215    let twon = 2.0 * a.n as f64;
216    let (mut re, mut im) = (0.0f64, 0.0f64);
217    for (i, c) in a.coeffs.iter().enumerate() {
218        let ci = c.to_i64().expect("embedding assumes coefficients fit i64") as f64;
219        let ang = 2.0 * PI * (j as f64) * (i as f64) / twon;
220        re += ci * ang.cos();
221        im += ci * ang.sin();
222    }
223    (re, im)
224}
225
226/// The log embedding `Log(a) = (log|a(ζ^j)|)_{j odd} ∈ ℝⁿ`.
227fn log_embedding(a: &Cyclo) -> Vec<f64> {
228    (1..2 * a.n)
229        .step_by(2)
230        .map(|j| {
231            let (re, im) = embed_at(a, j);
232            0.5 * (re * re + im * im).ln()
233        })
234        .collect()
235}
236
237fn dot(u: &[f64], v: &[f64]) -> f64 {
238    u.iter().zip(v).map(|(a, b)| a * b).sum()
239}
240
241/// Solve `A x = b` (small dense system) by Gaussian elimination with partial pivoting. `None` if singular.
242fn solve_linear(mut a: Vec<Vec<f64>>, mut b: Vec<f64>) -> Option<Vec<f64>> {
243    let n = b.len();
244    for col in 0..n {
245        let piv = (col..n).max_by(|&r1, &r2| {
246            a[r1][col]
247                .abs()
248                .partial_cmp(&a[r2][col].abs())
249                .unwrap_or(std::cmp::Ordering::Equal)
250        })?;
251        if a[piv][col].abs() < 1e-9 {
252            return None;
253        }
254        a.swap(col, piv);
255        b.swap(col, piv);
256        for r in 0..n {
257            if r == col {
258                continue;
259            }
260            let f = a[r][col] / a[col][col];
261            for k in col..n {
262                a[r][k] -= f * a[col][k];
263            }
264            b[r] -= f * b[col];
265        }
266    }
267    Some((0..n).map(|i| b[i] / a[i][i]).collect())
268}
269
270/// The cyclotomic units `b_j = 1 + X + ⋯ + X^{j−1} = (Xʲ−1)/(X−1)` for `j` an odd residue in `[3, n−1]`. These
271/// are `n/2 − 1` independent units — a basis of a finite-index subgroup of the unit group, and the basis of
272/// the log-unit lattice used by CDPR.
273pub fn cyclotomic_units(n: usize) -> Vec<Cyclo> {
274    (3..n)
275        .step_by(2)
276        .map(|j| Cyclo::from_ints(n, &vec![1i64; j]))
277        .collect()
278}
279
280/// **CDPR short-generator recovery.** Given a generator `h` of a principal ideal that has an *unusually short*
281/// generator `g` (so `h = g·u` for a unit `u`), recover a short generator: project `Log(h)` onto the log-unit
282/// lattice against the cyclotomic-unit basis to strip the unit, divide it out **exactly** (via the
283/// Galois-conjugate inverse), and pick the exact generator of smallest coefficient-norm over a local search
284/// around the rounded lattice point. Returns `g` up to a root of unity `±Xᵐ`. This is the genuine break on
285/// schemes that expose a short principal-ideal generator (Soliloquy, Smart–Vercauteren); it does **not** touch
286/// Module-LWE, where the secret is not such a generator.
287pub fn recover_short_generator(h: &Cyclo) -> Option<Cyclo> {
288    let n = h.n;
289    let units = cyclotomic_units(n);
290    let r = units.len();
291    let blogs: Vec<Vec<f64>> = units.iter().map(log_embedding).collect();
292    let target = log_embedding(h);
293
294    // Least-squares coordinates of Log(h) in the unit-log basis: (BᵀB) c = Bᵀ Log(h).
295    let mut btb = vec![vec![0.0; r]; r];
296    let mut bt = vec![0.0; r];
297    for i in 0..r {
298        for k in 0..r {
299            btb[i][k] = dot(&blogs[i], &blogs[k]);
300        }
301        bt[i] = dot(&blogs[i], &target);
302    }
303    let c = solve_linear(btb, bt)?;
304    let base: Vec<i64> = c.iter().map(|&x| x.round() as i64).collect();
305
306    // Local search over the rounded exponents: the true short generator is the exact divisor of least norm.
307    let inverses: Vec<Cyclo> = units.iter().filter_map(|u| u.unit_inverse()).collect();
308    if inverses.len() != r {
309        return None;
310    }
311    let mut best: Option<(i64, Cyclo)> = None;
312    for mask in 0..3usize.pow(r as u32) {
313        let mut m = mask;
314        let mut uprime = Cyclo::one(n);
315        for i in 0..r {
316            let e = base[i] + (m % 3) as i64 - 1;
317            m /= 3;
318            let base_elt = if e >= 0 { &units[i] } else { &inverses[i] };
319            for _ in 0..e.unsigned_abs() {
320                uprime = uprime.mul(base_elt);
321            }
322        }
323        let Some(uinv) = uprime.unit_inverse() else {
324            continue;
325        };
326        let g = h.mul(&uinv);
327        let norm = g.coeff_norm();
328        if best.as_ref().is_none_or(|(bn, _)| norm < *bn) {
329            best = Some((norm, g));
330        }
331    }
332    best.map(|(_, g)| g)
333}
334
335/// Gram–Schmidt orthogonalization of a set of `ℝ^m` vectors (returns the orthogonal `bᵢ*`).
336fn gram_schmidt(vs: &[Vec<f64>]) -> Vec<Vec<f64>> {
337    let mut out: Vec<Vec<f64>> = Vec::new();
338    for v in vs {
339        let mut u = v.clone();
340        for w in &out {
341            let coef = dot(v, w) / dot(w, w);
342            for j in 0..u.len() {
343                u[j] -= coef * w[j];
344            }
345        }
346        out.push(u);
347    }
348    out
349}
350
351/// An audit of the **log-unit lattice** geometry `Λ = Log(units)` that governs CDPR recovery — the decoding
352/// scale of the symmetry-quotient.
353#[derive(Clone, Debug)]
354pub struct LogUnitAudit {
355    pub n: usize,
356    /// The unit rank `r₁ + r₂ − 1 = n/2 − 1` (Dirichlet).
357    pub rank: usize,
358    /// Gram–Schmidt lengths `‖bᵢ*‖` of the cyclotomic-unit log-basis.
359    pub gs_lengths: Vec<f64>,
360    /// Covering-radius upper bound `μ ≤ ½·(Σ‖bᵢ*‖²)^½` — the scale below which a short generator is
361    /// decodable by rounding in `Λ`.
362    pub covering_radius_bound: f64,
363}
364
365/// Measure the log-unit lattice geometry for `R = ℤ[X]/(Xⁿ+1)`.
366pub fn audit_log_unit(n: usize) -> LogUnitAudit {
367    let units = cyclotomic_units(n);
368    let blogs: Vec<Vec<f64>> = units.iter().map(log_embedding).collect();
369    let gs = gram_schmidt(&blogs);
370    let gs_lengths: Vec<f64> = gs.iter().map(|v| dot(v, v).sqrt()).collect();
371    let cov = 0.5 * gs_lengths.iter().map(|l| l * l).sum::<f64>().sqrt();
372    LogUnitAudit {
373        n,
374        rank: units.len(),
375        gs_lengths,
376        covering_radius_bound: cov,
377    }
378}
379
380/// The **CDPR recovery margin** of a candidate generator `g`: `‖proj_{span Λ} Log(g)‖ / μ(Λ)`. A generator
381/// whose log projects to well within the covering radius (`margin < 1`) is decodable by stripping the unit;
382/// `margin ≫ 1` is beyond the decoding region. This measures *where the short-generator wall is* — and,
383/// honestly, it is **small even for short (ML-KEM-shaped) secrets**, showing the log-unit collapse is *not*
384/// where Module-LWE's hardness lives: that sits upstream (no principal-ideal-generator to hand the attacker,
385/// module rank ≥ 2, and the `2^Õ(√n)` Ideal-SVP approximation gap).
386pub fn recovery_margin(g: &Cyclo) -> f64 {
387    let n = g.n;
388    let blogs: Vec<Vec<f64>> = cyclotomic_units(n).iter().map(log_embedding).collect();
389    let r = blogs.len();
390    let lg = log_embedding(g);
391    let mut btb = vec![vec![0.0; r]; r];
392    let mut bt = vec![0.0; r];
393    for i in 0..r {
394        for k in 0..r {
395            btb[i][k] = dot(&blogs[i], &blogs[k]);
396        }
397        bt[i] = dot(&blogs[i], &lg);
398    }
399    let Some(c) = solve_linear(btb, bt) else {
400        return f64::INFINITY;
401    };
402    let mut proj = vec![0.0; n];
403    for i in 0..r {
404        for (j, pj) in proj.iter_mut().enumerate() {
405            *pj += c[i] * blogs[i][j];
406        }
407    }
408    dot(&proj, &proj).sqrt() / audit_log_unit(n).covering_radius_bound
409}
410
411/// **The upstream wall, measured.** The approximation scale of the log-unit collapse at dimension `n`: the
412/// covering radius `μ(Λ)` against the shortest basis log-length — a proxy for the factor by which a
413/// log-unit-decoded generator can exceed the true shortest vector. To *threaten* Module-LWE this factor would
414/// have to stay **polynomial**; instead it grows super-polynomially with `n` (asymptotically `2^{Õ(√n)}`,
415/// Cramer–Ducas–Wesolowski 2017). This is the real wall — not the symmetry-collapse rung (which is cheap, as
416/// [`recovery_margin`] shows) but the *quality* of what the collapse can decode as the field grows.
417pub fn approximation_scale(n: usize) -> f64 {
418    let a = audit_log_unit(n);
419    let shortest = a.gs_lengths.iter().cloned().fold(f64::INFINITY, f64::min);
420    a.covering_radius_bound / shortest
421}
422
423/// The `n = φ(2n)` Galois automorphisms of `R = ℤ[X]/(Xⁿ+1)`, as the odd residues mod `2n` that index them.
424pub fn galois_group(n: usize) -> Vec<u64> {
425    (1..(2 * n as u64)).step_by(2).collect()
426}
427
428#[cfg(test)]
429#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/cyclotomic/tests.rs"]
430mod tests;