We describe a general technique to simplify as well as to improve several lattice based cryptographic protocols. The technique is rather straightforward and is easily applied to the protocols, and gives both a simpler analysis and better performance than the original protocols. The improvement is global: the modified protocols are simpler, faster, require less storage, use less bandwidth and need less random bits than the originals. Moreover, the improvement is achieved without any loss in security: we formally prove that the modified protocols are at least as secure as the original ones. In fact, the modified protocols might even be more secure as the adversary gets less information. We exemplify our technique on the Goldreich-Goldwasser zero-knowledge proof systems for lattice problems and the GGH public key cryptosystem. Partially supported by DARPA grant DABT63-96-C-0018 and NTT grant 67627-00. 1 1 Introduction Various cryptographic protocols based on the hardness of la...
We describe a general technique to simplify as well as to improve several lattice based cryptographic protocols. The technique is rather straightforward and is easily applied to the protocols, and gives both a simpler analysis and better performance than the original protocols. The improvement is global: the modified protocols are simpler, faster, require less storage, use less bandwidth and need less random bits than the originals. Moreover, the improvement is achieved without any loss in security: we formally prove that the modified protocols are at least as secure as the original ones. In fact, the modified protocols might even be more secure as the adversary gets less information. We exemplify our technique on the Goldreich-Goldwasser zero-knowledge proof systems for lattice problems and the GGH public key cryptosystem. Partially supported by DARPA grant DABT63-96-C-0018 and NTT grant 67627-00. 1 1 Introduction Various cryptographic protocols based on the hardness of la...
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.
Current public key cryptosystems that are based on the hardness of integer factorization and discrete logarithm are insecure in the presence of large-scale quantum computers. Much effort has been devoted to replacing the quantum-insecure cryptosystems with newly developed "post-quantum" cryptosystem candidates, conjectured to be secure against quantum attack. Lattice-based cryptography has been widely recognized as a prominent candidate for practical post-quantum security.This dissertation improves the robustness and versatility of lattice-based cryptography through the following three contributions: 1. Chapter 3 introduces a constant-round protocol for unauthenticated group key exchange (i.e., with security against a passive eavesdropper). Group key exchange protocols allow a set of N parties to agree on a shared, secret key by communicating over a public network. Our protocol is based on the hardness of a lattice problem, which hence yields (plausible) post-quantum security. 2. In Chapter 4, we propose a framework for cryptanalysis of lattice-based schemes when certain types of information about the secret are leaked. Our framework generalizes the primal lattice reduction attack. The generalization allows for integrating the leaked information progressively before running a final lattice reduction step. Our framework can estimate the amount of security loss caused by the leaked information, and perform lattice reduction attacks with leaked information when computationally feasible. 3. Chapter 5 introduces an approach towards a ring analogue of the Leftover Hash Lemma (LHL). The LHL is a mathematical tool often used in the analysis of various lattice-based cryptosystems, as well as their leakage-resilient counterparts. However, it does not hold in the ring setting, which is typical for efficient cryptosystems. Lyubashevsky et al. (Eurocrypt '13) proved a "regularity lemma," which is used in the ring setting instead of the LHL; however, this applies only for centered, spherical Gaussian inputs, while the LHL applies when the input is drawn from any high min-entropy distribution. Our approach generalizes the "regularity lemma" of Lyubashevsky et al. to certain conditional distributions. A number of Ring-Learning with Errors based cryptosystems can achieve certain leakage resilience properties using our results.
With a recent increase in the advancement of the technology, computer system and it’s sensitive data are getting exhibited to unauthorised users, with steadily corroding the fundamentals of computer security. This, in fact, demanded fundamental innovations that require several cryptographic paradigms and security protocol. Previously it was thought that asymmetric cryptographic key like RSA, Diffie-Hellman, are very hard to decrypt by classical computation, but with the implementation of quantum computation, it is proved that this kind of cryptographic algorithm is very easy to decrypt and hackers can steal important Data [3], [6]. After the release of Ajtai’s research paper " Generating Hard Instances of Lattice Problem" [2], a million reasons arose in the minds of the researchers to develop on methods based on lattice-based cryptography to improve their security needs. Firstly, it provided much stronger security, and the average-case of several problems in lattice-based cryptography seems equivalent to the worst-case problem of these problems [2]. Moreover, lattices have the potential to persuade the cryptanalytic attacks created by any quantum computers i.e Quantum Computational Secure [3]. In this paper, we will discuss lattice-based cryptosystem, it’s security dimensions, a general brief on how it works, future scope, applications and areas of Interest.
Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem. However, all known such proof \n \nsystems have relatively weak security guarantees: Breaking each of these protocols is potentially easier than solving the underlying instance of the ISIS problem. As a consequence, cryptographic constructions relying on these proof systems typically inherit the sub-optimal security guarantees. Therefore, proof systems with stronger security guarantees are highly desirable. Such protocols are not only interesting from a theoretical point of view, but they also lead to lattice-based cryptographic constructions relying on weaker hardness assumptions than the contemporary schemes. \n \n \n \nIn this thesis, we construct a series of zero-knowledge proofs of knowledge with strong security guarantees and reasonable communication costs, that can find various applications in lattice-based cryptography. Our constructions rely on a simple, yet versatile and effective technique, called Decomposition-Extension. When adapting this technique to the Stern-KTX proof system (Stern ‘96 - Kawachi, Tanaka, Xagawa ‘08), we obtain a zero-knowledge proof of knowledge for the ISIS problem (in the infinity norm) with a very strong security guarantee: Breaking the protocol is as least as hard as solving the underlying ISIS instance. We then develop our technique to design the following lattice-based cryptographic constructions: \n \n \n \n- Efficient zero-knowledge proofs of plaintext knowledge with strong security guarantees \n \nfor 4 encryption schemes based on the Learning with Errors problem: Regev’s scheme (Regev ‘05); the Dual-Regev scheme (Gentry, Peikert, Vaikuntanathan ‘08); the PVW scheme (Peikert, Vaikuntanathan, Waters ‘08); and the GHV scheme (Gentry, Halevi, Vaikuntanathan ‘10). Our results immediately yield 4 lattice-based interactive encryption protocols that are secure under chosen ciphertext attacks. Previously, only zero-knowledge proofs of plaintext knowledge for Regev’s scheme were known, and they are relatively inefficient with rather weak security guarantees. \n \n \n \n- A lattice-based identity-based identification scheme relying on a weaker hardness assumption than in the previous works. Furthermore, we introduce an identity-based ring identification scheme based on the worst-case hardness of lattice problems. To the best of our knowledge, this is the first such scheme. \n \n \n \n- An improved lattice-based group signature scheme relying on relatively weak hardness assumptions, in which the signature size is logarithmic in the number of group users. Earlier lattice-based group signature schemes, which were published before 2013, rely on relatively weak hardness assumptions but have the undesirable property that the size of the signature is linear in the number of group users. A recent scheme (Laguillaumie, Langlois, Libert, Stehlé ‘13) achieves logarithmic signature size but it has to rely on relatively strong hardness assumptions. Our construction, thus, simultaneously achieves the good features of the existing schemes.
Abstract. We present a variant of Regev’s cryptosystem first presented in [Reg05], but with a new choice of parameters. By a recent classical re-duction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active ad-versaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper we show how one can, in zero-knowledge- prove knowledge of the plaintext contained in a given ciphertext from Regev’s original cryptosystem or our variant. The proof is of size only a constant times the size of the public key. 1
Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. \nIn this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. \nFirst, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. \nIn the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. \nIn the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.