All in the XL family: Theory and practice. (English) Zbl 1133.94336
Park, Choonsik (ed.) et al., Information security and cryptology – ICISC 2004. 7th international conference, Seoul, Korea, December 2–3, 2004. Revised Selected Papers. Berlin: Springer (ISBN 978-3-540-26226-8/pbk). Lecture Notes in Computer Science 3506, 67-86 (2005).
Summary: The XL (eXtended Linearization) equation-solving algorithm belongs to the same extended family as the advanced Gröbner Bases methods \(F_{4}/F_{5}\). XL and its relatives may be used as direct attacks against multivariate Public-Key Cryptosystems and as final stages for many “algebraic cryptanalysis” used today. We analyze the applicability and performance of XL and its relatives, particularly for generic systems of equations over medium-sized finite fields.
In examining the extended family of Gröbner Bases and XL from theoretical, empirical and practical viewpoints, we add to the general understanding of equation-solving. Moreover, we give rigorous conditions for the successful termination of XL, Gröbner Bases methods and relatives. Thus we have a better grasp of how such algebraic attacks should be applied. We also compute revised security estimates for multivariate cryptosystems. For example, the schemes SFLASH\(^{v2}\) and HFE Challenge 2 are shown to be unbroken by XL variants.
For the entire collection see [Zbl 1131.68012].
In examining the extended family of Gröbner Bases and XL from theoretical, empirical and practical viewpoints, we add to the general understanding of equation-solving. Moreover, we give rigorous conditions for the successful termination of XL, Gröbner Bases methods and relatives. Thus we have a better grasp of how such algebraic attacks should be applied. We also compute revised security estimates for multivariate cryptosystems. For example, the schemes SFLASH\(^{v2}\) and HFE Challenge 2 are shown to be unbroken by XL variants.
For the entire collection see [Zbl 1131.68012].
