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)
PDF
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-01-05: revised
2021-12-09: received
See all versions
Short URL
https://ia.cr/2021/1600
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.