PhD in Pure and Applied Mathematics

An introduction to Isogeny-based Cryptography

An introduction to Isogeny-based Cryptography

Academic year 2020/2021

Sommario del corso

• Program
• Teaching tools
• Course card

Program

• From/to: 14/01/2021 - March 2021
  
  
• Number of hours​: 30​ ​(4 hours per week - Tuesday from 10.30am to 12:30pm, Thursday from 11am to 1pm).
  
  
• Credits: 6 CFU
  
  
• Prerequisites​: Basic notions on big-o notation, complexity classes, finite fields
  
  
• Contacts: federico(dot)pintore(at)gmail(dot)com 

Program

Lecture 1

• Modern Cryptography: security definitions, provable security and hard mathematical problems
• Symmetric-key Encryption: computational indistinguishability, CPA-security, CCA-security
• Key-exchange protocols: security in the presence of an eavesdropper
• Public-key Encryption: CPA-security and CCA-security 

Lecture 2

• Key Encapsulation Mechanisms: CPA and CCA-security
• Hybrid encryption and its security
• The Random Oracle Model
• OW-PCA-, OW-CPA-,OW-VA- and OW-PCVA-security for public-key encryption
• Modular transformations that turn a public-key encryption scheme into a CCA-secure KEM, and their security

Lecture 3

• Digital signatures and existential unforgeability
• Three-move Interactive Identification protocols: special soundness, HVZK, Perfect Unique Response, Commitment Revocability
• The Fiat Shamir transform

Lecture 4

• The Discrete Logarithm Problem: Pohlig-Hellman algorithm, Baby-step/Giant-step method, Pollard's Rho Algorithm
• Group of points of elliptic curves: morphisms, isomorphisms, short Weierstrass form, the group law
• The ECDLP and its difficulty
• (Sketch of) Shor's algorithm

Lecture 5                                                                                                                               

• Isogenies between elliptic curves
• Example: multiplication-by-2 map
• Standard form for isogenies
• Degree of an isogeny
• Kernel of an isogeny from its standard form
• Separable and inseparable isogenies

Lecture 6

• Frobenius endomorphism
• Every isogeny is the composition of powers of the Frobenius endomorphism and a separable isogeny
• Separable and inseparable degree of an isogeny
• The separable degree coincides witht the order of the kernel
• Every finite subgroup G determines a unique isogeny with G as kernel
• Division polynomials and the multiplication-by-n map
• Ordinary and supersingular elliptic curves

Lecture 7

• The j-invariant
• Isomorphism between elliptic curves in Weierstrass form
• j-invariants and isomorphisms
• Every isogeny can be written as the composition of prime-degree isogenies
• The dual isogeny and its properties
• Supersingular elliptic curves have j-invariants in F_p²
• Supersingular j-invariants
• Hasse theorem; Waterhouse theorem; Tate theorem

Lecture 8

• Number of nodes of the subgraphs of G_l(F_p²,t), with t in {0,p,-p,-2p,2p}
• Quadratic twists
• Isomorphism between G_l(F_p²,-2p), G_l(F_p²,2p) and G_l over the algebraic closure of F_p²
• Non regularity of G_l(F_p²,2p), with an example
• Public parameters for SIDH and the derived schemes

Lecture 9

• Supersingular-Isogeny Diffie-Hellman (SIDH)
• SIDH-based encryption and identification protocol
• Offline efficiency (pre-computation): choice of the prime p, the curve E, and the basis {P_A,Q_A} and {P_B,Q_B}
• Online efficiency: cyclic isogenies of prime-power degree as composition of prime-degree isogenies; Velu's formulas for prime-degree isogenies
• Example: 2-isogenies from the j-invariant 1728

Lecture 10
- Compressed public keys
- SIKE and its state of the art implementation
- B-SIDH

Lecture 11
- SIDH-based digital signatures
- Unruh transformation
- Open problems: ring/group signatures? other zero-knowledge proofs?

Lecture 12
- The subring of endomorphisms defined over a base prime field
- Quadratic fields, orders and ideal class groups
- Class group action and CSIDH

Lecture 13
- Parallelization and vectorization problem, and their quantum equivalence
- Classical and quantum attacks
- CSIDH on the surface

Lecture 14
- Sea-sign and its improvements
- CSI-FiSh
- Lossy CSI-FiSh

Lecture 15
- Ring signatures
- Threshold signatures
- Open problems

• Teaching material
• Exams and finals
• Class schedule
• Go to Moodle
• Register for the course
• Enrolled students
• Invia email agli studenti registrati
• Export table