Paper 2021/1600
A New Isogeny Representation and Applications to Cryptography
Antonin Leroux
Abstract
This paper focuses on isogeny representations, defined as witnesses of 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$). This language and its proofs of membership are known to have several fundamental cryptographic applications such as the construction of digital signatures and validation of encryption keys. The first part of our article is dedicated to formalizing known results about isogenies to the framework of languages and proofs, culminating in a proof that the language of isogenous supersingular curves is in \textsf{NP} with the isogeny representation derived naturally from the Deuring Correspondence. Our main contribution is the design of the suborder representation, a new isogeny representation targetted 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. These new membership witnesses appear 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 our new suborder representation. In the process, we also 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: small typos here and there
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Isogeny-based cryptographyisogeny representationendomorphism ringsnon-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