** Instructors: **

- Part I: Elena Kirshanova
- Part II: Guillaume Hanrot

** Where: ** Amphi B, Monod

** When: ** Tuesdays, 15h45-17h45

** Evaluation: ** 50% scribe + 50% article presentation

** Template: ** Please use this template for your scribe

** Prerequisites (advisable but not mandatory): **

** Reading: **

- A.May, Lecture 'Kryptanalyse Teil II' (in German)
- J. Hoffstein, J.Pipher, J.H.Silverman "An Introduction to Mathematical Cryptography"
- S.D. Galbraith "Mathematics of Public Key Cryptography"
- A.Joux "Algorithmic Cryptanalysis"

Each student must choose one article from the proposed list and prepare an oral presentation.

Each student has

In the presentation you should

- put the result in the context of the course material (relevance of the result)
- explain the main technical contribution of the article
- summarize the result(s) of the article

- I. Dinur, O. Dunkelman, N. Keller, Adi Shamir
*Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems***[Tymofii Prokopenko]** - L. Minder, A. Sinclair
*The extended k-tree algorithm***[Ta Duy-Hoang]** - D. Aggarwal, P. Mukhopadhyay
*Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm***[Purohit Nidhi]** - S. D. Galbraith, S. W. Gebregiyorgis, S. Murphy
*Algorithms for the Approximate Common Divisor Problem***[Pierre Meyer]** - P. Nguyen, J. Stern
*The Hardness of the Hidden Subset Sum Problem and Its Cryptographic Implications***[Daniel Szilagyi]** - D. Boneh, G. Durfee, N. Howgrave-Graham Factoring
*N=p*for Large^{r }q*r***[François Pitois]** - J-S. Coron Finding Small Roots of Bivariate Integer
Polynomial Equations Revisited
**[Caroline Brosse]** - R. P. Brent, A. Kruppa, P. Zimmermann FFT extension for algebraic-group factorization algorithms
- M.Case A Beginner’s Guide To The General Number Field Sieve
**[Joël Felderhoff]** - B. A. LaMacchia, A. M. Odlyzko Computation of Discrete Logarithms in Prime Fields
- I. Duursma, P. Gaudry, F. Morain Speeding up the discrete log computation on curves with automorphisms
**[Robin Vacus]**

Week | Class Topic | Sources | Scribe | |
---|---|---|---|---|

11.09 | The subset sum problem. Schroeppel-Shamir algorithm | N.Howgrave-Graham, A.Joux New Generic Algorithms for Hard Knapsacks | Lecture 1 | |

18.09 | The k-list problem. An algorithm for dense subset sum | D.Wagner A generalized birthday problem V.Lyubashevsky On Random High Density Subset Sums |
Lecture 2 | |

25.09 | The Learning Parity with Noise (LPN) problem. The BKW algorithm for LPN. | A.Blum, A.Kalai, H.Wasserman Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model | Lecture 3 | |

02.10 | NO LECTURE | |||

09.10 | NO LECTURE | |||

17.10 | Information Set Decoding. The representation technique | A. May, A. Meurer, A. Thomae Decoding Random Linear Codes in \softO(2^{0.054n}) | Lecture 4 | |

23.10 | Euclidean lattices. An algorithm for low density subset sum | M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr An Improved Low-Density Subset Sum Algorithm | Lecture 5 | |

24.10 | Coppersmith method (univariate) | D. Coppersmith Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities | Lecture 6 | |

30.10 | VACATIONS | |||

06.11 | Coppersmith method (bivariate) | D. Coppersmith Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known | Lecture 7 | |

13.11 | Research School | |||

20.11 | Integer Factoring Algorithms I | Deterministic factoring, Pollard-rho, (p-1) Pollard | Lecture 8 | |

27.11 | Research School | |||

04.12 | Integer Factoring Algorithms II | (p+1) Method, ECM, Congruence-based methods (Dixon, quadratic sieve) | Lecture 9 | |

11.12 | The Dlog Problem I | Lecture 10 | ||

18.12 | The Dlog Problem II | Lecture 11 |