The XL-Algorithm and a Conjecture from Commutative Algebra

Claus Diem · International Conference on the Theory and Application of Cryptology and Information Security · 2004

Summary

The “XL-algorithm” is a computational method to solve overdetermined systems of polynomial equations which is based on a generalization of the well-known method of linearization.

Published: 2004-12-05
Cited by: 117
References: 15
Access: Open access
DOI: https://doi.org/10.1007/978-3-540-30539-2_23
Semantic Scholar: https://api.semanticscholar.org/CorpusID:10627380

References

Commutative Algebra: with a View Toward Algebraic GeometryD. Eisenbud — 1995
An inequality for Hilbert series of graded algebras.Ralf Fröberg — 1985
Introduction to commutative algebraMichael Atiyah — 1969
Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of ToyocryptNicolas T. Courtois — 2002
Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over F_2 with solutions in F_2Magali Bardet, Jean‐Charles Faugère, Bruno Salvy — 2002
The Art of Computer ProgrammingG.E. Whitesides — 1968
Essential Algebraic Structure within the AESSeán Murphy, Matthew J. B. Robshaw — 2002
On the method of "XL" and its inefficiency to TTM.T. Moh — 2001
Cryptanalysis of Block Ciphers with Overdefined Systems of EquationsNicolas T. Courtois, Josef Pieprzyk — 2002
Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial EquationsN. Courtois, A. Klimov, Jacques Patarin — 2000
Commutative Ring TheoryA. Frohlich, M. Taylor — 1989
Theoretical Analysis of XL over Small FieldsBo-Yin Yang, Jiun-Ming Chen — 2004
Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over F_2 with solutions in F_2J. Faugère — 2002

Cited by

ALGEBRAIC ATTACKS ON STREAM CIPHERS (SURVEY)Dong Hoon Lee — 2005
The Block Cipher CompanionLars R. Knudsen, Matthew J. B. Robshaw — 2011
Performance evaluation of eXtended sparse linearization in GF(2) and GF(28)Tigin Kaptanoglu — 2007
A Survey of Attacks on Multivariate CryptosystemsÁdám Feldmann — 2005
Algebraic aspects of the advanced encryption standardCarlos Cid, Robshaw, Matthew, Murphy, Sean — 2006
Counting equations in algebraic attacks on block ciphersLars R. Knudsen, Charlotte Vikkelsø Miolane — 2010
Quadratic Equations from APN Power FunctionsJung Hee Cheon — 2006
A family of weak keys in HFE and the corresponding practical key-recoveryCharles Bouillaguet, Pierre-Alain Fouque, Antoine Joux — 2009
Generic sequences of polynomialsKeith Pardue — 2010
Current Research Topics on Galois GeometryLeo Storme, Jan De Beule — 2011
Algebraic Attacks Galore!Martin Kreuzer — 2009
Small-Footprint Block Cipher Design - How far can you go?Andrey Bogdanov, Lars R. Knudsen, Gregor Leander — 2007
On the relation between the MXL family of algorithms and Gröbner basis algorithmsM. Albrecht, Carlos Cid, Jean‐Charles Faugère — 2012
DESIGN OF BLOCK CIPHERS AND CODING THEORYDaesung Kwon, Soo Hak Sung, Jung Hwan — 2005
TTS: Rank Attacks in Tame-Like Multivariate PKCsBo‐Yin Yang, Jiun-Ming Chen — 2004
Algebraic Cryptanalysis of Symmetric PrimitivesCarlos Cid, M. Albrecht, Anne Canteaut — 2008
On Deviations of the AES S-box when Represented as Vector Valued Boolean FunctionDanilo Gligoroski, Marie Elisabeth, Gaup Moe — 2007
On Some Necessary Conditions of Boolean Functions to Resist Algebraic AttacksDeepak Kumar Dalai — 2006
Codes de Reed-Muller et cryptanalyse du registre filtréFrédéric Didier — 2007
Growth of the ideal generated by a quadratic multivariate functionJíntai Ding, Victoria Kruglov — 2010

Related papers

No related papers recorded.