Paper 2022/357

An Effective Lower Bound on the Number of Orientable Supersingular Elliptic Curves

Antonin Leroux
Abstract

In this article, we prove a generic lower bound on the number of $\mathfrak{O}$-orientable supersingular curves over $\mathbb{F}_{p^2}$, i.e curves that admit an embedding of the quadratic order $\mathfrak{O}$ inside their endomorphism ring. Prior to this work, the only known effective lower-bound is restricted to small discriminants. Our main result targets the case of fundamental discriminants and we derive a generic bound using the expansion properties of the supersingular isogeny graphs. Our work is motivated by isogeny-based cryptography and the increasing number of protocols based on $\mathfrak{O}$-oriented curves. In particular, our lower bound provides a complexity estimate for the brute-force attack against the new $\mathfrak{O}$-uber isogeny problem introduced by De Feo, Delpech de Saint Guilhem, Fouotsa, Kutas, Leroux, Petit, Silva and Wesolowski in their recent article on the SETA encryption scheme.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
isogeny based cryptography quaternion orders quadratic orders
Contact author(s)
antonin leroux @ polytechnique org
History
2022-06-09: last of 2 revisions
2022-03-18: received
See all versions
Short URL
https://ia.cr/2022/357
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/357,
      author = {Antonin Leroux},
      title = {An Effective Lower Bound on the Number of Orientable Supersingular Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2022/357},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/357}},
      url = {https://eprint.iacr.org/2022/357}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.