Details:
Title  On the number of linearly independent equations generated by XL.  Author(s)  Haavard Raddum, Sondre Ronjom  Type  Book, Chapter in Book, Conference Proceeding  Abstract  Solving multivariate polynomial equation systems has been the focus of much attention in cryptography in the last years. Since most ciphers can be represented as a system of such equations, the problem of breaking a cipher naturally reduces to the task of solving them. Several papers have appeared on a strategy known as eXtended Linearization (XL) with a view to assessing its complexity. However, its efficiency seems to have been overestimated and its behaviour has yet to be fully understood. Our aim in this paper is to fill in some of these gaps in our knowledge of XL. In particular, by examining how dependencies arise from multiplication by monomials, we give a formula from which the efficiency of XL can be deduced for multivariate polynomial equations over 𝔽2. This confirms rigorously a result arrived at by Yang and Chen by a completely different approach. The formula was verified empirically by investigating huge amounts of random equation systems with varying degree, number of variables and number of equations.  Keywords  XL, Gröbner bases, Stream Ciphers  ISBN  9783540859116/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783540859123_22 
Language  English  Pages  239251  Publisher  Berlin: Springer  Year  2008  Edition  0  Translation 
No  Refereed 
No 
