On computing the double point multiplication in elliptic curve cryptography

The double point-multiplication (DPM) operation on elliptic curves, denoted as u.P + v.Q, where u and v are nonnegative integers and P, Q are points on the curve, is a critical operation in digital signature verification. Its computational scheme significantly impacts system performances in terms of speed, memory usage, and security. This article introduces a range of straightforward algorithms for DPM, which leverage an iterative uniform pattern based on constant-time arithmetic. This approach mitigates side-channel attacks (SCA) that exploit timing or power consumption measurements to compromise secret keys u and v. The proposed algorithms employ a w-bit windowing method to simultaneously recode the binary strings u and v and evaluate DPM on-the-fly from left-to-right. This one-pass recode/evaluation process accelerates DPM, reduces memory overhead, and enhances resilience against SCA. The new algorithms are systematically evaluated using precise analytic formulas for speed, memory usage, and security. They prioritize simplicity and flexibility, enabling easy adjustments between speed-memory and speed-security trade-offs to meet various constraints. Comparative analysis against state-of-the-art methods is conducted, comprehensively examining complexities using NIST-recommended GF(2l) curves, as well as twisted Edwards and Montgomery GF(p) curves.