Paper 2021/1600

A New Isogeny Representation and Applications to Cryptography

Antonin Leroux, Direction Générale de l'Armement, École Polytechnique, Inria Saclay - Île-de-France Research Centre

This paper focuses on isogeny representations, defined as ways to evaluate isogenies and verify membership to the language of isogenous supersingular curves (the set of triples $D,E_1,E_2$ with a cyclic isogeny of degree $D$ between $E_1$ and $E_2$). The tasks of evaluating and verifying isogenies are fundamental for isogeny-based cryptography. Our main contribution is the design of the suborder representation, a new isogeny representation targeted at the case of (big) prime degree. The core of our new method is the revelation of endomorphisms of smooth norm inside a well-chosen suborder of the codomain's endomorphism ring. This new representation appears to be opening interesting prospects for isogeny-based cryptography under the hardness of a new computational problem: the SubOrder to Ideal Problem (SOIP). As an application, we introduce pSIDH, a new NIKE based on the suborder representation. Studying new assumption appears to be particularly crucial in the light of the recent attacks against isogeny-based cryptography. In order to manipulate efficiently the suborder representation, we develop several heuristic algorithmic tools to solve norm equations inside a new family of quaternion orders. These new algorithms may be of independent interest.

Note: final version

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Isogeny-based cryptography isogeny representation endomorphism rings non-interactive key exchange
Contact author(s)
antonin leroux @ polytechnique org
2022-09-23: last of 2 revisions
2021-12-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Antonin Leroux},
      title = {A New Isogeny Representation and Applications to Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1600},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.