Crittografia basata su reticoli
- Introdotto da
- Miklós Ajtai
- Anno
- 1996
- Tipo
- public-key cryptosystem based on lattice hardness
- Famiglia
- Post-quantum cryptography
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
La crittografia basata su reticoli è una classe di sistemi crittografici la cui sicurezza deriva dalla difficoltà computazionale dei problemi sui reticoli, in particolare il problema del vettore più corto (SVP) e l'apprendimento con errori (LWE).
Proposti per la prima volta da Miklós Ajtai nel 1996, gli approcci basati su reticoli hanno guadagnato prominenza come i principali candidati per la crittografia post-quantistica. A differenza di RSA ed ECC, che sono vulnerabili ai computer quantistici, si ritiene che i problemi sui reticoli rimangano difficili anche contro algoritmi quantistici.
L’intuizione alla base del metodo
Un reticolo è un sottogruppo discreto dello spazio euclideo formato da combinazioni lineari intere di vettori di base. La crittografia basata su reticoli sfrutta il divario tra due problemi: trovare un vettore corto in un reticolo è computazionalmente difficile, ma con informazioni aggiuntive (una base segreta), il vettore corto può essere trovato rapidamente. La crittografia a chiave pubblica è costruita pubblicando una base difficile e mantenendo segreta una base facile. L'aggiunta di un piccolo rumore casuale (il paradigma dell'apprendimento con errori) rafforza ulteriormente la sicurezza rendendo il problema simile a un sistema lineare rumoroso difficile da risolvere.
Storia
Il lavoro fondamentale di Ajtai del 1996 ha collegato la durezza dei reticoli alla crittografia. Il framework di apprendimento con errori (LWE) di Regev nel 2005 ha fornito una base pratica e versatile per la crittografia basata su reticoli. Il campo ha accelerato dopo che istituzioni accademiche e governative hanno riconosciuto la minaccia del calcolo quantistico all'infrastruttura crittografica attuale. Nel 2022, il NIST ha standardizzato algoritmi crittografici post-quantistici, selezionando schemi basati su reticoli (CRYSTALS-Kyber per la cifratura, CRYSTALS-Dilithium per le firme) come raccomandazioni primarie.
Quando usarlo
La crittografia basata su reticoli è essenziale per i sistemi progettati per rimanere sicuri contro i futuri computer quantistici. È raccomandata per la confidenzialità a lungo termine dei dati sensibili, le comunicazioni governative e militari e le infrastrutture che devono rimanere sicure per decenni. Man mano che gli algoritmi post-quantistici standardizzati maturano (il NIST ha recentemente standardizzato ML-KEM e ML-DSA), i metodi basati su reticoli stanno diventando mainstream nei moderni sistemi crittografici.
Limiti e considerazioni
- Dimensioni delle chiavi e dei testi cifrati maggiori rispetto ai tradizionali RSA o ECC, aumentando l'overhead di archiviazione e trasmissione
- Più recente e meno diffuso di RSA o ECC, quindi l'esperienza di implementazione nel mondo reale è limitata
- Alcuni schemi basati su reticoli hanno scelte di parametri sottili che influenzano significativamente la sicurezza; parametri errati possono essere catastrofici
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Si ritiene sia resistente agli attacchi dei computer quantistici, incluso l'algoritmo di Shor
- Solide basi matematiche basate su problemi sui reticoli ben studiati
- Supporta sia la cifratura che le firme digitali all'interno dello stesso framework
- Implementazioni pratiche disponibili con costi computazionali ragionevoli per l'hardware moderno
Applicazioni
- Sicurezza dei trasporti post-quantistica per proteggere le comunicazioni dalla futura decrittazione quantistica
- Cifratura per archiviazione a lungo termine per documenti e dati che devono rimanere segreti per decenni
- Sistemi di comunicazione governativi e militari resilienti alle minacce quantistiche
- Sistemi blockchain e di criptovalute progettati per la sicurezza quantistica-resistente
- Sistemi IoT e embedded dove la resistenza quantistica è un requisito di progettazione
- Sistemi crittografici ibridi che combinano algoritmi basati su reticoli e tradizionali durante il periodo di transizione crittografica
Come funziona
Come funziona
Scegliere le dimensioni del reticolo n, il modulo q e la distribuzione degli errori. Generare una base corta segreta e derivarne una base pubblica tramite trasformazioni del reticolo.
La chiave pubblica è derivata dalla base difficile del reticolo; non fornisce alcuna informazione sulla base segreta da una prospettiva computazionale.
Per cifrare, aggiungere il testo in chiaro a una combinazione lineare rumorosa dei vettori della base pubblica, creando un punto del reticolo più rumore.
Utilizzando la base corta segreta, ridurre il punto del reticolo rumoroso ed estrarre il testo in chiaro.
Errori comuni
- La selezione dei parametri del reticolo (dimensione, modulo, distribuzione degli errori) non è banale; si raccomanda vivamente l'uso di parametri standard approvati dal NIST
- Gli attacchi a canale laterale (timing, analisi della potenza) sulle operazioni sui reticoli richiedono un'implementazione attenta; gli algoritmi a tempo costante sono essenziali
- Mescolare in modo errato algoritmi basati su reticoli e classici può creare sistemi ibridi con debolezze inaspettate
Domande frequenti
Cos'è il problema dell'apprendimento con errori (LWE)?
LWE è un problema computazionale in cui si ricevono equazioni lineari rumorose su un campo finito. Date equazioni del tipo a·x + e (mod q) dove a è casuale, x è segreto, ed e è un piccolo rumore, recuperare x senza conoscere e è computazionalmente difficile.
Perché le chiavi basate su reticoli sono più grandi delle chiavi RSA?
Le basi dei reticoli e le matrici che le codificano contengono più informazioni di un singolo numero composto. Codificare una base di reticolo crittograficamente richiede più bit, sebbene schemi recenti abbiano ottimizzato le rappresentazioni.
I problemi sui reticoli sono resistenti ai quanti?
Non esiste un algoritmo quantistico noto più veloce degli algoritmi classici per problemi sui reticoli come SVP o LWE, sebbene questa rimanga un'area di ricerca attiva. Si ipotizza che la durezza dei reticoli sopravviva ai computer quantistici.
Qual è la raccomandazione del NIST sulla crittografia basata su reticoli?
Il NIST ha standardizzato ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) per la cifratura e ML-DSA (Module-Lattice-Based Digital Signature Algorithm) per le firme come algoritmi post-quantistici primari nelle FIPS 203 e FIPS 204.
Posso usare la crittografia basata su reticoli oggi?
Sì. Molte librerie crittografiche moderne supportano ora algoritmi basati su reticoli standardizzati dal NIST. Le organizzazioni che gestiscono dati sensibili con lunghi periodi di conservazione dovrebbero iniziare la pianificazione della migrazione.
Metodi correlati
Fonti
Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.
Apri il riferimento della pubblicazioneCopiato.Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.
Apri il riferimento della pubblicazioneCopiato.