Cycles of supersingular elliptic curves for pairing-based proof systems

Nel mondo digitale, dimostrare di conoscere un segreto senza rivelare il segreto stesso è uno strumento potente. Questo è il cuore della crittografia moderna, dove i "sistemi di prova" permettono a un computer di convincere un utente che un calcolo è stato eseguito correttamente, senza dover rieseguire l'intero calcolo. Affinché queste prove siano utili nel mondo reale, devono essere brevi e veloci da verificare. Un tipo specifico di prova, noto come argomento non interattivo succinto, è diventato una pietra angolare di questa tecnologia. Per rendere queste prove ancora più potenti, i ricercatori hanno sviluppato un modo per impilarle, permettendo a una prova di verificarne un'altra, creando una catena di fiducia che può crescere indefinitamente. Questo processo, chiamato ricorsione, è il motore dietro alcune delle tecnologie di privacy e scalabilità più avanzate in uso oggi. Tuttavia, costruire queste catene richiede un tipo molto specifico di fondamento matematico: coppie di curve ellittiche che si incastrano perfettamente come pezzi di un puzzle. Per anni, gli unici pezzi noti che si adattavano a questa descrizione erano rari, difficili da trovare e limitati nel numero, creando un collo di bottiglia per la tecnologia.

Un team di ricercatori ha ora scoperto un nuovo modo per generare queste essenziali coppie di curve, sbloccando una vasta fornitura precedentemente inaccessibile. Hanno scoperto che, utilizzando una classe diversa di oggetti matematici chiamati curve supersingolari, possono costruire una famiglia infinita di queste coppie di pezzi di puzzle. A differenza del metodo precedente, che si affidava a un insieme ristretto di condizioni che rendeva la ricerca di nuove coppie una questione di fortuna e di immenso sforzo computazionale, questo nuovo approccio funziona in modo affidabile per quasi ogni numero scelto. I ricercatori hanno dimostrato di poter costruire questi nuovi cicli e di connetterli ad altre curve efficienti per formare ciò che chiamano "lollipops" (lecca-lecca). Queste strutture permettono che il lavoro pesante iniziale di una prova avvenga su un campo piccolo e veloce, mentre la l'impilamento ricorsivo avviene sul ciclo più grande e sicuro. In una ricerca pratica, hanno costruito con successo diciotto esempi distinti di queste nuove strutture, offrendo una risorsa flessibile e abbondante per la prossima generazione di sistemi digitali sicuri.

Il viaggio verso questa scoperta è iniziato con un limite della tecnologia esistente. Lo standard attuale per questi sistemi di prova ricorsiva si basa su una specifica disposizione di due curve ellittiche, spesso chiamate ciclo. In questa disposizione, il numero di punti sulla prima curva corrisponde alla dimensione del campo che definisce la seconda, e viceversa. Questo delicato equilibrio permette alla prova di passare da una curva all'altra senza problemi. Per oltre un decennio, l'unico modo noto per costruire tali cicli ha utilizzato curve "ordinarie", un metodo sviluppato da Miyaji, Nakabayashi e Takano. Sebbene questo metodo funzioni in teoria, in pratica è incredibilmente rado. Trovare una nuova coppia richiede la risoluzione di equazioni matematiche complesse dove i numeri devono essere esattamente giusti. Man mano che i requisiti di sicurezza crescono, la probabilità di imbattersi in una coppia valida scende vicino allo zero. È come cercare un granello di sabbia specifico su una spiaggia che soddisfi un preciso insieme di criteri; la spiaggia è infinita, ma i granelli giusti sono infinitamente rari. Questa scarsità ha costretto gli sviluppatori a utilizzare o parametri più vecchi e meno sicuri, o ad abbandonare l'ideale della ricorsione illimitata per catene più brevi e limitate.

I ricercatori si sono resi conto che il collo di bottiglia non era il concetto stesso di ciclo, ma il tipo specifico di curva utilizzato. Si sono rivolti alle curve "supersingolari". Queste sono una varietà matematica differente che, sebbene meno comune nella crittografia standard, possiede proprietà uniche che le rendono ideali per questo compito specifico. Il compromesso è che queste curve devono essere definite su campi matematici leggermente più grandi, il che rende alcuni calcoli un po' più pesanti. Tuttavia, il beneficio è travolgente: la nuova costruzione funziona per quasi ogni numero scelto, purché soddisfi un test di primalità di base. Non c'è bisogno di dare la caccia a numeri rari e fortunati. I ricercatori hanno dimostrato che per qualsiasi numero valido, possono generare immediatamente una coppia funzionante di curve supersingolari. Questo trasforma il problema da una caccia al tesoro a un processo di produzione. Invece di trovare solo pochi esempi sparsi, possono ora produrre un numero infinito di questi cicli su richiesta.

Per dimostrare che questo concetto funziona nel mondo reale, il team non si è limitato alla teoria; ha costruito un motore di ricerca per trovare esempi concreti. Si sono posti l'obiettivo di costruire quelli che chiamano "lollipops". Immaginate un lecca-lecca in cui il bastoncino è una catena di curve efficienti e la parte rotonda in cima è il ciclo ricorsivo. Il bastoncino permette alla prova di iniziare su un campo piccolo e veloce, rendendo i passi iniziali del calcolo molto rapidi. La parte rotonda, il ciclo, permette alla prova di essere impilata e verificata ricorsivamente senza limiti. I ricercatori hanno sviluppato un algoritmo per trovare queste strutture risolvendo un tipo specifico di puzzle numerico noto come equazione di Pell. Hanno eseguito questo algoritmo su computer potenti, cercando attraverso milioni di possibilità. La ricerca è stata un successo. Hanno trovato diciotto esempi distinti di questi lollipops, che variano in dimensione per supportare livelli di sicurezza da 80 bit fino a 128 bit e oltre. Uno dei loro esempi, un'istanza grande con un campo a 956 bit, ha persino superato i confini dell'interesse pratico, mostrando che queste strutture possono scalare per soddisfare le esigenze di sicurezza future.

La portata di queste scoperte risiede nella flessibilità che offrono ai progettisti di sistemi. Con il vecchio metodo, i progettisti erano costretti a utilizzare un insieme specifico, spesso inefficiente, di parametri perché non esistevano altre opzioni. Se volevano una maggiore sicurezza, dovevano accettare prestazioni più lente o limiti di ricorsione più piccoli. Con i nuovi cicli supersingolari, i progettisti possono scegliere parametri che siano ottimizzati per la velocità, come campi dove la matematica è particolarmente veloce da calcolare, o campi che abbiano proprietà specifiche utili per l'accelerazione hardware. Possono anche scegliere di connettere questi cicli ad altri tipi di curve che non sono "pairing-friendly" ma che sono estremamente efficienti per i passi iniziali di una prova. Questa capacità di mescolare e abbinare componenti, creando un "lollipop" personalizzato per una specifica applicazione, era impossibile con la tecnologia precedente. I ricercatori hanno osservato che, sebbene le nuove curve siano leggermente più grandi in alcune parti, la capacità di ottimizzare il resto del sistema e l'abbondanza di cicli disponibili rende il compromesso vantaggioso.

Il documento conclude sottolineando che questa è una svolta costruttiva. I ricercatori non hanno solo dimostrato che questi cicli esistono, ma hanno fornito gli strumenti per costruirli e un catalogo di diciotto esempi funzionanti. Riconoscono che il passo successivo è implementare questi nuovi cicli in un software reale per misurare i guadagni esatti di prestazione, poiché i vantaggi teorici devono essere pesati rispetto ai costi pratici dei campi più grandi. Tuttavia, la porta è ora aperta. La scarsità che un tempo limitava la crescita dei sistemi di prova ricorsiva è stata rimossa. Passando dalle curve ordinarie a quelle supersingolari, i ricercatori hanno fornito un nuovo, infinito approvvigionamento di blocchi matematici necessari per proteggere il futuro digitale, permettendo sistemi di prova che siano non solo più sicuri, ma anche più adattabili alle diverse esigenze del mondo reale.