CryptoDB
A New Isogeny Representation and Applications to Cryptography
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2022 |
| 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. In the first part of this article, we reinterpret known results on isogenies in the framework of languages and proofs to show 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 the 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. |
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32491,
title={A New Isogeny Representation and Applications to Cryptography},
publisher={Springer-Verlag},
author={Antonin Leroux},
year=2022
}