Linear cryptanalysis is an extremely important consideration when evaluating the security of symmetric primitives. After its introduction by Matsui in 1993, it has been largely extended and improved, and it has led to attacks on multiple ciphers. One of these developments is the proposal in 2007 by Collard et al. of an acceleration of the key-recovery part of Algorithm~2 for last-round attacks based on the FFT.
We now introduce a generalized, matrix-based version of this algorithm which easily allows to take into consideration an arbitrary number of key-recovery rounds.  We have also constructed efficient variants which exploit the key schedule and are compatible with multiple linear attacks.
As an example of application, we provide some new attacks on PRESENT, including the first on 28 rounds.