Parallel windowed method for scalar multiplication in elliptic curve cryptography

Parallel windowed method for scalar multiplication in elliptic curve cryptography

연구 분야: Cryptography

학회: CASCON '20: Proceedings of the 30th Annual International Conference on Computer Science and Software Engineering

Commercial software applications, such as permissioned Blockchains, are increasingly dependent on Elliptic Curve Cryptography for digital signatures. Elliptic Curve Cryptography uses a group operation, point addition, in the set of points on an elliptic curve over a prime field. Scalar multiplication is the repeated addition of a fixed point P in the curve. A common optimization for scalar multiplication, the windowed method, decomposes the number of additions into nibbles or other digits, using a pre-computed table of values P, 2P, 3P, and so on to compute the final product. To avoid side-channel attacks, implementations must avoid conditional execution. This ensures constant-time and constant-power execution. This paper presents a theoretical 42% reduction in latency for the windowed method using two tables and three cores, versus a single-threaded computation.