Revisiting Atomic Patterns for Scalar Multiplications on Elliptic Curves Extended Version
Franck Rondepierre · 2013
Abstract. This paper deals with the protection of elliptic curve scalar multiplications against side-channel analysis by using the atomicity prin-ciple. Unlike other atomic patterns, we investigate new formulæ with same cost for both doubling and addition. This choice is particularly well suited to evaluate double scalar multiplications with the Straus-Shamir trick. Since fixed point multiplications highly benefit from this trick, our pattern allows a huge improvement in this case as other atomic pat-terns cannot use it. Surprisingly, in other cases our choice remains very efficient. Besides, we also point out a security threat when the curve parameter a is null and propose an even more efficient pattern in this case.