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