Constructing Elliptic Curves for the GLV Method with Low-cost Decomposition
Michał Wroński, Robert Dryło, Tomasz Kijko, Piotr Bora · Fundamenta Informaticae · 2017
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 0 + k 1 λ mod r, where Φ acts on the subgroup of order r as multiplication by λ ∈ 𝔽 r and k 0 , k 1 are integers O ( r ) . In this note we consider the case when λ is of the form λ = 2 s + a, where a is a small integer and λ = O ( r ) , 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.