Introduction: The progress in the development of quantum computing has raised the problem of constructing post-quantum two-key cryptographic algorithms and protocols, i.e. crypto schemes resistant to attacks from quantum computers. Based on the hidden discrete logarithm problem, some practical post-quantum digital signature schemes have been developed. The next step could be the development of post-quantum blind signature protocols. Purpose: To develop blind signature protocols based on the computational difficulty of the hidden discrete logarithm problem. Method: The use of blinding factors introduced by the client during the blind signature protocol when the parameters necessary for the blind signature formation are passed to the signatory. Results: It has been proposed to use blinding multipliers of two different types: left-sided and right-sided ones. With them, you can develop blind signature protocols on the base of schemes with a verification equation defined in non-commutative algebraic structures. New blind signature protocols have been developed, based on the computational difficulty of the hidden discrete logarithm problem. As the algebraic carrier for the developed protocols, finite non-commutative associative algebras of two types are used: 1) those with a global two-sided unit, and 2) those with a large set of global left units. Practical relevance: The proposed protocols have a high performance and can be successfully implemented either in software or in hardware.
Introduction: The progress in the development of quantum computing has raised the problem of constructing post-quantum two-key cryptographic algorithms and protocols, i.e. crypto schemes resistant to attacks from quantum computers. Based on the hidden discrete logarithm problem, some practical post-quantum digital signature schemes have been developed. The next step could be the development of post-quantum blind signature protocols. Purpose: To develop blind signature protocols based on the computational difficulty of the hidden discrete logarithm problem. Method: The use of blinding factors introduced by the client during the blind signature protocol when the parameters necessary for the blind signature formation are passed to the signatory. Results: It has been proposed to use blinding multipliers of two different types: left-sided and right-sided ones. With them, you can develop blind signature protocols on the base of schemes with a verification equation defined in non-commutative algebraic structures. New blind signature protocols have been developed, based on the computational difficulty of the hidden discrete logarithm problem. As the algebraic carrier for the developed protocols, finite non-commutative associative algebras of two types are used: 1) those with a global two-sided unit, and 2) those with a large set of global left units. Practical relevance: The proposed protocols have a high performance and can be successfully implemented either in software or in hardware.
The advent of quantum computers poses a direct threat to the security of traditional digital signature schemes, which are based on the Rivest–Shamir–Adleman (RSA) and Elliptic Curve Cryptography (ECC) cryptosystems. Shor's algorithm allows solving the Discrete Logarithm Problem (DLP) in polynomial time, whereas Grover's algorithm significantly reduces the effort required for brute-force attacks on symmetric hash functions and ciphers. Although many post-quantum solutions have been proposed, such as lattice-based schemes (e.g., CRYSTALS-Dilithium, Falcon) or hash-based schemes (e.g., SPHINCS+), they still have some limitations to overcome, such as large public keys, bulky signatures, high computational costs, and difficulties in integrating into existing Public Key Infrastructures (PKIs). In this paper, we propose a new type of hard problem, defined over a finite prime field, in which the generator is kept secret to prevent any direct Shor attack and is only subject to a limited influence from Grover. Based on this newly proposed hard problem, we construct a post-quantum digital signature scheme that is both Shor-resistant and Grover-resistant, secure against classical attacks, and fully compatible with current PKI infrastructures. Compared with existing post-quantum digital signature schemes, our solution significantly optimizes the size of public keys and signatures while increasing the speed of signing and verification. The newly proposed hard problem cannot be solved by known classical or quantum algorithms, thus ensuring long-term security. Performance evaluation results show that the scheme provides an optimal balance between performance and security, opening up a cost-effective implementation path for the post-quantum cryptography era.
Digital signatures are used to ensure authentication. Blind signature schemes are a special form of digital signatures and important in scenarios which depend on anonymous and secure authentication. (e.g. e-voting) The common digital blind signature schemes are based on asymmetric cryptography with underlying hard problems like integer factorization or discrete logarithm. These hard problems will become weak with the development of quantum computers. To avoid the uselessness of classic cryptography in the post quantum era, it will be important to find alternative methods based on other hard problems. This book deals with the attempt of developing a new blind signature scheme based on lattice signature schemes.
The rapid development of quantum computing poses a threat to traditional public-key systems. The existing Internet security framework relies heavily on public-key cryptography and hash functions, with classical algorithms such as RSA and ECC widely used for digital signatures and identity authentication. Meanwhile, quantum algorithms, represented by Shor’s algorithm and Grover’s algorithm, which can solve the integer factorization and discrete logarithm problems in polynomial time or significantly accelerate brute-force attacks on symmetric ciphers, posing a fundamental threat to traditional public-key cryptographic systems. To address the security threats posed by quantum computing, post-quantum cryptography has emerged. Transition schemes, such as the NIST post-quantum standards, have been proposed; however, new post-quantum algorithms require significantly more computational time for verification than traditional algorithms, and their migration into practical network protocols and blockchain systems presents considerable challenges. Among these, post-quantum digital signature technology is a key branch. This paper systematically reviews research progress in post-quantum digital signatures, summarizes NIST-standardized algorithms and cutting-edge non-standard schemes, and compares the performance of typical algorithms.
Abstract Lattice-based digital signature has become one of the widely recognized post-quantum algorithms because of its simple algebraic operation, rich mathematical foundation and worst-case security, and also an important tool for constructing cryptography. This survey explores lattice-based digital signatures, a promising post-quantum resistant alternative to traditional schemes relying on factoring or discrete logarithm problems, which face increasing risks from quantum computing. The study covers conventional paradigms like Hash-and-Sign and Fiat-Shamir, as well as specialized applications including group, ring, blind, and proxy signatures. It analyzes the versatility and security strengths of lattice-based schemes, providing practical insights. Each chapter summarizes advancements in schemes, identifying emerging trends. We also pinpoint future directions to deploy lattice-based digital signatures including quantum cryptography.
Conventional cryptographic systems such as factorization and discrete logarithm problems are threatened by the quick development of quantum computing.This paper offers a thorough study of number-theoretic problems and structures underlying post-quantum cryptographic protocols based on modular arithmetic, algebraic structures, lattices and computational hardness assumptions.The research is based on the mathematical problems of Learning with Errors (LWE) and Short Integer Solution (SIS) which are used for secure quantum-resistant encryption, digital signature and key exchange mechanisms.In secure communication scenarios, a framework of structured protocol is analyzed, which combines lattice-based operations and modular polynomial transformations.Experimental comparisons show that these schemes are not only practically efficient in computation but also have a level of security greater than 95% @ E-mail:
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.