Post-quantum Digital Signatures using ElGamal Approach

Iavich M. Sairangazhykyzy D.A.
Jun. 2025 Modern Education and Computer Science Press

International Journal of Computer Network and Information Security
2025 #17 Issue 3 89 - 108 pp.

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 postquantum 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.

CVP , DLP , Index Terms: SIS , Lattice , PKE , Post-quantum , SVP

Text of the article Перейти на текст статьи

Department of Information Security Faculty, Caucasus University, Tbilisi, Georgia
Al-Farabi Kazakh National University, Almaty, Kazakhstan
Department of Cybersecurity, Information Processing and Storage, Satbayev University, Almaty, Kazakhstan

Department of Information Security Faculty
Al-Farabi Kazakh National University
Department of Cybersecurity

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026