Cryptology ePrint Archive: Report 2016/899

Parallelized Side-Channel Attack Resisted Scalar Multiplication Using q-Based Addition-Subtraction k-chains

Kittiphop Phalakarn and Kittiphon Phalakarn and Vorapong Suppakitpaisarn

Abstract: This paper presents parallel scalar multiplication techniques for elliptic curve cryptography using q-based addition-subtraction k-chain which can also effectively resist side-channel attack. Many techniques have been discussed to improve scalar multiplication, for example, double-and-add, NAF, w-NAF, addition chain and addition-subtraction chain. However, these techniques cannot resist side-channel attack. Montgomery ladder, random w-NAF and uniform operation techniques are also widely used to prevent side-channel attack, but their operations are not efficient enough comparing to those with no side-channel attack prevention. We have found a new way to use k-chain for this purpose. In this paper, we extend the definition of k-chain to q-based addition-subtraction k-chain and modify an algorithm proposed by Jarvinen et al. to generate the q-based addition-subtraction k-chain. We show the upper and lower bounds of its length which lead to the computation time using the new chain techniques. The chain techniques are used to reduce the cost of scalar multiplication in parallel ways. Comparing to w-NAF, which is faster than double-and-add and Montgomery ladder technique, the maximum computation time of our q-based addition-subtraction k-chain techniques can have up to 25.92% less addition costs using only 3 parallel computing cores. We also discuss on the optimization for multiple operand point addition using hybrid-double multiplier which is proposed by Azarderakhsh and Reyhani-Masoleh. The proposed parallel chain techniques can also tolerate side-channel attack efficiently.

Category / Keywords: Information and Communication Security; Efficient Implementations; Parallel Algorithms; Elliptic Curve Cryptography; Scalar Multiplication; k-Chain; Side-Channel Attack Countermeasure

Original Publication (with major differences):

Date: received 14 Sep 2016, last revised 25 Jan 2017

Contact author: vorapong at is s u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Note: This paper has been accepted for publication at proceedings of the Fourth International Symposium on Computing and Networking (CANDAR 2016), which is published by IEEE. It has been further edited by IEEE, and the final version is appearing at \url{

Version: 20170125:112754 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]