A tale of groups and rabbits: efficient 4-dimensional isogeny computations for cryptographic group actions

In the transition to post-quantum cryptography, cryptographic group actions can offer a modularity close to pre-quantum discrete logarithm problems. Not only can this modularity be used for basic primitives (e.g. key exchange, signatures), but also for advanced constructions, including threshold schemes for secure multi-party computation that will be proposed to the next NIST call.

In this talk, we present how such cryptographic group actions can be instantiated and computed with supersingular isogenies. With standard isogeny computation techniques, it was only possible to efficiently compute the action of some particular group elements generating the whole group. This limitation could restrict some cryptographic applications where random group elements were used. The (qt-)Pegasis algorithm (Practical Effective class Group Action uSIng 4-dimensional isogenieS) has been introduced last year to overcome this limitation. Following a more and more popular approach in isogeny-based cryptography since the downfall of SIKE (Supersingular Isogeny Key Encapsulation), (qt-)Pegasis relies on the computation of a 4-dimensional isogeny.

The (qt-)Pegasis algorithm also motivated further research on the efficient computation of 4-dimensional isogenies in order to make it practical and provide an efficient C implementation. We shall conclude the talk with a presentation of recent improvements of 4-dimensional isogeny computation algorithms involving mysterious rabbit-shaped graphs. »