Cryptology ePrint Archive: Report 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$).

Category / Keywords: implementation / Binary Finite Field Arithmetic, Elliptic Curve Cryptography, Kummer Line, Edwards Curve, Montgomery Ladder, Scalar Multiplication.

Date: received 13 Nov 2019, last revised 20 Nov 2019

Contact author: sabyasachi karati at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20191121:053344 (All versions of this report)

Short URL: ia.cr/2019/1316


[ Cryptology ePrint archive ]