Cycles of supersingular elliptic curves for pairing-based proof systems

In de digitale wereld is het bewijzen dat je een geheim kent zonder het geheim zelf te onthullen een krachtig instrument. Dit vormt de kern van de moderne cryptografie, waar "bewijs-systemen" (proof systems) een computer in staat stellen om een gebruiker te overtuigen dat een berekening correct is uitgevoerd, zonder dat de volledige berekening opnieuw moet worden uitgevoerd. Voor deze bewijzen om in de echte wereld bruikbaar te zijn, moeten ze kort en snel te controleren zijn. Een specifiek type bewijs, bekend als een succinct non-interactief argument, is een hoeksteen van deze technologie geworden. Om deze bewijzen nog krachtiger te maken, hebben onderzoekers een manier ontwikkeld om ze op te stapelen, waardoor het ene bewijs een ander kan verifiëren, wat een keten van vertrouwen creëert die onbeperkt kan groeien. Dit proces, genaamd recursie, is de motor achter sommige van de meest geavanceerde privacy- en schalingstechnologieën die vandaag de dag in gebruik zijn. Het bouwen van deze ketens vereist echter een zeer specifieke wiskundige basis: paren elliptische curves die perfect in elkaar passen als puzzelstukjes. Jarenlang waren de enige bekende puzzelstukjes die aan deze beschrijving voldeden zeldzaam, moeilijk te vinden en beperkt in aantal, wat een flessenhals creëerde voor de technologie.

Een team van onderzoekers heeft nu een nieuwe manier ontdekt om deze essentiële curve-paren te genereren, waarmee een enorme, voorheen onbereikbare voorraad wordt ontsloten. Ze ontdekten dat ze, door gebruik te maken van een andere klasse van wiskundige objecten genaamd supersinguliere curves, een oneindige familie van deze puzzelstukje-paren kunnen construeren. In tegenstelling tot de vorige methode, die vertrouwde op een smalle set voorwaarden waardoor het vinden van nieuwe paren een kwestie van geluk en immense computationele inspanning was, werkt deze nieuwe aanpak betrouwbaar voor bijna elk gekozen getal. De onderzoekers hebben aangetoond dat ze deze nieuwe cycli kunnen bouwen en ze kunnen verbinden met andere efficiënte curves om wat zij "lollipops" noemen, te vormen. Deze structuren zorgen ervoor dat het aanvankelijke, zware werk van een bewijs plaatsvindt op een klein, snel veld, terwijl het recursieve stapelen plaatsvindt op de grotere, veilige cyclus. In een praktische zoektocht hebben ze succesvol achttien verschillende voorbeelden van deze nieuwe structuren geconstrueerd, die een flexibele en overvloedige bron bieden voor de volgende generatie veilige digitale systemen.

De reis naar deze ontdekking begon bij een beperking in de bestaande technologie. De huidige standaard voor deze recursieve bewijs-systemen rust op een specifieke arrangement van twee elliptische curves, vaak een "cyclus" genoemd. In deze arrangement komt het aantal punten op de eerste curve overeen met de grootte van het veld dat de tweede curve definieert, en vice versa. Deze delicate balans zorgt ervoor dat het bewijs naadloos van de ene curve naar de andere kan overgaan. Al meer dan een decennium is de enige bekende manier om dergelijke cycli te bouwen het gebruik van "gewone" (ordinary) curves, een methode ontwikkeld door Miyaji, Nakabayashi en Takano. Hoewel deze methode in theorie werkt, is ze in de praktijk extreem schaars. Het vinden van een nieuw paar vereist het oplossen van complexe wiskundige vergelijkingen waarbij de getallen precies goed moeten zijn. Naarmate de beveiligingseisen groeien, daalt de waarschijnlijkheid om op een geldig paar te stuiten naar bijna nul. Het is als het zoeken naar een specifiek zandkorreltje op een strand dat aan een precieze set criteria voldoet; het strand is oneindig, maar de juiste korrels zijn uiterst zeldzaam. Deze schaarste heeft ontwikkelaars gedwongen ofwel oudere, minder veilige parameters te gebruiken, ofwel het ideaal van onbegrensde recursie op te geven voor kortere, beperkte ketens.

De onderzoekers realiseerden zich dat de flessenhals niet het concept van de cyclus zelf was, maar het specifieke type curve dat werd gebruikt. Ze richtten hun aandacht op "supersinguliere" curves. Dit zijn een andere wiskundige variëteit die, hoewel minder gebruikelijk in de standaard cryptografie, unieke eigenschappen bezitten die hen ideaal maken voor deze specifieke taak. Het nadeel is dat deze curves gedefinieerd moeten worden over iets grotere wiskundige velden, wat sommige berekeningen iets zwaarder maakt. Echter, het voordeel is overweldigend: de nieuwe constructie werkt voor bijna elk gekozen getal, mits het aan een basis primality-test voldoet. Er is geen noodzaak om te zoeken naar zeldzame, gelukkige getallen. De onderzoekers toonden aan dat ze voor elk geldig getal onmiddellijk een werkend paar supersinguliere curves kunnen genereren. Dit transformeert het probleem van een schattenjacht naar een productieproces. In plaats van enkele verspreide voorbeelden te vinden, kunnen ze nu op aanvraag een oneindig aantal van deze cycli produceren.

Om te bewijzen dat dit concept in de echte wereld werkt, vertrouwde het team niet alleen op de theorie; ze bouwden een zoekmachine om concrete voorbeelden te vinden. Ze zetten zich in om wat zij "lollipops" noemen te construeren. Stel je een zuurstok voor waarbij de steel een keten van efficiënte curves is en het ronde deel aan de bovenkant de recursieve cyclus is. De steel zorgt ervoor dat het bewijs op een klein, snel veld kan beginnen, waardoor de initiële stappen van de berekening zeer snel gaan. Het ronde deel, de cyclus, zorgt ervoor dat het bewijs zonder limiet gestapeld en geverifieerd kan worden. De onderzoekers ontwikkelden een algoritme om deze structuren te vinden door een specifiek type getallenpuzzel op te lossen, bekend als een Pell-vergelijking. Ze draalden dit algoritme op krachtige computers en doorzochten miljoenen mogelijkheden. De zoektocht was succesvol. Ze vonden achttien verschillende voorbeelden van deze lollipops, variërend in grootte om beveiligingsniveaus van 80 bits tot 128 bits en verder te ondersteunen. Een van hun voorbeelden, een grote instantie met een 956-bits veld, duwde zelfs de grenzen van praktische interesse op, wat aantoonde dat deze structuren kunnen schalen om aan toekomstige beveiligingseisen te voldoen.

De betekenis van deze bevindingen ligt in de flexibiliteit die ze bieden aan systeemontwerpers. Met de oude methode werden ontwerpers gedwongen een specifieke, vaak inefficiënte set parameters te gebruiken omdat er geen andere opties bestonden. Als ze hogere beveiliging wilden, moesten ze een lagere prestatie of kortere recursielimieten accepteren. Met de nieuwe supersinguliere cycli kunnen ontwerpers parameters kiezen die geoptimaliseerd zijn voor snelheid, zoals velden waar de wiskunde bijzonder snel te berekenen is, of velden die specifieke eigenschappen hebben die nuttig zijn voor hardwareversnelling. Ze kunnen ook ervoor kiezen om deze cycli te verbinden met andere typen curves die niet "pairing-friendly" zijn, maar extreem efficiënt zijn voor de initiële stappen van een bewijs. Deze mogelijkheid om componenten te mengen en te matchen, om zo een op maat gemaakte "lollipop" voor een specifieke toepassing te creëren, was onmogelijk met de vorige technologie. De onderzoekers merkten op dat hoewel de nieuwe curves in sommige delen iets groter zijn, het vermogen om de rest van het systeem te optimaliseren en de enorme overvloed aan beschikbare cycli de afweging de moeite waard maakt.

Het artikel concludeert door te benadrukken dat dit een constructieve doorbraak is. De onderzoekers hebben niet alleen bewezen dat deze cycli bestaan, maar hebben ook de instrumenten geleverd om ze te bouwen en een catalogus van achttien werkende voorbeelden gepresenteerd. Ze erkennen dat de volgende stap is om deze nieuwe cycli in werkelijke software te implementeren om de exacte prestatiewinsten te meten, aangezien de theoretische voordelen moeten worden afgewogen tegen de praktische kosten van de grotere velden. Echter, de deur staat nu open. De schaarste die voorheen de groei van recursieve bewijs-systemen beperkte, is weggenomen. Door over te stappen van gewone curves naar supersinguliere curves, hebben de onderzoekers een nieuwe, oneindige voorraad van de wiskundige bouwstenen geleverd die nodig zijn om de digitale toekomst te beveiligen, wat bewijs-systemen mogelijk maakt die niet alleen veiliger zijn, maar ook beter aanpasbaar aan de diverse behoeften van de echte wereld.