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.
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):
- S.D. Galbraith "Mathematics of Public Key Cryptography"
- A. Joux "Algorithmic Cryptanalysis"
- J. Hoffstein, J.Pipher, J.H.Silverman "An Introduction to Mathematical Cryptography"
I. Brute-force algorithms:
- Information set decoding (ISD) algorithms: problem statement, Prange and Stern algorithms
- The LPN problem and the BKW algorithm
- The LWE problem and the Arora-Ge algorithm
II. Lattice algorithms:
- Introduction to lattices, sieving algorithm for the Shortest Vector Problem
- Lattice reduction algorithms: LLL and BKZ
- Coppersmith small-root algorithm for solving system of modular linear equantions. Applications to RSA: stereotype-messages, short-pad attack
- Coppersmith continued (for multivariate polynomials): Applications to RSA: small public-exponent, partial key-exposure
- Attack on sparse subset-sum (knapsack cryptosystem), algorithm for the hidden-number problem
- Learning a parallelepiped, or how to break the NTRU and GGH signatures (Nguyen-Regev)
III. Algorithmic Number Theory:
- Algorithms for factoring:
- Pollard's (p-1) method, Pollard rho ; group-based method: Pollard p-1, p+1 (?), Lenstra's ECM
- Quadratic sieve, review of state-of-the art (NFS)
- Algorithms for discrete logarithm :
- Shanks' baby-step giant-step; Pollard rho;
- Lower bounds in a generic group
- Index calculus method. Review of state of the art (large, medium, small char).
- Short vectors in ideal lattices
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.
|| Lattices and lattice sieving
|| Lecture 1
|| Lattice sieving
|| Lecture 2, see also this survey
|| More lattice background
|| Lecture 3
|| The LLL and BKZ algorithms
|| Lecture 4
|| Basic applications of LLL (factoring integers polynomials, simultaneous Diophantine approximations)
|| Univariate Coppersmith method
|| Multivariate Coppersmith method
|| Elementary factoring algorithms
|| Faster factoring algorithms
|| Information set decoding
|| Lecture on ISD
|| Learning Parity with Noise and the BKW algorithm
|| Lecture on LPN
|| Factoring algorithms
|| DLP algorithms
|| Learning With Errors and algorithms to solve it
Based on a report on an article and a homework (50% of the grade each).
When: Before January 15th, 23:59:00
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
M. R. Albrecht. On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEALJulien Devevey
M. R. Albrecht, C. Cid, J.-C. Faugère, R. Fitzpatrick, L. Perret. Algebraic algorithms for LWEHerménégilde Valentin
M. R. Albrecht, L. Ducas, G. Herold, E. Kirshanova, E. W. Postlethwaite, M. Stevens. The general sieve kernel and new records in lattice reductionFabrice Lecuyer
- M. R. Albrecht, F. Göpfert, F. Virdia, T. Wunderer. Revisiting the expected cost of solving uSVP
and applications to LWE
R. Barbulescu, P. Gaudry, A. Joux, E. Thomé. A quasi-polynomial algorithm for discrete
logarithm in finite fields of small characteristicDenis Rochette
D. J. Bernstein, Y.-A. Chang, C.-M. Cheng, L.-P. Chou, N. Heninger. Factoring RSA keys from certified smart cards: Coppersmith in the wildSébastien Michelland
D. J. Bernstein, T. Lange, C. Peters. Smaller decoding exponents: ball-collision decodingUgo Giocanti
- J. Bi, J.-S. Coron, J.-C. Faugère, P. Q. Nguyen, G. Renault, R. Zeitoun. Rounding and chaining LLL: finding faster small roots of univariate polynomial congruences
R. P. Brent, A. Kruppa, P. Zimmermann FFT extension for algebraic-group factorization algorithms Léo Paviet Salomon
- Y. Chen, P. Q. Nguyen. BKZ 2.0: better lattice security estimates
J.-S. Coron. Finding Small roots of bivariate integer polynomial equations revisitedEmile Hohnadel
J.-S. Coron and A. May. Deterministic polynomial time equivalence of computing the RSA secret key and factoringFlorent Guépin
R. Cramer, L. Ducas, C. Peikert, O. Regev. Recovering short generators of principal ideals in cyclotomic ringsThéophile Dubuc
- R. Cramer, L. Ducas, B. Wesolowski. Short Stickelberger class relations and application to Ideal-SVP
- A. Esse, F. Heuer, R. Kübler, A. May, C. Sohöler. Dissection-BKW
S. D. Galbraith, J. M. Pollard, R. S. Ruprai. Computing discrete logarithms in an interval Quentin Deschamps
- P. Gaudry. An algorithm for solving the discrete log problem on hyperelliptic curves
- P. Gaudry, E. Thomé, N. Thériault, C. Diem. A double large prime variation for small genus hyperelliptic index calculus
E. Kirshanova, E. Martensson, E. W. Postlethwaite, S. R. Moulik. Quantum algorithms for the approximate k-list problem and their application to lattice sievingHadrien Brochet
- B. A. LaMacchia, A. M. Odlyzko. Computation of discrete logarithms in prime fields
A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard. The factorization of the ninth Fermat numberSamuel Humeau
- U. Maurer, S. Wolf. The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms
R. Montenegro, P. Tetali. How long does it take to catch a wild kangaroo? Lison Blondeau
P. M. Montgomery. Speeding the Pollard and elliptic curve methods of factorizationHugues Déprés
P. Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto ’97Krishna Acharya
P. C. van Oorschot, M. J. Wiener. Parallel collision search with cryptanalytic applicationsRémy Neveu
E. Teske. On random walks for Pollard's rho methodOijid Nacim
- J. Xu, S. Sarkar, L. Hu, H. Wang, Y. Pan. New results on modular inversion hidden number
problem and inversive congruential generator
Y. Yu, L. Ducas. Learning strikes again: the case of the DRS signature schemeJulien Du Crest