Skip to content
Torna ai risultati

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

Dimensione del carattere

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

1

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.

2

La chiave pubblica è derivata dalla base difficile del reticolo; non fornisce alcuna informazione sulla base segreta da una prospettiva computazionale.

3

Per cifrare, aggiungere il testo in chiaro a una combinazione lineare rumorosa dei vettori della base pubblica, creando un punto del reticolo più rumore.

4

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

  1. 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 pubblicazione
    Copiato.
  2. 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 pubblicazione
    Copiato.