Digital signatures are essential for the security of computer networks such as the Internet. For example, digital signatures are widely used to ensure the authenticity and integrity of updates for operating systems and other software applications. The security of the few practically used signature schemes is threatened by quantum computers. When large quantum computers are built, all currently used signature schemes will become insecure. It is therefore of extreme importance to develop alternative signature schemes that remain secure in the presence of quantum computers and which are able to compete with currently used signature schemes. A very promising candidate for a signature scheme that withstands quantum computer attacks is the Merkle signature scheme invented by Merkle in 1979. However, even combined with the improvements by Szydlo and Coronado, the Merkle signature scheme has certain efficiency drawbacks that keep it from being truly practical. First of all, it has highly unbalanced signature generation times. In the worst case, signature generation takes significantly longer than on average. Secondly, the Merkle--Szydlo--Coronado signature scheme produces very large signatures. It is also unclear if Merkle's signature scheme is suitable for application on resource constrained devices. The generalized Merkle signature scheme (GMSS) presented in this thesis solves the problems mentioned above. It drastically reduces the worst case signature generation time of the Merkle--Szydlo--Coronado signature scheme. The worst case signature generation time of GMSS corresponds to the average case signature generation time of the Merkle--Szydlo--Coronado signature scheme. Further, the worst case signature generation time of GMSS is extremely close to its average case signature generation time and thus, GMSS provides balanced timings for the signature generation. GMSS exploits the improved signature generation times to provide a noticeable reduction of the signature sizes while maintaining timings that are highly competitive to currently used signature schemes. A proof-of-concept implementation shows that GMSS can also be used on resource constrained devices and excellently compares to currently used signature schemes. This thesis also introduces a new construction method for Merkle signatures. This construction is provably secure under weaker security assumptions and yields a signature scheme with a significantly higher security level compared to the original construction.
Digital signatures are essential for the security of computer networks such as the Internet. For example, digital signatures are widely used to ensure the authenticity and integrity of updates for operating systems and other software applications. The security of the few practically used signature schemes is threatened by quantum computers. When large quantum computers are built, all currently used signature schemes will become insecure. It is therefore of extreme importance to develop alternative signature schemes that remain secure in the presence of quantum computers and which are able to compete with currently used signature schemes. A very promising candidate for a signature scheme that withstands quantum computer attacks is the Merkle signature scheme invented by Merkle in 1979. However, even combined with the improvements by Szydlo and Coronado, the Merkle signature scheme has certain efficiency drawbacks that keep it from being truly practical. First of all, it has highly unbalanced signature generation times. In the worst case, signature generation takes significantly longer than on average. Secondly, the Merkle--Szydlo--Coronado signature scheme produces very large signatures. It is also unclear if Merkle's signature scheme is suitable for application on resource constrained devices. The generalized Merkle signature scheme (GMSS) presented in this thesis solves the problems mentioned above. It drastically reduces the worst case signature generation time of the Merkle--Szydlo--Coronado signature scheme. The worst case signature generation time of GMSS corresponds to the average case signature generation time of the Merkle--Szydlo--Coronado signature scheme. Further, the worst case signature generation time of GMSS is extremely close to its average case signature generation time and thus, GMSS provides balanced timings for the signature generation. GMSS exploits the improved signature generation times to provide a noticeable reduction of the signature sizes while maintaining timings that are highly competitive to currently used signature schemes. A proof-of-concept implementation shows that GMSS can also be used on resource constrained devices and excellently compares to currently used signature schemes. This thesis also introduces a new construction method for Merkle signatures. This construction is provably secure under weaker security assumptions and yields a signature scheme with a significantly higher security level compared to the original construction.
The rapid advancement of quantum computing poses a serious threat to classical digital signature algorithms such as RSA and ECDSA, which rely on mathematical problems vulnerable to quantum attacks. Hash-based digital signatures offer a strong post-quantum alternative due to their reliance on cryptographic hash functions and their resistance to both classical and quantum adversaries. This study evaluates the feasibility of hash-based signatures in lightweight and resource-constrained environments by implementing three representative schemes: Lamport One-Time Signatures (OTS), Winternitz One-Time Signatures (WOTS), and Merkle-WOTS. The analysis focuses on key performance factors relevant to constrained devices, including key size, signature size, signing time, and verification speed. Experimental results show that while Lamport OTS provides conceptual simplicity and WOTS offers improved efficiency, the Merkle-WOTS scheme delivers the most practical balance. It supports multiple signatures under a compact public key while maintaining moderate signature sizes and competitive performance. These findings indicate that Merkle-WOTS is a strong candidate for post-quantum authentication in IoT and other lightweight embedded systems.
With the advancement of quantum computing, conventional digital signature algorithms such as RSA and El-Gamal are increasingly vulnerable to quantum attacks. This presents a significant challenge for ensuring the security and integrity of electronic signatures. As a result, there is a need to develop post-quantum signature algorithms that can withstand attacks from quantum computers while maintaining computational efficiency. This study proposes a novel modification of the Merkle post-quantum signature scheme, integrating an optimized version of Lamport’s one-time signature algorithm. The core contribution of this work is the design and implementation of a new algorithm that significantly reduces signature verification time without compromising cryptographic strength. A software implementation of the modified scheme was developed using Python and the PyQt 6 library, allowing for practical testing and analysis. The performance of the modified algorithm was compared against the standard Lamport algorithm using execution time measurements and statistical analysis. The experimental results demonstrate that the modified algorithm significantly improves signature verification speed, reducing the time required by up to 44.81% compared to the standard algorithm. The study presents a more efficient post-quantum Merkle signature scheme with a modified Lamport algorithm that enhances signature verification speed while maintaining strong cryptographic security. The results suggest that the proposed scheme is particularly well-suited for environments where fast authentication of multiple digital signatures is required. Experimental results confirm the advantage of the proposed approach, offering a more efficient solution for secure, high-speed digital authentication in post-quantum environments
Public key cryptography plays a pivotal role in maintaining digital security and privacy, with its foundations built on the hardness of certain mathematical problems. However, the emergence of quantum computing threatens the security of current cryptographic systems, making the adoption of post-quantum cryptography (PQC) an urgent necessity. Digital signature schemes are essential components in secure communications, providing authentication, non-repudiation, and data integrity. This paper examines the state of post-quantum digital signature schemes across various cryptographic approaches, including lattice-based, code-based, multivariate polynomial-based, hash-based, symmetric-key-based, and isogeny-based systems, alongside advancements in Multi-Party Computation in the Head (MPC-in-the-head) schemes. The paper then explores application-specific signatures such as blind, undeniable, threshold, chameleon, aggregate, and ring signatures, explaining their main use cases and the existing post-quantum cryptographic classifications that support these constructions individually. Software implementations of selected prominent PQC digital signature schemes were carried out, and their performance was systematically analysed using metrics such as bandwidth consumption, latency, and computational efficiency. These results provide key observations regarding the suitability of different schemes for both resource-constrained and high-performance environments. Subsequently, a detailed literature review of implementations on embedded and hardware platforms is presented, focusing on ARM-based devices and FPGA accelerators to evaluate deployment feasibility beyond general-purpose processors. Based on the software and implementation-level findings, a comparative analysis across software, embedded, and hardware platforms is conducted to highlight architectural influences on performance, scalability, and practicality. Furthermore the cryptanalytic attacks on post-quantum digital signature schemes across various PQC classifications are examined in this paper, taking into account both classical and quantum adversarial models. To evaluate realistic security constraints, implementation-oriented vulnerabilities such as side-channel and fault-based attacks are also examined. In addition, the applicability of post-quantum digital signature schemes within TLS, IoT, and related practical deployment scenarios is analysed. The study also discusses possible directions for further investigation, focusing on the requirement for effective and expandable PQC systems that can satisfy changing cybersecurity requirements. In order to protect sensitive data in the digital era, this study emphasizes the need for implementing quantum-secure systems by fusing theoretical understandings with real-world applications.
Modern-day cryptographic schemes are threatened by the rapid development of quantum computers, which are capable of solving discrete-logarithm-based problems in a reasonable amount of time. The paper proposes a novel approach to a PORS post-quantum secure signature. The main idea of the proposal is integrating a PORS signature scheme with a Verkle tree, which greatly reduces the signature size compared to a PORST that uses a Merkle tree, while reducing authentication overhead through constant-size vector commitment proofs at each tree level. The work is highly relevant as it proposes a post-quantum digital signature which has compact proofs and at the same time solves the problems of the original HORS signature scheme (subset-resilience problem). The work contributes to the ongoing standardization efforts in post-quantum cryptography by providing a theoretically scalable and efficient signature scheme that balances security, size, and verification speed.
The security of public key cryptosystems has become a major concern due to recent developments in the field of quantum computing. Despite efforts to enhance defenses against quantum attacks, current methods are impractical due to safety and efficacy concerns. A recent study explores hash-based digital signature methods and evaluates their effectiveness using Merkle trees. Furthermore, novel approaches based on Verkle trees and vector commitments have been studied to reduce quantum threats. First, we introduce a post-quantum digital signature system that combines vector commitments based on lattices with Verkle trees. This architecture optimizes traditional Merkle tree architecture by preserving resistance to quantum attacks while improving cryptographic proofs. Second, in order to ensure secure initial seed generation without sacrificing operational viability, we create a hybrid random number generation framework that combines quantum random number generation (QRNG) with pseudorandom approaches. We provide a detailed analysis of generating random numbers in our article, which makes it easier to build a post quantum cryptosystem that uses our generator to provide initial random values. Our system is notable for its robust security against quantum threats, speed, and efficiency.
Digital signatures are indispensable for security on the Internet, because they guarantee authenticity, integrity, and non-repudiation, of namely e-mails, software updates, and in the Transport Layer Security (TLS) protocol which is used for secure data transfer, for example. Most signature schemes that are currently in use such as the RSA signature scheme, are considered secure as long as the integer factorization problem or the discrete logarithm (DL) problem are computationally hard. At present, no algorithms have yet been found to solve these problems on conventional computers in polynomial time. However, in 1997, Shor published a polynomial-time algorithm that uses quantum computation to solve the integer factorization and the DL problem. In particular, this means that RSA signatures are considered broken as soon as large-scale quantum computers exist. Due to significant advances in the area of quantum computing, it is reasonable to assume that within 20 years, quantum computers that are able to break the RSA scheme, could exist. In order to maintain authenticity, integrity, and non-repudiation of data, cryptographic schemes that cannot be broken by quantum attacks are required. In addition, these so-called post-quantum secure schemes should be sufficiently efficient to be suitable for all established applications. Furthermore, solutions enabling a timely and secure transition from classical to post-quantum schemes are needed. This thesis contributes to the above-mentioned transition. In this thesis, we present the two lattice-based digital signature schemes TESLA and qTESLA, whereby lattice-based cryptography is one of five approaches to construct post-quantum secure schemes. Furthermore, we prove that our signature schemes are secure as long as the so-called Learning With Errors (LWE) problem is computationally hard to solve. It is presumed that even quantum computers cannot solve the LWE problem in polynomial time. The security of our schemes is proven using security reductions. Since our reductions are tight and explicit, efficient instantiations are possible that provably guarantee a selected security level, as long as the corresponding LWE instance provides a certain hardness level. Since both our reductions (as proven in the quantum random oracle model) and instantiations, take into account quantum attackers, TESLA and qTESLA are considered post-quantum secure. Concurrently, the run-times for generating and verifying signatures of qTESLA are similar (or faster) than those of the RSA scheme. However, key and signature sizes of RSA are smaller than those of qTESLA. In order to protect both the theoretical signature schemes and their implementations against attacks, we analyze possible vulnerabilities against implementation attacks. In particular, cache-side-channel attacks resulting from observing the cache behavior and fault attacks, which recover secret information by actively disrupting the execution of an algorithm are focused. We present effective countermeasures for each implementation attack we found. Our analyses and countermeasures also influence the design and implementation of qTESLA. Although our schemes are considered (post-quantum) secure according to state-of-the-art LWE attacks, cryptanalysis of lattice-based schemes is still a relatively new field of research in comparison to RSA schemes. Hence, there is a lack of confidence in the concrete instantiations and their promised security levels. However, due to developments within the field of quantum computers, a transition to post-quantum secure solutions seems to be more urgently required than ever. To solve this dilemma, we present an approach to combine two schemes, e.g., qTESLA and the RSA signature scheme, so that the combination is secure as long as one of the two combined schemes is secure. We present several of such combiners to construct hybrid signature schemes and hybrid key encapsulation mechanisms to ensure both authenticity and confidentiality in our Public-Key Infrastructure (PKI). Lastly, we also demonstrate how to apply the resulting hybrid schemes in standards such as X.509 or TLS. To summarize, this work presents post-quantum secure candidates which can, using our hybrid schemes, add post-quantum security to the current classical security in our PKI.