Linear Cryptanalysis in the Fixed-Key Model


The theory of linear cryptanalysis is revisited and generalized in light of recent developments in symmetric-key cryptography. Trade-offs in the design of lightweight cryptographic primitives have enabled new attacks such as block cipher invariants, and have renewed the interest in long-standing problems such as the effective use of nonlinear approximations in cryptanalysis. These developments are intrinsically related to linear cryptanalysis in the weak key model. In addition, permutation-based cryptography – which is based on keyless primitives – is gaining traction. In response to these urgent tendencies, the present thesis develops a pervasive generalization of linear cryptanalysis. The proposed “geometric approach” enables a uniform treatment of many variants of the classical linear attack and is suitable for use in the keyless and weak key models of analysis. The new framework additionally facilitates novel extensions to linear cryptanalysis. Furthermore, it is applied to resolve problems related to the use of nonlinear approximations. As a further contribution, the problem of proving security against linear cryptanalysis is revisited in the weak key model.

The full text can be downloaded here.

Source code:

Errata for the printed version: