Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Transactions on Emerging Telecommunications Technologies

Design of lattice‐based ElGamal encryption and signature schemes using SIS problem

Daya Sagar Gupta, G. P. Biswas

Published Nov 10, 2017• 49 citations
Publisher

Abstract

Abstract The emerging technologies like quantum computing and cloud computing have a complex computing power and can break the security of the classical cryptographic constructions (like ElGamal's cryptosystem). Thus, we were motivated to work on hard lattice problems, which are more complex and can resist these new modern technologies. In this proposal, we present a lattice‐based version of discrete logarithm problem‐based ElGamal public‐key encryption and signature schemes that exhibit strong security features and efficient implementation. The security of these presented schemes is based on the worst‐case hardness of approximating a small integer vector in their corresponding lattice. Furthermore, this proposed work illustrates a security proof of the proposed schemes and shows that the presented schemes are well protected in the modern computing environment. The performance analysis and comparison with classical ElGamal schemes and recent lattice‐based schemes are also made, and it is seen that the proposed schemes achieve better performance.

DOI
10.1002/ett.3255

Related papers

Lattice-Based Post-Quantum Public Key Encryption Scheme Using ElGamal’s Principles

Dana Sairangazhykyzy Amirkhanova, Maksim Iavich, Orken J. Mamyrbayev

Modern technologies like quantum and cloud computing have reshaped computing, offering immense power and scalability. While beneficial, they also challenge the security of traditional cryptographic systems. Quantum computing threatens RSA and ECC with algorithms like Shor’s algorithm, which can accelerate computations exponentially. This risks exposing these systems to attacks, necessitating quantum-resistant cryptography. Cloud computing poses data security concerns, requiring robust cryptographic mechanisms and access controls. Lattice-based cryptography, leveraging problems like the Short Integer Solution (SIS), emerges as a solution. This paper presents a novel quantum-resistant public key encryption scheme based on ElGamal and SIS, ensuring security against quantum and classical threats in modern cryptographic environments.

Cryptography•Jul 8, 2024•26 citations

A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption

Yang Li, Kee Siong Ng, Purcell, Michael

Why study Lattice-based Cryptography? There are a few ways to answer this question. 1. It is useful to have cryptosystems that are based on a variety of hard computational problems so the different cryptosystems are not all vulnerable in the same way. 2. The computational aspects of lattice-based cryptosystem are usually simple to understand and fairly easy to implement in practice. 3. Lattice-based cryptosystems have lower encryption/decryption computational complexities compared to popular cryptosystems that are based on the integer factorisation or the discrete logarithm problems. 4. Lattice-based cryptosystems enjoy strong worst-case hardness security proofs based on approximate versions of known NP-hard lattice problems. 5. Lattice-based cryptosystems are believed to be good candidates for post-quantum cryptography, since there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best-known classical (non-quantum) algorithms, unlike for integer factorisation and (elliptic curve) discrete logarithm problems. 6. Last but not least, interesting structures in lattice problems have led to significant advances in Homomorphic Encryption, a new research area with wide-ranging applications.

arXiv:2208.08125•Aug 17, 2022•15 citations

Efficient implementation of ideal lattice-based cryptography

Thomas Pöppelmann

Abstract Almost all practically relevant asymmetric cryptosystems like RSA or ECC are either based on the hardness of factoring or on the hardness of the discrete logarithm problem. However, both problems could be solved efficiently on a large enough quantum computer. While quantum computers powerful enough to break currently used parameter sets are not available yet, they are heavily researched and expected to reach maturity in 15 to 20 years. As a consequence, research on alternative quantum-safe cryptosystems is required. One alternative is lattice-based cryptography which allows the construction of asymmetric public-key encryption and signature schemes that offer a good balance between security, performance, and key as well as ciphertext sizes.

it - Information Technology•Nov 7, 2017•7 citations

Research on Lattice-Based Cryptographic Algorithms

WU Kun, TANG Jinyi, LI Peiqi, WANG Xiaorui, WANG Xiaoyu

The security of classical public-key cryptosystems, which operate based on the computational intractability of integer factorization and discrete logarithm problems, is profoundly threatened by the rapid development of quantum computing. Post-Quantum Cryptography (PQC) has been proposed to improve security against quantum attacks. Lattice-based cryptography is widely regarded as one of the most promising PQC method because of its proven security, efficient implementation, and functional versatility, and it has achieved significant progress in both algorithmic design and engineering implementation in recent years. This paper presents a systematic survey of the status of research on lattice-based cryptographic algorithms. First, the fundamental theory of lattices and their core hard problems are discussed. Next, the technical characteristics and performance of encryption and key encapsulation mechanisms, digital signature schemes, and key exchange protocols constructed based on lattice hard problems are reviewed and compared. Subsequently, the principles and optimization paths of two key technologies for lattice cryptography implementation, namely polynomial multiplication using the fast Number Theoretic Transform (NTT) and pre-image sampling algorithms, are discussed. Finally, considering the PQC standardization process of the National Institute of Standards and Technology (NIST), an outlook on future research directions for lattice-based cryptography is presented. The research directions include the development of more "succinct" fundamental hard problems, strengthening security proofs, improving algorithm efficiency, and countering novel attacks. This review serves as a reference for promoting the practical deployment and further research of lattice-based cryptography.

•Sep 1, 2026•0 citations

Post-quantum Digital Signatures using ElGamal Approach

Maksim Iavich, Dana Sairangazhykyzy Amirkhanova

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.

International Journal of Computer Network and Information Security•May 29, 2025•1 citation

A Survey on Digital Signature Schemes in Lattice Based Cryptography

Chetan Joshi, Nirdesh Pal

Quantum computers are moving closer to reality, and with that comes a serious concern for today’s public-key cryptography. Many of the encryption and digital signature systems we rely on now, such as RSA and ECC, may no longer be secure in the future. Because of this, researchers are actively looking for new methods that can protect digital communication in the post-quantum era. One of the most promising directions is lattice-based cryptography. This paper gives a simple and focused review of lattice-based signature schemes. It brings together the main ideas from the existing literature and explains how these schemes are built, why they are considered secure, and what makes them practical. The review mainly discusses schemes based on hard lattice problems such as SIS and LWE. To make the comparison clearer, a table is also included that compares different signature schemes in terms of key size, signature size, security level, and computational efficiency. Overall, this study shows why lattice-based signature schemes are becoming an important part of modern cryptographic research and why they may play a major role in securing digital systems against future quantum threats.

International Journal of Scientific Research in Science Engineering and Technology•May 18, 2026•0 citations
Abstract The emerging technologies like quantum computing and cloud computing have a complex computing power and can break the security of the classical cryptographic constructions (like ElGamal's cryptosystem). Thus, we were motivated to work on hard lattice problems, which are more complex and can resist these new modern technologies. In this proposal, we present a lattice‐based version of discrete logarithm problem‐based ElGamal public‐key encryption and signature schemes that exhibit strong security features and efficient implementation. The security of these presented schemes is based on the worst‐case hardness of approximating a small integer vector in their corresponding lattice. Furthermore, this proposed work illustrates a security proof of the proposed schemes and shows that the presented schemes are well protected in the modern computing environment. The performance analysis and comparison with classical ElGamal schemes and recent lattice‐based schemes are also made, and it is seen that the proposed schemes achieve better performance.
Modern technologies like quantum and cloud computing have reshaped computing, offering immense power and scalability. While beneficial, they also challenge the security of traditional cryptographic systems. Quantum computing threatens RSA and ECC with algorithms like Shor’s algorithm, which can accelerate computations exponentially. This risks exposing these systems to attacks, necessitating quantum-resistant cryptography. Cloud computing poses data security concerns, requiring robust cryptographic mechanisms and access controls. Lattice-based cryptography, leveraging problems like the Short Integer Solution (SIS), emerges as a solution. This paper presents a novel quantum-resistant public key encryption scheme based on ElGamal and SIS, ensuring security against quantum and classical threats in modern cryptographic environments.
Why study Lattice-based Cryptography? There are a few ways to answer this question. 1. It is useful to have cryptosystems that are based on a variety of hard computational problems so the different cryptosystems are not all vulnerable in the same way. 2. The computational aspects of lattice-based cryptosystem are usually simple to understand and fairly easy to implement in practice. 3. Lattice-based cryptosystems have lower encryption/decryption computational complexities compared to popular cryptosystems that are based on the integer factorisation or the discrete logarithm problems. 4. Lattice-based cryptosystems enjoy strong worst-case hardness security proofs based on approximate versions of known NP-hard lattice problems. 5. Lattice-based cryptosystems are believed to be good candidates for post-quantum cryptography, since there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best-known classical (non-quantum) algorithms, unlike for integer factorisation and (elliptic curve) discrete logarithm problems. 6. Last but not least, interesting structures in lattice problems have led to significant advances in Homomorphic Encryption, a new research area with wide-ranging applications.
Abstract Almost all practically relevant asymmetric cryptosystems like RSA or ECC are either based on the hardness of factoring or on the hardness of the discrete logarithm problem. However, both problems could be solved efficiently on a large enough quantum computer. While quantum computers powerful enough to break currently used parameter sets are not available yet, they are heavily researched and expected to reach maturity in 15 to 20 years. As a consequence, research on alternative quantum-safe cryptosystems is required. One alternative is lattice-based cryptography which allows the construction of asymmetric public-key encryption and signature schemes that offer a good balance between security, performance, and key as well as ciphertext sizes.
The security of classical public-key cryptosystems, which operate based on the computational intractability of integer factorization and discrete logarithm problems, is profoundly threatened by the rapid development of quantum computing. Post-Quantum Cryptography (PQC) has been proposed to improve security against quantum attacks. Lattice-based cryptography is widely regarded as one of the most promising PQC method because of its proven security, efficient implementation, and functional versatility, and it has achieved significant progress in both algorithmic design and engineering implementation in recent years. This paper presents a systematic survey of the status of research on lattice-based cryptographic algorithms. First, the fundamental theory of lattices and their core hard problems are discussed. Next, the technical characteristics and performance of encryption and key encapsulation mechanisms, digital signature schemes, and key exchange protocols constructed based on lattice hard problems are reviewed and compared. Subsequently, the principles and optimization paths of two key technologies for lattice cryptography implementation, namely polynomial multiplication using the fast Number Theoretic Transform (NTT) and pre-image sampling algorithms, are discussed. Finally, considering the PQC standardization process of the National Institute of Standards and Technology (NIST), an outlook on future research directions for lattice-based cryptography is presented. The research directions include the development of more "succinct" fundamental hard problems, strengthening security proofs, improving algorithm efficiency, and countering novel attacks. This review serves as a reference for promoting the practical deployment and further research of lattice-based cryptography.
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.
Quantum computers are moving closer to reality, and with that comes a serious concern for today’s public-key cryptography. Many of the encryption and digital signature systems we rely on now, such as RSA and ECC, may no longer be secure in the future. Because of this, researchers are actively looking for new methods that can protect digital communication in the post-quantum era. One of the most promising directions is lattice-based cryptography. This paper gives a simple and focused review of lattice-based signature schemes. It brings together the main ideas from the existing literature and explains how these schemes are built, why they are considered secure, and what makes them practical. The review mainly discusses schemes based on hard lattice problems such as SIS and LWE. To make the comparison clearer, a table is also included that compares different signature schemes in terms of key size, signature size, security level, and computational efficiency. Overall, this study shows why lattice-based signature schemes are becoming an important part of modern cryptographic research and why they may play a major role in securing digital systems against future quantum threats.