Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases

Heuberger, Clemens; Krenn, Daniel

Journal de théorie des nombres de Bordeaux, Tome 25 (2013) no. 2, pp. 353-386.

On étudie des systèmes de numération ${\sum }_{j=0}^{\ell -1}{\Phi }^j\left(D_j\right)$ avec un endomorphisme $\Phi$ d’un groupe abélien. On démontre que dans un tel système la condition $w$-NAF (chaque bloc de $w$ chiffres consécutifs contient au plus un chiffre non nul) minimise le poids de Hamming par rapport à toutes les représentations avec le même ensemble de chiffres si et seulement si la condition de sous-additivité est vérifiée (la somme de deux représentations de poids $1$ admet une représentation optimale $w$-NAF).

Ce résultat est ensuite appliqué sur les bases entières quadratiques complexes, qui sont utilisées pour la multiplication par un scalaire dans la cryptographie sur les courbes elliptiques. On présente un critère algorithmique et des réponses génériques pour des cas différents. Des entiers quadratiques complexes de trace au moins $3$ (en valeur absolue) admettent une $w$-NAF optimale pour $w\ge 4$. Il en va de même pour le cas particulier de la base $(\pm 3\pm \sqrt{-3})/2$ (quatre cas) et $w\ge 2$, qui correspond à des courbes de Koblitz en caractéristique trois. Dans le cas de $\tau =\pm 1\pm i$ (quatre cas), l’optimalité dépend de la parité de $w$. Des résultats numériques pour des traces plus petites sont présentés.

We consider digit expansions ${\sum }_{j=0}^{\ell -1}{\Phi }^j\left(d_j\right)$ with an endomorphism $\Phi$ of an Abelian group. In such a numeral system, the $w$-NAF condition (each block of $w$ consecutive digits contains at most one nonzero) is shown to minimise the Hamming weight over all expansions with the same digit set if and only if it fulfills the subadditivity condition (the sum of every two expansions of weight $1$ admits an optimal $w$-NAF).

This result is then applied to imaginary quadratic bases, which are used for scalar multiplication in elliptic curve cryptography. Both an algorithmic criterion and generic answers for various cases are given. Imaginary quadratic integers of trace at least $3$ (in absolute value) have optimal $w$-NAFs for $w\ge 4$. The same holds for the special case of base $(\pm 3\pm \sqrt{-3})/2$ (four cases) and $w\ge 2$, which corresponds to Koblitz curves in characteristic three. In the case of $\tau =\pm 1\pm i$ (again four cases), optimality depends on the parity of $w$. Computational results for small trace are given.

Classification : 11A63, 94A60
Mots clés : $\tau $-adic expansions, width-$w$ non-adjacent forms, redundant digit sets, elliptic curve cryptography, Koblitz curves, Frobenius endomorphism, scalar multiplication, Hamming weight, optimality, imaginary quadratic bases

[1] Roberto Avanzi, Clemens Heuberger, and Helmut Prodinger, Minimality of the Hamming weight of the $\tau$-NAF for Koblitz curves and improved combination with point halving. Selected Areas in Cryptography: 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11–12, 2005, Revised Selected Papers (B. Preneel and S. Tavares, eds.), Lecture Notes in Comput. Sci., vol. 3897, Springer, Berlin, 2006, pp. 332–344. | MR | Zbl

[2] —, Scalar multiplication on Koblitz curves. Using the Frobenius endomorphism and its combination with point halving: Extensions and mathematical analysis. Algorithmica 46 (2006), 249–270. | MR | Zbl

[3] —, Arithmetic of supersingular Koblitz curves in characteristic three. Tech. Report 2010-8, Graz University of Technology, 2010, http://www.math.tugraz.at/fosp/pdfs/tugraz_0166.pdf, also available as Cryptology ePrint Archive, Report 2010/436, http://eprint.iacr.org/.

[4] Roberto Maria Avanzi, A Note on the Signed Sliding Window Integer Recoding and a Left-to-Right Analogue. Selected Areas in Cryptography: 11th International Workshop, SAC 2004, Waterloo, Canada, August 9-10, 2004, Revised Selected Papers (H. Handschuh and A. Hasan, eds.), Lecture Notes in Comput. Sci., vol. 3357, Springer-Verlag, Berlin, 2004, pp. 130–143. | MR | Zbl

[5] Ian F. Blake, V. Kumar Murty, and Guangwu Xu, Efficient algorithms for Koblitz curves over fields of characteristic three. J. Discrete Algorithms 3 (2005), no. 1, 113–124. | MR | Zbl

[6] —, A note on window $\tau$-NAF algorithm. Inform. Process. Lett. 95 (2005), 496–502. | MR

[7] —, Nonadjacent radix-$\tau$ expansions of integers in Euclidean imaginary quadratic number fields. Canad. J. Math. 60 (2008), no. 6, 1267–1282. | MR | Zbl

[8] László Germán and Attila Kovács, On number system constructions. Acta Math. Hungar. 115 (2007), no. 1-2, 155–167. | MR | Zbl

[9] Daniel M. Gordon, A survey of fast exponentiation methods. J. Algorithms 27 (1998), 129–146. | MR | Zbl

[10] Clemens Heuberger, Redundant $\tau$-adic expansions II: Non-optimality and chaotic behaviour. Math. Comput. Sci. 3 (2010), 141–157. | MR | Zbl

[11] Clemens Heuberger and Daniel Krenn, Analysis of width-$w$ non-adjacent forms to imaginary quadratic bases. J. Number Theory 133 (2013), 1752–1808. | MR

[12] Clemens Heuberger and Helmut Prodinger, Analysis of alternative digit sets for nonadjacent representations. Monatsh. Math. 147 (2006), 219–248. | MR | Zbl

[13] Thomas W. Hungerford, Algebra. Graduate Texts in Mathematics, vol. 73, Springer, 1996. | MR | Zbl

[14] Jonathan Jedwab and Chris J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation. Electron. Lett. 25 (1989), 1171–1172. | Zbl

[15] Donald E. Knuth, Seminumerical algorithms. third ed., The Art of Computer Programming, vol. 2, Addison-Wesley, 1998. | MR | Zbl

[16] Neal Koblitz, CM-curves with good cryptographic properties. Advances in cryptology—CRYPTO ’91 (Santa Barbara, CA, 1991) (J. Feigenbaum, ed.), Lecture Notes in Comput. Sci., vol. 576, Springer, Berlin, 1992, pp. 279–287. | MR | Zbl

[17] —, An elliptic curve implementation of the finite field digital signature algorithm. Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998), Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 327–337. | MR

[18] Markus Kröll, Optimality of digital expansions to the base of the Frobenius endomorphism on Koblitz curves in characteristic three. Tech. Report 2010-09, Graz University of Technology, 2010, available athttp://www.math.tugraz.at/fosp/pdfs/tugraz_0167.pdf.

[19] M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. | MR | Zbl

[20] Willi Meier and Othmar Staffelbach, Efficient multiplication on certain nonsupersingular elliptic curves. Advances in cryptology—CRYPTO ’92 (Santa Barbara, CA, 1992) (Ernest F. Brickell, ed.), Lecture Notes in Comput. Sci., vol. 740, Springer, Berlin, 1993, pp. 333–344. | MR | Zbl

[21] James A. Muir and Douglas R. Stinson, New minimal weight representations for left-to-right window methods. Topics in Cryptology — CT-RSA 2005 The Cryptographers’ Track at the RSA Conference 2005, San Francisco, CA, USA, February 14–18, 2005, Proceedings (A. J. Menezes, ed.), Lecture Notes in Comput. Sci., vol. 3376, Springer, Berlin, 2005, pp. 366–384. | MR | Zbl

[22] —, Minimality and other properties of the width-$w$ nonadjacent form. Math. Comp. 75 (2006), 369–384. | MR

[23] Braden Phillips and Neil Burgess, Minimal weight digit set conversions. IEEE Trans. Comput. 53 (2004), 666–677.

[24] George W. Reitwiesner, Binary arithmetic. Advances in computers, vol. 1, Academic Press, New York, 1960, pp. 231–308. | MR

[25] Jerome A. Solinas, An improved algorithm for arithmetic on a family of elliptic curves. Advances in Cryptology — CRYPTO ’97. 17th annual international cryptology conference. Santa Barbara, CA, USA. August 17–21, 1997. Proceedings (B. S. Kaliski, jun., ed.), Lecture Notes in Comput. Sci., vol. 1294, Springer, Berlin, 1997, pp. 357–371. | Zbl

[26] —, Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19 (2000), 195–249. | MR | Zbl

[27] William A. Stein et al., Sage Mathematics Software (Version 4.7.1). The Sage Development Team, 2011, http://www.sagemath.org.

[28] Christiaan van de Woestijne, The structure of Abelian groups supporting a number system (extended abstract). Actes des rencontres du CIRM 1 (2009), no. 1, 75–79.