De nieuwe wiskunde van kwantumcryptografie

De originele versie van dit verhaal verscheen in Quanta Magazine .

Moeilijke problemen zijn meestal geen welkome aanblik. Maar cryptografen zijn er dol op. Dat komt doordat bepaalde moeilijke wiskundige problemen de basis vormen voor de beveiliging van moderne encryptie. Elke slimme truc om ze op te lossen, zal de meeste vormen van cryptografie de das omdoen.

Enkele jaren geleden ontdekten onderzoekers een radicaal nieuwe benadering van encryptie die deze potentiële zwakke plek mist. Deze benadering maakt gebruik van de bijzondere eigenschappen van de kwantumfysica. Maar in tegenstelling tot eerdere kwantumencryptiemethoden, die slechts voor een paar specifieke taken werken, kan de nieuwe benadering een veel breder scala aan taken uitvoeren. En het zou zelfs kunnen werken als alle problemen die aan de basis liggen van gewone "klassieke" cryptografie eenvoudig oplosbaar blijken te zijn.

Maar deze opvallende ontdekking was gebaseerd op onrealistische aannames. Het resultaat was "meer een proof of concept", aldus Fermi Ma , cryptografieonderzoeker aan het Simons Institute for the Theory of Computing in Berkeley, Californië. "Het is geen uitspraak over de echte wereld."

Nu heeft een nieuw artikel van twee cryptografen een pad naar kwantumcryptografie uitgestippeld zonder die bizarre aannames. "Dit artikel stelt dat als bepaalde andere vermoedens waar zijn, kwantumcryptografie moet bestaan", aldus Ma.

Je kunt moderne cryptografie zien als een toren met drie essentiële onderdelen. Het eerste onderdeel is de rotsbodem diep onder de toren, die bestaat uit lastige wiskundige problemen. De toren zelf is het tweede onderdeel: daar vind je specifieke cryptografische protocollen waarmee je privéberichten kunt versturen, digitale documenten kunt ondertekenen, geheim kunt stemmen en meer.

Tussendoor, om die dagelijkse toepassingen te beveiligen tegen wiskundige fundamenten, bevindt zich een fundament van bouwstenen genaamd eenrichtingsfuncties . Deze zijn verantwoordelijk voor de asymmetrie die inherent is aan elk encryptieschema. "Het is eenrichtingsverkeer omdat je berichten kunt encrypteren, maar niet decrypteren", aldus Mark Zhandry , cryptograaf bij NTT Research.

In de jaren 80 bewezen onderzoekers dat cryptografie gebaseerd op eenrichtingsfuncties de beveiliging voor veel verschillende taken zou garanderen. Maar decennia later zijn ze er nog steeds niet zeker van dat de basis sterk genoeg is om dit te ondersteunen. Het probleem is dat de basis bestaat uit speciale, moeilijke problemen – technisch bekend als NP-problemen – waarvan het bepalende kenmerk is dat het gemakkelijk is om te controleren of een kandidaat-oplossing correct is. (Het opsplitsen van een getal in zijn priemfactoren is bijvoorbeeld een NP-probleem: moeilijk uit te voeren voor grote getallen, maar gemakkelijk te controleren.)

Veel van deze problemen lijken intrinsiek moeilijk, maar computerwetenschappers hebben het nog niet kunnen bewijzen . Als iemand een ingenieus algoritme ontdekt om de moeilijkste NP-problemen snel op te lossen, zal de rotsbodem afbrokkelen en de hele toren instorten.

Helaas kun je je toren niet zomaar ergens anders heen verplaatsen. De fundering van de toren – eenrichtingsverkeer – kan alleen rusten op een fundament van NP-problemen.

Om een ​​toren te bouwen voor moeilijkere problemen, zouden cryptografen een nieuw fundament nodig hebben dat niet uit eenrichtingsfuncties bestaat. Dat leek onmogelijk tot een paar jaar geleden, toen onderzoekers zich realiseerden dat kwantumfysica kon helpen.

Het begon met een paper uit 2021 van een promovendus genaamd William Kretschmer, die de aandacht vestigde op een vreemd probleem met de eigenschappen van kwantumsystemen. Onderzoekers toonden al snel aan dat Kretschmers probleem eenrichtingsfuncties kon vervangen als basis voor een nieuwe toren van cryptografische protocollen . Het jaar daarop bewezen Kretschmer en anderen dat deze alternatieve aanpak zelfs zonder moeilijke NP-problemen kon werken. Plotseling leek het mogelijk om een ​​cryptografisch fort te bouwen dat veel steviger zou zijn.

Maar waar moest het gebouwd worden? Het kwantumprobleem dat Kretschmer als basis gebruikte, betrof hypothetische rekenmachines, orakels genaamd, die direct specifieke vragen kunnen beantwoorden. Orakels kunnen nuttige theoretische hulpmiddelen zijn, maar ze bestaan ​​niet echt. Kretschmers bewijzen waren als een blauwdruk voor het bouwen van een luchtkasteel. Was er een manier om het op aarde te brengen?

In het najaar van 2022 trok die vraag de aandacht van Dakshita Khurana , cryptograaf aan de Universiteit van Illinois in Urbana-Champaign en NTT Research. Khurana en haar promovendus Kabir Tomer begonnen met het bouwen van een nieuwe cryptografietoren. Haar eerste stap was het bouwen van een nieuwe fundering met behulp van kwantumbouwstenen in plaats van klassieke eenrichtingsfuncties. Vervolgens moest ze bewijzen dat deze nieuwe fundering een toren met andere cryptografische protocollen kon ondersteunen. Zodra ze had bewezen dat de fundering de toren kon ondersteunen, moest ze een solide basis vinden voor het geheel – een fundament van praktische problemen die nog moeilijker lijken dan de NP-problemen die in de klassieke cryptografie worden gebruikt.

Voor de eerste stap concentreerden Khurana en Tomer zich op een kwantumversie van een eenrichtingsfunctie, een zogenaamde eenrichtingstoestandsgenerator , die voldeed aan de drie eigenschappen die eenrichtingsfuncties nuttig maken. Ten eerste moet de functie snel werken, zodat je gemakkelijk een cryptografisch slot en de bijbehorende sleutel kunt genereren om het te openen voor elk bericht dat je wilt verzenden. Ten tweede moet elk slot veilig zijn, waardoor het veel moeite kost om het open te breken zonder de juiste sleutel. Ten slotte moet elk slot gemakkelijk te openen zijn met de juiste sleutel.

Het cruciale verschil lag in de aard van de sloten. Klassieke eenrichtingsfuncties genereren wiskundige sloten bestaande uit bits – de nullen en enen die informatie opslaan in een klassieke computer. Kwantum eenrichtingstoestandsgeneratoren zouden in plaats daarvan sloten genereren die bestaan ​​uit eenheden kwantuminformatie, qubits genaamd. Deze kwantumsloten zouden potentieel veilig kunnen blijven, zelfs als alle klassieke sloten gemakkelijk te kraken zijn. Khurana en Tomer hoopten met deze nieuwe kwantumfundering te beginnen en er een toren van cryptografische protocollen op te bouwen. "Dit bleek behoorlijk lastig te zijn", zei Khurana. "We zaten er vele, vele maanden vast."

In juli 2023 was Khurana bijna negen maanden zwanger en maakte ze plannen voor ouderschapsverlof. Tomer had geen inspiratie meer. "Ik ben veel pessimistischer dan Dakshita," zei hij. "Zij is altijd degene die gelooft dat het goedkomt."

Toen bereikten ze een doorbraak. De cruciale stap was het definiëren van een andere wiskundige bouwsteen die dienstdeed als een soort kelderverdieping: een structuur die de basis van eenrichtingstoestandsgeneratoren zou verbinden met een toren van cryptografische protocollen. Toen Khurana en Tomer uitzochten welke eigenschappen die bouwsteen moest hebben, ontdekten ze dat hij leek op een eenrichtingsfunctie met een verwarrende mix van kwantum- en klassieke kenmerken. Net als bij een gewone eenrichtingsfunctie waren zowel sloten als sleutels gemaakt van klassieke bits, maar de procedure voor het genereren van deze sloten en sleutels zou alleen op een quantumcomputer kunnen draaien. Nog vreemder was dat de nieuwe bouwsteen voldeed aan de eerste twee bepalende eigenschappen van eenrichtingsfuncties, maar niet aan de derde: het was gemakkelijk om sloten en sleutels te genereren, en elk slot was moeilijk te breken. Maar een sleutel kreeg het slot niet zomaar open.

Khurana en Tomer noemden deze verwarrende nieuwe bouwstenen 'eenrichtingspuzzels'. Intuïtief gezien is het moeilijk voor te stellen hoe ze nuttig zouden kunnen zijn: wat heb je aan een sleutel die je nooit kunt gebruiken? Maar de twee cryptografen lieten zien dat eenrichtingspuzzels, gecombineerd met andere kwantumtrucs, juist veel cryptografische protocollen mogelijk zouden maken. Als je sloten en sleutels kunt genereren die in principe op elkaar passen, maakt het niet uit of de ontgrendelingsprocedure enorm inefficiënt is.

"Alleen al de wetenschap dat er een algoritme bestaat dat willekeurig langzaam kan zijn, is voldoende", aldus Kretschmer, die nu onderzoeker is bij het Simons Instituut. "Dat is zeer verrassend."

Nu dat ontbrekende stukje op zijn plaats zat, voltooiden ze op 4 augustus het bewijs. Slechts enkele dagen later werd Khurana's dochter geboren.

In november was Khurana weer aan het werk en klaar om de tweede fase van haar plan uit te voeren. Zij en Tomer hadden aangetoond dat veel soorten cryptografie gebouwd konden worden op eenzijdige puzzels, en dat eenzijdige puzzels op hun beurt gebouwd konden worden op een nieuwe kwantumbasis, bestaande uit eenzijdige toestandsgeneratoren. De volgende stap in hun oorspronkelijke plan was om die kwantumbasis te verbinden met een nieuwe basis: een relatief onaantastbare reeks wiskundige problemen die nog lastiger te doorgronden zijn dan die in NP.

Maar terwijl Khurana en Tomer met die taak worstelden, besloten ze een directere aanpak te kiezen: ze lieten de eenrichtingsgeneratoren voor toestanden achterwege en verankerden in plaats daarvan eenrichtingspuzzels direct aan de wiskundige basis.

Vanuit een bepaald perspectief leek dat een vreemde keuze. Eenrichtingspuzzels waren wiskundige eigenaardigheden die Khurana en Tomer in een tussenstap in hun bewijs hadden gebruikt.

Toch hadden eenrichtingspuzzels ook voordelen. Ten eerste zijn ze weliswaar kwantum, maar de sloten en sleutels die ze genereren zijn klassiek. Khurana dacht dat dit het misschien makkelijker zou maken om ze te verbinden met een basis van klassieke wiskunde. Bovendien genereren eenrichtingspuzzels sleutels die te onhandig zijn om daadwerkelijk sloten te openen. Dat zou het makkelijker kunnen maken om ze te koppelen aan problemen die zo lastig zijn dat zelfs het controleren van oplossingen hopeloos moeilijk lijkt.

Maar welke specifieke problemen zouden werken? Khurana had een kandidaat in gedachten: het berekenen van een specifieke combinatie van de waarden in een tabel met getallen, een zogenaamde matrix. Dit probleem, bekend als het matrixpermanente probleem, is notoir moeilijk op te lossen voor grote matrices, en er is geen eenvoudige manier om te controleren of een berekening correct is. Het matrixpermanente probleem heeft ook andere speciale wiskundige eigenschappen die cryptografen aantrekkelijk vinden.

“Dit zou een prachtig probleem zijn om cryptografie op te baseren”, aldus Khurana.

Het matrixpermanente probleem sluit ook aan bij een ander probleem dat quantumcomputers gemakkelijk kunnen oplossen, maar klassieke computers schijnbaar niet . Onderzoekers werken eraan om dit computationele voordeel van quantumcomputers in een precieze theoretische zin te bewijzen. Khurana en Tomer toonden aan dat een dergelijk bewijs hen ook in staat zou stellen om veilige eenrichtingspuzzels – en daarmee de hele toren van quantumcryptografie – bovenop het permanente probleem te bouwen.

"Ze konden dit doen op basis van deze goed onderzochte aannames", zei Kretschmer. "Ik was erg blij dat te zien."

Met hun nieuwe resultaat hebben Khurana en Tomer effectief twee openstaande problemen teruggebracht tot één. Als onderzoekers het bewijs leveren dat quantumcomputers klassieke computers daadwerkelijk overtreffen bij een specifieke taak, zal dat quantumcryptografie automatisch een veel sterkere theoretische basis geven dan praktisch elke vorm van klassieke cryptografie.

Helaas zul je de nieuwe aanpak van Khurana en Tomer om geheime berichten te versturen voorlopig niet kunnen gebruiken. Ondanks recente vooruitgang is de quantumcomputertechnologie nog niet volwassen genoeg om hun ideeën in de praktijk te brengen. Ondertussen hebben andere onderzoekers methoden voor quantumcryptografie ontwikkeld die eerder gebruikt zouden kunnen worden , hoewel er meer onderzoek nodig zal zijn om vast te stellen of ze echt veilig zijn.

Kwantumcryptografie heeft al veel verrassingen opgeleverd, en onderzoekers zijn pas onlangs begonnen met het verkennen van de mogelijkheden. "We proberen gewoon dit nieuwe landschap te begrijpen dat eigenlijk altijd al bestond", aldus Zhandry.

Oorspronkelijk verhaal met toestemming overgenomen uit Quanta Magazine , een redactioneel onafhankelijke publicatie van de Simons Foundation. De missie van dit tijdschrift is om het begrip van wetenschap bij het publiek te vergroten door verslag te doen van ontwikkelingen en trends in het onderzoek naar wiskunde, natuurkunde en levenswetenschappen.