Séminaire de Théorie Algorithmique des Nombres

One of the most important building blocks in isogeny-based cryptography is an algorithm for translating ideals to their corresponding isogenies. The current state-of-the-art for quaternion ideals is an approach that is based on Clapoti, which is the main part of both signing and key generation in both SQIsign and PRISM.

In this talk, we will have a look at the issues with the current algorithm, specifically how the non-negligable failure rate affect both the performance and security proofs. We then present Qlapoti, a new approach that also builds on Clapoti, but is more specialised to quaternion ideals. We will then have an in-depth look at Qlapoti and its failure rate, and show how it solves the remaining issues with the current ideal to isogeny algorithms, while also making key generation and signing in SQIsign/PRISM around 2x faster.

We explicitly realize the group 17T7, an extension of SL(2,16) by C_2, as a Galois group over the rationals. The group arises from the field of definition of the 2-torsion on an abelian fourfold with real multiplication defined over a real quadratic field. We find such fourfolds using Hilbert modular forms, first numerically, then certifying the result with exact methods.