Paper 2024/1844 Original: eprint.iacr.org/2024/1844 ↗

KLaPoTi: An asymptotically efficient isogeny group action from 2-dimensional isogenies

Abstract

We construct and implement an efficient post-quantum commutative cryptographic group action based on combining the SCALLOP framework for group actions from isogenies of oriented elliptic curves on one hand with the recent Clapoti method for polynomial-time evaluation of the CM group action on elliptic curves on the other. We take advantage of the very attractive performance of $(2^e,2^e)$-isogenies between products of elliptic curves in the theta coordinate system. To successfully apply Clapoti in dimension $2$, it is required to resolve a particular quadratic diophantine norm equation, for which we employ a slight variant of the KLPT algorithm. Our work marks the first practical instantiation of the CM group action for which both the setup and the online phase can be computed in (heuristic) polynomial time. We also point out that the order of the acting group — equivalently, the size of the set being acted on — is known, and can be chosen (within constraints) during parameter generation, in our construction.