Amplifying Randomized Encodings & Applications

In het uitgestrekte landschap van de moderne cryptografie bestaat er een fundamentele spanning tussen veiligheid en efficiëntie. We willen systemen die ongelooflijk moeilijk te breken zijn, maar ook eenvoudig genoeg om op alledaagse apparaten te draaien. Om dit te bereiken, vertrouwen cryptografen vaak op "eenrichtingsfuncties", wiskundige operaties die gemakkelijk uitvoerbaar zijn in de ene richting, maar bijna onmogelijk om te keren zonder een geheime sleutel. Het bestaan van deze functies is het fundament van digitale privacy, maar decennialang hebben wiskundigen gestreden om te bewijzen dat zij bestaan op basis van de moeilijkst mogelijke problemen in de informatica. In plaats van te vertrouwen op specifieke, potentieel kwetsbare aannames, hebben onderzoekers lang geprobeerd aan te tonen dat eenrichtingsfuncties moeten bestaan simpelweg omdat bepaalde brede klassen van problemen inherent moeilijk op te lossen zijn. Onder deze moeilijke klassen behoren problemen met betrekking tot "zero-knowledge proofs" (bewijzen met nul kennis), een methode waarbij één partij een andere partij kan overtuigen dat zij een geheim kent zonder enige details over dat geheim te onthullen. De vraag is gebleven: als deze zero-knowledge problemen moeilijk op te lossen zijn in het slechtste scenario (worst-case), garandeert dat dan het bestaan van de eenrichtingsfuncties die nodig zijn voor veilige encryptie?

Een team van onderzoekers heeft nu een belangrijke stap gezet naar het beantwoorden van deze vraag door een nieuwe manier te ontwikkelen om de betrouwbaarheid van "gerandomiseerde coderingen" te versterken. Stel je een gerandomiseerde codering voor als een manier om een complex probleem te vertalen naar een eenvoudigere, gehusselde versie. Het doel is om een vertaling te creëren die niets over het oorspronkelijke probleem onthult behalve het uiteindelijke antwoord, terwijl deze veel gemakkelijker te berekenen is dan het origineel. De onderzoekers concentreerden zich op een specifiek type van deze vertalingen waarbij de veiligheidsgarantie alleen geldt voor "ja"-antwoorden, een scenario dat bekend staat als een eenzijdige codering (one-sided encoding). Zij ontdekten dat zelfs als deze coderingen aanvankelijk imperfect zijn — wat betekent dat ze een kleine hoeveelheid informatie kunnen lekken of af en toe een foutief antwoord kunnen geven — ze systematisch verbeterd kunnen worden. Door een nieuwe techniek toe te passen die gebaseerd is op het concept van "lossy reducties", die meet hoeveel informatie wordt weggegooid tijdens een transformatie, bewees het team dat deze gebrekkige coderingen kunnen worden versterkt totdat de fouten en informatielekken verwaarloosbaar klein worden, effectief nihil.

Dit versterkingsproces is de sleutel tot het ontsluiten van diepere verbindingen in de informatica. De onderzoekers lieten zien dat als een probleem met zelfs een bescheiden niveau van privacy en correctheid gecodeerd kan worden, het getransformeerd kan worden naar een versie die vrijwel perfect is. Ze pasten deze bevinding toe op de klasse van problemen die bekend staat als NISZK, die gaat over non-interactieve zero-knowledge bewijzen. Jarenlang was het een open vraag of de zero-knowledge eigenschap van deze bewijzen versterkt kon worden van een zwakke, invers-polynomiale garantie naar een sterke, verwaarloosbare garantie. Het team bewees dat dit kan, waarmee zij een probleem oplosten dat sinds de late jaren 1990 onbeantwoord was gebleven. Dit betekent dat elk probleem met een zwak zero-knowledge bewijs kan worden omgezet in een probleem met een vrijwel perfecte zero-knowledge garantie, mits het onderliggende probleem moeilijk genoeg is.

De implicaties van dit werk strekken zich rechtstreeks uit naar het bestaan van eenrichtingsfuncties. De onderzoekers demonstreerden dat als de worst-case versies van deze zero-knowledge problemen inderdaad moeilijk op te lossen zijn, eenrichtingsfuncties moeten bestaan, mits een specifieke procedure voor foutverwijdering bij eenzijdige coderingen kan worden vastgesteld. Ze bereikten dit door aan te tonen dat het vermogen om fouten uit eenzijdige coderingen te verwijderen voldoende is om de kloof te overbruggen tussen de moeilijkheid van deze specifieke problemen en de creatie van veilige cryptografische hulpmiddelen. Hoewel het artikel vaststelt dat deze foutverwijdering voldoende zou zijn, laat het expliciet de constructie van een dergelijk algoritme voor foutverwijdering als een open vraag voor toekomstig werk. Bovendien verkenden ze de kwantumwereld en toonden aan dat vergelijkbare principes gelden voor kwantumcoderingen, wat op zijn beurt de existentie van "one-way state generators" impliceert, een kwantumequivalent van eenrichtingsfuncties. Dit suggereert dat de fundamentele moeilijkheid van deze problemen robuust genoeg is om zowel klassieke als kwantumcryptografie te ondersteunen.

De studie behandelde ook de aard van "indistinguishability obfuscation" (ononderscheidbaarheids-obfuscatie), een krachtig cryptografisch hulpmiddel dat de interne werking van een computerprogramma verbergt terwijl de functie behouden blijft. Vorig onderzoek had aangetoond dat obfuscatie alleen eenrichtingsfuncties impliceert onder zeer strikte voorwaarden waarbij het programma ofwel perfect verborgen is, ofwel een zeer laag foutpercentage heeft. Het nieuwe werk bewijst dat zelfs als de obfuscatie zwak en imperfect is — waarbij een aanzienlijke hoeveelheid informatie lekt en frequente fouten maakt — dit nog steeds de existentie van eenrichtingsfuncties impliceert, zolang een belangrijke theoretische structuur in de informatica, de Polynomial Hierarchy, niet instort. Deze bevinding verbreedt de voorwaarden waaronder we zeker kunnen zijn dat veilige cryptografie mogelijk is aanzienlijk, wat suggereiert dat de drempel om het te bouwen lager en robuuster is dan voorheen gedacht.

Door deze verbindingen te leggen, hebben de onderzoekers een helderder kaart van de theoretische fundamenten van de cryptografie geschetst. Ze toonden aan dat de moeilijkheid van het oplossen van bepaalde brede klassen van problemen niet slechts een abstracte wiskundige curiositeit is, maar een directe bron van de veiligheid die nodig is voor onze digitale wereld. Hun werk bevestigt dat als we kunnen vertrouwen op het feit dat deze complexe problemen moeilijk zijn in de worst-case scenario's, en als de open vraag van foutverwijdering voor eenzijdige coderingen wordt opgelost, we kunnen rekenen op het bestaan van de eenrichtingsfuncties die onze gegevens veilig houden. De resultaten suggereren niet alleen een mogelijkheid; ze bieden een rigoureus bewijs dat de weg van moeilijke problemen naar veilige encryptie openligt, onder de voorwaarde dat de succesvolle verfijning van coderingstechnieken om fouten te elimineren. Dit brengt de theoretische gemeenschap dichter bij een definitief begrip van waarom cryptografie werkt en wat er werkelijk voor nodig is om het te bouwen.