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 | | | ISBN | 978-3-540-85911-6/pbk |
| URL |
http://link.springer.com/chapter/10.1007%2F978-3-540-85912-3_22 |
| Language | English | | Pages | 239--251 | | Publisher | Berlin: Springer | | Year | 2008 | | Edition | 0 | | Translation |
No | | Refereed |
No |
|
