###
Question 59. What is Linear Cryptanalysis?

*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].