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;