On Random Sampling of Supersingular Elliptic Curves

Marzio Mula, Nadir Murru, and Federico Pintore

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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Isogeny-based cryptographySupersingular elliptic curveEndomorphism ring
Contact author(s)
marzio mula @ unitn it
federico pintore @ uniba it
History
2022-05-23: last of 2 revisions
See all versions
Short URL
https://ia.cr/2022/528

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.