NUMBER-THEORETIC REFINEMENT OF CONCRETE SECURITY ESTIMATES FOR RING-LWE AND CRYSTALS-KYBER: THE ROLE OF THE CYCLOTOMIC DISCRIMINANT

Abstract

Shor's algorithm is a threat to RSA and elliptic curve cryptography, the type of quantum computers. Leading alternatives are lattice-based protocols (standardized under the name ML-KEM), but very few security estimates for these protocols follow the number-theoretic structure of the fields they rely on. In this paper, Ring Learning with Errors (Ring-LWE) and Module-LWE in algebraic number fields are investigated. The design has three phases: mathematical formalization, an LWE Estimator based computational security analysis and testing on three Kyber parameter sets. The study provides closed form formulas |ΔK| = n for the discriminant of the power-of-two cyclotomic fields, leading to logarithms of 2048, 4608 and 10240 bits for degrees 256, 512, and 1024 respectively. Estimator results show that 128-bit and 256-bit security need lattice dimensions of 512 and 1,024 (q = 3,329, σ = 2.5). The 2n coefficient isometries of the ring create a hardness gap of about 15 bits between Module-LWE and unstructured LWE. Kyber512, Kyber768 and Kyber1024 have estimated bit values of 118, 180 and 242 respectively with a heuristic discriminant-based correction. These values are slightly lower than the generic ones (7–8 bits). In terms of key generation published benchmarks show Kyber being approximately 3 times faster than ECC and ordering of 104 times faster than RSA. A hypothetical erosion of 2 bits per year brings the margin of Kyber512 over a 100-bit threshold to around the year 2034, and Kyber768 and Kyber1024 have a margin of decades for that. The correction is heuristic, which means that the results are suggestions for the choice of parameters and a starting point for a strict subsequent investigation.