Séminaire de Théorie Algorithmique des Nombres

Generally, polynomial systems that arise in algebraic cryptanalysis have extra structure compared to generic systems, which comes from the algebraic modelling of the cryptographic scheme. Sometimes, part of this extra structure can be caught with polynomial rings with non-standard grading. For example, in the Kipnis-Shamir modelling of MinRank one considers the system over a bi-graded polynomial ring instead. This allows for better approximations of the solving degree of such systems when using Gröbner basis algorithms.

In this talk, I will present ongoing work in which this idea is extended to multi-graded polynomial rings. Furthermore, I will show how we can use this grading to tailor existing algorithms to use this structure and speed up computation.