Galois Invariants in Cyclotomic Lattice Enumeration: Deterministic Collapse of the SVP Search Space via Modular Projection Pruning

This repository contains the manuscript, the interactive supplementary notebook, and the complete computational framework for the research article titled "Galois Invariants in Cyclotomic Lattice Enumeration: An Efficient Meet-in-the-Middle Attack on Ring-LWE under Partial Key Exposure". The work quantifies the devastating impact of modular projection leakage —obtainable through physical side channels— on the security of lattice-based post-quantum cryptography. Repository Contents Manuscript (LaTeX / PDF): The full paper submitted to the Journal of Cryptographic Engineering, presenting the Law of Oracle Independence, the Galois group reduction, the extrapolation to ML‑KEM, and the area‑law entropy analysis. Interactive Supplementary Notebook: A self‑contained Google Colab notebook that reproduces every experimental result reported in the paper. It compiles on the fly a highly optimised Meet‑in‑the‑Middle (MitM) C++ engine with OpenMP parallelism and 128‑bit packed keys, and includes guided Markdown explanations for reviewers. Empirical Data: All survivor counts, uniformity tests, and entropy measurements up to dimension d=32d=32, generated with fixed random seeds for full reproducibility. Key Scientific Findings Law of Oracle Independence: The number of ternary secret vectors compatible with kk leaked ideal residues collapses exactly as 3d/∏qi3d/∏qi, where qi=pifiqi=pifi are the true ideal norms. Empirically validated for d=32d=32 with pruning rates exceeding 99. 999999991%. Galois Group Reduction: Conjugate prime ideals are tied by Frobenius automorphisms, effectively dividing the number of independent side‑channel oracles by the orbit size. ML‑KEM Extrapolation: In the NIST standard ring Q (ζ512) Q (ζ512) (n=256n=256), two leaked inert‑prime residues suffice to uniquely determine the secret, even before accounting for Galois conjugacy. Area‑Law Entropy: The configuration entropy of the surviving search space saturates to a constant once ∏qi>3d∏qi>3d, a hallmark of non‑ergodic phases. Adaptive Two‑Phase Search: A prioritised search strategy, inspired by quantum modular algorithms, is validated on a fully enumerated d=8d=8 instance. Computational Methodology To overcome "oracle blindness" at shallow depths of the search tree, the engine implements a Meet‑in‑the‑Middle architecture that splits the dd-dimensional problem into two halves of size d/2d/2. The forward phase stores packed residues in a sorted vector; the backward phase performs massive binary searches via std: : equalᵣange. Aggressive bit‑packing (28 bits per residue into _ᵢnt128) and OpenMP multi‑core parallelism allow processing d=32d=32 in approximately 50 seconds per oracle configuration on a standard cloud instance. Licensing and Citation Code & Software: PolyForm Noncommercial License 1. 0. 0. Manuscript & Visual Assets: Creative Commons Attribution‑NonCommercial‑ShareAlike 4. 0 International (CC BY‑NC‑SA 4. 0). If you use this computational framework, the MitM C++ architecture, or the theoretical derivations in your research, please cite this repository using the DOI assigned by Zenodo and the corresponding article. Keywords: Ring‑LWE, Side‑Channel Attack, Partial Key Exposure, Meet‑in‑the‑Middle, Cyclotomic Ideals, ML‑KEM, Post‑Quantum Cryptography, Cryptographic Engineering