TARU PUBLICATIONS
Journal of Discrete Mathematical Sciences and Cryptography cover

Journal of Discrete Mathematical Sciences and Cryptography

(Since 1998)
Hybrid ·Peer-reviewed·ISSN (Online): 2169-0065·ISSN (Print): 0972-0529

CiteScore 2025: 2.7 (Q1)

Powered by:Powered by

Monthly Journal: Publishes theoretical and applied research in all areas of Discrete Mathematical Sciences, Cryptography, Combinatorics, Elliptic Curves and Information Security.

Issues up to 2022 co-published with and available at:Taylor & Francis Online
submissions@tarupublications.com
Taru Online First Current IssueSpecial IssuesBrowse all Issues
Journal of Discrete Mathematical Sciences and Cryptography
Open Access A

An alternative proof of the minimality of the Hamming weight of width-3 non-adjacent form

* ,

* Corresponding author · click or hover a name for details

pp. 387–402Vol. 26Issue 2March 2022DOI: 10.1080/09720529.2021.1925449 Crossmark XML
Received:
01 Oct 2020
Accepted:
05 Feb 2021
Published Online:
23 Feb 2022
Article type:
A
Language:
EN
Article no.:
JDMSC-1346
Pages:
387–402

Abstract

In elliptic curve cryptography (ECC for short), point multiplication (or scalar multiplication) is the dominant operation. It is a very important matter to improve the efficiency of point multiplication for practical use. In ECC, recoding methods of the scalars play an important role in the performance of the algorithm used. One such example is the width-ω non-adjacent form (ω-NAF). Bosma (2001) proved that the Hamming weight of the NAF (2-NAF) is minimal, and Muir and Stinson (2005) proved that the Hamming weight of the ω-NAF is minimal. As other examples, the generalized non-adjacent form (GNAF) and the τ-adic non-adjacent form (τ -NAF) are known. Clark and Liang (1973) proved that the Hamming weight of the GNAF is minimal by constructing an injective map. A similar strategy was adopted by Hakuta, Sato, and Takagi (2010) to prove the minimality of the Hamming weight of the τ -NAF. In this paper, we shall give an alternative proof of the minimality of the Hamming weight of the 3-NAF (ω-NAF with ω = 3). We also discuss that our alternative proof may not work in the case ω ≥ 4.

Keywords

Elliptic curvesCryptographyHamming weightPoint multiplication (scalar multiplication)Width-ω non-adjacent form (ω-NAF)

Subject Classifications

(2010) Primary 11A63Secondary 11G2094A60

References

  1. R.M. Avanzi, C. Heuberger, and H. Prodinger, Minimality of the Hamming Weight of the τ -NAF for Koblitz Curves and Improved Combination with Point Halving, In: B. Preneel, S. Tavares (eds.), Selected Areas in Cryptography – SAC 2005, Lecture Notes in Computer Science, vol. 3897 (2006), 332–344. [Google Scholar]
  2. R.M. Avanzi, C. Heuberger, and H. Prodinger, Scalar multiplication on Koblitz curves using the Frobenius endomorphism and its combination with point halving: extensions and mathematical analysis, Algorithmica 46 (2006), no. 3–4, 249–270. doi: https://doi.org/10.1007/s00453-006-0105-9 [Crossref], [Web of Science ®], [Google Scholar]
  3. G. Avoine, J. Monnerat, and T. Peyrin, Advances in Alternative Non- adjacent Form Representations, In: A. Canteaut and K. Viswanathan (eds.), Progress in Cryptology – INDOCRYPT 2004, Lecture Notes in Computer Science, vol. 3348 (2004), 260–274. [Google Scholar]
  4. W. Bosma, Signed bits and fast exponentiation, J. Théor. Nombres Bordeaux 13 (2001), 27–41. doi: https://doi.org/10.5802/jtnb.301 [Crossref], [Google Scholar]
  5. W.E. Clark and J.J. Liang, On arithmetic weight for a general radix representation of integers, IEEE Trans. Inform. Theory 19 (1973), no. 6, 823–826. doi: https://doi.org/10.1109/TIT.1973.1055100 [Crossref], [Web of Science ®], [Google Scholar]
  6. S.S. Dhanda, B. Singh, and P. Jindal, Demystifying elliptic curve cryptography: Curve selection, implementation and countermeasures to attacks, J. Interdiscip. Math. 23 (2020), 463–470. doi: https://doi.org/10.1080/09720502.2020.1731959 [Taylor & Francis Online], [Web of Science ®], [Google Scholar]
  7. K. Hakuta, H. Sato, and T. Takagi, Explicit lower bound for the length of minimal weight t -adic expansions on Koblitz curves, J. Math-for- Ind. 2A (2010), 75–83. [Google Scholar]
  8. K. Hakuta, H. Sato, and T. Takagi, Some properties of τ -adic expansions on hyperelliptic Koblitz curves, J. Appl. Math. Comput. 58 (2018), 367–388. doi: https://doi.org/10.1007/s12190-017-1149-5 [Crossref], [Web of Science ®], [Google Scholar]
  9. D. Hankerson, A.J. Menezes, and S. Vanstone, Guide to elliptic curve cryptography, Springer Professional Computing, Springer, New York, NY (2004). [Google Scholar]
  10. N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. doi: https://doi.org/10.1090/S0025-5718-1987-0866109-5 [Crossref], [Web of Science ®], [Google Scholar]
  11. N. Koblitz, CM-curves with good cryptographic properties, In: J. Feigenbaum (eds.), Advances in Cryptology – CRYPTO ‘91, Lecture Notes in Computer Science, vol. 576 (1992), 279–287. [Crossref], [Google Scholar]
  12. K.A. Kumar, A.V.N. Krishna, and K.S. Chatrapati, New secure routing protocol with elliptic curve cryptography for military heterogeneous wireless sensor networks, Journal of Information and Optimization Sciences 38 (2017), 341–365. doi: https://doi.org/10.1080/02522667.2016.1220092 [Taylor & Francis Online], [Web of Science ®], [Google Scholar]
  13. V. Miller, Use of elliptic curves in cryptography, In: H.C. Williams (eds.), Advances in Cryptology – CRYPTO ‘85, Lecture Notes in Computer Science, vol. 218 (1986), 417–426. [Crossref], [Google Scholar]
  14. J.A. Muir and D.R. Stinson, Alternative digit sets for nonadjacent representations, SIAM J. Discrete Math. 19 (2005), no. 1, 165–191. doi: https://doi.org/10.1137/S0895480103437651 [Crossref], [Web of Science ®], [Google Scholar]
Views: 163Downloads: 66Citations: 0