Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations

By Nicolas T. Courtois, A. Klimov, Jacques Patarin, Adi Shamir. International Conference on the Theory and Application of Cryptographic Techniques, 2000

911 citations recorded by the source corpus.

Subfields: Algebra and Number Theory, Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/79858106fb51cb531cf96b16eee821a4ee537c54

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Cube Attacks on Tweakable Black Box Polynomials (2009, methodology): “There are several improved algorithms such as XL and XSL (see [3],[4],[5], [6] and [7]) which reduce the number of required equations and the time and space complexities, but they are still completely impractical for such sizes.”
Cryptanalysis of Block Ciphers with Overdefined Systems of Equations (2002, methodology): “In the original paper about XL [22], the system was solved when T − Free was a small number.”
Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases (2003, methodology): “In this class, we find the relinearization technique of [15], the XL algorithm [8] and also the Gröbner basis [1,2,3] approach.”
Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (2003, methodology): “Note that if the first frame’s f [10] might is one, the attacker is forced to wait another six seconds for a frame with a zero f [10].”
Algebraic Attacks on Stream Ciphers with Linear Feedback (2003, methodology): “However their application to cryptographic attacks did not receive sufficient attention, probably because only recently people became aware of the existence of efficient algorithms for solving systems of nonlinear multivariate equations of low degree [ 21 ,8,9,10].”
Advances in Cryptology — ASIACRYPT 2002 (2002, methodology): “Since then, more and more separations between cryptographic primitives have been established following this paradigm [21,23,17,7,9,8,6].”
PRESENT: An Ultra-Lightweight Block Cipher (2007, methodology): “Some specialised techniques such as XL [10] and XSL [11] have been proposed, though flaws in both techniques have been discovered [8, 14].”