CdSMATEMATICA
Codice079AA
CFU6
PeriodoSecondo semestre
LinguaItaliano
Gli studenti avranno una conoscenza degli algoritmi e srumenti di base per i codici correttori e la crittografia, e una buoma base di partenza per ulteriori ricerche sul tema.
The students will have a knowledge of the basic algorithms and tools for ECC and cryptography, and have a sound starting basis for further investigations on the subject.
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
Riconoscere gli algoritmi e i protocolli appropriati per la comunicazione e l'autenticazione di documenti con affidabilità e confidenzialità.
Identify the proper algorithms and protocols for communication and authentication of documents with reliability and confidentiality
Verifica nel corso dell'esame orale finale, che comprenderà una breve relazione tecnica su un argomento a scelta
Verification during the final oral presentation, conteining a short technical presentation on a theme chosen by the student.
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.
Most prerequisites of arithmetics, basic algebra, polynomial algebra, finite fields. linear algebra are given in first year courses, and will be anyway recalled during the lessons.
Alcuni concetti utili sono insegnati nel corso di Algebra II, ma sono comunque ripresi a lezione.
Some useful concepts are taught in the course Algebra II, but are anyway explained in the lessons.
I temi di ricerca sulla crittografia post-quantistica sono critici per il futuro della crittografia (e i codici correttori ne sono un ingrediente essenziale) Parte del corso sarà dedicata ad una breve presentazione di alcuni di questi metodi.
The research themes on post-quantum cryptography are critical for the future of cryptography (and error correcting codes are an essential ingredient of this research). Part of the course will be devoted to a short presentation of these themes.
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
ARITMETICA
Complessità delle operazioni sugli interi: somma, prodotto, divisione, GCD. Karatsuba.
Complessità delle operazioni modulari: esponenziale. Radice quadrata su un campo finito: algoritmi di Cipolli e Tonelli-Shanks.
Equivalenza di radice quadrata modulo n composto e fattorizzazione di n.
Simbolo di Legendre e di Jacobi, reciprocità quadratica.
Test di primalità: Solovay-Strassen, Miller-Rabin, ricerca di numeri primi.
Fattorizzazione di polinomi su campi finiti. Rialzamento P-adico.
CODICI CORRETTORI
Codici lineari e trasmissione. MLD (Maximum Likelihood Decoding). Errori e cancellature, soft decoding. Lunghezza, distanza, dimensione.
Codici a blocchi e di convoluzione.
Esempi di codici: parità, ripetizione, codice duale. Codici accorciati, bucati, estesi, contratti. Codici di Hamming.
Matrice generatrice e di parità. Codici sistematici.
Diseguaglianze sui codici: Hamming, Singleton, Gilbert-Varshamov.
Codici ciclici, Reed-Müller, Reed-Solomon, BCH, Goppa, codici di convoluzione.
Decodifica dei codici: polinomio locatore, equazione chiave, maggioranza, Viterbi.
Esempio di uso dei codici: CD audio.
CRITTOGRAFIA
Algoritmi e protocolli crittografici. Cifratura, firma, identificazione, scambio di chiavi. Cifratura simmetrica e a chiave pubblica. Hash crittografico. Successioni pseudocasuali crittografiche.
Definizione di sicurezza crittografica: IND-CPA, IND-CCA, IND-CCA2. Zero-knowledge proof.
Protocolli crittografici: DES, AES. RSA, Diffie-Hellmann, El Gamal, DSS, Blum-Goldwasser, Merkle-Hellmann. Autenticazione: Fiat-Shamir, Fiat-Feige-Shamir.
ALGORITMI ARITMETICI E CRITTANALISI
Fattorizzazione degli interi: rho di Pollard, N-1, criterio di Fermat, crivelli, crivello quadratico.
Logaritmo discreto: baby step-giant step, rho, Pohlig-Hellmann, basi di fattori.
CURVE ELLITTICHE E CRITTOGRAFIA
Curve ellittiche, fattorizzazione tramite curve ellittiche.
Crittografia su curve ellittiche.
ALGEBRA LINEARE INTERA
Algebra lineare sugli interi, reticoli. Vettore più corto, vettore più vicino. Teorema di Minkowski. Basi ridotte. Algoritmi di Babai.
LLL, fattorizzazione dei polinomi a coefficianti interi tramite reticoli.
Crittanalisi tramite LLL.
CALCOLO QUANTISTICO E CRITTOGRAFIA POST QUANTISTICA (cenni)
Cenni sul Calcolo quantistico e sugli algoritmi di Shor e Grover.
Cenni di crittografia post-quantistica. Standardizzazione di protocolli post-quantistici del NIST.
Alcuni esempi: reticoli, LWE, NTRU, HFE, McEliece-Niederreiter e possibilmente altri.
Complexity of integer operations: sum, product, division, GCD. Karatsuba multiplication.
Complexity of modular operations: exponential. Square root on a field.
Equivalence between square root modulo n composit and factorization of n.
Legendre and Jacobi symbols, quadratic reciprocity.
Primality tests: Solovay-Strassen, Miller-Rabin, search for prime numbers.
Factorization of polynomials on finite fields. P-adic lifting.
ERROR CORRECTING CODES
Linear codes and transmission. MLD (Maximum Likelihood Decoding). Errors and erasures, soft decoding. Length, distance, dimension.
Block and convolution codes.
Examples: parity, repetition, dual code. Shortened, punctured, extended, contracted codes. Hamming codes.
Generating and parity matrix, systematic codes.
Code inequalities: Hamming, Singleton, Gilbert-Varshamov.
Cyclic codes, Reed-Müller, Reed-Solomon, BCH, Goppa, convolution codes.
Decoding: error locator, key equation, majority, Viterbi.
Examples of code use: audio CD.
CRYPTOGRAPHY
Cryptographic algorithms and protocols. Cipher, signature, identification, key exchange. Symmetric, public key cryptography, cryptographic hashing. Cryptographic pseudo-random sequences.
Cryptographic definition of security: IND-CPA, IND-CCA, IND-CCA2. Zero-knowledge proofs.
Some cryptographic protocols: DES, AES, RSA, Diffie-Hellmann, El Gamal, DSS, Blum-Goldwasser, Merkle-Hellmann. Authentication: Fiat-Shamir, Feige-Fiat-Shamir.
ARITHMETIC ALGORITHMS AND CRYPTANALYSIS
Integer factorization: Pollard's rho, N-1, Fermat criterion, sieves, quadratic sieve.
Discrete logarithm: baby step-giant step, rho, Pohlig-Hellmann, factor bases.
ELLIPTIC CURVES IN CRYPTOGRAPHY
Elliptic curves, use in factorization.
Elliptic curve cryptography.
INTEGER LINEAR ALGEBRA
Integer linear algebra, lattices. Shortest and nearest vector problem. Minkowski theorem. Reduced bases. Babai algorithms.
LLL, factorization of integer polynomial through lattices.
LLL in cryptanalysis.
QUANTUM COMPUTING AND POST-QUANTUM CRYPTOGRAPHY (outline)
Outline on quantum computing and Shor and Grover algorithms.
Outline on post-quantum cryptography. NIST standardization of post-quantum protocols.
Examples: lattices, LWE, NTRU, HFE, McEliece-Niederreiter and maybe others.
Letture consigliate di parti di:
D. G. Hoffman D. A. Leonard C. C. Lidner K. T. Phelps C. A. Rodger Coding Theory: The Essentials
H. J. van Lint Introduction to Coding Theory
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
Recommended reading includes selections from the following works:
D. G. Hoffman D. A. Leonard C. C. Lidner K. T. Phelps C. A. Rodger Coding Theory: The Essentials
H. J. van Lint Introduction to Coding Theory
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 meet with the teachers, also by appointment.
Esame orale finale.
Final oral exam
A richiesta, anche per conto di altri corsi.
Upon request, also for other courses.
https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
https://csrc.nist.gov/Projects/Post-Quantum-Cryptography