Paper 2025/847
Deterministic algorithms for class group actions
, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de BordeauxAbstract
We present an algorithm for the CSIDH protocol that is fully deterministic and strictly constant time. It does not require dummy operations and can be implemented without conditional branches. Our proof-of-concept C implementation shows that a key exchange can be performed in a constant (i.e. fixed) number of finite field operations, independent of the secret keys. The algorithm relies on a technique reminiscent of the standard Montgomery ladder, and applies to the computation of isogenies that divide an endomorphism of smooth degree represented by its kernel. We describe our method in the general context of class group actions on oriented elliptic curves, giving rise to a large family of non-interactive key exchanges different from CSIDH.
Note: In a previous version of the article, we incorrectly claimed that Algorithm 3 automatically validates public keys; this mistake was kindly pointed out to us by Krijn Reijnders. We have updated Section 4.3 accordingly.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in CRYPTO 2025
- Keywords
- Isogeny-based cryptographyCSIDHOrientationsRestricted Effective Group Action
- Contact author(s)
- marc houben @ math u-bordeaux fr
- History
- 2025-07-27: revised
- 2025-05-13: received
- See all versions
- Short URL
- https://ia.cr/2025/847
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/847,
author = {Marc Houben},
title = {Deterministic algorithms for class group actions},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/847},
year = {2025},
url = {https://eprint.iacr.org/2025/847}
}
