Cryptology ePrint Archive: Report 2015/408

Revisiting Atomic Patterns for Scalar Multiplications on Elliptic Curves

Franck Rondepierre

Abstract: This paper deals with the protection of elliptic curve scalar multiplications against side-channel analysis by using the atomicity principle. 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 patterns 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.

Category / Keywords: implementation / Elliptic Curves, Scalar Multiplication, Straus-Shamir Trick, Side-Channel Analysis, Atomicity

Original Publication (with major differences): CARDIS 2013

Date: received 30 Apr 2015

Contact author: f rondepierre at oberthur com

Available format(s): PDF | BibTeX Citation

Version: 20150501:121845 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]