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

Kittiphop Phalakarn; Kittiphon Phalakarn; Vorapong Suppakitpaisarn

Paper 2016/899

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

Kittiphop Phalakarn, 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.

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{http://ieeexplore.ieee.org/document/7818605/

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Major revision. http://ieeexplore.ieee.org/document/7818605/
DOI: 10.1109/CANDAR.2016.0035
Keywords: Information and Communication Security Efficient Implementations Parallel Algorithms Elliptic Curve Cryptography Scalar Multiplication k-Chain Side-Channel Attack Countermeasure
Contact author(s): vorapong @ is s u-tokyo ac jp
History: 2017-01-25: last of 2 revisions; 2016-09-15: received; See all versions
Short URL: https://ia.cr/2016/899
License: CC BY

BibTeX

@misc{cryptoeprint:2016/899,
      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},
      url = {https://eprint.iacr.org/2016/899}
}