One of the biggest milestones regarding Gröbner basis computation was the introduction of F₅ due to Jean-Charles Faugère. In this video, I motivate how F₅ improves on F₄, introduce the concepts used in F₅, and present the core algorithm step by step.

There is a lot more to be said regarding signature based Gröbner basis algorithms. For example, thanks to F₅, we have a better understanding of the complexity of Gröbner basis computations. Stay tuned for upcoming posts!

Have you ever computed a Gröbner basis in some monomial order ≺₀ only to then realize that you actually wanted it in another order ≺₁? I know, happens all the time… But fret not, FGLM can convert between the two orders, and you don’t have to start your computation from scratch.

Here’s a recording where I’m explaining how FGLM works. If you’d like to look through the slides at your own pace, here they are. You can also find the two Gröbner bases used in the example as well as pseudocode for FGLM in the slides, in case you want to retrace the steps yourself.

If you are interested in not only how but also why FGLM works, have a look at the original publication. Section 5 and 6 give a comprehensive overview of FGLM’s complexity, which can be summarized as O(n·D³) where D is the dimension of quotient ring k[x₀, …, x_n-1] / <G> as a k-vector-space. More intuitively, D is the number of monomials in the staircase of a Gröbner basis, which are those dots in the non-blue region in this post’s first picture.

Next Wednesday, 12 August 2020 at 16:30 CET, our own Ferdinand Sauer will be giving an introductory presentation on Gröbner basis attacks in the context of attacking arithmetization-oriented ciphers. Be sure to tune in if you want to learn more about the attack space for AO ciphers like Rescue and Poseidon. Email us if you want access to the zoom link.

Update: Slides & VoD

Couldn’t make it? Not to worry! Take a peek at the slides, and complement them by watching the recording.