A Geometric View of Cryptographic Equation Solving
Sean Murphy and Maura Paterson
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.