Parallel Windowed Method for Scalar Multiplication in Elliptic Curve Cryptography

Abstract

Commercial applications, including Blockchain, require large numbers of cryptographic signing and verification operations, increasingly using Elliptic Curve Cryptography. This uses a group operation (called point addition) in the set of points on an elliptic curve over a prime field. Scalar multiplication of the repeated addition of a fixed point, P , in the curve. Along with the infinity point, which serves as the identity of addition and the zero of scalar multiplication, this forms a vector space over the prime field. The scalar multiplication can be accelerated by decomposing the number of additions into nibbles or other digits, and using a pre-computed table of values P , 2P , 3P, . . . This is called a windowed method. To avoid side-channel attacks, implementations must ensure that the time and power used do not depend on the scalar. Avoiding conditional execution ensures constant-time and constant-power execution. This thesis presents a theoretical reduction in latency for the windowed method by introducing parallelism. Using three cores can achieve an improvement of 42% in the latency versus a single-threaded computation.