Succinct Arguments for QMA from Collapsing Hash Functions

In de wereld van de cryptografie bestaat er een constante spanning tussen veiligheid en efficiëntie. Aan de ene kant hebben we de behoefte om te verifiëren dat een complexe berekening correct is uitgevoerd zonder dat we de volledige berekening zelf opnieuw hoeven te doen. Dit is het domein van beknopte argumenten (succinct arguments), een methode die een verifieerder in staat stelt om een bewijs te controleren met veel minder middelen dan de tijd die het kostte om het te creëren. Decennialang is deze technologie een hoeksteen van digitaal vertrouwen geweest, wat alles mogelijk maakt van blockchain-verificatie tot beveiligde cloud computing. Er heeft echter een aanzienlijke kloof bestaan tussen de klassieke wereld van standaardcomputers en de opkomende wereld van quantumcomputers. Hoewel we weten hoe we deze efficiënte bewijzen voor klassieke problemen kunnen maken met behulp van slechts basis, ongestructureerde wiskundige hulpmiddelen, leek het doen van hetzelfde voor quantumproblemen veel zwaardere, complexere cryptografische machines vereist te hebben. De heersende overtuiging was dat het verifiëren van quantumbewijzen altijd de voor nodig zou hebben van de geavanceerde, publieke-sleutel encryptiesystemen die veel rekenintensiever en structureel complexer zijn dan de eenvoudige hulpmiddelen die worden gebruikt voor klassieke verificatie.

Dit artikel verandert dat landschap door aan te tonen dat efficiënte verificatie van quantumbewijzen mogelijk is met behulp van alleen de eenvoudigste, meest fundamentele cryptografische aannames. De onderzoekers hebben een protocol geconstrueerd waarmee een cliënt een quantumcomputatie met hoge zekerheid kan verifiëren, waarbij uitsluitend wordt vertrouwd op het bestaan van "instortende hashfuncties" (collapsing hash functions). Dit zijn de quantum-veilige versies van een basisinstrument dat wordt gebruikt om de integriteit van gegevens te waarborgen, en ze vertegenwoordigen het zwakst mogelijke niveau van cryptografische veiligheid die vereist is voor deze taak. Door te bewijzen dat een dergelijk systeem gebouwd kan worden zonder de zware machine van publieke-sleutel encryptie nodig te hebben, laten de auteurs zien dat het vermogen om quantumcomputaties te verifiëren in een veel eenvoudigere, meer toegankelijke laag van de cryptografie leeft dan voorheen gedacht. Deze prestatie overbrugt een kritieke kloof en suggereert dat de instrumenten die nodig zijn om de quantumtoekomst te beveiligen, al binnen handbereik liggen, geworteld in dezelfde basisprincipes die onze huidige digitale wereld beveiligen.

De kern van deze doorbraak ligt in een nieuwe methode voor het genereren van een specif kind type quantumcorrelatie bekend als een "claw state". Om de betekenis te begrijpen, stel je een scenario voor waarin een krachtige server wil bewijzen dat hij een complexe berekening heeft uitgevoerd, maar een zwakkere cliënt een deel van het werk wil controleren zonder de berekening zelf te doen. De cliënt moet een gedeelde, geheime verbinding met de server tot stand brengen die bewijst dat de server de regels volgt, zonder de geheime informatie zelf te onthullen. In eerdere pogingen vereiste het creëren van deze verbindingen dat de cliënt een enorme hoeveelheid quantumwerk verrichtte of vertrouwde op complexe publieke-sleutel systemen. De auteurs realiseerden zich dat de cliënt niet volledig klassiek hoeft te zijn; de cliënt kan een kleine, vaste hoeveelheid quantumoperaties uitvoeren en toch het doel bereiken. Dit inzicht stelde hen in staat om een protocol te ontwerpen waarbij de cliënt vooraf een reeks zorgvuldig voorbereide quantumberichten maakt, nog voordat er enige interactie begint. De server verwerkt deze berichten vervolgens om duizenden van deze geheime "claw"-verbindingen te generen, terwijl de cliënt slechts een minimale hoeveelheid quantumwerk verricht.

Het protocol werkt door de cliënt tijdens elke ronde van interactie een superpositie van vele mogelijkheden tegelijk te laten verzenden. De server, die gebruikmaakt van enkel klassieke communicatie en zijn eigen rekenkracht, is in staat om deze superpositie te "laten instorten" in een set specifieke, geverifieerde quantumtoestanden. Het slimme deel van het ontwerp is dat de server een enorme hoeveelheid van deze toestanden kan genereren, maar niet de specifieke geheime labels die ermee geassocieerd zijn kan achterhalen. Als de server probeert de labels te raden, is het protocol zo ontworpen dat de kans op een correcte gok drastisch afneemt. Om deze veiligheid robuust te maken, voeren de onderzoekers dit proces meerdere keren achter elkaar uit, waarbij ze opeenvolgende quantumberichten verzenden. Ze gebruiken vervolgens een techniek om de resultaten van deze afzonderlijke runs aan elkaar te "lijmen", waardoor een enkele, zeer veilige quantumtoestand ontstaat. Dit amplificatieproces zorgt ervoor dat zelfs als de server in één instantie een kleine kans heeft om af te wijken, de kans op afwijking over alle instanties heen verwaarloosbaar klein wordt, wat het systeem effectief veilig maakt tegen elke realistische aanval.

Deze nieuwe methode voor het genereren van quantumcorrelaties dient als de motor voor een groter systeem genaamd "blinde delegatie" (blind delegation). In deze opstelling kan een cliënt een complexe quantumcomputatie delegeren aan een server zonder dat de server leert wat de berekening is of hoe de invoergegevens eruitzien. De cliënt voorziet de server van de noodzakelijke quantumbronnen, en de server voert de berekening uit en geeft een resultaat terug dat de cliënt kan verifiëren. Omdat het nieuwe protocol zo efficiënt is en minimale quantumbronnen van de cliënt vereist, past het perfect in een raamwerk dat de communicatie tussen de twee partijen comprimeert. Door deze efficiënte delegatiemethode te combineren met een compiler die de hoeveelheid uitgewisselde gegevens verkleint, creëerden de onderzoekers een compleet systeem voor beknopte argumenten voor quantumproblemen. Het uiteindelijke resultaat is een protocol waarbij de totale hoeveelheid verzonden en ontvangen data klein is, en de tijd die de cliënt nodig heeft om het resultaat te verifiëren afhangt van de omvang van de probleemstelling, en niet van hoe lang de berekening duurde om uit te voeren. Het is echter belangrijk op te merken dat dit protocol vereist dat de verifieerder quantum is en quantumcommunicatie gebruikt, wat een kernbeperking is van de huidige aanpak.

De betekenis van dit werk strekt zich uit voorbij de technische details van het protocol. Het lost een langlopende vraag op over de fundamentele vereisten voor quantumverificatie. Jarenlang was het onduidelijk of het verifiëren van quantumbewijzen de zware, complexe instrumenten van publieke-sleutel cryptografie vereiste, of dat ze gebouwd konden worden met de lichtere, eenvoudigere instrumenten die worden gebruikt voor klassieke verificatie. De auteurs hebben bewezen dat dat laatste waar is. Ze hebben aangetoond dat het bestaan van deze efficiënte quantumverificatiesystemen gegarandeerd wordt door dezelfde basisaannames die de veiligheid van het internet vandaag de dag ondersteunen. Dit plaatst het vermogen om quantumcomputaties te verifiëren in een categorie van de cryptografie die bekend staat als "Minicrypt", een rijk dat wordt gedefinieerd door eenvoudige, ongestructureerde aannames, in plaats van het complexere "Cryptomania" rijk dat voorheen noodzakelijk werd geacht. Deze bevinding suggereert dat de infrastructuur voor een veilige quantumtoekomst eenvoudiger en robuuster is dan verwacht, en rust op dezelfde fundamentele bouwstenen die onze digitale wereld al decennia lang beschermen.