Linear cryptanalysis was first devised by Matsui and Yamagishi [MY92] in an attack on FEAL (see Question 79). It was extended by Matsui [Mat93] to attack DES (see Question 64). Linear cryptanalysis is a known plaintext attack (see Question 63) and uses a linear approximation to describe the behavior of the block cipher. Given sufficient pairs of plaintext and corresponding ciphertext, bits of information about the key can be obtained and increased amounts of data will usually give a higher probability of success.
There have been a variety of enhancements and improvements to
the basic attack. Langford and Hellman
[LH94] introduced an attack
called differential-linear cryptanalysis which combines
elements of differential cryptanalysis
(see Question 58) with
those of linear cryptanalysis. Also, Kaliski and Robshaw
[KR94]
showed that a linear cryptanalytic attack using multiple approximations
might allow for a reduction in the amount of data required for
a successful attack. Other issues such as protecting ciphers against
linear cryptanalysis have been considered by Nyberg
[Nyb95], Knudsen
[Knu93], and O'Conner [Oco95].