Department of Mathematics
Royal Holloway University Of London

Technical report: A Geometric View of Cryptographic Equation Solving

Authors: Sean Murphy and Maura Paterson

Reference: RHUL-MA-2007-4

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.

Download the full report from this page.

posted 21 May 2007


Department of Mathematics, Royal Holloway, University of London, Egham, Surrey TW20 0EX
Tel/Fax: +44 (0)1784 443093/430766