1. Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields

    With Pierre-Jean Spaenlehauer · 2022 July · arXiv,, ePrint

    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 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.