On Random Sampling of Supersingular Elliptic Curves

Marzio Mula; Nadir Murru; Federico Pintore

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Isogeny-based cryptography Supersingular elliptic curve Endomorphism ring
Contact author(s): marzio mula @ unitn it
nadir murru @ unitn it
federico pintore @ uniba it
History: 2022-11-02: last of 3 revisions; 2022-05-10: received; See all versions
Short URL: https://ia.cr/2022/528
License: CC BY

BibTeX

@misc{cryptoeprint:2022/528,
      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{https://eprint.iacr.org/2022/528}},
      url = {https://eprint.iacr.org/2022/528}
}