Cryptanalysis

General Information

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"

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.

Articles for presenations

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^r q for Large 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]

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