Welcome to the resource topic for 2021/1600
Title:
A New Isogeny Representation and Applications to Cryptography
Authors: 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.
ePrint: https://eprint.iacr.org/2021/1600
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .