Some New Methods to Generate Short Addition Chains
Modular exponentiation and scalar multiplication are important operations in most public-key cryptosystems, and their efficient computation is essential to cryptosystems. The shortest addition chain is one of the most important mathematical concepts to realize the optimization of computation. Howev...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-03-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/10284 |
| _version_ | 1811158080906330112 |
|---|---|
| author | Yuanchao Ding Hua Guo Yewei Guan Hutao Song Xiyong Zhang Jianwei Liu |
| author_facet | Yuanchao Ding Hua Guo Yewei Guan Hutao Song Xiyong Zhang Jianwei Liu |
| author_sort | Yuanchao Ding |
| collection | DOAJ |
| description |
Modular exponentiation and scalar multiplication are important operations in most public-key cryptosystems, and their efficient computation is essential to cryptosystems. The shortest addition chain is one of the most important mathematical concepts to realize the optimization of computation. However, finding a shortest addition chain of length r is generally regarded as an NP-hard problem, whose time complexity is comparable to O(r!). This paper proposes some novel methods to generate short addition chains. We firstly present a Simplified Power-tree method by deeply deleting the power-tree whose time complexity is reduced to O(r2). In this paper, a Cross Window method and its variant are introduced by improving the Window method. The Cross Window method uses the cross correlation to deal with the windows and its pre-computation is optimized by a new Addition Sequence Algorithm. The theoretical analysis is conducted to show the correctness and effectiveness. Meanwhile, our experiments show that the new methods can obtain shorter addition chains compared to the existing methods. The Cross Window method with the Addition Sequence algorithm can attain 44.74% and 9.51% reduction of the addition chain length, in the best case, compared to the Binary method and the Window method respectively.
|
| first_indexed | 2024-04-10T05:18:18Z |
| format | Article |
| id | doaj.art-8c2b123c1c1e4e18b4478a349b626a05 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-10T05:18:18Z |
| publishDate | 2023-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-8c2b123c1c1e4e18b4478a349b626a052023-03-08T15:37:32ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-03-012023210.46586/tches.v2023.i2.270-285Some New Methods to Generate Short Addition ChainsYuanchao Ding0Hua Guo1Yewei Guan2Hutao Song3Xiyong Zhang4Jianwei Liu5School of Cyber Science and Technology, Beihang University, Beijing, China; State Key Laboratory of Cryptology, P.O. Box, Beijing, ChinaSchool of Cyber Science and Technology, Beihang University, Beijing, China; State Key Laboratory of Cryptology, P.O. Box, Beijing, ChinaSchool of Cyber Science and Technology, Beihang University, Beijing, China; State Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaSchool of Cyber Science and Technology, Beihang University, Beijing, China; State Key Laboratory of Software Development Environment, Beihang University, Beijing, ChinaBeijing Institute of Satellite Information Engineering, Beijing, ChinaSchool of Cyber Science and Technology, Beihang University, Beijing, China Modular exponentiation and scalar multiplication are important operations in most public-key cryptosystems, and their efficient computation is essential to cryptosystems. The shortest addition chain is one of the most important mathematical concepts to realize the optimization of computation. However, finding a shortest addition chain of length r is generally regarded as an NP-hard problem, whose time complexity is comparable to O(r!). This paper proposes some novel methods to generate short addition chains. We firstly present a Simplified Power-tree method by deeply deleting the power-tree whose time complexity is reduced to O(r2). In this paper, a Cross Window method and its variant are introduced by improving the Window method. The Cross Window method uses the cross correlation to deal with the windows and its pre-computation is optimized by a new Addition Sequence Algorithm. The theoretical analysis is conducted to show the correctness and effectiveness. Meanwhile, our experiments show that the new methods can obtain shorter addition chains compared to the existing methods. The Cross Window method with the Addition Sequence algorithm can attain 44.74% and 9.51% reduction of the addition chain length, in the best case, compared to the Binary method and the Window method respectively. https://tches.iacr.org/index.php/TCHES/article/view/10284addition chainwindow methodsimplified power-tree methodcross window methodaddition sequence |
| spellingShingle | Yuanchao Ding Hua Guo Yewei Guan Hutao Song Xiyong Zhang Jianwei Liu Some New Methods to Generate Short Addition Chains Transactions on Cryptographic Hardware and Embedded Systems addition chain window method simplified power-tree method cross window method addition sequence |
| title | Some New Methods to Generate Short Addition Chains |
| title_full | Some New Methods to Generate Short Addition Chains |
| title_fullStr | Some New Methods to Generate Short Addition Chains |
| title_full_unstemmed | Some New Methods to Generate Short Addition Chains |
| title_short | Some New Methods to Generate Short Addition Chains |
| title_sort | some new methods to generate short addition chains |
| topic | addition chain window method simplified power-tree method cross window method addition sequence |
| url | https://tches.iacr.org/index.php/TCHES/article/view/10284 |
| work_keys_str_mv | AT yuanchaoding somenewmethodstogenerateshortadditionchains AT huaguo somenewmethodstogenerateshortadditionchains AT yeweiguan somenewmethodstogenerateshortadditionchains AT hutaosong somenewmethodstogenerateshortadditionchains AT xiyongzhang somenewmethodstogenerateshortadditionchains AT jianweiliu somenewmethodstogenerateshortadditionchains |