Séminaire Algorithmique : « Revenge of the 4D: Can 4-dimensional isogenies become practical? », Pierrick Dartois (INRIA Rennes)

The devastating attacks against SIDH (Supersingular Isogeny Diffie-Hellman) in 2022 introduced higher-dimensional isogenies as a cryptanalytic tool. As opposed to elliptic curve isogenies, higher-dimensional isogenies are defined between abelian varieties (which generalize elliptic curves in higher dimension). These isogenies quickly became a powerful constructive tool in cryptography with the introduction of SQIsignHD and FESTA, followed up by many new isogeny-based cryptographic schemes.

The digital signature scheme SQIsignHD, based on SQIsign was the first scheme to use 4-dimensional isogenies but soon became obsolete when 2-dimensional alternatives were introduced and proposed as a part of the SQIsign NIST post-quantum signatures standard submission. For efficiency reasons, most isogeny based schemes aiming for practical use rely on isogenies of dimension at most 2, and it is widely believed in the isogeny community that isogenies of dimension bigger than 2 should be avoided.

The recent introduction of the Pegasis algorithm to compute the ideal class group action on oriented supersingular elliptic curves without restriction on the ideal has changed this perspective. This algorithm using 4-dimensional isogenies beats all 2-dimensional alternatives. Pegasis can be used as a tool to improve advanced cryptographic schemes that require unrestricted cryptographic group actions and is to be integrated in a NIST post-quantum threshold cryptographic standard submission. 4-dimensional isogenies also appear in the tensor-MIKE key exchange that remains to be implemented. These works make 4-dimensional isogenies more credible while algorithms to compute them are still making progress.