Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00514426
Contributor : Pierrick Gaudry <>
Submitted on : Thursday, September 2, 2010 - 1:19:22 PM
Last modification on : Thursday, March 5, 2020 - 6:21:51 PM
Long-term archiving on: : Friday, December 3, 2010 - 2:37:03 AM

File

euro01.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Mireille Fouquet, Pierrick Gaudry, Robert Harley. Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy. Eurocrypt, 2001, Innsbruck, Austria. pp.14-29, ⟨10.1007/3-540-44987-6_2⟩. ⟨inria-00514426⟩

Share

Metrics

Record views

809

Files downloads

352