Speeding Up Elliptic Curve Multiplication with Mixed-base Representation for Applications to SIDH Ciphers

Abstract

Elliptic curve multiplications can be improved by replacing the standard ladder algorithm's base 2 representation of the scalar multiplicand, with mixed-base representations with power-of-2 bases, processing the n bits of the current digit in one optimized step. For this purpose, we also present a new methodology to compute short Weierstrass form elliptic curve operations of the type mP+nQ, where m and n are small integers, aiming for faster implementation with the lowest cost among previous algorithms, using only one inversion. In particular, the proposed techniques enable more opportunities for optimizing computations, leading to an important speed-up for applications based on elliptic curves, including the post-quantum cryptosystem Super Singular Isogeny Diffie Hellman (SIDH).