Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Isogeny-based cryptography, isogeny representation, endomorphism rings, non-interactive key exchange

Date: received 7 Dec 2021, last revised 5 Jan 2022

Contact author: antonin leroux at polytechnique org

Available format(s): PDF | BibTeX Citation

Note: small typos here and there

Version: 20220105:131204 (All versions of this report)

Short URL: ia.cr/2021/1600


[ Cryptology ePrint archive ]