Cryptology ePrint Archive: Report 2014/427

Fast point multiplication algorithms for binary elliptic curves with and without precomputation

Thomaz Oliveira and Diego F. Aranha and Julio López and Francisco Rodríguez-Henríquez

Abstract: In this paper we introduce new methods for computing constant-time variable-base point multiplications over the Galbraith-Lin-Scott (GLS) and the Koblitz families of elliptic curves. Using a left-to-right double-and-add and a right-to-left halve-and-add Montgomery ladder over a GLS curve, we present some of the fastest timings yet reported in the literature for point multiplication. In addition, we combine these two procedures to compute a multi-core protected scalar multiplication. Furthermore, we designed for the first time a regular $\tau$-adic scalar expansion for Koblitz curves. As a result, using the regular recoding approach, we set the speed record for a single constant-time point multiplication on standardized binary elliptic curves at the $128$-bit security level.

Category / Keywords: public-key cryptography / binary elliptic curves, scalar multiplication, software implementation

Date: received 4 Jun 2014, last revised 30 Jul 2014

Contact author: thomaz figueiredo at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140731:042243 (All versions of this report)

Short URL: ia.cr/2014/427

Discussion forum: Show discussion | Start new discussion