期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2018
卷号：8
期号：2
页码：166-185
语种：English
出版社：International Journal of Networking and Computing
摘要：This paper introduces an optimal representation for a right-to-left parallel elliptic curve scalar point multiplication. The right-to-left approach is easier to parallelize than the conventional left-to-right approach. However, unlike the left-to-right approach, there is still no work considering number representations for the right-to-left parallel calculation. By simplifying the implementation by Robert, we devise a mathematical model to capture the computation time of the calculation. Then, for any arbitrary amount of doubling time and addition time, we propose algorithms to generate representations which minimize the time in that model. As a result, we can show a negative result that a conventional representation like NAF is almost optimal. The parallel computation time obtained from any representation cannot be better than NAF by more than 1%. In addition to that, we devise a time model and propose an algorithm to generate optimal representations for multi-scalar point multiplication (under a condition). Similar to the result of scalar point multiplication, NAF is almost optimal also for multi-scalar point multiplication as the difference of parallel computation time obtained from optimal representation and NAF is less than 1% in all experimental settings.
其他摘要：This paper introduces an optimal representation for a right-to-left parallel elliptic curve scalar point multiplication. The right-to-left approach is easier to parallelize than the conventional left-to-right approach. However, unlike the left-to-right approach, there is still no work considering number representations for the right-to-left parallel calculation. By simplifying the implementation by Robert, we devise a mathematical model to capture the computation time of the calculation. Then, for any arbitrary amount of doubling time and addition time, we propose algorithms to generate representations which minimize the time in that model. As a result, we can show a negative result that a conventional representation like NAF is almost optimal. The parallel computation time obtained from any representation cannot be better than NAF by more than 1%. In addition to that, we devise a time model and propose an algorithm to generate optimal representations for multi-scalar point multiplication (under a condition). Similar to the result of scalar point multiplication, NAF is almost optimal also for multi-scalar point multiplication as the difference of parallel computation time obtained from optimal representation and NAF is less than 1% in all experimental settings.
关键词：information and communication security; efficient implementation; elliptic curve cryptography; scalar point multiplication; binary representation; parallel algorithms
