F₅ – Gröbner bases using signatures

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!

Event: State of the Art of Cryptography in Blockchains

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.