International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 17, No. 3, 8 Jun. 2025
Cover page and Table of Contents: PDF (size: 1658KB)
Post-quantum Digital Signatures using ElGamal Approach
PDF (1658KB), PP.89-108
Views: 0 Downloads: 0
Author(s)
Index Terms
SIS, Post-quantum, CVP, SVP, DLP, PKE, Lattice
Abstract
The paper offers a novel digital signature scheme that integrates ElGamal cryptographic principles with the Short Integer Solution (SIS) problem, specifically designed to ensure post-quantum security. As quantum computers advance and present significant risks to traditional cryptographic systems, this scheme offers an interesting alternative for securing digital signatures against potential quantum threats. The scheme uses only basic secure principles. The offered approach offers key generation, where parameters and random matrices are selected, and signature generation, which involves creating signatures based on hashed messages and matrix computations. Verification ensures the authenticity and integrity of signatures. We provide experimental evaluations detailing key generation, signature creation, and verification times across different matrix dimensions and message sizes. Key generation takes between 2.5–10.2 seconds, while signature generation ranges from 0.20 to 9.30 milliseconds and verification from 0.18 to 8.90 milliseconds, depending on message size and matrix dimension. The scheme maintains a consistent signature size of 1.7 KB, independent of message length due to a hash-and-sign strategy. These results demonstrate that the scheme balances post-quantum security with practical performance, especially in high-security contexts. A comparison with traditional ElGamal encryption reveals the trade-offs between security and efficiency. While the SIS-based scheme delivers enhanced protection against quantum threats, it also entails increased computational complexity and larger signature sizes compared to conventional schemes.
Overall, our proposed digital signature scheme stands as an excellent option for safe communications in a post-quantum world, representing a crucial step in protecting the authenticity and integrity of digital exchanges against changing technological risks. We believe that as quantum computing continues to develop, research into robust cryptographic alternatives will become increasingly important for safeguarding sensitive information across various sectors.
Cite This Paper
Maksim Iavich, Dana Amirkhanova Sairangazhykyzy, "Post-quantum Digital Signatures using ElGamal Approach", International Journal of Computer Network and Information Security(IJCNIS), Vol.17, No.3, pp.89-108, 2025. DOI:10.5815/ijcnis.2025.03.06
Reference
[1]Dejpasand, Mohamad Taghi, and Morteza Sasani Ghamsari. "Research trends in quantum computers by focusing on qubits as their building blocks." Quantum Reports 5.3 (2023): 597-608.
[2]Di Meglio, Alberto, et al. "Quantum Computing for High-Energy Physics: State of the Art and Challenges." PRX Quantum 5.3 (2024): 037001.
[3]Gill, Sukhpal Singh, et al. "Quantum Computing: Vision and Challenges." arXiv preprint arXiv:2403.02240 (2024).
[4]Micciancio, Daniele, and Oded Regev. "Lattice-based cryptography." Post-quantum cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 147-191.
[5]Regev, Oded. "Lattice-based cryptography." Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.
[6]Gagnidze, Avtandil, Maksim Iavich, and Giorgi Iashvili. "Analysis of post quantum cryptography use in practice." Bull. Georgian Natl. Acad. Sci 11.2 (2017): 29-36.
[7]Kumar, Ajay, and Sunita Garhwal. "State-of-the-art survey of quantum cryptography." Archives of Computational Methods in Engineering 28 (2021): 3831-3868.
[8] Bernstein, Daniel J., and Tanja Lange. "Post-quantum cryptography." Nature 549.7671 (2017): 188-194.
[9]Pan, Chen, Yafeng Han, and Jiping Lu. "Design and optimization of lattice structures: A review." Applied Sciences 10.18 (2020): 6374.
[10]Khot, Subhash. "Inapproximability results for computational problems on lattices." The LLL algorithm: Survey and applications. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 453-473.
[11]Peikert, Chris. "A decade of lattice cryptography." Foundations and trends® in theoretical computer science 10.4 (2016): 283-424.
[12]Chen, Yilei. "Quantum algorithms for lattice problems." Cryptology ePrint Archive (2024).
[13]Buchheit, Andreas A., Torsten Keßler, and Kirill Serkh. "On the computation of lattice sums without translational invariance." arXiv preprint arXiv:2403.03213 (2024).
[14]Zhang, Jiang, Yu Chen, and Zhenfeng Zhang. "Lattice-Based Programmable Hash Functions and Applications." Journal of Cryptology 37.1 (2024): 4.
[15]Wang, Yu, et al. "Image encryption algorithm based on lattice hash function and privacy protection." Multimedia Tools and Applications 81.13 (2022): 18251-18277.
[16]Wang, Yong, Kwok-Wo Wong, and Di Xiao. "Parallel hash function construction based on coupled map lattices." Communications in Nonlinear Science and Numerical Simulation 16.7 (2011): 2810-2821.
[17]Ye, Zewen, et al. "A Highly-efficient Lattice-based Post-Quantum Cryptography Processor for IoT Applications." IACR Transactions on Cryptographic Hardware and Embedded Systems 2024.2 (2024): 130-153.
[18]Mishra, Nimish, SK Hafizul Islam, and Sherali Zeadally. "A comprehensive review on collision-resistant hash functions on lattices." Journal of Information Security and Applications 58 (2021): 102782.
[19]Iavich, Maksim, et al. "Lattice based merkle." IVUS. 2019.
[20]Mohammed, Elsayed, A-E. Emarah, and K. El-Shennaway. "A blind signature scheme based on ElGamal signature." Proceedings of the Seventeenth National Radio Science Conference. 17th NRSC'2000 (IEEE Cat. No. 00EX396). IEEE, 2000.
[21]Anusha, R., and R. Saravanan. "Enhancement of Lightweight Secure Blockchain Based Edward-El Gamal in the Internet of Things (IoT)." Wireless Personal Communications 134.3 (2024): 1421-1442.
[22]Kairi, Animesh, et al. "An Innovative Method for DNA Cryptography-Based Digital Signature Verification." International Conference on Cyber Intelligence and Information Retrieval. Singapore: Springer Nature Singapore, 2023.