Paper 2023/376

Efficient computation of $(3^n,3^n)$-isogenies

Thomas DeCrewimec-COSIC, KU Leuven, Belgium
Sabrina Kunzweiler, University. Bordeaux, CNRS, Bordeaux INP, Inria, France

The parameterization of $(3,3)$-isogenies by Bruin, Flynn and Testa requires more than 37.500 multiplications if one wants to evaluate a single isogeny at a point. We simplify their formulas and reduce the amount of multiplications required by 94%. Additionally we derive explicit formulas for evaluating $(3,3)$-splitting and gluing maps in the framework of the parameterization by Brocker, Howe, Lauter, and Stevenhagen. We provide implementations to compute $(3^n,3^n)$-isogenies between primarily polarized abelian surfaces, focusing on cryptographic applications. Our implementation can recover Alice’s secret isogeny in 11 seconds for SIKEp751 parameters, which was targeted at NIST level 5 security.


      author = {Thomas Decru and Sabrina Kunzweiler},
      title = {Efficient computation of $(3^n,3^n)$-isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2023/376},
      year = {2023},
      note = {\url{
      url = {


See also  Asymmetric quantum secure multi-party computation with vulnerable clients against unscrupulous majority

By admin