Gröbner bases and Cryptography Last years a new kind of cryptanalysis has made its entrance in cryptography: the so-called algebraic cryptanalysis.  In a nutshell, the idea of algebraic cryptanalysis is that for a given cryptosystem one has to generate a suitable algebraic system of equations whose zeroes correspond to the deciphered message or the secret key. A fundamental issue of this cryptanalysis consists thus in finding zeroes of algebraic systems. Gröbner bases, which are a fundamental tool of commutative algebra, constitute the most elegant and efficient way for solving this problem.  They provide an algorithmic solution for solving several problems related to algebraic systems. From a practical point of view, we employed a fast Gröbner basis algorithm, namely F5, for solving the corresponding algebraic system. Very often this approach is efficient in practice and obliges to modify the parameter of the cryptosystem. Some research papers FJ03, AFIK04, AF05, FP06a, FP06b, FLP08, FOPT10, FS10, FMR10, BFFP11, BFP11, AFFP11, FPPR12, BFP12.

Understanding the complexity of computing Gröbner bases is a fundamental issue. Following step by step the F5 algorithm it is possible to predict quite accurately the complexity of the computation. To this end, it is necessary to understand the shape of the matrices generated by F5 (generic quadratic system of 12 equations in 12 variables) [BFS2014]:

Matrix generated by the F4 algorithm