Cryptology ePrint Archive: Report 2020/1111

Extending the Signed Non-zero Bit and Sign-Aligned Columns Methods to General Bases for Use in Cryptography

Abhraneel Dutta and Aaron Hutchinson and Koray Karabina

Abstract: An efficient scalar multiplication algorithm is a crucial component of elliptic curve cryptosystems. We propose a scalar multiplication algorithm based on scalar recodings that is regular in nature. Our scalar multiplication algorithm is made from two scalar recoding algorithms called $\Recode$ and $\Align$. $\Recode$ is the generalization of the signed non-zero bit recoding algorithm given by Hedabou, Pinel and Bénéteau in 2005. It recodes the $k$-ary representation of the given scalar into a signed non-zero form by means of a small lookup table. On the other hand, $\Align$ is the generalized $k$-ary version of the sign-aligned columns recoding algorithm given by Faz-Hernández, Longa and Sánchez in 2014. It recodes the $k$-ary representation of a scalar in such a way that the sign of each of its digits agrees with a given $\lbrace 1,-1 \rbrace$-valued sequence. When analyzing the choice of $k \in \lbrace 2,3 \rbrace$, we find some theoretical evidence that $k=3$ may offer better performance in certain scenarios.

Category / Keywords: public-key cryptography / Elliptic curves, scalar multiplication, scalar recoding

Date: received 14 Sep 2020, last revised 27 Oct 2020

Contact author: adutta2016 at fau edu,a5hutchinson@uwaterloo ca,koray karabina@nrc-cnrc gc ca

Available format(s): PDF | BibTeX Citation

Version: 20201028:023017 (All versions of this report)

Short URL: ia.cr/2020/1111


[ Cryptology ePrint archive ]