Cryptanalysis

This course is offered at the 2nd year of Master degree, at ENS de Lyon, and will take place in Fall 2019. This is a revised edition of a this course by Elena Kirshanova and Guillaume Hanrot, which took place in Fall 2018. Some scribe notes are available on the webpage of that first edition of the course.

General Information

Instructors:

Where: Typically, room B1

When: Wednesday, 1:30pm-3:30pm

Evaluation: Evaluation will take place at the end of December. If there are no more than 12 students, then 50% report on an article + 50% presentation of that article. If there are more students, then 50% report on an article + 50% written exam. This will be decided in mid-October.

Prerequisites (advisable but not mandatory):

Readings:

Tentative plan:

I. Brute-force algorithms:

  1. Information set decoding (ISD) algorithms: problem statement, Prange and Stern algorithms
  2. The LPN problem and the BKW algorithm
  3. The LWE problem and the Arora-Ge algorithm

II. Lattice algorithms:

  1. Introduction to lattices, sieving algorithm for the Shortest Vector Problem
  2. Lattice reduction algorithms: LLL and BKZ
  3. Coppersmith small-root algorithm for solving system of modular linear equantions. Applications to RSA: stereotype-messages, short-pad attack
  4. Coppersmith continued (for multivariate polynomials): Applications to RSA: small public-exponent, partial key-exposure
  5. Attack on sparse subset-sum (knapsack cryptosystem), algorithm for the hidden-number problem
  6. Learning a parallelepiped, or how to break the NTRU and GGH signatures (Nguyen-Regev)

III. Algorithmic Number Theory:

Schedule

Some handwritten notes are provided below in pdf. Use them with caution, at your own risk, I did not polish them nor removed the numerous bugs.
Week Class Topic Notes
11.09 Lattices and lattice sieving Lecture 1
18.09 Lattice sieving Lecture 2, see also this survey
25.09 More lattice background Lecture 3
02.10 The LLL and BKZ algorithms Lecture 4
09.10 Basic applications of LLL (factoring integers polynomials, simultaneous Diophantine approximations)
18.10 Univariate Coppersmith method
23.10 Multivariate Coppersmith method
06.11 Elementary factoring algorithms
13.11 Faster factoring algorithms
27.11 Information set decoding Lecture on ISD
02.12 Learning Parity with Noise and the BKW algorithm Lecture on LPN
04.12 Factoring algorithms
11.12 DLP algorithms
18.12 Learning With Errors and algorithms to solve it

Evaluation

Based on a report on an article and a homework (50% of the grade each).
When: Before January 15th, 23:59:00
Report:
Each student must choose one article from the proposed list and write a report of at most three pages.
The report should contain: a summary of the results, a summary of the techniques, and a contextualization of the result (based on prior and posterior results). You may choose to go into the details of one contribution of the paper, or stay at a general level. You should use critical sense to take out what you find most important and most interesting.
Homework: See later.

Articles for reports