Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy

Abstract : The use of elliptic curves in cryptography relies on the ability to count the number of points on a given curve. Before 1999, the SEA algorithm was the only efficient method known for random curves. Then Satoh proposed a new algorithm based on the canonical p-adic lift of the curve for p>=5. In an earlier paper, the authors extended Satoh's method to the case of characteristics two and three. This paper presents an implementation of the Satoh-FGH algorithm and its application to the problem of finding curves suitable for cryptography. By combining Satoh-FGH and an early-abort strategy based on SEA, we are able to find secure random curves in characteristic two in much less time than previously reported. In particular we can generate curves widely considered to be as secure as RSA-1024 in less than one minute each on a fast workstation.
Type de document :
Communication dans un congrès
Birgit Pfitzman. Eurocrypt, 2001, Innsbruck, Austria. Springer Verlag, 2045, pp.14-29, 2000, LNCS. 〈10.1007/3-540-44987-6_2〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00514426
Contributeur : Pierrick Gaudry <>
Soumis le : jeudi 2 septembre 2010 - 13:19:22
Dernière modification le : mercredi 25 avril 2018 - 10:45:20
Document(s) archivé(s) le : vendredi 3 décembre 2010 - 02:37:03

Fichier

euro01.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mireille Fouquet, Pierrick Gaudry, Robert Harley. Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy. Birgit Pfitzman. Eurocrypt, 2001, Innsbruck, Austria. Springer Verlag, 2045, pp.14-29, 2000, LNCS. 〈10.1007/3-540-44987-6_2〉. 〈inria-00514426〉

Partager

Métriques

Consultations de la notice

488

Téléchargements de fichiers

85