Paper 2019/1316

Binary Kummer Line

Sabyasachi Karati

Abstract

In this work, we explore the problem of secure and efficient scalar multiplication on binary field using Kummer lines. Gaudry and Lubicz first introduced the idea of Kummer line in [12]. We investigate the possibilities of speedups using Kummer lines compared to binary Edwards curve and Weierstrass curves. Firstly, we propose a binary Kummer line $\mathsf{BKL}251$ on binary field $\mathbb{F}_{2^{251}}$ where the associated elliptic curve satisfies the required security conditions and offers 124.5-bit security which is same as the $\mathsf{BBE251}$ and $\mathsf{CURVE2251}$. $\mathsf{BKL}251$ also has small parameter and small base point. We implement the software of $\mathsf{BKL}251$ using the instruction ${\tt PCLMULQDQ}$ of modern Intel processors. For fair comparison, we also implement the software $\mathsf{BEd}251$ for binary Edwards curve introduced in [4] using the same field arithmetic library of the $\mathsf{BKL}251$ and thus this work also complements the works of [7,4]. In both the implementations, scalar multiplications take constant time which use Montgomery ladder. Binary Kummer line requires $4[\mathsf{M}]+5[\mathsf{S}]+1[\mathsf{C}]+1[\mathsf{B}]$ field operations for each ladder step where ladder step of binary Edwards curve requires $4[\mathsf{M}]+4[\mathsf{S}]+2[\mathsf{C}]+1[\mathsf{B}]$. Our experimental results show that fixed-base scalar multiplication of $\mathsf{BKL}251$ is $8.36\%-9.33\%$ faster than that of $\mathsf{BEd}251$. On the other hand, variable-base scalar multiplications take almost same time for both the curves (variable-base scalar multiplication of $\mathsf{BKL}251$ is $0.25\%-1.55\%$ faster than that of $\mathsf{BEd}251$).