Ring-LWE og modulgitre

Standard-LWE kræver store matrix-vektor-produkter, hvilket fører til store nøglestørrelser. Ring-LWE, som blev introduceret af Lyubashevsky, Peikert og Regev i 2010, erstatter vektorer og matricer med polynomier i en ring R_q = Z_q[X]/(f(X)). Denne strukturerede tilgang giver langt mere kompakte nøgler og hurtigere aritmetik, hvilket gør Ring-LWE til det praktiske grundlag for gitterkryptografi i den virkelige verden.

Polynomiet f(X), der bruges i Ring-LWE, er typisk f(X) = X^n + 1, hvor n er en potens af 2. Dette er det 2n-te cyklotomiske polynomium. Det vælges, fordi det er irreducibelt over Z, sikrer, at ringen R_q har gode algebraiske egenskaber, og muliggør den talteoretiske transformation (NTT) til effektiv multiplikation. Cyklotomiske ringe er grundigt undersøgt og anses for sikre.

I Ring-LWE er hemmeligheden s et polynomium i R_q, og prøverne har formen (a, b = a*s + e), hvor a er et ensartet tilfældigt ringelement, og e er et lille fejlpolynomium. Angriberen ser mange sådanne prøver og skal genskabe s eller skelne dem fra ensartede tilfældige prøver. Sværhedsgraden bygger på Ring-LWE-antagelsen, som har en reduktion fra problemer i værst tænkelige tilfælde på ideelle gittere.

Ring-LWE er sværere for en angriber, men har også en lidt anderledes sikkerhedsreduktion end almindelig LWE. Reduktionen kommer fra problemer i værst tænkelige tilfælde på ideelle gittere (ideal-SVP), ikke vilkårlige gittere. Den ekstra struktur i ideelle gittere kan i princippet gøre dem lettere at angribe end generelle gittere, og dette er et aktivt forskningsområde. Der kendes ingen praktiske angreb, der udnytter denne struktur.

Module-LWE (M-LWE) generaliserer både LWE og Ring-LWE ved at arbejde med en k x k-matrix af ringelementer i stedet for et enkelt ringelement eller en stor matrix af heltal. Når k = 1, reduceres det til Ring-LWE; når k vokser, nærmer det sig standard-LWE. Denne justerbare parameter k gør det muligt at afveje tilliden til sikkerheden mod ydeevnen.

CRYSTALS-Kyber (nu ML-KEM, FIPS 203) er baseret på Module-LWE med en rang-k-matrix over R_q. Parameteren k styrer sikkerhedsniveauet direkte: k=2 sigter mod 128-bit sikkerhed (ML-KEM-512), k=3 sigter mod 192-bit (ML-KEM-768), og k=4 sigter mod 256-bit (ML-KEM-1024). Modulstrukturen gør det muligt at bruge én kodebase med sikkerhed, der skaleres ved at ændre k.

Multiplikation af polynomier i R_q = Z_q[X]/(X^n + 1) er flaskehalsen for ydeevnen. Den talteoretiske transformation (NTT) er en diskret Fourier-transformation over Z_q, der omdanner polynomier til evalueringsform, hvor multiplikation bliver punktvis. Når q vælges, så NTT kan anvendes, tager multiplikation af polynomier O(n log n) tid i stedet for O(n^2), hvilket er en afgørende optimering i ML-KEM og ML-DSA.

NTT kræver, at q er et primtal med q = 1 mod 2n, hvilket sikrer, at Z_q indeholder en primitiv 2n-te enhedsrod. For ML-KEM med n = 256 opfylder q = 3329 dette krav. NTT over Z_3329 er ekstremt hurtig på moderne hardware med SIMD-instruktioner, hvilket muliggør tusindvis af ML-KEM-operationer i sekundet på almindelige CPU'er.

Ring-LWE og Module-LWE reducerer nøglestørrelserne markant sammenlignet med standard-LWE. En offentlig standard-LWE-nøgle til 128-bit sikkerhed kan være 1 MB; Ring-LWE reducerer dette til omkring 800 byte, og Module-LWE (ML-KEM-768) opnår en offentlig nøgle på 1184 byte med 192-bit postkvantesikkerhed. Denne kompakthed gør gitterskemaer praktiske til TLS og indlejrede systemer.

Nogle kryptografer er bekymrede for, at den ekstra algebraiske struktur i cyklotomiske ringe kan muliggøre angreb, som ikke er relevante for almindelig LWE. I 2024 offentliggjorde Elias Rokicki og kolleger en analyse af det 2n-te cyklotomiske polynomium. De fandt ingen praktiske udnyttelser, men fremhævede betydningen af fortsat granskning. NIST's PQC-proces tog denne risiko i betragtning og valgte delvist Module-LWE for at mindske afhængigheden af en enkelt ringstruktur.

Ud over Kyber ligger Ring-LWE til grund for CRYSTALS-Dilithium (ML-DSA), det NIST-standardiserede signaturskema. SEAL-biblioteket fra Microsoft muliggør homomorf kryptering via Ring-LWE. Googles Tink-kryptografibibliotek indeholder understøttelse af ML-KEM. Ring-LWE er på bemærkelsesværdigt kort tid gået fra teoretisk konstruktion til produktionsudrulning, drevet af NIST's standardiseringsproces.

Ring-LWE flytter LWE ind i polynomiumringen R_q = Z_q[X]/(X^n+1), hvilket markant reducerer nøglestørrelserne og muliggør hurtig NTT-baseret aritmetik. Module-LWE generaliserer dette med en rang-k-struktur, som danner grundlag for ML-KEM (FIPS 203) og ML-DSA (FIPS 204). Det NTT-venlige primtal q = 3329 muliggør en effektiv implementering. Sikkerheden bygger på sværhedsgraden af problemer på ideal- og modulgitre.