Crittografia post-quantica sui reticoli: esempi e applicazioni

Antonelli, Erminia (2018) Crittografia post-quantica sui reticoli: esempi e applicazioni. [Laurea], Università di Bologna, Corso di Studio in Matematica [L-DM270], Documento ad accesso riservato.
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Full-text accessibile solo agli utenti istituzionali dell'Ateneo
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato

Download (536kB) | Contatta l'autore

Abstract

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.

Abstract
Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Antonelli, Erminia
Relatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
reticoli GGH LLL AJTAI REGEV crittografia
Data di discussione della Tesi
14 Dicembre 2018
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^