With? Pierre-Jean Spaenlehauer
When? 2022 July 5
Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields
We explore algorithmic aspects of a simply transitive commutative group action coming from the class field theory of imaginary hyperelliptic function fields. Namely, the Jacobian of an imaginary hyperelliptic curve defined over Fq acts on a subset of isomorphism classes of Drinfeld modules. We describe an algorithm to compute the group action efficiently. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. We report on an explicit computation done with our proof-of-concept C++/NTL implementation; it took a fraction of a second on a standard computer. We prove that the problem of inverting the group action reduces to the problem of finding isogenies of fixed τ-degree between Drinfeld Fq[X]-modules, which is solvable in polynomial time thanks to an algorithm by Wesolowski.
This paper is a rewrite of arXiv:2203.06970v2. It takes into account the recent attack of Wesolowski (https://eprint.iacr.org/2022/438) on the cryptographic applications we proposed in the original preprint. All mathematical and algorithmic statements are the same as in the original preprint; we removed cryptographic applications, and the introduction and experimental results have been widely rewritten. The arXiv and Hal submissions are updated; the IACR eprint submission will remain unchanged.