In 1996 Hoffstein, Pipher ad Silverman presented NTRUEncrypt, which is to
date the fastest known lattice-based encryption scheme. Its moderate
key-sizes, excellent asymptotic performance and conjectured resistance to
quantum attacks make it a perfect candidate to succeed where factorization and discrete log fail. Unfortunately, no security proof has been produced for NTRUEncrypt nor for its signature counterpart NTRUSign.
In 2013 Stehle and Steinfield proposed to apply some mild modification to
the encryption and signature scheme to make them provably secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. In particular they showed that if the secret key polynomials of the encryption scheme are chosen from discrete Gaussians, then the public key, i.e their ratio, is statistically indistinguishable from uniform. The security will then follow from the hardness of the R-LWE problem.The aim of this thesis is to present Stehle's and Steinfield's work in a slightly more accessi-ble form, providing some more background and details in some points.
In 1996 Hoffstein, Pipher ad Silverman presented NTRUEncrypt, which is to
date the fastest known lattice-based encryption scheme. Its moderate
key-sizes, excellent asymptotic performance and conjectured resistance to
quantum attacks make it a perfect candidate to succeed where factorization and discrete log fail. Unfortunately, no security proof has been produced for NTRUEncrypt nor for its signature counterpart NTRUSign.
In 2013 Stehle and Steinfield proposed to apply some mild modification to
the encryption and signature scheme to make them provably secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. In particular they showed that if the secret key polynomials of the encryption scheme are chosen from discrete Gaussians, then the public key, i.e their ratio, is statistically indistinguishable from uniform. The security will then follow from the hardness of the R-LWE problem.The aim of this thesis is to present Stehle's and Steinfield's work in a slightly more accessi-ble form, providing some more background and details in some points.
Since the presentation of NTRU public-key cryptosystem by Hoffstein, Pipher and Silverman, its favorable properties, such as easily created keys, high speed, excellent performance and conjectured resistance to quantum computers, have made it to be of great use. This paper proposes an enhanced scheme based on the hard learning with error over ring (R-LWE) problem to improve the security of the modified NTRUEncrypt presented by Stehle and Steinfled. We used part of the padding ideas of Fujisaki and Okamoto to obtain this scheme. It is semantically secure in strong sense of indistinguishability against adaptive chosen-ciphertext attacks in the random oracle model assuming the quantum hardness of standard worst-case problem over ideal lattices. It is also possible to arbitrarily decrease the error probability, and even to eliminate it completely. We gave the detailed analysis using the known results from classic works. Furthermore, this scheme owns many advantages such as the uniformity of public key, usual assumptions and the freedom for coding messages.
Jarvis and Nevins presented ETRU in 2013 which has applausive performance with moderate key-sizes and conjectured resistance to quantum computers. ETRU, as an efficient NTRUEncrypt-like cryptosystem, is over the ring of Eisenstein integers that is faster with smaller keys for the same or better level of security than does NTRUEncrypt which is a desirable alternative to public-key cryptosystems based on factorisation and discrete logarithm problem. However, because of its construction, doubts have regularly arisen on its security. In this paper, we propose how to modify ETRU to make it provably secure, under our modified assumption of quantum hardness of standard worst-case lattice problems, restricted to extended ideal lattices related to some extensions of cyclotomic fields structures. We describe the structure of all generated polynomial rings of quotient over direct product of Dedekind domains Z and Z[ζ3], where ζ3 is complex cube root of unity. We give a detailed description to show that if the private key polynomials of the ETRU are selected from direct product of some Dedekind domains using discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. The security then proves for our main system from the already proven hardness of the R-SIS and R-LWE problems by their extensions.
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.
This dissertation examines the NTRU cryptosystem, one of the earliest and most updated lattice-based public key cryptographic schemes. Presented in 1996 by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, NTRU was conceived as an alternative to classical cryptographic protocols such as the RSA cryptosystem and Diffie–Hellman systems, whose security is based upon the computational intractability of integer factorisation and discrete logarithm problems. Although these problems remain infeasible for classical computation, the coming of sufficiently powerful quantum computers would render such schemes helpless through the application of the already existing Shor’s algorithm. By contrast, NTRU derives its security from hard problems in lattice theory, for which no efficient quantum algorithms are currently known, thereby establishing it as one of the foremost candidates for secure communication in the post-quantum era. The first chapter begins with a rigorous introduction to the theory of lattices, displaying their main algebraic and geometric properties together with several fundamental computational problems, most notably the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). The computational hardness and infeasibility of these problems constitutes the mathematical foundation upon which NTRU is built. Particular attention is given to the Lenstra–Lenstra–Lovasz (LLL) lattice reduc- ´ tion algorithm. Its theoretical framework, geometric interpretation, and algorithmic behaviour are examined in detail, with special emphasis on its ability to construct reduced lattice bases that mirror some of the properties given by orthogonality, while remaining computationally feasible. The dissertation further explores the decisive role played by lattice reduction techniques in cryptography, both as practical tools for addressing difficult lattice problems and as powerful methods in the analysis of cryptosystems. Following this necessary theoretical development, in the second chapter the NTRU public key cryptosystem is presented and described in detail. The processes of key generation, encryption, and decryption are presented alongside the correct selection criteria of the system’s parameters, required to guarantee both correctness and security. Finally, the third chapter examines the security issues of NTRU through a range of attack models, including conventional attacks and, mainly, sophisticated attacks based on lattice reduction methods, thereby illustrating the deep connection between the security of NTRU and the intrinsic difficulty of solving lattice problems efficiently. Taken together, this dissertation presents a full guide of the mathematical structures underlying the NTRU cryptosystem, highlighting the fundamental role of algebraic tools such as lattice theory in the construction of cryptographic systems capable of withstanding the paradigm shift that is rapidly approaching with the rise of quantum computation.
One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.
Authentication has been adopted in many areas, but most of these authentication schemes are built using traditional cryptographic primitives. It is widely believed that such primitives are not resistant to quantum algorithms. To deal with those quantum attacks, lattice-based cryptography was introduced by Ajtai in 1996. To the best of our knowledge, the existing lattice-based authentication schemes are based on a lattice-based public key encryption called NTRU: a ring-based public key cryptosystem, proposed by Hoffstein, Pipher, and Silverman in 1998. However, these schemes only support the case of a single user. In view of the aforementioned issue, we propose the first lattice-based group authentication scheme. The proposed scheme is secure against replay attacks and man-in-the-middle attacks. Moreover, compared with the existing lattice-based authentication schemes, ours provides the most efficient method to agree upon a session key among a group of users after mutual authentication.