Universite Bordeaux 1
In this paper, the authors report on an improvement of matsui's linear cryptanalysis that reduces the complexity of an attack with algorithm 2, by taking advantage of the fast fourier transform. Using this improvement, the time complexity decreases from O (2k x 2k) to O (k x 2k), where k is the number of bits in the key-guess. This improvement is very generic and can be applied against a broad variety of ciphers including SPN and feistel schemes. In certain (practically meaningful) contexts, it also involves a reduction of the attacks data complexity (which is usually the limiting factor in the linear cryptanalysis of block ciphers).