Constructing Elliptic Curves for the GLV Method with Low-cost Decomposition

Abstract

The GLV method allows to improve scalar multiplication on an elliptic curve E/𝔽 _q with an efficiently computable endomorphism Φ : E → E over 𝔽 _q . For points in a subgroup of large prime order r this requires decomposition of scalar k = k₀ + k₁λ mod r, where Φ acts on the subgroup of order r as multiplication by λ ∈ 𝔽 _r and k₀, k₁ are integers $O\left(\sqrt{r}\right)$ . In this note we consider the case when λ is of the form λ = 2 ^s + a, where a is a small integer and $\lambda =O\left(\sqrt{r}\right)$, which allows very easy and fast decomposition of k especially in hardware implementations. We give a method to construct such elliptic curves based on the complex multiplication method, and give examples of elliptic curves for λ ∈ {2 ^s , 2 ^s − 1} and various security levels.