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

Clemens Heuberger[1]; Daniel Krenn[2]

  • [1] Institute of Mathematics Alpen-Adria-Universität Klagenfurt Universitätsstraße 65–67, 9020 Klagenfurt am Wörthersee, Austria
  • [2] Institute of Optimisation and Discrete Mathematics (Math B) Graz University of Technology Steyrergasse 30/II, 8010 Graz, Austria

Journal de Théorie des Nombres de Bordeaux (2013)

  • Volume: 25, Issue: 2, page 353-386
  • ISSN: 1246-7405

Abstract

top
We consider digit expansions ∑ j = 0 ℓ - 1 Φ j ( d j ) with an endomorphism Φ 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 ≥ 4 . The same holds for the special case of base ( ± 3 ± - 3 ) / 2 (four cases) and w ≥ 2 , which corresponds to Koblitz curves in characteristic three. In the case of τ = ± 1 ± i (again four cases), optimality depends on the parity of w . Computational results for small trace are given.

How to cite

top

Heuberger, Clemens, and Krenn, Daniel. "Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases." Journal de Théorie des Nombres de Bordeaux 25.2 (2013): 353-386. <http://eudml.org/doc/275784>.

@article{Heuberger2013,
abstract = {We consider digit expansions $\sum _\{j=0\}^\{\ell -1\} \Phi ^j(d_j)$ 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.},
affiliation = {Institute of Mathematics Alpen-Adria-Universität Klagenfurt Universitätsstraße 65–67, 9020 Klagenfurt am Wörthersee, Austria; Institute of Optimisation and Discrete Mathematics (Math B) Graz University of Technology Steyrergasse 30/II, 8010 Graz, Austria},
author = {Heuberger, Clemens, Krenn, Daniel},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {$\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; -adic expansions; width- non-adjacent forms},
language = {eng},
month = {9},
number = {2},
pages = {353-386},
publisher = {Société Arithmétique de Bordeaux},
title = {Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases},
url = {http://eudml.org/doc/275784},
volume = {25},
year = {2013},
}

TY - JOUR
AU - Heuberger, Clemens
AU - Krenn, Daniel
TI - Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases
JO - Journal de Théorie des Nombres de Bordeaux
DA - 2013/9//
PB - Société Arithmétique de Bordeaux
VL - 25
IS - 2
SP - 353
EP - 386
AB - We consider digit expansions $\sum _{j=0}^{\ell -1} \Phi ^j(d_j)$ 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.
LA - eng
KW - $\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; -adic expansions; width- non-adjacent forms
UR - http://eudml.org/doc/275784
ER -

References

top
  1. Roberto Avanzi, Clemens Heuberger, and Helmut Prodinger, Minimality of the Hamming weight of the τ -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. Zbl1151.94474MR2241647
  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. Zbl1106.94021MR2291956
  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. Zbl1117.94007MR2180673
  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. Zbl1070.11056MR2167767
  6. —, A note on window τ -NAF algorithm. Inform. Process. Lett. 95 (2005), 496–502. MR2155136
  7. —, Nonadjacent radix- τ expansions of integers in Euclidean imaginary quadratic number fields. Canad. J. Math. 60 (2008), no. 6, 1267–1282. Zbl1228.11160MR2462447
  8. László Germán and Attila Kovács, On number system constructions. Acta Math. Hungar. 115 (2007), no. 1-2, 155–167. Zbl1153.11003MR2316627
  9. Daniel M. Gordon, A survey of fast exponentiation methods. J. Algorithms 27 (1998), 129–146. Zbl0915.11064MR1613189
  10. Clemens Heuberger, Redundant τ -adic expansions II: Non-optimality and chaotic behaviour. Math. Comput. Sci. 3 (2010), 141–157. Zbl1205.11014MR2608292
  11. Clemens Heuberger and Daniel Krenn, Analysis of width- w non-adjacent forms to imaginary quadratic bases. J. Number Theory 133 (2013), 1752–1808. Zbl1300.11013MR3007130
  12. Clemens Heuberger and Helmut Prodinger, Analysis of alternative digit sets for nonadjacent representations. Monatsh. Math. 147 (2006), 219–248. Zbl1094.11007MR2215565
  13. Thomas W. Hungerford, Algebra. Graduate Texts in Mathematics, vol. 73, Springer, 1996. Zbl0442.00002MR600654
  14. Jonathan Jedwab and Chris J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation. Electron. Lett. 25 (1989), 1171–1172. Zbl0709.94699
  15. Donald E. Knuth, Seminumerical algorithms. third ed., The Art of Computer Programming, vol. 2, Addison-Wesley, 1998. Zbl0895.65001MR633878
  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. Zbl0780.14018MR1243654
  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. MR1670960
  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. Zbl1001.68093MR1905123
  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. Zbl0817.94015MR1287863
  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. Zbl1079.94566MR2174389
  22. —, Minimality and other properties of the width- w nonadjacent form. Math. Comp. 75 (2006), 369–384. Zbl1091.94026MR2176404
  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. MR122018
  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. Zbl1032.11062
  26. —, Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19 (2000), 195–249. Zbl0997.94017MR1759617
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.