A Geometric View of Cryptographic Equation Solving

Sean Murphy and Maura Paterson

(2007)

Sean Murphy and Maura Paterson (2007) A Geometric View of Cryptographic Equation Solving.

Our Full Text Deposits

Full text access: Open

Full Text - 358.21 KB

Links to Copies of this Item Held Elsewhere

Mathematics Departmental Web Page

Abstract

This paper considers the geometric properties of the Relinearisation algorithm and of the XL algorithm used in cryptology for equation solving. We give a formal description of each algorithm in terms of projective geometry, making particular use of the Veronese variety. We establish the fundamental geometrical connection between the two algorithms and show how both algorithms can be viewed as being equivalent to the problem of finding a matrix of low rank in the linear span of a collection of matrices, a problem sometimes known as the MinRank problem. Furthermore, we generalise the XL algorithm to a geometrically invariant algorithm, which we term the GeometricXL algorithm. The GeometricXL algorithm is a technique which can solve certain equation systems that are not easily soluble by the XL algorithm or by Groebner basis methods.

Information about this Version

This is a Published version
This version's date is: 14/05/2007
This item is peer reviewed

Link to this Version

https://repository.royalholloway.ac.uk/items/c9e13031-43e5-f425-eab4-4ab63150ac14/1/

Item TypeMonograph (Technical Report)
TitleA Geometric View of Cryptographic Equation Solving
AuthorsMurphy, Sean
Paterson, Maura
DepartmentsFaculty of Science\Mathematics

Deposited by () on 28-Jun-2010 in Royal Holloway Research Online.Last modified on 14-Dec-2010

Notes

References

1. G. Bard and N. Courtois. Algebraic Cryptanalysis of the Data Encryption Stan-
dard , 2006. http://eprint.iacr.org/2006/402.

2. E. Bertini. Introduzione Alla Geometrica Proiettiva Degli Iperspazi, Con Appen-
dice Sulle Curve Algebriche E Loro Singolarit¶a. Pisa, 1907. http://historical.
library.cornell.edu/cgi-bin/cul.math/docviewer?did=00%790002&seq=5.

3. B. Buchberger. Ein Algorithmus zum Au±nden der Basiselemente des Restk-
lassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, UniversitÄat
Innsbruck, 1965.

4. E. Carlini. Reducing the Number of Variables of a Ploynomial. In M. Elkadi,
B. Mourrain, and R. Piene, editors, Algebraic Geometry and Geometric Modelling
(Mathematics and Visualisation), pages 237{247. Springer, 2006.

5. Rey Casse. Projective Geometry: An Introduction. Oxford University Press, 2006.

6. C. Cid, S. Murphy, and M. Robshaw. Algebraic Aspects of the Advanced Encryption
Standard. Springer, 2006.

7. P. Cohn. Classical Algebra. John Wiley, 2000.

8. N. Courtois, A. Klimov, J. Patarin, and A. Shamir. E±cient Algorithms for Solving
Overde¯ned Systems of Multivariate Polynomial Equations. In B. Preneel, editor,
Advances in Cryptology { EUROCRYPT 2000, volume 1807 of LNCS, pages 392{
407. Springer{Verlag, 2000.

9. D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Undergraduate
Texts in Mathematics. Springer{Verlag, second edition, 1997.
10. D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry, volume 185 of Grad-
uate Texts in Mathematics. Springer, second edition, 2004.

11. C. Diem. The XL-Algorithm and a Conjecture from Commutative Algebra. In P.J.
Lee, editor, Advances in Cryptology { ASIACRYPT 2004, volume 3329 of LNCS,
pages 323{337. Springer{Verlag, 2004.

12. J-C. Faugµere. A New E±cient Algorithm for Computing GrÄobner bases (F4).
Journal of Pure and Applied Algebra, 139:61{88, 1999.

13. J-C. Faugµere. A New E±cient Algorithm for Computing GrÄobner Bases without
Reduction to Zero (F5). In T. Mora, editor, International Symposium on Symbolic
and Algebraic Computation { ISSAC 2002, pages 75{83, 2002.

14. W.T. Gowers. How to Lose your Fear of Tensor Products, 2005. http://www.
dpmms.cam.ac.uk/\~wtg10/tensors3.html.

15. W. GrÄobner. ÄUber Veronesesche VarietÄaten und deren Projektionen. Arch. Math.,
16:257{264, 1965.

16. J. Harris. Algebraic Geometry: A First Course. Number 133 in Graduate Text in
Mathematics. Springer, 1992.

17. J.W.P. Hirschfeld and J.A. Thas. General Galois Geometries. Oxford University
Press, 1991.

18. A. Iarrobino and V. Kanev. Power Sums, Gorenstein Algebras and Determinantal
Loci. Number 1725 in Lecture Notes in Mathematics. Springer, 1999.

19. V. Kanev. Chrodal Varieties of Veronese Varieties and Catalechticant Matrices.
Journal of Mathematical Sciences, 94:1114{1125, 1999.

20. A. Kipnis and A. Shamir. Cryptanalysis of the HFE Public Key Cryptosystem by
Relinearization. In H. Imai and Y. Zheng, editors, Advances in Cryptology, Crypto
'99, volume 1267 of LNCS, pages 19{30. Springer{Verlag, 1999.

21. R. Lidl and H. Niederreiter. Introduction to Finite Fields and Their Applications.
Cambridge University Press, 1994.

Details