Linear cryptanalysis

This course is an introduction to the security analysis (cryptanalysis) of symmetric-key cryptography. Instead of giving a broad overview, the approach followed by the course is to focus exclusively on one technique, linear cryptanalysis, and to cover it at an advanced level. The course is organized as Capita Selecta Mathematical Engineering A (H08K8A) and counts for 3 ECTS.

The course consists of 11 lectures, accompanied by three exercise sessions. Dates and contents of the lectures and exercise sessions:

Date	Time	Room	Title	Teacher
03/10	14:00-15:55	200D 05.11	Introduction	Vincent Rijmen
10/10	14:00-15:55	200D 05.11	Correlation matrices	Vincent Rijmen
16/10	14:00-15:55	200D 06.34	Exercises for Chapters 1 and 2	Tim Beyne
17/10	14:00-15:55	200D 05.11	Optimization of linear trails	Tim Beyne
24/10	14:00-15:55	200D 05.11	Statistics of linear cryptanalysis	Vincent Rijmen
31/10			Fall break
06/11	14:00-15:55	200D 06.34	Exercises for Chapters 3 and 4	Tim Beyne
07/11	14:00-15:55	200D 05.11	Key-recovery techniques	Tim Beyne
14/11	14:00-15:55	200D 05.11	Multiple linear cryptanalysis	Tim Beyne
21/11	14:00-15:55	200D 05.11	Optimal statistical methods	Tim Beyne
28/11	14:00-15:55	200D 05.11	Zero-correlation approximations	Vincent Rijmen
04/12	14:00-15:55	200D 06.34	Exercises for Chapters 5 to 8	Tim Beyne
05/12	14:00-15:55	200D 05.11	Miscellaneous extensions	Vincent Rijmen
12/12	14:00-15:55	200D 05.11	Functions on finite Abelian groups	Tim Beyne
19/12	14:00-15:55	200D 05.11	Geometric approach	Tim Beyne
25/01	08:00-11:00	ELEC 00.54	Examination

Outcomes: At the end of the course, it is expected that students will:

Have a solid understanding of the theory of linear cryptanalysis and its description using correlation matrices
Be able to apply linear cryptanalysis in practice (for the purpose of designing a new cipher, or breaking an existing one), with the help of optimization tools (MILP/SAT/SMT solvers).
Be familiar with the most important extensions of linear cryptanalysis: multiple and multidimensional linear cryptanalysis, zero-correlation linear cryptanalysis.
Be aware of the geometric approach to linear cryptanalysis and its applications to advanced extensions such as invariants and nonlinear approximations.
Be able to learn about other techniques (such as integral and differential cryptanalysis) by reading the academic literature.

Applications: The course touches several subjects that themselves have many other applications outside of cryptography:

Combinatorial optimization (tree search, SAT/SMT, MILP).
Optimal hypothesis testing (Neyman-Pearson, Kullback-Leibler divergence).
Fourier analysis of functions on finite Abelian groups

Evaluation: The exam is written with oral clarification and will consist of exercises and (a smaller number of) knowledge questions. A second examination moment will be organized in the third examination period for students who did not pass on the first attempt.