# Cryptanalysis

## General Information

Instructors:

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"

## Exam

When: 15th of January 2019
Where: TBA
Rules:
Each student must choose one article from the proposed list and prepare an oral presentation.
Each student has 20 minutes for the presentation + 20 minutes for questions.
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
There is no template, use whatever you want (LaTex, PowerPoint, etc.) At the end of the presentation, the examiners will ask question(s) on the course material.

## Schedule

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