A New Isogeny Representation and Applications to Cryptography

Antonin Leroux

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

Abstract

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in ASIACRYPT 2022
Keywords: Isogeny-based cryptography isogeny representation endomorphism rings non-interactive key exchange
Contact author(s): antonin leroux @ polytechnique org
History: 2022-09-23: last of 2 revisions; 2021-12-09: received; See all versions
Short URL: https://ia.cr/2021/1600
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1600,
      author = {Antonin Leroux},
      title = {A New Isogeny Representation and Applications to Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1600},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1600}
}