A Parallelized Elliptic Curve Multiplication and its Resistance against Side-Channel Attacks (Algorithms in Algebraic Systems and Computation Theory)

This paper proposes afast scalar multiplication algorithm, which improves both on an addition chain and an addition formula, based on [MOn87].Our addition chain is applicable for for any types of elliptic curves over finite fields Fg, requires no table look-up (or afew $\mathrm{p}\mathrm{r}\triangleright \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{d}$ points) and can be implemented in parallel.The computing time for $n$-bit scalar multiplication is one $\mathrm{E}\mathrm{C}\mathrm{D}\mathrm{B}\mathrm{L}+(n-1)$ ECADDs in the parallel case and $(n-1)\mathrm{E}\mathrm{C}\mathrm{D}\mathrm{B}\mathrm{L}\mathrm{s}+(n-1)$ ECADDs in the single case.We also propose faster addition formulas which only use the $x$ -coordinates of the points.We also show acriteria which makes our algorithm resistant against the side channel attacks (SCA).We establish afaster scalar multiplication resistant against the SCA in both single and parallel cases.The improvement is about 37% for two processors and 5.6% for asingle processor.