On the elliptic curves y^2=x^3 - c with embedding degree one

Curves over finite and local fields (11G20) Exponential sums (11T23) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Elliptic curves (14H52) Cryptography (94A60)

Review text

This paper determines when the elliptic curves \(y^2=x^3-c\), defined over a prime field \(F_p\), \(p\equiv 1 \bmod 3\), can have embedding degree \(k=1\) (the embedding degree is the smallest integer \(k\) such that \(n\mid p^k-1\), where \(n\) is the largest prime divisor of \( \sharp E(F_p))\). Curves with small embedding degree are useful in pairing-based cryptography. To find the conditions to have \(k=1\), the paper computes \( \sharp E(F_p)\) (in terms of characters and Jacobi sums) when \(p\equiv 1 \bmod 3\) (if \(p\equiv 2 \bmod 3\), that cardinal is always \(p+1\)). Theorem 1 gives explicit formulas for \( \sharp E(F_p)\) according to the values of \( \chi_2(c)\), \(\chi_3(c)\), \(\chi_6(c)\), where \(\chi_2\), \(\chi_3\), \(\chi_6\) are quadratic, cubic and sextic characters on \(F_p\). As a corollary, the elliptic curve \(y^2=x^3-1\) over \(F_p\), with \(p=27A^2+1\), has embedding degree 1. The conjecture of \textit{P. T. Bateman} and \textit{R. A. Horn} [Math. Comput. 16, 363--367 (1962; Zbl 0105.03302)] shows that there are (conjecturally) infinitely many primes of this form. Table 1 gives, for different cryptographic security levels, the minimum bit length of \(p\) and \(n\) for an efficient and secure implementation. Finally, the paper provides several examples of such values.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: On the elliptic curves \(y^{2}=x^{3} - c\) with embedding degree one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q555157)