Linear cryptanalysis

In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. 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).[1] 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).[2][3] The attack on DES is not generally practical, requiring 247 known plaintexts.[3]

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.

  1. ^ Matsui, M. & Yamagishi, A. "A new method for known plaintext attack of FEAL cipher". Advances in Cryptology – EUROCRYPT 1992.
  2. ^ Matsui, M. "The first experimental cryptanalysis of the data encryption standard". Advances in Cryptology – CRYPTO 1994.
  3. ^ a b Matsui, M. "Linear cryptanalysis method for DES cipher" (PDF). Advances in Cryptology – EUROCRYPT 1993. Archived from the original (PDF) on 2007-09-26. Retrieved 2007-02-22.