CdSMATEMATICA
Codice703AA
CFU6
PeriodoSecondo semestre
LinguaItaliano
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.
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.
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
The student will be assessed on his/her demonstrated ability to discuss the main course contents using the appropriate terminology
Methods:
* Final oral exam
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.
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.
Verifica nel corso dell'esame orale finale, che comprenderà anche una breve relazione tecnica su un argomento a scelta
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.
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.
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.
Tramite colloqui durante le lezioni e i ricevimenti
Through interaction during the lessons and periodical meetings
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.
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.
Il corso è indipendente da altri corsi, anche se sinergie sono possibili.
The course is indipendent of other courses, although synergies are possible.
Indicazioni su studi utili per la continuazione delle ricerche illustrate nel corso saranno date a lezione o in documentazione resa disponibile.
Indications on further studies useful to forward the researches described in the course will be given inj the lessons, or through documentation provided.
Esame: orale
Frequenza: consigliata
Attività di insegnamento:
* Frequenza alle lezioni frontali
* Preparazione di esposti orali
* Studio individuale
Metodologia di Insegnamento:
* Lezioni frontali
Delivery: face to face
Attendance: Advised
Learning activities:
- attending lectures
- preparation of oral report
- individual study
Teaching methods:
- Lectures
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
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.
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
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
Gli studenti sono invitati a colloqui coi docenti anche su appuntamento.
Students are invited to take part to meeting the teachers, also by individual appointment
Esame orale finale.
Final oral examination
A richiesta, anche per conto di altri corsi.
Upon request, also for other courses.