Redundant \(\tau \)-adic expansions. II: Non-optimality and chaotic behaviour. (English) Zbl 1205.11014

Summary: When computing scalar multiples on Koblitz curves, the Frobenius endomorphism can be used to replace the usual doublings on the curve. This involves digital expansions of the scalar to the complex base \(\tau=(\pm 1\pm \sqrt{-7})/2\) instead of binary expansions. As in the binary case, this method can be sped up by enlarging the set of valid digits at the cost of precomputing some points on the curve. In the binary case, it is known that a simple syntactical condition (the so-called \(w\)-NAF-condition) on the expansion ensures that the number of curve additions is minimised. The purpose of this paper is to show that this is not longer true for the base \(\tau \) and \(w \in {4, 5, 6}\). Even worse, it is shown that there is no longer an online algorithm to compute an optimal expansion from the digits of some standard expansion from the least to the most significant digit, which can be interpreted as chaotic behaviour. The proofs heavily depend on symbolic computations involving transducer automata.
For Part I see [R. Avanzi, C. Heuberger and H. Prodinger, “Redundant \(\tau\)-adic expansions. I. Non-adjacent digit sets and their applications to scalar multiplication”, to appear in Des. Codes Cryptogr.].


11A63 Radix representation; digital problems
68W30 Symbolic computation and algebraic computation
68Q45 Formal languages and automata
94A60 Cryptography
Full Text: DOI Link


[1] Avanzi, R.: A note on the signed sliding window integer recoding and a left-to-right analogue. In: Handschuh, H., Hasan, M.A. (eds.) Selected Areas in Cryptography: 11th International Workshop, SAC 2004, Waterloo, Canada, August 9–10, 2004, Revised Selected Papers. Lecture Notes in Comput. Sci., vol. 3357, pp. 130–143. Springer, Berlin (2004) · Zbl 1117.94007
[2] Avanzi, R.M., Heuberger, C., Prodinger, H.: Minimality of the Hamming weight of the {\(\tau\)}-NAF for Koblitz curves and improved combination with point halving. In: Preneel, B., Tavares, St. (eds.) Selected Areas in Cryptography: 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11–12, 2005, Revised Selected Papers. Lecture Notes in Comput. Sci., vol. 3897, pp. 332–344. Springer, Berlin (2006) · Zbl 1151.94474
[3] Avanzi R.M., Heuberger C., Prodinger H.: Scalar multiplication on Koblitz curves. Using the Frobenius endomorphism and its combination with point halving: extensions and mathematical analysis. Algorithmica 46, 249–270 (2006) · Zbl 1106.94021
[4] Avanzi, R.M., Heuberger, C., Prodinger, H.: On redundant {\(\tau\)}-adic expansions and non-adjacent digit sets. In: Biham, E., Youssef, A. (eds.) Selected Areas in Cryptography: 13th International Workshop, SAC 2006, Montreal, Canada, August 2006, Revised Selected Papers. Lecture Notes in Comput. Sci., vol. 4356, pp. 285–301. Springer, Berlin (2007) · Zbl 1161.94380
[5] Avanzi, R.M., Heuberger, C., Prodinger, H.: Redundant {\(\tau\)}-adic expansions. I: Non-adjacent digit sets and their applications to scalar multiplication. Cryptology ePrint Archive, Report 2008/148, 2008. http://eprint.iacr.org/ · Zbl 1230.94003
[6] Ciet, M., Lange, T., Sica, F., Quisquater, J.-J.: Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms. Advances in Cryptology–EUROCRYPT 2003. In: Biham, E. (ed.) International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003. Proceedings. Lecture Notes in Comput. Sci., vol. 2656, pp. 388–400. Springer, Berlin (2003) · Zbl 1038.11507
[7] Gordon D.M.: A survey of fast exponentiation methods. J. Algorithms 27, 129–146 (1998) · Zbl 0915.11064
[8] Grabner P.J., Heuberger C., Prodinger H.: Distribution results for low-weight binary representations for pairs of integers. Theoret. Comput. Sci. 319, 307–331 (2004) · Zbl 1050.94009
[9] Heuberger C.: Minimal redundant digit expansions in the Gaussian integers. J. Théor. Nombres Bordeaux 14, 517–528 (2002) · Zbl 1076.11005
[10] Heuberger C., Muir J.: Minimal weight and colexicographically minimal integer representations. J. Math. Cryptol. 1, 297–328 (2007) · Zbl 1161.11002
[11] Heuberger C., Prodinger H.: Analysis of alternative digit sets for nonadjacent representations. Monatsh. Math. 147, 219–248 (2006) · Zbl 1094.11007
[12] Kátai I., Kovács B.: Canonical number systems in imaginary quadratic fields. Acta Math. Hungar. 37, 159–164 (1981) · Zbl 0477.10012
[13] Kátai I., Szabó J.: Canonical number systems for complex integers. Acta Sci. Math. (Szeged) 37, 255–260 (1975) · Zbl 0297.12003
[14] Knuth D.E.: Seminumerical Algorithms, 3rd edn. The Art of Computer Programming, vol. 2. Addison-Wesley, Reading (1998) · Zbl 0895.65001
[15] Koblitz, N.: CM-curves with good cryptographic properties. Advances in cryptology–CRYPTO ’91 (Santa Barbara, CA, 1991). Lecture Notes in Comput. Sci., vol. 576, pp. 279–287. Springer, Berlin (1992)
[16] Lothaire M.: Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, Cambridge (2002) · Zbl 1001.68093
[17] Morain F., Olivos J.: Speeding up the computations on an elliptic curve using addition-subtraction chains. RAIRO Inform. Théor. Appl. 24, 531–543 (1990) · Zbl 0724.11068
[18] Muir, J.A., Stinson, D.R.: New minimal weight representations for left-to-right window methods. In: Menezes, A.J. (ed.) Topics in Cryptology–CT-RSA 2005 The Cryptographers’ Track at the RSA Conference 2005, San Francisco, CA, USA, February 14–18, 2005, Proceedings. Lecture Notes in Comput. Sci., vol. 3376, pp. 366–384. Springer, Berlin (2005) · Zbl 1079.94566
[19] Muir J.A., Stinson D.R.: Minimality and other properties of the width-w nonadjacent form. Math. Comp. 75, 369–384 (2006) · Zbl 1091.94026
[20] Phillips B., Burgess N.: Minimal weight digit set conversions. IEEE Trans. Comput. 53, 666–677 (2004)
[21] Proos, J.: Joint sparse forms and generating zero columns when combing. Technical Report CORR 2003-23, Centre for Applied Cryptographic Research, University of Waterloo, 2003. Available at http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-23.ps
[22] Reitwiesner G.W.: Binary Arithmetic. Advances in Computers, vol. 1, pp. 231–308. Academic Press, New York (1960)
[23] Solinas, J.A.: An improved algorithm for arithmetic on a family of elliptic curves. In: Kaliski, B.S. Jr. (ed.) Advances in Cryptology–CRYPTO ’97. 17th Annual International cryptology conference, Santa Barbara, CA, USA, August 17–21, 1997. Proceedings. Lecture Notes in Comput. Sci., vol. 1294, pp. 357–371. Springer, Berlin (1997) · Zbl 1032.11062
[24] Solinas J.A.: Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19, 195–249 (2000) · Zbl 0997.94017
[25] Solinas, J.A.: Low-weight binary representations for pairs of integers. Technical Report CORR 2001-41, Centre for Applied Cryptographic Research, University of Waterloo, 2001. Available at http://www.cacr.math.uwaterloo.ca/techreports/2001/corr2001-41.ps
[26] Straus E.: Addition chains of vectors (Problem 5125). Am. Math. Monthly 71, 806–808 (1964) · Zbl 0135.31202
[27] Zhu, Y.F., Kuang, B.J., Zhang, Y.J.: An improved algorithm for up + vq on a family of elliptic curves. In: 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05)–Workshop 17, p. 294. IEEE Computer Society, Los Alamitos (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.