Vai al contenuto principale
Coronavirus: aggiornamenti per la comunità universitaria / Coronavirus: updates for UniTo Community

An introduction to Isogeny-based Cryptography


An introduction to Isogeny-based Cryptography


Academic year 2020/2021

Federico Pintore (Lecturer)
Teaching period
Course disciplinary sector (SSD)
INF/01 - informatics
MAT/02 - algebra
MAT/03 - geometry
Formal authority
Type of examination

Sommario del corso



  • 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 


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 Fp2
  • Supersingular j-invariants
  • Hasse theorem; Waterhouse theorem; Tate theorem

Lecture 8

  • Number of nodes of the subgraphs of Gl(Fp2,t), with t in {0,p,-p,-2p,2p}
  • Quadratic twists
  • Isomorphism between Gl(Fp2,-2p), Gl(Fp2,2p) and Gl over the algebraic closure of Fp2
  • Non regularity of Gl(Fp2,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 {PA,QA} and {PB,QB}
  • 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

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

Suggested readings and bibliography

Last update: 20/02/2021 09:35
Non cliccare qui!