Cryptology ePrint Archive: Report 2022/349
Hard Homogeneous Spaces from the Class Field Theory of Imaginary Hyperelliptic Function Fields
Antoine Leudière and Pierre-Jean 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 Couveignes-Rostovtsev-Stolbunov group action. Our
proof-of-concept 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 post-quantum 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 isogeny-based 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 polynomial-time algorithm for imaginary quadratic number fields is known.
For $q=2$ and parameters similar to CSIDH-512, we compute this order more than
8500 times faster than the record computation for CSIDH-512 by Beullens,
Kleinjung and Vercauteren.
Category / Keywords: public-key cryptography / isogeny-based cryptography, Drinfeld modules
Date: received 14 Mar 2022, last revised 7 Apr 2022
Contact author: antoine leudiere at inria fr, pierre-jean spaenlehauer at inria fr
Available format(s): PDF | BibTeX Citation
Version: 20220407:105712 (All versions of this report)
Short URL: ia.cr/2022/349
[ Cryptology ePrint archive ]