Scheda programma d'esame
TEORIA DEI CODICI E CRITTOGRAFIA
CARLO TRAVERSO
Anno accademico2018/19
CdSMATEMATICA
Codice079AA
CFU6
PeriodoSecondo semestre
LinguaItaliano

ModuliSettore/iTipoOreDocente/i
TEORIA DEI CODICI E CRITTOGRAFIAMAT/02LEZIONI48
PATRIZIA GIANNI unimap
CARLO TRAVERSO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

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.

Knowledge

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.

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à

Riconoscere gli algoritmi e i protocolli appropriati per la comunicazione e l'autenticazione di documenti con affidabilità e confidenzialità.

Skills

Identify the proper algorithms and protocols for communication and authentication of documents with reliability and confidentiality

Modalità di verifica delle capacità

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

Assessment criteria of skills

Verification during the final oral presentation, conteining a short technical presentation on a theme chosen by the student.

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. 

Prerequisites

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.

Corequisiti

Alcuni concetti utili sono insegnati nel corso di Algebra II, ma sono comunque ripresi a lezione.

Co-requisites

Some useful concepts are taught in the course Algebra II, but are anyway explained in the lessons.

Prerequisiti per studi successivi

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.

Prerequisites for further study

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.

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)

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.

Syllabus

 

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.

Bibliografia e materiale didattico

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

Bibliography

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

 

 

Indicazioni per non frequentanti

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

Non-attending students info

Students are invited to meet with the teachers, also by appointment.

Modalità d'esame

Esame orale finale.

Assessment methods

Final oral exam

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/CCC

Altri riferimenti web

https://csrc.nist.gov/Projects/Post-Quantum-Cryptography

Additional web pages

https://csrc.nist.gov/Projects/Post-Quantum-Cryptography

Ultimo aggiornamento 11/10/2018 06:27