Modified Hash to Obtain Random Subset-Tree (MHORST) Using Merkle Tree and Mersenne Twister

Faidhil Nugrah Ramadhan Ahmad; Ari Moesriami Barmawi

doi:10.15575/join.v10i2.1471

Authors

Faidhil Nugrah Ramadhan Ahmad Graduate School of Informatics, School of Computing, Telkom University, Indonesia
Ari Moesriami Barmawi Graduate School of Forensic Science and Cyber Security, School of Computing, Indonesia

DOI:

https://doi.org/10.15575/join.v10i2.1471

Keywords:

Digital Signature, HORST, HORSIC, Merkle Tree, Mersenne Twister, Quantum Computing, Security Level

Abstract

The development of quantum computing triggers new challenges in data security, particularly in addressing attacks that can solve complex mathematical problems on the fly. Several hash-based data security methods have been proposed to deal with this threat, one of them being Hash to Obtain Random Subset-Tree (HORST). However, HORST has drawbacks, such as low security, because it only uses one hash round. The security of HORST is already improved by Hash to Obtain Random Subset and Integer Composition (HORSIC). However, HORSIC’s execution time is significantly increased. The problem of this research is the low-security HORST and the high execution time of HORSIC. This research proposes a new method, Modified Hash to Obtain Random Subset-Tree (MHORST), which aims to improve the security of HORST and reduce the execution time to less than HORSI’s. MHORST uses Merkle tree, SHA-256 hashes, and Mersenne Twister to build public keys and digital signatures. Based on the experiment results, MHORST reduces the signing time by more than 3.3 times compared to HORST. MHORST reduces the verification time by more than 1.1 times HORST and 17 times HORSIC. Although the security level of MHORST decreases slightly compared to HORSIC, this method is still more secure than HORST against signature forgery.

References

[1] V. Srivastava, A. Baksi, and S. K. Debnath, "An overview of hash-based signatures," National Institute of Technology Jamshedpur & Nanyang Technological University, Singapore, 2020.

[2] F. Shahid and A. Khan, “Smart Digital Signatures (SDS): A post-quantum digital signature scheme for distributed ledgers,” Future Generation Computer Systems, vol. 111, pp. 241–253, Oct. 2020, doi: 10.1016/j.future.2020.04.042.

[3] L. Li, X. Lu, and K. Wang, “Hash-based signature revisited,” Jul. 01, 2022, Springer Science and Business Media B.V. doi: http://dx.doi.org/10.1186/s42400-022-00117-w.

[4] E. Fathalla and M. Azab, "Beyond classical cryptography: A systematic review of post-quantum hash-based signature schemes, security, and optimizations," IEEE Access, vol. 12, pp. 175969-175986, Dec. 2024, doi: 10.1109/ACCESS.2024.3485602.

[5] P. Lafrance, Digital Signature Schemes Based on Hash Functions, M.Math. thesis, Univ. of Waterloo, Waterloo, ON, Canada, 2017.

[6] K. Zhang, H. Cui, and Y. Yu, "SPHINCS-α: A compact stateless hash-based signature scheme," IACR Cryptology ePrint Archive, Jun. 2023.

[7] J. Lee and Y. Park, “HORSIC+: An efficient post-quantum few-time signature scheme,” Applied Sciences (Switzerland), vol. 11, no. 16, Aug. 2021, doi: 10.3390/app11167350.

[8] R. Hu, “Visual Blockchain Using Merkle Tree,” Thesis, 2019. Accessed: Sep. 16, 2024. [Online]. Available: https://hdl.handle.net/10292/12529

[9] W. Wirachantika, A. M Barmawi, and B. A. Wahyudi, “Memperkuat Fawkescoin Melawan Serangan Pembelanjaan Ganda Menggunakan Merkle Tree,” pp. 49–54, Jan. 2019, doi: https://doi.org/10.1145/3309074.3309105.

[10] J. P. Aumasson and G. Endignoux, “Improving stateless hash-based signatures,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 2018, pp. 219–242. doi: 10.1007/978-3-319-76953-0_12.

[11] M. Alegri, "Identities involving sum of divisors, integer partitions and compositions," Online Journal of Analytic Combinatorics, Feb. 2024, doi: 10.61091/ojac-1703.

[12] Q. He, “Improved Algorithms for Integer Complexity,” Department of Computer Science, University of Illinois at Urbana-Champaign, Sep. 2023.

[13] K. Algazy, K. Sakan, A. Khompysh, and D. Dyusenbayev, "Development of a new post-quantum digital signature algorithm: Syrga-1," Computers, vol. 13, no. 26, Jan. 2024, doi: 10.3390/computers13010026.

[14] B. U. I. Khan, R. F. Olanrewaju, M. A. Morshidi, R. N. Mir, M. L. M. Kiah, and A. M. Khan, "Evolution and analysis of secure hash algorithm (SHA) family," Malaysian Journal of Computer Science, vol. 35, no. 3, pp. 179-200, 2022, doi: 10.22452/mjcs.vol35no3.1

[15] S. Bouaziz–Ermann, A. B. Grilo, and D. Vergnaud, "Quantum security of subset cover problems," LIP6, Sorbonne Université, 2023

[16] M. Yehia, R. Altawy, and T. A. Gulliver, “Hash-based Signatures Revisited: A Dynamic FORS with Adaptive Chosen Message Security,” A. Nitaj and A. Youssef, Eds., Springer International Publishing, Jul. 2020, pp. 239–257. doi: https://doi.org/10.1007/978-3-030-51938-4_12.

[17] J.-P. Aumasson and G. Endignoux, “Clarifying the subset-resilience problem,” Kudelski Security, Switzerland, 2017.

[18] H. Li, Y.-M. Xie, X.-Y. Cao, C.-L. Li, Y. Fu, H.-L. Yin, and Z.-B. Chen, “One-Time Universal Hashing Quantum Digital Signatures without Perfect Keys,” National Laboratory of Solid State Microstructures and School of Physics, Nanjing University, Oct. 2023

[19] A. Shafarenko, “Winternitz Stack Protocols for Embedded Systems and IoT,” Cybersecurity, vol. 7, no. 34, 2024. doi: 10.1186/s42400-024-00225-9

[20] N. Boutsioukis, "Comparative analysis of pseudorandom number generators: Mersenne Twister, middle square method, and linear congruential generator through Dieharder tests," SSRN, Jan. 2023, doi: 10.4761542.