Fast and Secure Scalar Multiplication on Elliptic Curve GLS254
Ryosuke Kido, Atsuko Miyaji · 2024
Elliptic curve cryptosystems (ECCs), based on the discrete logarithm problem, give compact and fast cryptosystems with smaller key sizes than Rivest-Shamir-Adleman (RSA). It is expected to be used in$\text{IoT}$devices, where available memory is limited. In addition, it is necessary to construct ECCs secure against side-channel attacks (SCA). Therefore, more compact and fast ECCs secure against SCA is needed. Elliptic curve scalar multiplication (ECSM) is the dominant computation of ECCs, and thus, it is important to build a secure, compact, and fast ECSM. GLS254 defined over$\mathbb{F}_{q^{2}}$(with$q=2^{m}$) was proposed, which gives a fast ECSM by using an endomorphism. Recently, GLS254 is improved by newly introducing$(x,\ s)$. coordinates, where an addition formula can be executed without any exception. In this study, we further improve secure, compact, and fast GLS254 by introducing additional new coordinates and optimizing ECSM. As a result, our ECSM achieves 29371 cycles on an Intel x86 CPU, which improves the best previous records by 7.1 %.