PSSM: An Efficient Parallel Single-Scalar Multiplication Framework for ECC on CPU

Scalar multiplication is a key operation on elliptic curves, and the implementation of scalar encoding is crucial to overall performance. Existing research on optimizing scalar encoding rarely considers parallel optimization for computing multiple single-scalar multiplications, because different scalars lead to different ordered calculation sequences, which makes it difficult to use SIMD and other techniques for parallel computing. In order to solve the problem of inconsistent scalar computation sequences, this paper proposes an efficient parallel single-scalar multiplication framework, named PSSM. By introducing a greedy sequence scheduling algorithm, this framework generates identical operation sequences when computing different scalars in parallel. Then, the method of constructing parallel modules with SIMD is given. The experimental results show that the common encoding methods—NAF, wNAF, and BNAF—implemented with PSSM achieve speedups of 5.98×, 5.69×, and 5.38×, respectively, on the i7-14700HX platform. The framework proposed can improve the implementation speed of existing NAF and its variant scalar encoding methods on CPU, which is significant for improving the performance of ECC-based cryptographic systems.