Efficient Computation of $(3^n , 3^n)$-Isogenies
KUNZWEILER, Sabrina
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
KUNZWEILER, Sabrina
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
< Reduce
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]
Language
en
Communication dans un congrès
This item was published in
Lecture Notes in Computer Science, Lecture Notes in Computer Science, AfricaCrypt 2023, 2023-07-19, Sousse. 2023-07-13, vol. 14064, p. 53-78
English Abstract
The parametrization of $(3, 3)$-isogenies by Bruin, Flynn and Testa requires over 37.500 multiplications if one wants to evaluate a single isogeny in a point. We simplify their formulae and reduce the amount of required ...Read more >
The parametrization of $(3, 3)$-isogenies by Bruin, Flynn and Testa requires over 37.500 multiplications if one wants to evaluate a single isogeny in a point. We simplify their formulae and reduce the amount of required multiplications by 94%. Further we deduce explicit formulae for evaluating $(3, 3)$-splitting and gluing maps in the framework of the parametrization by Bröker, Howe, Lauter and Stevenhagen. We provide implementations to compute $(3^n , 3^n)$-isogenies between principally polarized abelian surfaces with a focus on cryptographic application. Our implementation can retrieve Alice's secret isogeny in 11 seconds for the SIKEp751 parameters, which were aimed at NIST level 5 security.Read less <
English Keywords
Isogenies
Post-quantum Cryptography
Abelian surfaces
ANR Project
Cryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008
Origin
Hal imported