ON SOME PATTERNS OF TNAF FOR SCALAR MULTIPLICATION OVER KOBLITZ CURVE
Article Sidebar
Main Article Content
Abstract
A τ-adic non-adjacent form (TNAF) of an element α of the ring Z(τ) is an expansion whereby the digits are generated by iteratively dividing α by τ, allowing the remainders of -1,0 or 1. The application of TNAF as a multiplier of scalar multiplication (SM) on the Koblitz curve plays a key role in Elliptical Curve Cryptography (ECC). There are several patterns of TNAF (α) expansion in the form of [c0,0,…,0,cl-1 ], [c0,0,…,c(l-1)/2,…,0,c(l-1)], 2+2k, 3+4k, 5+4k and 8k1+8k2 that have been produced in prior work in the literature. However, the construction of their properties based upon pyramid number formulas such as Nichomacus’s theorem and Faulhaber’s formula remains to be rather complex. In this work, we derive such types of TNAF in a more concise manner by applying the power of Frobenius map (τm) based on v-simplex and arithmetic sequences.
Downloads
Article Details
Transfer of Copyrights
- In the event of publication of the manuscript entitled [INSERT MANUSCRIPT TITLE AND REF NO.] in the Malaysian Journal of Science, I hereby transfer copyrights of the manuscript title, abstract and contents to the Malaysian Journal of Science and the Faculty of Science, University of Malaya (as the publisher) for the full legal term of copyright and any renewals thereof throughout the world in any format, and any media for communication.
Conditions of Publication
- I hereby state that this manuscript to be published is an original work, unpublished in any form prior and I have obtained the necessary permission for the reproduction (or am the owner) of any images, illustrations, tables, charts, figures, maps, photographs and other visual materials of whom the copyrights is owned by a third party.
- This manuscript contains no statements that are contradictory to the relevant local and international laws or that infringes on the rights of others.
- I agree to indemnify the Malaysian Journal of Science and the Faculty of Science, University of Malaya (as the publisher) in the event of any claims that arise in regards to the above conditions and assume full liability on the published manuscript.
Reviewer’s Responsibilities
- Reviewers must treat the manuscripts received for reviewing process as confidential. It must not be shown or discussed with others without the authorization from the editor of MJS.
- Reviewers assigned must not have conflicts of interest with respect to the original work, the authors of the article or the research funding.
- Reviewers should judge or evaluate the manuscripts objective as possible. The feedback from the reviewers should be express clearly with supporting arguments.
- If the assigned reviewer considers themselves not able to complete the review of the manuscript, they must communicate with the editor, so that the manuscript could be sent to another suitable reviewer.
Copyright: Rights of the Author(s)
- Effective 2007, it will become the policy of the Malaysian Journal of Science (published by the Faculty of Science, University of Malaya) to obtain copyrights of all manuscripts published. This is to facilitate:
- Protection against copyright infringement of the manuscript through copyright breaches or piracy.
- Timely handling of reproduction requests from authorized third parties that are addressed directly to the Faculty of Science, University of Malaya.
- As the author, you may publish the fore-mentioned manuscript, whole or any part thereof, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given. You may produce copies of your manuscript, whole or any part thereof, for teaching purposes or to be provided, on individual basis, to fellow researchers.
- You may include the fore-mentioned manuscript, whole or any part thereof, electronically on a secure network at your affiliated institution, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given.
- You may include the fore-mentioned manuscript, whole or any part thereof, on the World Wide Web, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given.
- In the event that your manuscript, whole or any part thereof, has been requested to be reproduced, for any purpose or in any form approved by the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers), you will be informed. It is requested that any changes to your contact details (especially e-mail addresses) are made known.
Copyright: Role and responsibility of the Author(s)
- In the event of the manuscript to be published in the Malaysian Journal of Science contains materials copyrighted to others prior, it is the responsibility of current author(s) to obtain written permission from the copyright owner or owners.
- This written permission should be submitted with the proof-copy of the manuscript to be published in the Malaysian Journal of Science
References
Avanzi R M., Heuberger C., Prodinger H. (2007). On redundant τ-adic expansions and non-adjacent digit sets, Proceeding of the 13th International Workshop on Selected Areas in Cryptography, SAC 2006, Lecture Notes in Computer Science, Springer-Verlag 4356: 285-301.
Avanzi R M., Heuberger C., Prodinger H. (2011). Redundant τ-adic expansions I: Non-adjacent digit sets and their applications to scalar multiplication, Des. Codes Cryptography 58 (2): 173-202.
Blake I F V., Murty K., Xu G. (2008). Nonadjacent Radix-τ expansions of integers in euclidean imaginary quadratic number fields, Canadian Journal of Mathematics 60(6): 1267-1282.
Hadani N H., Yunos F. (2018). Alternative formula of τ^m in scalar multiplication on Koblitz curve, Proceeding of the 25th National Symposium on Mathematical Sciences (Sksm25), AIP Publishing, AIP Conference Proceedings 1974(1): 1-9.
Hadani N H., Yunos F., Suberi S. (2019a). On some specific patterns of τ -adic non-adjacent form expansion over ring Z (τ): An alternative formula. In AIP Conference Proceedings 2138 Issue 1; Ibrahim, H., Zulkepli J., Yaakub, A M.; AIP Publishing: 1-10.
Hadani N H., Yunos F., Kamel Arifin M R., Sapar S H. and Rahman N N A. (2019b). Alternative method to find the number of points on Koblitz curve, Malaysian Journal of Science. 13(S) August, Special Issue: The 6th International Cryptology and Information Security Conference: 13-30.
Hankerson D., Menzenes A J., Venstone S. (2006). Guide to elliptic curve cryptography, Springer Science & Business Media.
Heuberger C. (2010). Redundant τ-adic expansions II: non-optimality and chaotic behaviour, Mathematics in Computer Science 3(2):141-157.
Heuberger C., Krenn D. (2013a). Existence and optimality of w-non-adjacent forms with an algebraic integer base, Acta Mathematica Hungarica 140: 90-104.
Heuberger C., Krenn D. (2013b). Analysis of width-w non-adjacent forms to imaginary quadratic, Journal of Number Theory 133(5): 1752-1808.
Hakuta K., Sato H., Takagi T., Jarvinen K. (2010). Explicit lower bound for the length of minimal weight τ-adic expansions on Koblitz curves, Journal of Math-for-Industry 2 (2010A-7): 75-83.
Koblitz N. (1987). Elliptic curve cryptosystem, Mathematics Computation 48 (177): 203-209. https://doi.org/10.1090/S0025-5718-1987-0866109-5.
Koblitz N. (1992). CM curves with good cryptographic properties. In Advances in cryptology CRYPTO 91: Proceedings 576; Feigenbaum J.; Springer: Berlin, Heidelberg: 279-287. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.6778
Solinas J A. (1997). An improved algorithm for arithmetic on a family of elliptic curves, Advance in Cryptology-CRYPTO’97, 1294, Burton S., and Kaliski Jr.; Springer: Berlin, Heidelberg: 357-371.
Solinas J A. (2000). Efficient arithmetic on Koblitz curves, Kluwer Academic Publishers, Design, Codes, and Cryptography, J.A.; Springer: Boston, Massachusetts 19: 195-249. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.157.2469
Suberi S., Yunos F., Md Said M R. (2016). An even and odd situation for the multiplier of scalar multiplication with pseudo τ -adic non-adjacent form. In AIP Conference Proceedings 1750, AIP Publishing: 1-9. https://doi.org/10.1063/1.4954597
Suberi S., Yunos F., Md Said M R., Sapar S H., Said Husain Sh K. (2018). Formula of τ-adic nonadjacent form with the least number of non-zero coefficients, Jurnal Karya Asli Lorekan Ahli Matematik 11(1): 23-30.
Yunos F., Atan M K A. (2013). An average density of τ-adic naf (τ-NAF) representation: An alternative proof, Malaysian Journal of Mathematical Sciences 7(1): 111-123.
Yunos F., Atan M K A., Md Said M R., Ariffin M R K. (2014). A reduced τ-NAF (RTNAF) representation for scalar multiplication on anomalous binary curves (ABC), Pertanika Journal of Science and Technology 22(2): 489-506.
Yunos F., Atan M K A., Md Said M R., Ariffin M R K. (2015a). Pseudo T-Adic nonadjacent form for scalar multiplication on Koblitz curves, Malaysian Journal of Mathematical Sciences 9(S) (Special Issue: The 4th International Cryptology and Information Security Conference 2014): 71-88.
Yunos F., Atan M K A., Md Said M R., Ariffin M R K. (2015b). Pseudo T-adic nonadjacent form for scalar multiplication on Koblitz curves, Conference Proceeding of the 4th International Cryptology and Information Security Conference 2014: 120-130.
Yunos F., Atan M K A., Md Said M R., Ariffin M R K. (2015c). Kembangan Pseudotnaf bagi pendaraban skalar ke atas lengkuk Koblitz, Ph.D. thesis, Universiti Putra Malaysia.
Yunos F., Atan M K A. (2016). Improvement to scalar multiplication on Koblitz curves by using Pseudo τ-adic non-adjacent form, Advances in Industrial and Applied Mathematics, Proceedings of 23rd Malaysian National Symposium of Mathematical Sciences (SKSM23), AIP Publishing 1750: 050006.
Yunos F., Suberi S. (2018). Even and odd nature for pseudo τ-adic non-adjacent form, Malaysian Journal of Science 37(2): 94-102.
Yunos F., Suberi S., Said Husain Sh K., Ariffin M R K., Asbullah M A. (2019). On some specific patterns of τ -adic non-adjacent form expansion over ring Z (τ), Journal of Engineering and Applied Sciences.
Yunos F., Mohd Yusof A., Hadani N H., Kamel Arifin M R., Sapar S H. (2021). Power of frobenius endomorphism and its performance on PseudoTNAF system, new ideas in Cryptology in Malaysian Journal of Mathematical Sciences 15(S) December: 105-121.