Motivated by the need to have secure strong designate verifier signatures (SDVS) even in the presence of quantum computers, a post-quantum lattice-based SDVS scheme is proposed based on the hardness of the short integer solution problem (SIS) and the learning with errors problem (LWE). The proposed SDVS scheme utilizes the Bonsai trees and pre-image sample-able function primitives to generate the designate verifier signature (DVS). In this construction, the un- forge-ability is based on the hardness of the SIS problem which is proven in the random oracle model and the non-transferability is based on the hardness of the LWE problem. As an application of the proposed SDVS scheme, we design a strong designate verifier ring signature scheme (SDVRS) which satisfies non-transferability. It is proven that the identity of the signer is unconditionally protected not only for any third-party but also for the designate verifier. Under the hardness of the SIS problem, the proposed SDVRS scheme is proven to be existentially un-forgeable in the random oracle model.
Motivated by the need to have secure strong designate verifier signatures (SDVS) even in the presence of quantum computers, a post-quantum lattice-based SDVS scheme is proposed based on the hardness of the short integer solution problem (SIS) and the learning with errors problem (LWE). The proposed SDVS scheme utilizes the Bonsai trees and pre-image sample-able function primitives to generate the designate verifier signature (DVS). In this construction, the un- forge-ability is based on the hardness of the SIS problem which is proven in the random oracle model and the non-transferability is based on the hardness of the LWE problem. As an application of the proposed SDVS scheme, we design a strong designate verifier ring signature scheme (SDVRS) which satisfies non-transferability. It is proven that the identity of the signer is unconditionally protected not only for any third-party but also for the designate verifier. Under the hardness of the SIS problem, the proposed SDVRS scheme is proven to be existentially un-forgeable in the random oracle model.
An Efficient Strong Designated Verifier Signature Based on R− SIS Assumption
The designated verifier signature (DVS), introduced by Jakobssonet al., has the property that only the designated verifier can verify the generated signature. In order to prevent an eavesdropper to get the signature on-line before the designated verifier receives it, they also proposed strong designated verifier signature (SDVS). In this paper, according to an efficient SDVS proposed by Saeedniaet al., we present a post-quantum SDVS in the random oracle model based on lattice assumption. The unforgeability is based on the hardness of the average-case hard problemR−SISq,n,m,β, which is at least as hard as worst-case SVPγover ideal lattices. In addition, compared with existing lattice-based SDVS schemes, our scheme cuts by more than 50 percent repetitions and the size of signature is shorter with 256 bits security.
In this paper, we propose an ID-based strong designated verifier signature (SDVS) over R - SIS assumption in the random model. We remove pre-image sampling function and Bonsai trees such complex structures used in previous lattice-based SDVS schemes. We only utilize simple rejection sampling to protect the security of our scheme. Hence, we will show our design has the shortest signature size comparing with existing lattice-based ID-based SDVS schemes. In addition, our scheme satisfies anonymity (privacy of signer’s identity) proved in existing schemes rarely, and it can resist side-channel attacks with uniform sampling.
Digital signatures are fundamental cryptographic primitives that ensure the authenticity and integrity of digital communication. However, in scenarios involving sensitive interactions -- such as e-voting or e-cash -- there is a growing need for more controlled signing mechanisms. Strong-Designated Verifier Signature (SDVS) offers such control by allowing the signer to specify and restrict the verifier of a signature. The existing state-of-the-art SDVS are mostly based on number-theoretic hardness assumptions. Thus, they are not secure against quantum attacks. Moreover, Post-Quantum Cryptography (PQC)-based SDVS are inefficient and have large key and signature sizes. In this work, we address these challenges and propose an efficient post-quantum SDVS (namely, LaSDVS) based on ideal lattices under the hardness assumptions of the Ring-SIS and Ring-LWE problems. LaSDVS achieves advanced security properties including strong unforgeability under chosen-message attacks, non-transferability, non-delegatability, and signer anonymity. By employing the algebraic structure of rings and the gadget trapdoor mechanism of Micciancio et al., we design LaSDVS to minimize computational overhead and significantly reduce key and signature sizes. Notably, our scheme achieves a compact signature size of O(nlogq), compared to O(n2) size, where n is the security parameter, in the existing state-of-the-art PQC designs. To the best of our knowledge, LaSDVS offers the \textit{smallest private key and signature size} among the existing PQC-based SDVS schemes.
Universal designated verifier signatures can be used to resolve the conflict between authenticity and privacy in some applications. However, all of existing constructions for this primitive are based on hard problems in number theory, and will be ultimately broken in quantum era. To address this issue, we construct the first lattice-based universal designated verifier signatures as a post-quantum candidate for this primitive. Our construction is obtained by directly extending a ring-based variant of the Gentry-Peikert-Vaikuntanathan signature scheme with some additional algorithms, thus the existing key generation and signing implementation can be used without modification. We also show that our construction is provably secure under the Small Integer Solution problem over rings, in the random oracle model.
Digital signatures are unsuitable for specific applications that are sensitive on a personal or commercial level because they are universally verifiable. Jakobsson et al. proposed the Designated Verifier Signature (DVS) system, which only allows the intended verifier to validate a message’s signature. It prohibits the disclosure of a conviction to a third party. This functionality is useful in applications that require both authenticity and signer privacy, such as electronic voting and tender calls. The vast majority of current DVS schemes are based on difficult number theory problems such as integer factorization or discrete log problems over various groups. The development of a large-scale quantum computer would render these schemes unsafe. As a result, it is critical to develop quantum-resistant DVS methods. In both quantum and classical computers, signatures based on one-way functions are more efficient and secure. They have several advantages over digital signatures based on trapdoor functions. As a result, hash-based signatures are now considered viable alternatives to number-theoretic signatures. Existing hash-based signatures, on the other hand, are easily verifiable by anyone. As a result, they do not protect the signer’s identity. In addition, they are one-time signatures. This paper presents a hash-based multi-time designated verifier signature scheme that ensures signer anonymity. The unforgeability of the signature scheme is also tested in the random oracle model under chosen message attack. The properties such as non-transferability and non-delegatability are investigated.
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.