• basi di Gröbner
• Crittografia
• reticoli

In questa tesi descriveremo in dettaglio il crittosistema asimmetrico che
prende il nome di Lattice Polly Cracker o LPC. Esso sfrutta la stretta relazione
esistente tra ideali binomiali saturi e reticoli di rango massimo, utilizzando
la struttura a blocchi del reticolo per agevolare il calcolo della forma
normale di un binomio e di una base di Gröbner, risultando in questo modo
un crittosistema sicuro e decisamente veloce. I primi due capitoli di
questa tesi introducono gli strumenti e le tecniche usate nella definizione
del crittosistema, descrivendo alcuni aspetti dell'algebra computazionale e
mettendo in luce poi alcuni risultati della teoria delle basi di Gröbner per
reticoli essenziali per una completa indagine del crittosistema. Durante la
trattazione ci siamo occupati di analizzare le peculiarità di questo algoritmo
uniformando la notazione e mettendo in chiaro, e a volte completando,
alcune dimostrazioni utili per capirne meglio le caratteristiche.
In particolare abbiamo visto come definire l’insieme dei messaggi in modo
da assicurare maggiore sicurezza allo schema. Sfruttando la forma normale
di Hermite di una matrice definiamo la chiave pubblica in modo da mantenere
inalterata la sicurezza del sistema e allo stesso tempo diminuire il
numero di bit necessari per memorizzare la chiave.
Utilizziamo reticoli con una struttura a blocchi, in modo da poter lavorare
in dimensioni molto alte, e abbiamo visto che è proprio nella capacità
di nascondere tale struttura che risiede la sicurezza del crittosistema.
Abbiamo studiato in dettaglio alcuni attacchi contro il nuovo crittosistema,
specificando i valori da assegnare ai vari parametri nelle implementazioni
per ottenere un crittosistema sicuro. Abbiamo riportato i tempi necessari a
costruire un'istanza del crittosistema, a criptare e decriptare un messaggio
Abbiamo calcolato lo spazio necessario per memorizzare chiavi pubbliche e
private e crittogrammi confrontandolo con i dati conosciuti di crittosistemi
già esistenti. Abbiamo preso in esame alcuni attacchi basati su algoritmi
quantistici usati in crittoanalisi e abbiamo messo in luce i motivi per i quali
il crittosistema è immune. Infine abbiamo presentato il crittosistema introdotto
da Goldreich, Goldwasser e Halevi, che presenta molti punti in comune
con Lattice Polly Cracker, e ne abbiamo descritto le debolezze e i difetti. In
particolare abbiamo mostrato come l'attacco presentato da Nguyen che ne
ha portato alla rottura sia invece inefficace contro il crittosistema LPC.