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!
On 12 November 2020, the Cryptography Working Group (jointly with CVLabs) held the first event on the theme “cryptography in blockchains”. We counted 99 (!) registrations in the Eventbrite. However, in light of the dire situation in regards to the Covid-19 pandemic, the decision was made to host the event entirely online. Approximately 40 people tuned in for the live stream, a recording of which is on YouTube. Have a look here!
The event started with an introduction by Ralf Kubli to the Cryptovalley ecosystem and CVVC specifically, followed by an introduction to CVLabs by Fabiola Luna Huerta.
The first speaker was Alan Szepieniec, of AS Discrete Mathematics and the Cryptography Working Group. He introduced the theme of the event: the focus on the intersection between two disparate worlds, cryptography and cryptocurrency respectively. This talk made the case for growing this intersection.
Next up was Jean-Philippe Aumasson of TaurusGroup, who gave a talk on the implementation pitfalls of multisignature schemes. The idea behind this type of scheme is that multiple independent parties must collaborate in order to release funds or approve a payment, thereby eliminating the security hazard posed by having a single point of failure. However, two new attacks show that upgrading a regular signature scheme to a multisignature scheme is a process fraught with vulnerabilities and pitfalls. It can work, but only if you’re extremely careful.
The third speaker was professor Kenny Paterson of ETH Zurich. He spoke about research he and his collaborators had done to undermine the privacy guarantees of private cryptocurrencies, colloquially known as privacycoins. Rather than attacking the cryptography itself from an abstract and mathematical perspective, these attacks focus on how the cryptography was implemented. For instance, clients took longer to respond to ping requests when they were validating a new transaction to which they were the recipient. This network-level information source allows the attacker to determine the IP address of the recipient of funds, even though this destination is hidden by the cryptography.
The last speaker was Luca De Feo, who is a researcher at IBM Zurich and whose research focuses on elliptic curve isogenies. Typically, isogeny-based cryptography is touted as a strategy for achieving post-quantum cryptography with compact public keys, ciphertexts and signatures. However, today’s talk was about combining isogenies with pairings, which are not post-quantum secure. However, it turns out that by combining the two one can construct verifiable delay functions whose evaluation proofs are 0 bytes — in other words, the verifier needs no extra information to verify the correct output. The scheme does rely on an updatable trusted setup, and it remains to be determined whether this trusted setup can be eliminated altogether.
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[x0, …, xn-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.
Researchers at StarkWare have published a report detailing their decision process of hash function for hashing over STARKs. In the end they chose for the arithmetization oriented cipher Rescue. The report also includes an appendix by Jean-Charles Faugère and Ludovic Perret about the security of these ciphers against Gröbner basis attacks. Read the report here.
