Il celebre algoritmo di crittografia ottiene un aggiornamento | Rivista Quanti

Nelle nostre vite sempre più digitali, la sicurezza dipende dalla crittografia. Invia un messaggio privato o paga una fattura online e ti affiderai ad algoritmi progettati per mantenere segreti i tuoi dati. Naturalmente, alcune persone vogliono scoprire questi segreti, quindi i ricercatori lavorano per testare la forza di questi sistemi per assicurarsi che non crollino per mano di un aggressore intelligente.

Uno strumento importante in questo lavoro è l'algoritmo LLL, dal nome dei ricercatori che pubblicato nel 1982 — Arjen Lenstra, Hendrik Lenstra Jr. e László Lovász. LLL, insieme ai suoi numerosi discendenti, in alcuni casi può infrangere gli schemi crittografici; studiare come si comportano aiuta i ricercatori a progettare sistemi meno vulnerabili agli attacchi. E le potenzialità dell'algoritmo vanno oltre la crittografia: è anche uno strumento utile in ambiti matematici avanzati come la teoria computazionale dei numeri.

Nel corso degli anni, i ricercatori hanno affinato le varianti di LLL per rendere l’approccio più pratico, ma solo fino a un certo punto. Ora, una coppia di crittografi ha creato un nuovo algoritmo in stile LLL con un significativo aumento dell’efficienza. La nuova tecnica, che ha vinto il Premio per il miglior articolo alla Conferenza internazionale di crittologia 2023, amplia la gamma di scenari in cui informatici e matematici possono utilizzare approcci simili a LLL.

"È stato davvero emozionante", ha detto Chris Peikert, un crittografo dell'Università del Michigan che non era coinvolto nell'articolo. Lo strumento è stato al centro dello studio per decenni, ha detto. "È sempre bello quando un obiettivo su cui si è lavorato così a lungo... dimostra che ci sono ancora delle sorprese da trovare."

Gli algoritmi di tipo LLL operano nel mondo dei reticoli: raccolte infinite di punti regolarmente spaziati. Per visualizzarlo, immagina di piastrellare un pavimento. Potresti coprirlo con piastrelle quadrate e gli angoli di quelle piastrelle formerebbero un reticolo. In alternativa, potresti scegliere una forma diversa della piastrella, ad esempio un lungo parallelogramma, per creare un reticolo diverso.

Un reticolo può essere descritto utilizzando la sua “base”. Si tratta di un insieme di vettori (essenzialmente elenchi di numeri) che puoi combinare in diversi modi per ottenere ogni punto del reticolo. Immaginiamo un reticolo con base composta da due vettori: [3, 2] e [1, 4]. Il reticolo è semplicemente l'insieme dei punti che puoi raggiungere aggiungendo e sottraendo copie di quei vettori.

Quella coppia di vettori non è l'unica base del reticolo. Ogni reticolo con almeno due dimensioni ha infinite basi possibili. Ma non tutte le basi sono uguali. Una base i cui vettori sono più corti e vicini agli angoli retti tra loro è solitamente più facile da lavorare e più utile per risolvere alcuni problemi computazionali, quindi i ricercatori chiamano quelle basi “buone”. Un esempio di ciò è la coppia di vettori blu nella figura seguente. Le basi costituite da vettori più lunghi e meno ortogonali – come i vettori rossi – possono essere considerate “cattive”.

Questo è un compito per LLL: fornirgli (o ai suoi fratelli) la base di un reticolo multidimensionale e ne sputerà fuori uno migliore. Questo processo è noto come riduzione della base reticolare.

Cosa c’entra tutto questo con la crittografia? Si scopre che il compito di violare un sistema crittografico può, in alcuni casi, essere riformulato come un altro problema: trovare un vettore relativamente corto in un reticolo. E a volte, quel vettore può essere estratto dalla base ridotta generata da un algoritmo in stile LLL. Questa strategia ha aiutato i ricercatori a rovesciare sistemi che, in superficie, sembrano avere poco a che fare con i reticoli.

In senso teorico, l'algoritmo LLL originale viene eseguito rapidamente: il tempo necessario per l'esecuzione non scala in modo esponenziale con la dimensione dell'input, ovvero la dimensione del reticolo e la dimensione (in bit) dei numeri nell'algoritmo. vettori di base. Ma aumenta come funzione polinomiale e “se vuoi davvero farlo, il tempo polinomiale non è sempre così fattibile”, ha detto Leone Ducas, crittografo presso l'istituto di ricerca nazionale CWI nei Paesi Bassi.

In pratica, ciò significa che l'algoritmo LLL originale non può gestire input troppo grandi. "Matematici e crittografi volevano la possibilità di fare di più", ha detto Kegan Ryan, uno studente di dottorato presso l'Università della California, San Diego. I ricercatori hanno lavorato per ottimizzare gli algoritmi in stile LLL per accogliere input più grandi, ottenendo spesso buone prestazioni. Tuttavia, alcuni compiti sono rimasti ostinatamente fuori portata.

Il nuovo articolo, scritto da Ryan e dal suo consulente, Nadia Heninger, combina più strategie per migliorare l'efficienza del suo algoritmo in stile LLL. Per prima cosa, la tecnica utilizza una struttura ricorsiva che suddivide l’attività in parti più piccole. Dall'altro, l'algoritmo gestisce attentamente la precisione dei numeri coinvolti, trovando un equilibrio tra velocità e risultato corretto. Il nuovo lavoro rende possibile per i ricercatori ridurre le basi di reticoli con migliaia di dimensioni.

Il lavoro passato ha seguito un approccio simile: A carta 2021 combina anche la ricorsione e la gestione della precisione per lavorare rapidamente su reticoli di grandi dimensioni, ma ha funzionato solo per tipi specifici di reticoli e non per tutti quelli importanti in crittografia. Il nuovo algoritmo si comporta bene su un intervallo molto più ampio. "Sono davvero felice che qualcuno lo abbia fatto", ha detto Tommaso Espitau, ricercatore di crittografia presso la società PQShield e autore della versione 2021. Il lavoro del suo team ha offerto una “prova di concetto”, ha detto; il nuovo risultato mostra che “è possibile eseguire una riduzione del reticolo molto veloce e in modo efficace”.

La nuova tecnica ha già iniziato a rivelarsi utile. Aurel Pagina, un matematico dell'istituto di ricerca nazionale francese Inria, ha affermato che lui e il suo team hanno adattato l'algoritmo per lavorare su alcuni compiti di teoria computazionale dei numeri.

Gli algoritmi di stile LLL possono anche svolgere un ruolo nella ricerca relativa ai sistemi di crittografia basati su reticolo progettati per resta al sicuro anche in un futuro con potenti computer quantistici. Non rappresentano una minaccia per tali sistemi, poiché per eliminarli è necessario trovare vettori più brevi di quelli che questi algoritmi possono ottenere. Ma i migliori attacchi che i ricercatori conoscono utilizzano un algoritmo in stile LLL come “elemento fondamentale”, ha affermato Wessel van Woerden, crittografo dell'Università di Bordeaux. Negli esperimenti pratici per studiare questi attacchi, questo elemento fondamentale può rallentare tutto. Utilizzando il nuovo strumento, i ricercatori potrebbero essere in grado di espandere la gamma di esperimenti che possono eseguire sugli algoritmi di attacco, offrendo un quadro più chiaro delle loro prestazioni.

Quanta sta conducendo una serie di sondaggi per servire meglio il nostro pubblico. Prendi il nostro Sondaggio tra i lettori di informatica e potrai partecipare alla vincita gratuita Quanta merce.