Sikkerhedsbeviser og reduktioner i gitterskemer

Et sikkerhedsbevis for et kryptografisk skema er et formelt matematisk argument, der viser, at det at bryde skemaet medfører løsning af et underliggende vanskeligt problem. Beviset garanterer ikke absolut sikkerhed; det viser, at enhver effektiv modstander mod skemaet kan omdannes til en effektiv løser af det vanskelige problem. Hvis det vanskelige problem ikke kan løses effektivt, er skemaet sikkert.

Regevs banebrydende bevis fra 2005 viser, at en algoritme i polynomiel tid, der løser beslutningsversionen af LWE, kan bruges til at løse GapSVP (Gap Shortest Vector Problem) på gittere i n dimensioner. Reduktionen er kvantemekanisk: Den bruger en kvantemekanisk udtagningsprocedure til at omdanne en LWE-løser til en gitterløser. Det betyder, at LWE under kvanteberegning er mindst lige så vanskeligt som gitterproblemer i værste fald.

Regevs reduktion er ikke stram: De polynomielle faktorer i reduktionen betyder, at det sikkerhedsniveau, som beviset garanterer, er noget svagere end de bedste kendte angreb antyder. Ved valg af praktiske parametre bruger kryptografer den konkrete sikkerhed, der følger af de bedste kendte angreb (via gitterestimatoren), frem for den teoretiske reduktionsgrænse, fordi reduktionen er konservativ.

Et LWE-baseret krypteringsskema bevises IND-CPA-sikkert (umuligt at skelne under angreb med valgt klartekst) via et hybridargument. Beviset viser, at en IND-CPA-skelner medfører en LWE-skelner. I det første hybridtrin erstattes den ægte chiffertekst med en ensartet tilfældig streng; umuligheden af at skelne følger af LWE-antagelsen. Dette giver et klart sikkerhedsbevis for grundlæggende gitterbaseret kryptering.

IND-CPA-sikkerhed er ikke tilstrækkelig for nøgleindkapslingsmekanismer, der bruges i TLS: De skal have IND-CCA2-sikkerhed (sikkerhed mod angreb med valgt chiffertekst). Fujisaki-Okamoto-transformationen (FO) omdanner ethvert IND-CPA-skema til en IND-CCA2-KEM i modellen med tilfældige orakler (ROM). ML-KEM anvender en variant af FO-transformationen på den underliggende Module-LWE-kryptering og giver dermed den CCA2-sikkerhed, der kræves til udrulning i den virkelige verden.

Modellen med tilfældige orakler (ROM) modellerer hashfunktioner som ægte tilfældige funktioner. Mange sikkerhedsbeviser, herunder beviserne for FO-transformationen, kræver ROM. I praksis er hashfunktioner som SHA-3 ikke ægte tilfældige orakler, så ROM-beviser garanterer ikke sikkerhed i standardmodellen. ROM-beviser accepteres dog bredt i kryptografiske fagmiljøer som stærk evidens for sikkerhed.

Et bevis i standardmodellen idealiserer ikke hashfunktioner og er derfor strengt stærkere end et ROM-bevis. De fleste praktiske gitterskemaer bruger ROM-beviser, fordi CCA2-beviser i standardmodellen for gitterbaserede KEM'er er langt mere komplekse og giver dårligere konkrete parametre. NIST accepterede ROM-baserede beviser for ML-KEM og vurderede dem som tilstrækkelige for de tilsigtede sikkerhedsniveauer.

Sikkerhedsbeviset for ML-KEM foregår i to trin. Først vises det, at den underliggende Module-LWE-kryptering er IND-CPA-sikker under M-LWE-antagelsen. Derefter opgraderer Fujisaki-Okamoto-transformationen (nærmere bestemt T- og U-transformationerne, der bruges i Kyber) dette til IND-CCA2 i den kvantemekaniske ROM (QROM), som håndterer modstandere, der sender forespørgsler til det tilfældige orakel i superposition.

Gitterestimatoren af Albrecht, Player og Scott er standardværktøjet til at beregne den konkrete sikkerhed for LWE-baserede skemaer. Den modellerer omkostningen ved de bedste kendte gitterangreb (BKZ med silning eller opregning) og returnerer den estimerede bitsikkerhed for givne parametre (n, q, sigma). Værktøjet opdateres jævnligt, efterhånden som nye algoritmer og omkostningsmodeller for hardware offentliggøres.

Block Korkine-Zolotarev-algoritmen (BKZ) er den bedste praktiske gitterreduktionsalgoritme. BKZ med blokstørrelsen beta finder korte vektorer med en kompleksitet på omtrent 2^{0.292*beta} gate-operationer ved brug af de bedste silningsalgoritmer. For ML-KEM-768 er den estimerede klassiske sikkerhed omkring 180 bit og kvantesikkerheden omkring 164 bit, hvilket er et godt stykke over målet på 192 bit.

Asymptotiske sikkerhedsbeviser viser, at et skema er sikkert for tilstrækkeligt store parametre, men angiver ikke, hvad "tilstrækkeligt store" betyder i praksis. Analyse af konkret sikkerhed udfylder dette hul ved at estimere den faktiske omkostning ved det bedste angreb for de valgte parametre. Postkvantestandardisering bygger i høj grad på analyse af konkret sikkerhed, hvor parametre vælges, så de modstår angreb på forventet kvantehardware over en tidshorisont på 30 år.

Sikkerhedsbeviser for gitterskemaer reducerer skemaets sikkerhed til sværhedsgraden af LWE eller SVP. Regevs reduktion garanterer, at LWE er mindst lige så svært som gitterproblemer i værste fald. Fujisaki-Okamoto-transformationen opgraderer IND-CPA til IND-CCA2 i ROM. Den konkrete sikkerhed evalueres med gitterestimatoren ved hjælp af kompleksitetsmodeller for BKZ. Gab i reduktionernes stramhed betyder, at praktiske parametre baseres på estimater af angrebsomkostninger frem for alene reduktionsgrænser.