ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-02092015-093049


Tipo di tesi
Tesi di laurea magistrale
Autore
VAIRA, ANTONIO
URN
etd-02092015-093049
Titolo
Post Quantum Cryptography
Dipartimento
FISICA
Corso di studi
FISICA
Relatori
relatore Prof. Morsch, Oliver
relatore Borrelli, Cristiano
Parole chiave
  • post-quantum
  • cryptography
  • quantum computing
  • lattice-based
  • ring-LWE
  • learning with errors
Data inizio appello
02/03/2015
Consultabilità
Completa
Riassunto
Riassunto tesi magistrale:
Post Quantum Cryptography
Candidato: VAIRA Antonio

Durante la stesura della mia tesi, su cui ho lavorato quest'ultimo anno della mia carriera universitaria, ho cercato di rispondere alla domanda:
Qual è lo stato dell'arte della crittografia odierna in grado di sostenere un attacco da parte di utente malevolo in possesso di un “grande” computer quantistico?
Per “grande” si intende un computer quantistico che abbia un registro di diverse migliaia di qubit e quindi sia in grado di far girare degli algoritmi quantistici effettivamente utilizzabili.
Ad oggi sono stati ideati solamente due algoritmi quantistici per scopi cripto-analitici ed uno di questi, l’algoritmo di Shor, permette di fattorizzare grandi numeri in un tempo ridotto.
Questo “semplice” problema matematico (o meglio algoritmico) è alla base della sicurezza dei cripto-sistemi a chiave pubblica utilizzati oggi. In un sistema a chiave pubblica odierno, come l'RSA, la difficoltà di manomissione è legata alla difficoltà algoritmica di fattorizzare grandi numeri, dove difficoltà implica non l'impossibilità ma bensì un dispendio di risorse/tempo per l’hacking maggiore del valore stesso dell'informazione che si otterrebbe da tale hacking.
Nel mio lavoro inizialmente ho preso in esame, in linea di massima, sia i cripto-sistemi utilizzati oggi sia gli algoritmi quantistici utilizzabili in un ipotetico futuro per comprometterli. Successivamente, ho focalizzato la mia attenzione sulle alternative “mainstream” ai cripto-sistemi impiegati oggi: ovvero algoritmi post-quantum, proposti dalla comunità di cripto-analisti attivi nel campo, e ho provato a costruire un framework per valutarne l'effettivo impiego.
In questo framework, quindi, ho scelto di approfondire lo studio della famiglia dei lattice-based (algoritmi la cui sicurezza è basata sulla difficoltà di risolvere problemi relativi ai lattici multidimensionali). All'interno di questa famiglia di cripto-sistemi ne ho individuato uno in particolare, lo NTRU, particolarmente promettente per un impiego, nell'immediato futuro, all'interno di una corporate PKI (un esempio a me vicino è la PKI sviluppata all'interno dell'Airbus, per la quale ho lavorato durante quest'ultimo anno).
Ho in seguito approfondito lo studio di un altro algoritmo appartenente alla medesima famiglia dei cripto-sistemi lattice-based : il ring-LWE in quanto molto più interessante da un punto di vista accademico ma ancora relativamente sconosciuto. Successivamente ho elaborato alcune modifiche per lo stesso algoritmo con lo scopo di renderlo più veloce e affidabile, incrementando così la probabilità di recuperare un messaggio corretto dal corrispondente crittogramma.
Come ultima tappa, ho implementato l'algoritmo di criptazione modificato utilizzando un linguaggio ad alto livello (molto vicino a python) e ho comparato sia i tempi di esecuzione sia le risorse utilizzate con un versione non modificata ma implementata con lo stesso linguaggio, rendendo così i confronti il più coerenti possibile. Dai risultati ottenuti risulta che la versione modificata del ring-LWE è estremamente promettente ma necessita di una più approfondila analisi da un punto di vista cripto-analitico, ovvero è necessario stressare l'algoritmo per capire se introduca o meno ulteriori vulnerabilità rispetto alla versione originale.
In conclusione l'algoritmo ring-LWE, che ho maggiormente approfondito, offre diversi e interessanti spunti di riflessione ma è ben lontano dall'essere implementato in una infrastruttura reale. Nel evenienza di una sostituzione immediata è in generale buona norma in crittografia ripiegare su strade già battute e implementazioni più vecchie e fidate, un esempio all'interno degli algoritmi post-quantum è sicuramente lo NTRU (già dal 2008 standard IEEE: Std 1363.1).
Come ultima riflessione personale vorrei aggiungere che malgrado in questo mio lavoro di tesi l'aspetto fisico appaia marginale è solo grazie alla preparazione, che ho maturato nel mio percorso di studi, che ho potuto svolgerlo senza grandi difficoltà e facendo un esperienza davvero costruttiva in una grande azienda come l'Airbus. Dopo tutto un bagaglio fisico ci rende dei “problem-solver” nelle situazioni più disparate.
File