Kortste-vectorprobleem
Stel je een oneindig, regelmatig rooster van punten voor in de ruimte, zoals de kruispunten van millimeterpapier maar dan in tientallen of honderden dimensies tegelijk. Het kortste-vectorprobleem, in het Engels "Shortest Vector Problem" of SVP, vraagt: wat is het dichtstbijzijnde roosterpunt bij de oorsprong, ofwel welke vector in dat rooster heeft de kleinste lengte? In twee of drie dimensies is dat met het blote oog te zien, maar in hoge dimensies wordt het antwoord vinden verrassend lastig, zelfs voor de snelste computers.
Dit klinkt als een abstract wiskundig raadsel, en dat is het ook, maar het is tegelijk de basis onder een van de belangrijkste vormen van cryptografie die de komende decennia onze data moet beschermen. Omdat niemand een snelle manier kent om het kortste-vectorprobleem in hoge dimensies op te lossen, kun je het gebruiken als een soort digitaal slot: iemand die het rooster en een lastige beschrijving ervan kent, kan het slot makkelijk openen, maar een buitenstaander die alleen een verwarrende beschrijving ziet, staat voor een vrijwel onmogelijke zoekopdracht. Dit principe heet roostercryptografie (lattice-based cryptography) en het wordt gezien als een van de meest kansrijke kandidaten om computers te beschermen tegen toekomstige kwantumcomputers.
Wat is het precies?
Een rooster (lattice) in de wiskundige zin is een verzameling punten die ontstaat door steeds gehele veelvouden van een aantal basisvectoren bij elkaar op te tellen. Denk aan twee pijlen die samen een rooster van punten opspannen op een plat vlak; in de cryptografie werkt men met tientallen tot duizenden van zulke basisvectoren tegelijk, in een ruimte met evenveel dimensies.
Een rooster kan op oneindig veel verschillende manieren beschreven worden met verschillende sets basisvectoren, die allemaal exact hetzelfde rooster van punten opleveren. Sommige beschrijvingen zijn "netjes": de basisvectoren staan ongeveer loodrecht op elkaar en zijn kort, waardoor je meteen kunt zien welk roosterpunt het dichtst bij de oorsprong ligt. Andere beschrijvingen zijn "rommelig": lange, scheve vectoren die wiskundig gezien hetzelfde rooster vormen, maar waarbij het totaal onduidelijk is welke combinatie de kortste vector oplevert.
Het kortste-vectorprobleem vraagt om, gegeven zo'n rommelige beschrijving, toch de kortste niet-nulvector van het rooster te vinden. Voor lage dimensies bestaan er goede algoritmen, met als bekendste het LLL-algoritme uit 1982 (vernoemd naar de wiskundigen Lenstra, Lenstra en Lovász), dat een rommelige basis omzet in een redelijk nette. Maar naarmate de dimensie oploopt, groeit de rekentijd van de beste bekende methodes exponentieel: elke extra dimensie maakt het probleem substantieel moeilijker, en boven een paar honderd dimensies wordt exacte oplossing praktisch onhaalbaar met huidige computers.
Cryptografen gebruiken meestal niet het exacte probleem, maar een verwante, iets soepelere versie: het benaderde kortste-vectorprobleem, waarbij je niet de precies kortste vector hoeft te vinden, maar een die hooguit een bepaalde factor langer is. Ook deze benaderde versie blijft in hoge dimensies rekenkundig zeer zwaar, en juist die eigenschap maakt hem bruikbaar als veiligheidsfundament.
Wat wil men ermee bereiken?
De directe drijfveer is dreigende kwantumcomputers. Veel van de cryptografie die nu het internet beveiligt, zoals RSA en elliptische-krommecryptografie, steunt op problemen (grote getallen ontbinden in priemfactoren, of het discrete-logaritmeprobleem) die in theorie snel op te lossen zijn met een voldoende krachtige kwantumcomputer, dankzij het algoritme dat Peter Shor in 1994 publiceerde. Zulke computers bestaan vandaag nog niet in bruikbare vorm, maar omdat versleuteld verkeer soms jarenlang wordt opgeslagen en later alsnog ontsleuteld kan worden ("harvest now, decrypt later"), willen overheden, banken en techbedrijven nu al overstappen op alternatieven.
Het kortste-vectorprobleem, en de nauw verwante "Learning With Errors"-problemen, gelden als bestand tegen zowel klassieke als kwantumcomputers, voor zover bekend. Er is geen kwantumalgoritme bekend dat roosterproblemen in hoge dimensies snel oplost, in tegenstelling tot factorisatie en discrete logaritmen. Dat maakt roostercryptografie een van de hoofdkandidaten voor "post-kwantumcryptografie": nieuwe standaarden die nu al worden ingevoerd, zodat systemen klaar zijn tegen de tijd dat kwantumcomputers een echte dreiging vormen.
Een tweede, meer theoretische reden is dat roosterproblemen een ongewoon sterke veiligheidsgarantie bieden. De Hongaarse wiskundige Miklós Ajtai liet in 1996 zien dat het gemiddelde geval van bepaalde roosterproblemen minstens zo moeilijk is als het allerlastigste geval ervan. Dat is zeldzaam in cryptografie: bij veel andere systemen kan een sleutel toevallig "zwak" uitvallen, terwijl bij roostercryptografie de veiligheid theoretisch is terug te voeren op de moeilijkste varianten van het probleem, wat vertrouwen geeft dat willekeurig gekozen sleutels niet stiekem makkelijk te kraken zijn.
Voorbeelden uit de praktijk
Het oudste praktische systeem is NTRU, voorgesteld in 1996 door de Amerikaanse wiskundigen Jeffrey Hoffstein, Jill Pipher en Joseph Silverman. NTRU gebruikt een speciale, compacte vorm van roosters en wordt nog altijd onderzocht en soms toegepast, onder meer in enkele draadloze en embedded toepassingen.
Het belangrijkste hedendaagse voorbeeld is CRYSTALS-Kyber, een systeem voor sleuteluitwisseling dat in 2022 door het Amerikaanse standaardisatie-instituut NIST werd gekozen als winnaar van een jarenlange wedstrijd voor post-kwantumalgoritmen. Kyber is gebaseerd op het Module-Learning-With-Errors-probleem, een variant die nauw verwant is aan het kortste-vectorprobleem in gestructureerde roosters. In augustus 2024 publiceerde NIST de definitieve standaard hiervoor onder de naam FIPS 203, met de formele naam ML-KEM.
Voor digitale handtekeningen koos NIST tegelijkertijd CRYSTALS-Dilithium, eveneens roostergebaseerd en gestandaardiseerd als FIPS 204 (ML-DSA), naast het niet-roostergebaseerde SPHINCS+ (FIPS 205) als alternatief voor het geval roosterproblemen ooit onverwacht zwak blijken.
Een conservatievere, minder gestructureerde variant is FrodoKEM, ontwikkeld door een internationaal onderzoeksteam en gebaseerd op "kaal" Learning With Errors zonder de wiskundige structuur die Kyber gebruikt voor snelheid. FrodoKEM is trager en heeft grotere sleutels, maar geldt bij sommige onderzoekers als extra voorzichtige keuze, precies omdat het minder structuur bevat die in theorie aanvallen zou kunnen vergemakkelijken.
Tot slot is er de Darmstadt Lattice Challenge / SVP Challenge, een publieke benchmark die de Technische Universiteit Darmstadt sinds ongeveer 2008-2010 host. Onderzoekers wereldwijd proberen hierin het kortste-vectorprobleem op te lossen voor roosters van steeds hogere dimensie, en de resultaten worden gebruikt om in te schatten hoe groot cryptografische sleutels in de praktijk moeten zijn om veilig te blijven.
Hoe ver is de techniek?
Roostercryptografie is, in tegenstelling tot sommige andere post-kwantumkandidaten, inmiddels het stadium van internationale standaardisatie voorbij: met FIPS 203 en 204 zijn er sinds augustus 2024 officiële Amerikaanse overheidsstandaarden die bedrijven en overheden kunnen implementeren. Grote browsers en clouddiensten zijn al begonnen met het geleidelijk invoeren van Kyber-achtige sleuteluitwisseling, vaak in combinatie met bestaande klassieke cryptografie als extra vangnet ("hybride" opzet).
Toch blijft er onzekerheid. Het exacte kortste-vectorprobleem is bewezen NP-moeilijk (onder bepaalde aannames), maar de precieze moeilijkheidsgraad van de benaderde versies die in de praktijk gebruikt worden, is niet volledig uitgekristalliseerd; onderzoekers verbeteren gestaag de aanvalsalgoritmen (met name varianten van roosterreductie zoals BKZ), waardoor aanbevolen sleutelgroottes van tijd tot tijd naar boven worden bijgesteld. Ook is er, in tegenstelling tot factorisatie, minder decennia aan analysegeschiedenis: RSA is sinds de jaren zeventig grondig onderzocht, terwijl praktische roostercryptografie pas sinds de jaren negentig bestaat en breed toegepaste standaarden er sinds 2022-2024 pas zijn.
Een belangrijk obstakel is verder de implementatie zelf: net als bij oudere cryptografie zijn niet alle kwetsbaarheden wiskundig, maar praktisch. Zo bleek dat sommige vroege implementaties van roosteralgoritmen gevoelig waren voor "side-channel"-aanvallen, waarbij een aanvaller sleutelinformatie afleidt uit stroomverbruik of timing van een chip, iets dat losstaat van de onderliggende wiskundige moeilijkheid maar wel de veiligheid in de praktijk kan ondermijnen.
Wie werken eraan?
Het Amerikaanse National Institute of Standards and Technology (NIST) trekt het formele standaardisatieproces en bepaalt welke algoritmen wereldwijd als referentie gaan gelden. Aan de onderzoekskant zijn academische groepes toonaangevend, waaronder de Technische Universiteit Darmstadt in Duitsland (bekend van de Lattice Challenge en van cryptografen als Johannes Buchmann), de École Normale Supérieure in Parijs, de University of Waterloo in Canada (met onder meer de ontwikkelaars van FrodoKEM) en verschillende Israëlische en Amerikaanse universiteiten die betrokken waren bij Kyber en Dilithium, ontwikkeld binnen het bredere CRYSTALS-consortium met onderzoekers van onder meer IBM Research Zürich, de Radboud Universiteit Nijmegen en de Ruhr-Universität Bochum.
Ook grote techbedrijven investeren actief: IBM, Google, Amazon (AWS), Microsoft en Cloudflare experimenteren met of implementeren al hybride post-kwantumverbindingen in hun infrastructuur. Gespecialiseerde bedrijven zoals het Britse PQShield en het Canadese ISARA Corporation richten zich specifiek op post-kwantum-implementaties voor de industrie. In Nederland doet het Centrum Wiskunde & Informatica (CWI) in Amsterdam fundamenteel onderzoek naar roosterproblemen en cryptografische veiligheidsbewijzen, en dragen onderzoekers van de Radboud Universiteit actief bij aan internationale standaardisatietrajecten.