**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 ]