Welcome to the resource topic for 2019/1316
Title:
Binary Kummer Line
Authors: Sabyasachi Karati
Abstract:Gaudry and Lubicz introduced the idea of Kummer line in 2009, and Karati and Sarkar proposed three Kummer lines over prime fields in 2017. In this work, we explore the problem of secure and efficient scalar multiplications on binary field using Kummer line and investigate the possibilities of speedups using Kummer line compared to Koblitz curves, binary Edwards curve and Weierstrass curves. We propose a binary Kummer line \mathsf{BKL}251 over binary field \mathbb{F}_{2^{251}} where the associated elliptic curve satisfies the required security conditions and offers 124.5-bit security which is the same as that of Binary Edwards curve \mathsf{BEd251} and Weierstrass curve \mathsf{CURVE2251}. \mathsf{BKL}251 has small curve parameter and small base point. We implement our software of \mathsf{BKL}l251 using the instruction {\tt PCLMULQDQ} of modern Intel processors and batch software \mathsf{BBK251} using bitslicing technique. For fair comparison, we also implement the software \mathsf{BEd}251 for binary Edwards curve. In both the implementations, scalar multiplications take constant time which use Montgomery ladders. In case of left-to-right Montgomery ladder, both the Kummer line and Edwards curve have almost the same number of field operations. For right-to-left Montgomery ladder scalar multiplication, each ladder step of binary Kummer line needs less number of field operations compared to Edwards curve. Our experimental results show that left-to-right Montgomery scalar multiplications of \mathsf{BKL}251 are 9.63\% and 0.52\% faster than those of \mathsf{BEd}251 for fixed-base and variable-base, respectively. Left-to-right Montgomery scalar multiplication for variable-base of \mathsf{BKL}251 is 39.74%, 23.25% and 32.92% faster than those of the curves \mathsf{CURVE2251}, K-283 and B-283 respectively. Using right-to-left Montgomery ladder with precomputation, \mathsf{BKL}251 achieves 17.84% speedup over \mathsf{BEd}251 for fixed-base scalar multiplication. For batch computation, \mathsf{BBK251} has comparatively the same (slightly faster) performance as \mathsf{BBE251} and \mathsf{sect283r1}. Also it is clear from our experiments that scalar multiplications on \mathsf{BKL}251 and \mathsf{BEd251} are (approximately) 65% faster than one scalar multiplication (after scaling down) of batch software \mathsf{BBK251} and \mathsf{BBE251}.
ePrint: https://eprint.iacr.org/2019/1316
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .