Crittografia post-quantica sui reticoli: esempi e applicazioni

Per crittografia post-quantica sui reticoli si intende l'insieme delle costruzioni crittografiche che coinvolgono i reticoli geometrici, nella prova di sicurezza o nella stessa costruzione. Il termine post-quantico sottolinea l'inesistenza, ad oggi, di attacchi quantistici efficienti per i problemi sui reticoli. Invece sono già noti algoritmi per computer quantistici che risolvono in tempo polinomiale i problemi della fattorizzazione e del logaritmo discreto, alla base della sicurezza dei sistemi maggiormente utilizzati e conosciuti. Il nostro punto di partenza è il risultato ottenuto da Ajtai nel 1996. Nell'articolo "Generating hard instances of lattice problems" egli mostra l'esistenza di un legame tra la crittografia e la difficoltà di alcuni problemi su reticoli. In particolare l'autore presenta un sistema la cui sicurezza si fonda sulla difficoltà di un problema nel caso peggiore. Al contrario, nei sistemi crittografici studiati sino a quel momento, la sicurezza si basa sulla difficoltà nel caso intermedio: si suppone che il problema sia mediamente difficile poichè alcune scelte dei parametri in gioco potrebbero portare alla sua risoluzione. Nel primo capitolo esporremo la parte propedeutica alla comprensione dei sistemi crittografici sui reticoli. Partiremo col dare la definizione di reticolo e descriverne le principali proprietà. Il corpo centrale invece sarà dedicato al problema SVP, ovvero la ricerca di un vettore di lunghezza minima nel reticolo, e allo studio di una sua possibile risoluzione, sia nel caso bidimensionale che per maggiori dimensioni. Descriveremo infine l'algoritmo LLL, evidenziandone vantaggi ed eventuali problematiche. Nel secondo capitolo l'analisi sarà concentrata sulla costruzione di tre sistemi che basano la loro sicurezza su SVP o sulla sua variante CVP (Closest vector problem), descrivendone gli algoritmi e riportando alcuni esempi per evidenziare la facilità dei calcoli coinvolti.