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

Lorenz Panny; Christophe Petit; Miha Stopar

Paper 2024/1844

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

Lorenz Panny, Technische Universität München, Germany

Christophe Petit, Université libre de Bruxelles, Belgium, University of Birmingham, UK

Miha Stopar, Université libre de Bruxelles, Belgium, Ethereum Foundation

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 -isogenies between products of elliptic curves in the theta coordinate system. To successfully apply Clapoti in dimension , 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 as well as the online phase can be computed in (heuristic) polynomial time.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: post-quantum group action isogenies quaternions
Contact author(s): lorenz panny @ tum de
christophe f petit @ gmail com
stopar miha @ gmail com
History: 2024-11-11: approved; 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},
      url = {https://eprint.iacr.org/2024/1844}
}