2004 | OriginalPaper | Buchkapitel
The XL-Algorithm and a Conjecture from Commutative Algebra
verfasst von : Claus Diem
Erschienen in: Advances in Cryptology - ASIACRYPT 2004
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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; it was introduced to cryptology at Eurocrypt 2000.In this paper, we prove upper bounds on the dimensions of the spaces of equations in the XL-algorithm. These upper bounds provide strong evidence that for any fixed finite field K and any fixed cεℕ the median of the running times of the original XL-algorithm applied to systems of m = n + c quadratic equations in n variables over K which have a solution in K is not subexponential in n. In contrast to this, in the introduction of the original paper on XL, the authors claimed to “provide strong theoretical and practical evidence that the expected running time of this technique is [...] subexponential if m exceeds n by a small number”.More precise upper bounds on the dimensions of the spaces of equations in the XL-algorithm can be obtained if one assumes a standard conjecture from commutative algebra. We state the conjecture and discuss implications on the XL-algorithm.