Editing Linear cryptanalysis (section)

{{Short description|Form of cryptanalysis}}
In [[cryptography]], '''linear cryptanalysis''' is a general form of [[cryptanalysis]] based on finding [[affine transformation|affine]] approximations to the action of a [[cipher]]. Attacks have been developed for [[block cipher]]s and [[stream cipher]]s. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being [[differential cryptanalysis]].
 
The discovery is attributed to [[Mitsuru Matsui]], who first applied the technique to the [[FEAL]] cipher (Matsui and Yamagishi, 1992).<ref name="FEAL_linear">{{cite conference |author1=Matsui, M.  |author2=Yamagishi, A  |name-list-style=amp| title = A new method for known plaintext attack of FEAL cipher | book-title = Advances in Cryptology – [[EUROCRYPT]] 1992 }}</ref> Subsequently, Matsui published an attack on the [[Data Encryption Standard]] (DES), eventually leading to the first experimental cryptanalysis of the cipher reported in the open community (Matsui, 1993; 1994).<ref name="experimental_cryptanalysis">{{cite conference | author = Matsui, M | title = The first experimental cryptanalysis of the data encryption standard | book-title = Advances in Cryptology – [[CRYPTO]] 1994 }}</ref><ref name="DES_linear">{{cite conference|author=Matsui, M |title=Linear cryptanalysis method for DES cipher |book-title=Advances in Cryptology – EUROCRYPT 1993 |url=http://homes.esat.kuleuven.be/~abiryuko/Cryptan/matsui_des.PDF |access-date=2007-02-22 |url-status=dead |archive-url=https://web.archive.org/web/20070926205624/http://homes.esat.kuleuven.be/~abiryuko/Cryptan/matsui_des.PDF |archive-date=2007-09-26 }}</ref> The attack on DES is not generally practical, requiring 2<sup>47</sup> [[known-plaintext attack|known plaintexts]].<ref name="DES_linear"/>

A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating non-linear expressions, leading to a generalized [[partitioning cryptanalysis]]. Evidence of security against linear cryptanalysis is usually expected of new cipher designs.