CdSMATEMATICA
Codice703AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
Gli studenti acquisiranno le conoscenze relative ai concetti di base della crittografia moderna e degli attacchi crittografici derivanti dal potenziale sviluppo di grandi computer quantistici, e sui protocolli crittografici che sembrano essere più resistenti agli attuali attacchi quantistici.
A tal fine, illustreremo gli attacchi di Shor e Grover, e come il primo renda completamente insicuri tutti i sistemi crittografici a chiave pubblica in uso.
Illustreremo poi alcuni protocolli che resistono all'algoritmo di Shor, in particolare quelli considerati dall'attuale progetto di standardizzazione di crittografia post-quantistica del NIST, attualmente in fase di sviluppo.
Descriveremo i risultati matematici su cui si basano questi protocolli e gli algoritmi utilizzati per attaccarli. Studieremo principalmente algoritmi sui reticoli, codici correttori di errore e curve ellittiche.
The students will acquire the knowledges relative to the basic concepts of modern cryptography and 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 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 particular 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 used to attack them. In particular, we will study algorithms on lattices, error correcting codes, multivariate polynomial systems, and elliptic curves.
Si valuterà l'abilità dello studente di discutere con competenza e chiarezza i contenuti principali del corso.
Modalita'
* Esame orale finale
The student will be assessed on their 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, including a short technical presentation on a theme chosen by the student and a discussion of the contents of the lectures.
Gli studenti sono consigliati a frequentare le lezioni e a studiare gli argomenti via via presentati.
Students are advised to follow the lessons, study the subjects discussed
Nessuna
None
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 bachelor, 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.
INTRODUZIONE ALLA CRITTOGRAFIA MODERNA
- Sicurezza incondizionata vs sicurezza computazionale, crittografia simmetrica, funzioni unidirezionali, PRF e PRG, funzioni hash
- Crittografia a chiave pubblica. Sicurezza CPA/CCA. Diffie-Hellman, RSA, Curve ellittiche
- Firme digitali, definizione di sicurezza
- Dimostrazioni a conoscenza zero
ARITMETICA
- Teorema dei numeri primi. Il simbolo di Lagrange. Criterio di Eulero. Reciprocita' quadratica. Simbolo di Jacobi . Radice quadrata su un campo finito: algoritmi di Cipolla e Tonelli-Shanks.
- Test di primalita': pseudoprimi. Pseudoprimi di Eulero, pseudoprimi forti. Test di Miller Rabin. Fattorizzazione di interi: algoritmo Rho di Pollard. Fattorizzazione di interi: algoritmi di Fermat, di Dixon e Crivello quadratico. Logaritmo discreto
CALCOLO QUANTISTICO
- Introduzione al calcolo quantistico. Qubits. Quantum circuits. Modelli di calcolo. Quantum Gates.
- Trasformata di Fourier quantistica. Algoritmo per il calcolo della fase, algoritmo per il calcolo di un autovalore, algoritmo per il calcolo dell'ordine di un elemento
- Algoritmo di Shor: fattorizzazione e logaritmo discreto. Algoritmo di Grover
CRITTOGRAFIA POST-QUANTISTICA
- Progetto NIST di standardizzazione della crittografia post-quantistica
- Reticoli, geometria dei reticoli,problemi difficili su reticoli (SVP, CVP, LWE, NTRU), LLL e applicazioni, BKZ. Esempi di schemi.
- Codici correttori d'errore: codici lineari, codici ciclici, codici Goppa, McEliece e altri schemi. Codici quantistici, Reed-Muller.
- Isogenie: scambio di chiavi, CRS, SIDH e SIKE
- Schemi basati su primitive simmetriche: PICNIC
CONCLUSIONI E PROSPETTIVE
INTRODUCTION TO MODERN CRYPTOGRAPHY
- Information-theoretic vs computational security,
- Symmetric encryption, public-key encryption and digital signatures, hash functions;
- Security definitions and security models;
- Zero-knowledge schemes
ARITHMETIC
- Diffie-Hellman, RSA, Elliptic curves
- Primality testing and factoring
- Discrete logarithms
QUANTUM COMPUTING
- Introduction to quantum computing. Quantum circuits. Quantum Gates. Pauli's Gates. Boolean gates simulation. XOR. Controlled gates. Toffoli gate. Deutsch-Josza algorithm.
- Quantum Fast Fourier Transform
- Shor’s algorithm. Grover's algorithm
POST-QUANTUM CRYPTOGRAPHY
- Lattice-based constructions: lattices, hard problems on lattices (SVP, CVP, LWE, NTRU), LLL and applications, BKZ. Examples of schemes.
- Code-based constructions: linear codes, cyclic codes, Goppa codes, McEliece and other schemes. Quantum codes, Reed-Muller
- Isogeny-based constructions: mathematics of isogeny-based cryptography, CRS, SIDH, CSIDH
- Schemes based on symmetric primitives: PICNIC
CONCLUSIONS AND PERSPECTIVES
Note e slides
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
J. Silverman, The Arithmetic of Elliptic Curves
J. Katz and Y. Lindell, Introduction to Modern Cryptography
N. Smart, Cryptography Made Simple
Lectures notes and slides
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
J. Silverman, The Arithmetic of Elliptic Curves
J. Katz and Y. Lindell, Introduction to Modern Cryptography
N. Smart, Cryptography Made Simple
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
Final oral examination
A richiesta, anche per conto di altri corsi
Upon request, also for other courses.