Output details
11 - Computer Science and Informatics
Royal Holloway, University of London
A geometric view of cryptographic equation solving
<18> This paper considers efficient algorithms for solving a multivariate polynomial equation system over a field with large characteristic. Such equation systems often arise in cryptology. The paper shows how to unify previously known algorithms such as Relinearisation and XL (a Groebner basis algorithm) by using an innovative approach based on projective geometry. This geometric approach leads to a novel categorisation of systems for which such well-known techniques fail and the development of a simple generalised algorithm (GeometricXL) which encompasses all of the above techniques, but which can also solve many instances that were not easily solved before.