POKEx: Performance analysis of POKE-key exchange and SIDH-variants

Immaginate che internet sia una città gigante e frenetica dove tutti si scambiano lettere segrete. Per mantenere queste lettere al sicuro dai ladri, usiamo dei "lucchetti" chiamati crittografia. Per decenni, i migliori lucchetti sono stati realizzati usando problemi matematici che sono facili da eseguire in un senso ma incredibilmente difficili da invertire, come mescolare i colori della vernice. Tuttavia, gli scienziati sono preoccupati che in futuro, computer super-potenti (chiamati computer quantistici), possano invertire questi lucchetti istantaneamente, lasciando i nostri segreti completamente scoperti. Per fermare questo, i ricercatori stanno costruendo nuovi lucchetti basati su una branca della matematica strana e bellissima chiamata "isogenia". Pensate alle isogenie come a un tipo speciale di ponte che collega diverse forme (curve matematiche). Il segreto del lucchetto è il percorso specifico che percorrete attraverso il ponte. Per molto tempo, il design del ponte più popolare è stato chiamato SIDH. Era famoso perché i lucchetti erano minuscoli e veloci, rendendolo un forte contendente per proteggere il nostro futuro mondo digitale.

Ma poi, nel 2023, un paio di ricercatori ha scoperto un trucco astuto per rompere il ponte SIDH. Hanno scoperto che i progettisti del ponte avevano accidentalmente lasciato la mappa del percorso visibile a chiunque guardasse, permettendo di scoprire la rotta segreta in pochi secondi. Questo è stato un duro colpo, poiché significava che il più promettente lucchetto "quantum-proof" era in realtà stato violato. Da allora, gli scienziati stanno cercando freneticamente di costruire nuovi ponti che nascondano meglio la mappa. Alcuni hanno provato a coprire la mappa con una coperta (mascheramento), altri hanno provato a costruire il ponte con materiali diversi. La grande domanda rimaneva: possiamo costruire un ponte che sia sia indistruttibile che abbastanza veloce da essere usato nel mondo reale?

Questo articolo, intitolato "POKEx", entra in quel cantiere caotico per testare un nuovo e lucente design di ponte chiamato POKÉ. Gli autori, Hyeonhak Kim e Suhri Kim, hanno deciso di trasformare il metodo di crittografia POKÉ in un sistema completo di scambio di chiavi (che chiamano POKEx) e di farlo gareggiare contro gli altri principali contendenti che cercano di riparare il rotto ponte SIDH. Non si sono limitati a indovinare; hanno costruito versioni funzionanti di questi sistemi e le hanno cronometrate su un computer potente. La loro scoperta principale è che POKEx è attualmente il più veloce ed efficiente di tutti i ponti basati su isogenia. Nei loro test, era circa 21 volte più veloce dell'alternativa successiva migliore (terSIDH) e quasi 65 volte più veloce di un altro design popolare (CSIDH). Sebbene sia ancora più lento di altri tipi di lucchetti sicuri contro i computer quantistici, la sua velocità e la sua dimensione ridotta lo rendono un candidato molto promettente per il futuro, offrendo un modo per mantenere sicuri i nostri segreti digitali senza rallentare internet.

La storia del ponte rotto e della nuova soluzione

Per capire perché questo articolo è importante, dobbiamo prima guardare il problema del "ponte". Nel mondo della crittografia, uno "scambio di chiavi" è come due persone che concordano una password segreta senza mai pronunciarla ad alta voce. Per molto tempo, il sistema SIDH è stato il protagonista. Utilizzava curve ellittiche supersingolari — pensate a queste come a forme complesse e sinuose in un universo matematico. La magia di SIDH era che utilizzava i "punti di torsione", che sono come punti di riferimento specifici su queste curve, per costruire il ponte. Il sistema era così efficiente che aveva chiavi piccole (l'equivalente digitale di un lucchetto minuscolo e leggero) ed era molto veloce.

Tuttavia, il ponte SIDH aveva un difetto fatale. Per costruire il ponte, il sistema doveva pubblicare alcune informazioni sui punti di riferimento (punti di torsione) che utilizzava. Nel 2023, Castryck e Decru hanno trovato un modo per usare questi punti di riferimento pubblicati, combinati con un trucco matematico astuto chiamato "Kani's glue-and-split", per ricostruire il percorso segreto. Era come lasciare una scia di briciole di pane che conduceva direttamente al tesoro. Una volta scoperto questo attacco, SIDH è stato considerato rotto e rimosso dalla lista dei candidati per il futuro della sicurezza di internet.

La corsa per riparare il ponte

Dopo la caduta di SIDH, la comunità della crittografia non si è arresa. Hanno iniziato a costruire nuovi ponti per sostituirlo. Alcuni hanno cercato di nascondere i punti di riferimento coprendoli con rumore casuale (un metodo chiamato M-SIDH). Altri hanno cercato di cambiare completamente la forma del ponte usando l' "orientamento artificiale" (terSIDH). C'era anche CSIDH, un tipo diverso di ponte che non era stato colpito dallo stesso attacco, ma che aveva i suoi problemi di velocità.

Il problema era che questi nuovi ponti erano o troppo lenti o troppo grandi. Coprire i punti di riferimento con il rumore richiedeva numeri molto più grandi per rimanere sicuri, il che rendeva i lucchetti pesanti e lenti da usare. Cambiare la forma del ponte (terSIDH) aiutava, ma presentava comunque delle variazioni di velocità che potevano essere pericolose. La comunità aveva bisogno di una soluzione che fosse sia sicura che veloce.

Entra POKEx: Il demone della velocità

È qui che il nuovo eroe dell'articolo, POKEx, entra in scena. POKEx si basa su uno schema chiamato POKÉ, proposto recentemente da Basso e Maino. Gli autori di questo articolo hanno preso POKÉ e l'hanno trasformato in un sistema completo di scambio di chiavi, completo di tutti i passaggi necessari per generare chiavi e scambiare segreti in modo sicuro.

La formula segreta di POKEx è il modo in cui gestisce i "punti di riferimento". Invece di usare solo percorsi monodimensionali come il vecchio SIDH, POKEx utilizza una "rappresentazione bidimensionale". Immaginate di dover attraversare un fiume. SIDH era come camminare su una singola tavola. Se qualcuno avesse visto dove mettevate i piedi, avrebbe potuto capire il vostro percorso. POKEx, invece, è come camminare su una griglia di tavole dove potete muovervi in due direzioni contemporaneamente. Questo rende il percorso molto più difficile da indovinare. Inoltre, POKEx utilizza un tipo speciale di campo matematico (un numero primo della forma $2^a3^b5^c-1$) che permette calcoli molto veloci, a differenza degli altri nuovi ponti che dovevano usare numeri molto più grandi e lenti.

La grande sfida: Cosa dicono i numeri

Gli autori non si sono limitati a parlare di POKEx; l'hanno messo alla prova. Hanno costruito un software per far girare POKEx insieme ai suoi principali contendenti: M-SIDH, terSIDH e CSIDH. Li hanno impostati tutti allo stesso livello di sicurezza (livello di sicurezza NIST 1, che è lo standard per proteggere i dati governativi top-secret) e hanno cronometrato quanto tempo occorreva per scambiare una chiave.

I risultati sono stati sorprendenti.

• M-SIDH era il più lento del gruppo, impiegando quasi 190 secondi per fare ciò che POKEx faceva in una frazione di secondo. Gli autori hanno notato che questo rende M-SIDH impraticabile per l'uso nel mondo reale.
• terSIDH era molto più veloce di M-SIDH, ma impiegava comunque circa 6,5 secondi.
• CSIDH ha impiegato circa 20 secondi.
• POKEx, tuttavia, ha completato il lavoro in soli 306,95 millisecondi (circa 0,3 secondi).

Per mettere questo in prospettiva, POKEx era 21,21 volte più veloce di terSIDH e 64,97 volte più veloce di CSIDH. Questo rende POKEx il campione attuale dello scambio di chiavi basato su isogenia.

È perfetto?

L'articolo è attento a non definire questa come una soluzione "perfetta". Sebbene POKEx sia il più veloce tra i ponti basati su isogenia, è ancora molto più lento di altri tipi di lucchetti sicuri contro i computer quantistici, come ML-KEM (che ha impiegato solo 0,10 millisecondi nel test). Tuttavia, gli autori sottolineano un compromesso cruciale. ML-KEM è veloce, ma i suoi "lucchetti" (chiavi pubbliche e ciphertext) sono enormi, occupando molto spazio su internet. POKEx, d'altro canto, ha chiavi molto piccole (solo 324 byte per la chiave pubblica), il che significa che utilizza meno larghezza di banda. In un mondo in cui la velocità di internet e i limiti di dati contano, questa piccola dimensione è un enorme vantaggio.

Il punto fondamentale

Questo articolo dimostra che, sebbene il vecchio ponte SIDH sia rotto, la strada verso un nuovo, sicuro ponte è aperta. POKEx è attualmente il candidato più promettente nella famiglia delle isogenie, offrendo una rara combinazione di alta velocità e dimensioni ridotte. Dimostra che possiamo costruire lucchetti resistenti ai computer quantistici che non rallentano la nostra vita digitale. Sebbene debba ancora fare molta strada per raggiungere la velocità di altri metodi sicuri contro i computer quantistici, la sua efficienza suggerisce che potrebbe diventare uno strumento vitale per mantenere sicuro il nostro futuro internet, specialmente in situazioni in cui risparmiare spazio nei dati è importante quanto risparmiare tempo.