Scheda programma d'esame
CRITTOGRAFIA POST-QUANTISTICA
PATRIZIA GIANNI
Anno accademico2019/20
CdSMATEMATICA
Codice703AA
CFU6
PeriodoSecondo semestre
LinguaItaliano

ModuliSettore/iTipoOreDocente/i
CRITTOGRAFIA POST-QUANTISTICAMAT/02LEZIONI42
PATRIZIA GIANNI unimap
CARLO TRAVERSO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Gli studenti acquisiranno le conoscenze relative ai potenziali attacchi alla sicurezza crittografica derivanti dal possibile futuro sviluppo di calcolatori quantistici di rilevante dimensione, e sui protocolli crittografici che resistono meglio a tali attacchi attualmente noti. 

A tal fine si illustreranno gli algoritmi quantistici di Shor e Grover, e come il primo renda totalmente insicuri RSA, Diffie-Hellmann e la sua estensione alle curve ellittiche, e il secondo possa richiedere l'uso di chavi crittografiche più lunghe.

Saranno quindi illustrati i vari protocolli resistenti all'algoritmo di Shor, in particolare quelli studiati dal corrente progetto di standardizzazione di protocolli di crittografia post-quantistica, lanciato dal NIST nel 2016, ed attualmente in sviluppo.

Saranno delineati i risultati matematici che sono alla base di tali protocolli, e quali algoritmi sono utilizzati per gli attacchi ad essi. In particolare, si studieranno gli algoritmi sui reticoli, i codici correttori, i sistemi di equazioni polinomiali multivariate, e le curve ellittiche.

Knowledge

The students will acquire the knowledges relative to the cryptographic attacks arising from the potential future development of large quantum computers, and on cryptographic protocols that seem to be better resistant to current quantum attacks

We will illustrate the attcks through Shor's and Grover's attacks, and how the first makes RSA, Diffie-Hellmann and elliptic curves DH completely insecure, while the second might require longer keys.

We will then illustrate several protocols that resist to Shor's algorithm, in particulas those considered by the current NIST project of post-quantum cryptography standardization, currently being developed.

We will outline the mathematical results on which these protocols are based, and the algorithms use to attack them. In particular, we will study algorithms on lattices, error correcting codes, multivariate polynomial systems, and elliptic curves.

Modalità di verifica delle conoscenze

Gli studenti saranno valutati dalla loro dimostrazione di abilità nel discutere i contenuti principali del corso con l'uso della terminologia appropriata.

Metodo:

* Esame orale finale

Assessment criteria of knowledge

The student will be assessed on his/her demonstrated ability to discuss the main course contents using the appropriate terminology

Methods:

Final oral exam

Capacità

Gli studenti acquisiranno le conoscenze necessarie per partecipare alla ricerca nel campo della crittografia post-quantistica, e collaborare all'implementazione di algoritmi in questo campo, compresi algoritmi di crittanalisi.

Skills

The students will acquire the knowledges necessary to take part into research on post-quantum cryptography, and to cooperate to the implementation of algorithms in this domain, including cryptanalysis.

Modalità di verifica delle capacità

Verifica nel corso dell'esame orale finale, che comprenderà anche una breve relazione tecnica su un argomento a scelta

Assessment criteria of skills

Verification during the final oral exam, includeing a short technical presentation on a theme chosen by the student and a discussion of the contrnts of the lessons.

 

Comportamenti

Gli studenti sono consigliati a frequentare le lezioni e a studiare gli argomenti via via presentati, e, soprattutto in caso di impossibilità a frequentare, tenersi aggiornati con colloqui coi docenti.

Behaviors

Students are advised to follow the lessons, study the subjects discussed, and, especially if they cannot follow the lessons, keep themselves up to date meeting the teachers periodically.

Modalità di verifica dei comportamenti

Tramite colloqui durante le lezioni e i ricevimenti

Assessment criteria of behaviors

Through interaction during the lessons and periodical meetings

Prerequisiti (conoscenze iniziali)

I prerequisiti di aritmetica, fondamenti di algebra, algebra polinomiale, campi finiti, algebra lineare sono insegnati nei corsi del primo anno, e saranno comunque ripresi a lezione.

I prerequisiti necessari di carattere crittografico e algebro-geometrico insegnati in altri corsi saranno richiamati e saranno date precise indicazioni bibliografiche.

Prerequisites

The prerequisites of arithmetic, algebraic foundations, polynomial algebra, finite fields, linear algebra are taught in the courses of the first year of laurea, and will anyway be recalled.

The prerequisites of cryptography and algebraic geometry taught in other courses will be recalled with precise bibliographic informations.

Corequisiti

Il corso è indipendente da altri corsi, anche se sinergie sono possibili.

Co-requisites

The course is indipendent of other courses, although synergies are possible.

Prerequisiti per studi successivi

Indicazioni su studi utili per la continuazione delle ricerche illustrate nel corso saranno date a lezione o in documentazione resa disponibile.

Prerequisites for further study

Indications on further studies useful to forward the researches described in the course will be given inj the lessons, or through documentation provided.

Indicazioni metodologiche

Esame: orale

Frequenza: consigliata

Attività di insegnamento:

* Frequenza alle lezioni frontali

* Preparazione di esposti orali

* Studio individuale

Metodologia di Insegnamento:

* Lezioni frontali

Teaching methods

Delivery: face to face

Attendance: Advised

Learning activities:

  • attending lectures
  • preparation of oral report
  • individual study

 Teaching methods:

  • Lectures

 

Programma (contenuti dell'insegnamento)

1 Test di primalità e fattorizzazione (non-quantistica). Logaritmo discreto. Trasformata di Fourier rapida.

2 Curve ellittiche

3 Sicurezza crittografica: Inadeguatezza della teoria classica della complessità. IND-CPA, IND-CCA, ecc.

4 Crittografia pre-quantistica:
4.1 Crittografia simmetrica, hashing. DES, AES, SHA1, SHA2, Keccak (SHA-3)
4.2 Crittografia asimmetrica pre-quantistica: RSA, Diffie-Hellman, curve ellittiche: cifra, KEM, firma.
4.3 Successioni pseudo-casuali, zero-knowledge, autenticazione.

5 Calcolo quantistico e crittografia
5.1 Cenni sui modelli matematici di computer quantistici, e loro realizzazione.

5.2 Attacchi quantistici alla crittografia pre-quantistica: algoritmo di Shor, algoritmo di Grover (cenni).
5.3 Progetto NIST di standardizzazione della crittografia post-quantistica.

6 Alcuni Protocolli crittografici post-quantistici
6.1 Reticoli, LWE, NTRU e derivati
6.1.1 LLL e applicazioni; reticoli ridotti, SVP e CVP. BKZ.
6.1.2 Complessità generica dei problemi sui reticoli, dimostrazioni di sicurezza.
6.2 Codici di Goppa, McEliece e crittografia sui codici correttori
6.3 HFE e problemi derivati.
6.4 Polly Cracker e Lattice Polly Cracker
6.5 Merkle tree e firma digitale
6.6 SIKE: Isogenie di curve ellittiche supersingolari.

7 Conclusioni e prospettive

Syllabus

1 Primality tests and (non-quantum) factorization. Discrete logarithm. Fast Fourier Transform.

2 elliptic curves.

3 Cryptographic security: inadequacy of classic complexty, IND-CPA, IND-CCA, etc

4 Pre-quantum cryptography:
4.1 Symmetric cryptography, hashing. DES, AES, SHA!, SHA2, Keccak (SHA-3)
4.2 Pre-quantum asymmetric cryptography: RSA, Diffie-Hellmann. Elliptic curves: cipers, KEM, signature.
4.3 Pseudo-random sequences, zero-knowledge, authentication.

5 Quantum computing and cryptography
5.1 Outline of mathematical models of quantum computing, their implementation.
5.2 Quantum attacks to pre-quantum cryptography. Shor's and Grover's algorithms (outline).
5.3 NIST project of post-quantum cryptography standardization

6 Some post-quantum cryptographic protocols
6.1 Lattices, LWE, NTRU and variants
6.1.1 LLL and applications, reduced lattices, SVP, CVP. BKZ
6.1.2 Generic complexity of lattice problems, security proofs.
6.2 Goppa codes, McEliece, cryptography with error correcting codes
6.3 HFE and derived problems
6.4 Polly Cracker and Lattice Polly nCracker
6.5 Merkle trees and digital signatures
6.6 SIKE: isogenies of supersingular elliptic curves isogeny

7. Conclusions and perspectives.

Bibliografia e materiale didattico

N Koblitz A course in number theory and cryptography

N. Koblitz Algebraic aspects of cryptography

D Micciancio, S Goldwasser Complexity of lattice problems: a cryptographic perspective,

Post-quantum cryptography (D. Bernstein, J. Buchmann, E. Dahmen, eds.)

S. Goldwasser and M. Bellare Lecture Notes on Cryptography (MIT notes) https://cseweb.ucsd.edu/~mihir/papers/gb.html

Bibliography

N Koblitz A course in number theory and cryptography

N. Koblitz Algebraic aspects of cryptography

D Micciancio, S Goldwasser Complexity of lattice problems: a cryptographic perspective,

Post-quantum cryptography (D. Bernstein, J. Buchmann, E. Dahmen, eds.)

S. Goldwasser and M. Bellare Lecture Notes on Cryptography (MIT notes) https://cseweb.ucsd.edu/~mihir/papers/gb.html

Indicazioni per non frequentanti

Gli studenti sono invitati a colloqui coi docenti anche su appuntamento.

 

Non-attending students info

Students are invited to take part to meeting the teachers, also by individual appointment

Modalità d'esame

Esame orale finale.

Assessment methods

Final oral examination

Stage e tirocini

A richiesta, anche per conto di altri corsi.

Work placement

 Upon request, also for other courses. 

 

Pagina web del corso

http://barba.dm.unipi.it/PQC

Ultimo aggiornamento 27/09/2019 09:32