Algorithmic techniques in algebraic cryptanalysis and their applications

This thesis studies algorithms for computing Gröbner bases of ideals in multivariate polynomial rings and explores their practical applications. A Gröbner basis provides a structured way to represent polynomial ideals. The work focuses on improving both the theoretical understanding and implementation of such algorithms. A central contribution is the introduction of a new Gröbner basis algorithm, called M4GB, designed to maintain polynomials in tail-reduced form throughout the computation. The algorithm is described in a way that unifies a high-level description with its main implementation aspects, without obscuring the nature of its implementation. The algorithm incorporates a recursive polynomial reduction strategy that improves performance in practice. The effectiveness of M4GB is demonstrated through its applications to solving systems of multivariate quadratic (MQ) polynomial equations over finite fields. Notably, it sets a new record in the Fukuoka MQ-challenges for parameters representing public keys in MQ-based digital signature schemes. Further applications include solving binary puzzles by translating their constraints into polynomial systems, as well as analyzing cryptographic properties of vectorial Boolean functions. These results highlight the broad applicability of Gröbner basis techniques in both combinatorial and cryptographic contexts.