Abstract
From several decades, non-adjacent form (NAF) representations for integers have been extensively studied as an alternative to the usual binary number system where digits are in {0,1}. In cryptography, the non-adjacent digit set (NADS) {–1,0,1} is used for optimization of arithmetic operations in elliptic curves. At SAC 2003, Muir and Stinson published new results on alternative digit sets: they proposed infinite families of integers x such that {0,1,x} is a NADS as well as infinite families of integers x such that {0,1,x} is not a NADS, so called a NON-NADS. Muir and Stinson also provided an algorithm that determines whether x leads to a NADS by checking if every integer \(n \epsilon [0, \lfloor \frac{-x}{3} \rfloor]\) has a {0,1,x}-NAF. In this paper, we extend these results by providing generators of NON-NADS infinite families. Furthermore, we reduce the search bound from \(\lfloor \frac{-x}{3} \rfloor\) to \(\lfloor \frac{-x}{12} \rfloor\). We introduce the notion of worst NON-NADS and give the complete characterization of such sets. Beyond the theoretical results, our contribution also aims at exploring some algorithmic aspects. We supply a much more efficient algorithm than those proposed by Muir and Stinson, which takes only 343 seconds to compute all x’s from 0 to –107 such that {0,1,x} is a NADS.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Booth, A.: A signed binary multiplication technique. The Quarterly Journal Mechanics and Applied Mathematics 4, 236–240 (1951)
Bosma, W.: Signed bits and fast exponentiation. Journal de théorie des nombres de Bordeaux 13(1), 27–41 (2001)
De Win, E., Mister, S., Preneel, B., Wiener, M.: On the performance of signature schemes based on elliptic curves. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 252–266. Springer, Heidelberg (1998)
Fong, K., Hankerson, D., López, J., Menezes, A.: Field inversion and point halving revisited. IEEE Transactions on Computers 53(8), 1047–1059 (2004)
Gordon, D.: A survey of fast exponentiation methods. Journal of Algorithms 27(1), 129–146 (1998)
Jedwab, J., Mitchell, C.: Minimum weight modified signed-digit representations and fast exponentiation. Electronics Letters 25(17), 1171–1172 (1989)
Joye, M., Tymen, C.: Compact encoding of non-adjacent forms with applications to elliptic curve cryptography. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 353–364. Springer, Heidelberg (2001)
Joye, M., Yen, S.: Optimal left-to-right binary signed-digit recoding. IEEE Transactions on Computers 49(7), 740–748 (2000)
Koyama, K., Tsuruoka, Y.: Speeding up elliptic cryptosystems by using a signed binary window method. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 345–357. Springer, Heidelberg (1993)
Lalanne, L.: Note sur quelques propositions d’arithmologie élémentaire. Comptes rendus hebdomadaires des séances de l’Académie des sciences 11, 903–905 (1840)
Matula, D.: Basic digit sets for radix representation. Journal of the Association for Computing Machinery 29(4), 1131–1143 (1982)
Okeya, K., Takagi, T.: The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 328–343. Springer, Heidelberg (2003)
Okeya, K., Takagi, T.: A More Flexible Countermeasure against Side Channel Attacks Using Window Method. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 397–410. Springer, Heidelberg (2003)
Morain, F., Olivos, J.: Speeding up the computations on an elliptic curve using addition-subtraction chains. RAIRO – Theoretical Informatics and Applications 24(6), 531–543 (1990)
Muir, J., Stinson, D.: Alternative digit sets for nonadjacent representations. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 306–319. Springer, Heidelberg (2004)
Muir, J., Stinson, D.: Alternative digit sets for nonadjacent representations. Technical Report CORR 2004-09, Centre for Applied Cryptographic Research, University of Waterloo, Canada (2004), http://www.cacr.math.uwaterloo.ca
Reitwiesner, G.: Binary arithmetic. Advances in Computers 1, 231–308 (1960)
Solinas, J.: An improved algorithm for arithmetic on a family of elliptic curves. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 357–371. Springer, Heidelberg (1997)
Solinas, J.: Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography 19(2–3), 195–249 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Avoine, G., Monnerat, J., Peyrin, T. (2004). Advances in Alternative Non-adjacent Form Representations. In: Canteaut, A., Viswanathan, K. (eds) Progress in Cryptology - INDOCRYPT 2004. INDOCRYPT 2004. Lecture Notes in Computer Science, vol 3348. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30556-9_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-30556-9_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24130-0
Online ISBN: 978-3-540-30556-9
eBook Packages: Computer ScienceComputer Science (R0)