Linear Cryptanalysis
Also known as: linear attack, linear approximation, piling-up lemma
Linear cryptanalysis is a known-plaintext attack that exploits linear approximations of a cipher's non-linear transformations to recover secret key bits. Introduced by Mitsuru Matsui in 1993, linear cryptanalysis provides practical attacks on ciphers like DES with computational complexity less than brute force. The technique analyzes statistical biases in how linear combinations of plaintext and ciphertext bits relate to key bits, enabling key recovery with reduced data requirements.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Linear cryptanalysis is used in cryptanalysis research and cipher design evaluation. It guides cipher designers in selecting S-boxes and transformations that resist linear approximations. Modern ciphers are designed with proven bounds on linear approximation strength.
Strengths & limitations
- Practical attack on DES requiring 2^43 plaintext-ciphertext pairs and 2^39 operations
- Well-formalized mathematical framework (piling-up lemma) for analyzing approximation biases
- Complements differential cryptanalysis, finding weaknesses differential analysis might miss
- Shapes cipher design requirements for S-box selection and round transformation
- Modern ciphers (AES) are carefully designed to resist linear cryptanalysis with provable bounds
- Requires known plaintext-ciphertext pairs, which may not be available in all scenarios
- Computational and data requirements can exceed practical feasibility for well-designed ciphers
- Discovering strong linear approximations for modern ciphers is extremely difficult
Frequently asked
What is the piling-up lemma?
The piling-up lemma provides a method for computing the bias of linear approximations across multiple rounds by combining biases of individual round approximations. It is foundational to linear cryptanalysis.
How does AES resist linear cryptanalysis?
AES uses S-boxes chosen to minimize maximum linear approximation probability and a diffusion layer ensuring fast diffusion of linear biases across rounds. Proven bounds guarantee no practical linear approximations.
What is the difference between linear and differential cryptanalysis?
Differential analysis studies input-output differences, while linear analysis studies linear approximations (XOR of plaintext and ciphertext bits). Both exploit structural weaknesses in ciphers.
Can linear cryptanalysis break modern ciphers?
Not practically. Modern ciphers like AES have provable bounds on linear approximations making attacks computationally infeasible.
How do I evaluate linear resistance in my cipher design?
Analyze S-box linear approximation tables and compute maximum bias through rounds using the piling-up lemma. Ensure maximum bias is negligible across all possible linear approximations.
Sources
- Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397. DOI: 10.1007/3-540-48285-7_33 ↗
- Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11. DOI: 10.1007/3-540-48658-5_1 ↗
How to cite this page
ScholarGate. (2026, June 3). Linear Cryptanalysis. ScholarGate. https://scholargate.app/en/cryptography/linear-cryptanalysis
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- AES (Rijndael)Cryptography↔ compare
- Differential CryptanalysisCryptography↔ compare
- Side-Channel AnalysisCryptography↔ compare