Improving the Time Complexity of Matsui's Linear Cryptanalysis

Download Now
Provided by: Universite Bordeaux 1
Topic: Security
Format: PDF
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).
Download Now

Find By Topic