Codici correttori e loro applicazioni alla crittografia post-quantum = Corrector Codes and their applications to Post-Quantum Cryptography

Il sistema crittografico oggi più diffuso è l'RSA. Tale sistema si basa sul fatto che, dato il prodotto di due numeri interi, è molto difficile risalire ai fattori di partenza. Questa sicurezza è però minata dal (probabile) avvento imminente del computer quantistico, su cui è possibile eseguire un algoritmo computazionalmente efficiente (l'algoritmo di Shor) per fattorizzare un intero. Per ovviare a questa minaccia, è stato introdotto un nuovo ramo di ricerca, detto crittografia post-quantum, che studia quegli algoritmi in grado di funzionare su computer classici ma resistenti anche ad attacchi quantistici. Fa parte di questo ramo la cosiddetta code-based cryptography, cioè l'insieme di quegli algoritmi crittografici che si basano sui codici correttori. Il primo è stato il sistema di McEliece, introdotto nel 1978 ma a cui all'inizio non era stata data grande considerazione. Esistono molteplici codici su cui basarsi per costruire un sistema crittografico; l'idea che sviluppiamo in questa tesi è quella di usare il codice di Fibonacci, studiato per la prima volta da Stakhov nel 1999. Il percorso seguito inizia con la presentazione di RSA e la sua spiegazione dal punto di vista dell'aritmetica modulare. Si prosegue poi con la dimostrazione di come il computer quantistico, usando l'algoritmo di Shor, sia in grado di romperlo. Vengono, a questo punto introdotti i codici correttori, di cui viene data una breve descrizione, soffermandosi in particolare sul codice di Goppa, che è quello usato nel sistema di McEliece. Nell'ultimo capitolo viene presentato un altro codice, quello di Fibonacci, per poi concludere esaminando i problemi che ostacolano la costruzione di un sistema crittografico basato su tale codice.