Provable Security of Block Ciphers Against Linear Cryptanalysis - A Mission Impossible?
In this paper, the authors are concerned with the security of block ciphers against linear cryptanalysis and discuss the distance between the so-called practical security approach and the actual theoretical security provided by a given cipher. For this purpose, they present a number of illustrative experiments performed against small (i.e. computationally tractable) ciphers. They compare the linear probability of the best linear characteristic and the actual best linear probability (averaged over all keys). They also test the key equivalence hypothesis.