Efficient Scalar Multiplication of ECC Using Lookup Table and Fast Repeating Point Doubling - Fu-Jung Kan; Yan-Haw Chen; Jeng-Jung Wang; Chong-Dao Lee (Mathematics)
Reducing the computation time of scalar multiplication for elliptic curve cryptography is a significant challenge. This study proposes an efficient scalar multiplication method for elliptic curves over finite fields <semantics>GF(2m)</semantics>. The proposed method first converts the scalar into a binary number. Then, using Horner’s rule, the binary number is divided into fixed-length bit-words. Each bit-word undergoes repeating point doubling, which can be precomputed. However, repeating point doubling typically involves numerous inverse operations. To address this, significant effort has been made to develop formulas that minimize the number of inverse operations. With the proposed formula, regardless of how many times the operation is repeated, only a single inverse operation is required. Over <semantics>GF(2m)</semantics>, the proposed method for scalar multiplication outperforms the sliding window method, which is currently regarded as the fastest available. However, the introduced formulas require more multiplications, squares, and additions. To reduce these operations, we further optimize the square operations; however, this introduces a trade-off between computation time and memory size. These challenges are key areas for future improvement.