Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in CIC 2025
- DOI
- 10.62056/ahp2wakrz
- Keywords
- post-quantumgroup actionisogeniesquaternions
- Contact author(s)
-
lorenz panny @ tum de
christophe f petit @ gmail com
stopar miha @ gmail com - History
- 2026-02-12: revised
- 2024-11-10: received
- See all versions
- Short URL
- https://ia.cr/2024/1844
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1844,
author = {Lorenz Panny and Christophe Petit and Miha Stopar},
title = {{KLaPoTi}: An asymptotically efficient isogeny group action from 2-dimensional isogenies},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1844},
year = {2024},
doi = {10.62056/ahp2wakrz},
url = {https://eprint.iacr.org/2024/1844}
}
