Paper 2022/528

On Random Sampling of Supersingular Elliptic Curves

Marzio Mula, University of Trento
Nadir Murru, University of Trento
Federico Pintore, University of Bari

We consider the problem of sampling random supersingular elliptic curves over finite fields of cryptographic size (SRS problem). The currently best-known method combines the reduction of a suitable complex multiplication (CM) $j$-invariant and a random walk over some supersingular isogeny graph. Unfortunately, this method is not suitable for numerous cryptographic applications because it gives information about the endomorphism ring of the generated curve. This motivates a stricter version of the SRS problem, requiring that the sampling algorithm gives no information about the endomorphism ring of the output curve (cSRS problem). In this work we formally define the SRS and cSRS problems, which both enjoy a theoretical interest. We discuss the relevance of the latter also for cryptographic applications, and we provide a self-contained survey of the known approaches to both problems. Those for the cSRS problem work only for small finite fields, have exponential complexity in the characteristic of the base finite field (since they require computing and finding roots of polynomials of large degree), leaving the problem open. In the second part of the paper, we propose and analyse some alternative techniques — based either on Hasse invariant or division polynomials — and we explain the reasons why them do not readily lead to efficient cSRS algorithms, but they may open promising research directions.

Available format(s)
Public-key cryptography
Publication info
Isogeny-based cryptography Supersingular elliptic curve Endomorphism ring
Contact author(s)
marzio mula @ unitn it
nadir murru @ unitn it
federico pintore @ uniba it
2022-11-02: last of 3 revisions
2022-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marzio Mula and Nadir Murru and Federico Pintore},
      title = {On Random Sampling of Supersingular Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2022/528},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.