View syllabus
POST-QUANTUM CRYPTOGRAPHY
EMMANUELA ORSINI
Academic year2021/22
CourseMATHEMATICS
Code703AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
CRITTOGRAFIA POST-QUANTISTICAMAT/02LEZIONI42
PATRIZIA GIANNI unimap
EMMANUELA ORSINI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

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.

Knowledge

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.

Modalità di verifica delle conoscenze

Si valuterà l'abilità dello studente di discutere con competenza e chiarezza i contenuti principali del corso.

Modalita'

* Esame orale finale

Assessment criteria of knowledge

The student will be assessed on their 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, including a short technical presentation on a theme chosen by the student and a discussion of the contents of the lectures.

Comportamenti

Gli studenti sono consigliati a frequentare le lezioni e a studiare gli argomenti via via presentati.

Behaviors

Students are advised to follow the lessons, study the subjects discussed

Modalità di verifica dei comportamenti

Nessuna

Assessment criteria of behaviors

None

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 bachelor, 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.

Programma (contenuti dell'insegnamento)

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

Syllabus

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

Bibliografia e materiale didattico

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

Bibliography

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

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

Assessment methods

Final oral examination

Stage e tirocini

A richiesta, anche per conto di altri corsi

Work placement

Upon request, also for other courses. 

Updated: 15/09/2021 11:58