Computing the Isogeny Class-Group Action on Ordinary Elliptic Curves by going into Higher Dimensions

Abstract

We assess the feasibility of using the new higher-dimensional methods of CLAPOTI to evaluate the isogeny class-group action on ordinary elliptic curves; this action is (conjecturally) an instance of a post-quantum cryptographic group action from which many primitives can be built. By specialising the theory to ordinary elliptic curves and then giving an almost complete Sage implementation for toy examples we conclude that the only bottleneck to practical usage of CLAPOTI lies in the fact that we are considering ordinary elliptic curves. As such, we suspect CLAPOTI to not only be asymptotically polynomial time, but concretely efficient when evaluating the isogeny class-group action on supersingular elliptic curves. The bottleneck for ordinary elliptic curves arises as follows. To obtain a cryptographically secure instance of the isogeny class-group action, we require the (ordinary) elliptic curves in question to have endomorphism rings with large class-groups; on the other hand, to utilise currently available higher-dimensional tools, we also require the curves to have large $2^n$-torsion. These requirements appear to be fundamentally at odds with each other for ordinary elliptic curves with current knowledge.