Introduzione
Nel 1994, l'informatico Peter Shor scoperto che se i computer quantistici fossero mai stati inventati, avrebbero decimato gran parte dell'infrastruttura utilizzata per proteggere le informazioni condivise online. Quella spaventosa possibilità ha portato i ricercatori a lottare per produrre nuovi schemi di crittografia "post-quantum", per salvare quante più informazioni possibili dalla caduta nelle mani degli hacker quantistici.
All'inizio di quest'anno, il National Institute of Standards and Technology rivelato quattro finalisti nella sua ricerca di uno standard di crittografia post-quantistica. Tre di loro usano la "crittografia a reticolo", uno schema ispirato a reticoli, disposizioni regolari di punti nello spazio.
La crittografia a reticolo e altre possibilità post-quantistiche differiscono dagli standard attuali in modi cruciali. Ma si basano tutti sull'asimmetria matematica. La sicurezza di molti sistemi crittografici attuali si basa sulla moltiplicazione e sulla fattorizzazione: qualsiasi computer può moltiplicare rapidamente due numeri, ma potrebbero volerci secoli per scomporre un numero crittograficamente grande nei suoi costituenti primi. Questa asimmetria rende i segreti facili da codificare ma difficili da decodificare.
Ciò che Shor ha rivelato nel suo algoritmo del 1994 è che una stranezza del factoring lo rende vulnerabile agli attacchi dei computer quantistici. "È una cosa molto specifica e speciale che il computer quantistico può fare", ha detto Caterina Stange, un matematico presso l'Università del Colorado, Boulder. Quindi, dopo Shor, i crittografi hanno avuto un nuovo lavoro: trovare una nuova serie di operazioni matematiche facili da eseguire ma quasi impossibili da annullare.
La crittografia a reticolo è uno dei tentativi di maggior successo finora. Sviluppato originariamente negli anni '1990, si basa sulla difficoltà del reverse engineering di somme di punti.
Ecco un modo per descrivere la crittografia a reticolo: immagina che il tuo amico abbia un reticolo, che è solo un mucchio di punti in uno schema regolare e ripetuto su tutto il piano. Il tuo amico vuole che tu indichi 10 di questi punti. Ma è difficile e non disegnerà l'intero reticolo. Invece, elenca solo due punti: il primo con un x-valore di 101 e a y-valore di 19, l'altro con coordinate [235, 44].
Fortunatamente, è facile trovare nuovi punti su un reticolo, perché quando aggiungi e sottrai due punti qualsiasi su un reticolo, ottieni un terzo punto nello stesso reticolo. Quindi tutto ciò che devi fare è sommare i punti che il tuo amico ti ha dato, o moltiplicarli per numeri interi e poi sommarli, o una combinazione dei due. Fallo in otto modi diversi e sarai in grado di rispondere alla domanda del tuo amico.
Ma il tuo amico non è ancora soddisfatto. Ti dà gli stessi due punti di partenza e poi ti chiede se il punto [2, 1] si trova sullo stesso reticolo. Per rispondere correttamente a questa domanda, devi trovare la combinazione di [101, 19] e [235, 44] che produce [2, 1]. Questo problema è molto più difficile del primo e probabilmente finirai per indovinare e controllare per ottenere la risposta.* Questa asimmetria è ciò che sta alla base della crittografia a reticolo.
Se desideri effettivamente utilizzare la crittografia a reticolo per condividere informazioni, dovresti fare quanto segue. Immagina che un amico (uno più gentile!) voglia inviarti un messaggio sicuro. Inizi con una griglia quadrata di numeri. Supponiamo che abbia due righe e due colonne e assomigli a questo:
Ora ti viene in mente una "chiave" privata che solo tu conosci. In questo esempio, supponiamo che la tua chiave privata sia composta solo da due numeri segreti: 3 e −2. Moltiplichi i numeri nella prima colonna per 3 e quelli nella seconda colonna per -2. Somma i risultati in ogni riga per ottenere una terza colonna con due voci.
Attacca la nuova colonna all'estremità della griglia. Questa nuova griglia a tre colonne è la tua chiave pubblica. Condividilo liberamente!
(Uno scenario del mondo reale sarà un po' più complicato. Per impedire agli hacker di decodificare la tua chiave privata, devi aggiungere un po' di rumore casuale nella tua colonna finale. Ma qui ignoreremo questo passaggio per semplicità. )
Ora il tuo amico utilizzerà la chiave pubblica per inviarti un messaggio. Pensa a due suoi numeri segreti: 2 e 0. Moltiplica i numeri nella prima riga per 2 e quelli nella seconda riga per 0. Quindi somma i risultati in ciascuna colonna per ottenere una terza riga.
Ora allega la nuova riga in fondo alla griglia e te la rimanda. (Di nuovo, in un sistema reale, avrebbe bisogno di aggiungere un po' di rumore alla sua fila.)
Ora leggerai il messaggio. Per fare ciò, controlla se l'ultima riga del tuo amico è corretta. Applica la tua chiave privata alle prime due voci della sua riga. Il risultato dovrebbe corrispondere all'ultima voce.
Il tuo amico può anche scegliere di inviarti una riga con un numero sbagliato nell'ultima colonna. Sa che questo numero non corrisponderà ai tuoi calcoli.
Se la tua amica invia una riga in cui l'ultimo numero è corretto, interpreterai questo come 0. Se invia una riga in cui il numero non è corretto, lo interpreterai come 1. La riga, quindi, codifica un singolo bit: 0 o 1.
Tieni presente che un utente malintenzionato esterno non avrà accesso né alla tua chiave privata né a quella del tuo amico. Senza quelli, l'attaccante non avrà idea se il numero finale è corretto o meno.
In pratica, vorresti inviare messaggi più lunghi di un bit. Quindi le persone che vogliono ricevere, diciamo, un messaggio a 100 bit genereranno 100 nuove colonne invece di una sola. Quindi il mittente del messaggio creerà un'unica nuova riga, modificando le ultime 100 voci per codificare uno 0 o un 1 per ciascuna voce.
Se la crittografia reticolare viene effettivamente implementata, avrà innumerevoli sfumature non coperte in questo scenario. Ad esempio, se vuoi che il messaggio sia veramente al sicuro da occhi indiscreti, la matrice deve avere un numero impensabile di voci, rendendo il tutto così ingombrante che non vale la pena usarlo. Per aggirare questo problema, i ricercatori utilizzano matrici con utili simmetrie che possono ridurre il numero di parametri. Oltre a ciò, c'è un'intera suite di modifiche che possono essere applicate al problema stesso, al modo in cui gli errori vengono incorporati e altro ancora.
Naturalmente, è sempre possibile che qualcuno trovi un difetto fatale nella crittografia reticolare, proprio come ha fatto Shor per il factoring. Non vi è alcuna garanzia che un particolare schema crittografico funzionerà di fronte a qualsiasi possibile attacco. La crittografia funziona finché non viene craccata. Infatti, all'inizio di quest'estate un promettente schema di crittografia post-quantistica è stato violato usando non un computer quantistico, ma un normale laptop. Per Stange, l'intero progetto crea uno scomodo paradosso: "Quello che trovo così sorprendente della crittografia è che abbiamo costruito questa infrastruttura per la razza umana sulla ferma convinzione che le nostre capacità come esseri umani siano limitate", ha detto. "È così arretrato."
*: La risposta, se sei curioso, è 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [torna all'articolo]
