Abstract Elliptic curve cryptography (ECC) is a typical public key cryptography technique that can ensure equivalent security with considerably smaller key sizes than Rivest-Shamir-Adleman (RSA). Hence, various implementations based on ECC are recommended for block chain and Internet of Things (IoT) devices. Because elliptic curve scalar multiplication (ECSM) is a fundamental computation in ECC, enhancing the security and efficiency of ECSM is important. ECSM specifies a scalar multiplication algorithm and elliptic curve addition formulae. Elliptic curve addition formulae on affine coordinates are compact from a memory cost perspective but weak against side channel attacks. Elliptic curve complete addition (CA) formulae can achieve secure ECSMs but are inefficient. A newly proposed secure ECSM, which uses a right-to-left (RL) scalar multiplication algorithm and (extended) affine coordinates, takes advantage of elliptic curve addition formulae on affine coordinates. However, it can only scan the input scalars from right to left. We propose new ECSMs, which can scan the input scalars from left to right (LR) based on (extended) affine coordinates. We also prove that our LR ECSMs satisfy secure generality without requiring exceptional computations. We enhance the efficiency of both LR and RL ECSMs with optimized inversion. Our LR ECSM with a memory of 12 field elements reduces that of the Montgomery ladder and Joye’s LR with CA formulae by 36.84% and that of 2-ary RL with (extended) affine coordinates by 14.29%, respectively. Our compact ECSMs are fit for applications on IoT devices and block chain, with a critical memory requirement.

Elliptic curve cryptosystems (ECCs) are widely used because of their short key size. They can ensure enough security with shorter keys, and use less memory space to reduce parameters. Hence, an elliptic curve is typically used in embedded systems. The dominant computation of an ECC is scalar multiplication $$Q = kP, P \in E({\mathbb F}_{q})$$ . Thus, the security and efficiency of scalar multiplication are paramount. To render secure ECCs, complete addition formulae can be employed for a secure scalar multiplication. However, this requires significant memory and is thus not suitable for compact devices. Several coordinates exist for elliptic curves such as affine, Jacobian, projective. The complete addition formulae are not based on affine coordinates and thus require considerable memory. In this study, we achieved a compact ECC by focusing on affine coordinates. In fact, affine coordinates are highly advantageous in terms of memory but require many if statements for scalar multiplication owing to exceptional points. We improve the scalar multiplication and reduce the limitations for input k. Furthermore, we extend the affine addition formulae to delete some exceptional inputs for scalar multiplication. Our compact ECC reduces memory complexity up to 26 % and is much more efficient compared to Joye’s RL 2-ary algorithm with the complete addition of formulae when the ratio I / M of computational complexity of inversion (I) to multiplication (M) is less than 7.2.