Paper 2016/899

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

Kittiphop Phalakarn, Kittiphon Phalakarn, and Vorapong Suppakitpaisarn


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.

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{

Available format(s)
Publication info
Published elsewhere. Major revision.
Information and Communication SecurityEfficient ImplementationsParallel AlgorithmsElliptic Curve CryptographyScalar Multiplicationk-ChainSide-Channel Attack Countermeasure
Contact author(s)
vorapong @ is s u-tokyo ac jp
2017-01-25: last of 2 revisions
2016-09-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kittiphop Phalakarn and Kittiphon Phalakarn and Vorapong Suppakitpaisarn},
      title = {Parallelized Side-Channel Attack Resisted Scalar Multiplication Using q-Based Addition-Subtraction k-chains},
      howpublished = {Cryptology ePrint Archive, Paper 2016/899},
      year = {2016},
      doi = {10.1109/CANDAR.2016.0035},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.