It is very important that the communicating parties are able to verify their identity in order to communicate with each other properly. Identification schemes are used for this purpose. The identification schemes, widely used in applications, are based on the hardness of the discrete logarithm or integer factorization problem. Shor proposed an algorithm that solve discrete logarithm and factorization problems by using quantum computers in polynomial-time. Therefore, there is a huge need for identification schemes which can be used post-quantum. In this paper, the identification schemes based on hardness of different lattice problems are surveyed. In addition, a new zero-knowledge lattice-based identification scheme is proposed.
It is very important that the communicating parties are able to verify their identity in order to communicate with each other properly. Identification schemes are used for this purpose. The identification schemes, widely used in applications, are based on the hardness of the discrete logarithm or integer factorization problem. Shor proposed an algorithm that solve discrete logarithm and factorization problems by using quantum computers in polynomial-time. Therefore, there is a huge need for identification schemes which can be used post-quantum. In this paper, the identification schemes based on hardness of different lattice problems are surveyed. In addition, a new zero-knowledge lattice-based identification scheme is proposed.
It is known that the development of quantum computers will break the cryptographic schemes that are in use today. Since Shor’s algorithm is able to solve the factoring and discrete logarithm problems, all cryptographic systems based on these two problems will get broken in the presence of large-scale quantum computers. Lattice-based schemes, however, are considered secure against attacks with these new machines. In this paper we present an overview of lattice-based cryptosystems, showing the most recent and the most promising candidates for encryption and signatures based on lattice problems. We explain the advantages and disadvantages of the cryptographic schemes. We also adjoin details about zero knowledge identification. With this work we try to give insight to one of the most promising candidates of future cryptography, for the time when potential quantum computers exist. We also point out drawbacks of these systems, which discloses directions for future work in lattice-based cryptography.
In this paper we propose a new 5-pass zero-knowledge identification scheme with soundness error close to 1/2. We use the hardness of the Inhomogeneous Small Integer Solution problem as security basis. Our protocol achieves lower communication costs compared with previous lattice-based zeroknowledge identification schemes. Besides, our construction allows smaller public and secret keys by applying the use of ideal lattices. We allow the prover to possess several pairs of secret and public keys, and choose randomly which pair is to be used in a given round of execution. We also dealt with nonces in zero-knowledge schemes in a new way, lowering the number of values exchanged between the prover and the verifier. Hence, our scheme has the good features of having a zero-knowledge security proof based on a well known hard problem of lattice theory, with worst to average-case reduction, and small size of secret and public keys.
Identity-based signcryption schemes based on large integer factorization and discrete logarithm problems were considered to be insecure for the quantum computer attack. Thus, choosing a quantum-resist platform and constructing secure schemes based on new hard assumptions are challenges. In this paper, we propose an alternative scheme - an identity-based signcryption on lattice, which does not need to rely on a trapdoor. Meanwhile, our scheme achieves IND-CCA2 and sUF-CMA security, and it is also secure against the current quantum algorithm attacks based on LWE problem for lattice. Furthermore, we demonstrate that the newly proposed scheme has much shorter secret key size, and higher speeds in signcryption and unsigncryption stages, compared with some exiting identity-based signcryption schemes.
The advent of quantum computers introduces new challenges to the fields of encryption and authentication. Traditional cryptographic systems, such as RSA and ECC, rely on mathematical problems that are computationally hard for classical computers to solve. However, quantum computers have the potential to render these algorithms ineffective by leveraging Shor's algorithm, which can efficiently factor large numbers and solve the discrete logarithm problem. This capability threatens the security of many widely deployed encryption and authentication schemes. There have been a number of post-quantum cryptography methods proposed in the past. However, they are either relatively difficult to implement in current small-scale quantum computers or they do not take noise and error mitigation into account. In this paper, we propose a new framework of post-quantum key generation and identity verification mechanisms which are relatively easy to implement and adapt. Our approaches take the noisy nature of current quantum devices into consideration. As a result, our proposed approach can resist attacks from malicious quantum computers and the successful attack rate could quickly decay to zero as the number of qubits increases.
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.
Most of the provably-secure proxy signature schemes rely on the average-case hardness problems such as the integer factorization problems and the discrete logarithm problems. Therefore, those schemes are insecure to quantum analysis algorithms, since there exist quantum algorithms efficiently solving the factorization and logarithm problems. To make secure proxy signature schemes against quantum analysis, some lattice-based proxy signature schemes are suggested. However, none of the suggested lattice-based proxy signature schemes is proxy-protected in the adaptive security model. In the paper, we propose a provably-secure ID-based proxy signature scheme based on the lattice problems. Our scheme is proxy-protected in the adaptive security model.