Paper 2022/349
Hard Homogeneous Spaces from the Class Field Theory of Imaginary Hyperelliptic Function Fields
Antoine Leudière and PierreJean Spaenlehauer
Abstract
We explore algorithmic aspects of a free and 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 $\mathbb{F}_q$ 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 CouveignesRostovtsevStolbunov group action. Our proofofconcept C++/NTL implementation only requires a fraction of a second on a standard computer. Also, we state a conjecture — supported by experiments — which implies that the current fastest algorithm to solve its inverse problem runs in exponential time. This action is therefore a promising candidate for the construction of Hard Homogeneous Spaces, which are the building blocks of several postquantum cryptographic protocols. This demonstrates the relevance of using imaginary hyperelliptic curves and Drinfeld modules as an alternative to the standard setting of imaginary quadratic number fields and elliptic curves for isogenybased cryptographic applications. Moreover, our function field setting enables the use of Kedlaya's algorithm and its variants for computing the order of the group in polynomial time when $q$ is fixed. No such polynomialtime algorithm for imaginary quadratic number fields is known. For $q=2$ and parameters similar to CSIDH512, we compute this order more than 8500 times faster than the record computation for CSIDH512 by Beullens, Kleinjung and Vercauteren.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 isogenybased cryptographyDrinfeld modules
 Contact author(s)

antoine leudiere @ inria fr
pierrejean spaenlehauer @ inria fr  History
 20220407: last of 2 revisions
 20220314: received
 See all versions
 Short URL
 https://ia.cr/2022/349
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/349, author = {Antoine Leudière and PierreJean Spaenlehauer}, title = {Hard Homogeneous Spaces from the Class Field Theory of Imaginary Hyperelliptic Function Fields}, howpublished = {Cryptology ePrint Archive, Paper 2022/349}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/349}}, url = {https://eprint.iacr.org/2022/349} }