### A New Isogeny Representation and Applications to Cryptography

##### 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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2021/1600

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},
note = {\url{https://eprint.iacr.org/2021/1600}},
url = {https://eprint.iacr.org/2021/1600}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.