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.
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.
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.
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.
Since the introduction of the ring learning with errors (R-LWE) by Lyubashevsky, Peikert and Regev, many efficient and secure applications were founded in cryptography. In this paper, we mainly present an efficient public-key encryption scheme based on the R-LWE assumption. It is very simple to describe and analyze. As well as it can achieve security against certain key-dependent message (KDM) attacks. Namely, this efficient encryption scheme can securely encrypt its own secret key. The security of this scheme follows from the already proven hardness of the R-LWE problem since the R-LWE assumption is reducible to worst-case problems on the ideal lattice. Besides, the scheme enjoys a high level efficiency and low cost since the operations of the scheme are very simple and fast. The cost of both the encryption and decryption is only polylog(n) bit per message symbol.
The only known threat to some symmetric cryptographic schemes like DES is Grover’s algorithm that proposes a square root speed-up over classical brute force algorithms. NIST [14] points out that if the key sizes are sufficient, symmetric cryptographic schemes (specifically the Advanced Encryption Standard-AES) are resistant to quantum computers. The development of quantum computer is on full pace, hopefully it might be available in a decade. Thus, it is necessary to develop efficient quantum secure public key cryptosystems to provide safe key exchange in quantum era. In this paper we presented an efficient implementation of a Ring-Learning with errors public key cryptosystem whose security is based on intractability of hard problem on lattices. And comparative analysis of proposed cryptosystem with RSA, ECDH and LWE based key exchange protocols is presented.
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.
Identity-based proxy re-encryption (IB-PRE) is a kind of public key cryptography that allows a proxy to convert the ciphertext based on Alice’s identity into another ciphertext of the same message for Bob. It has important applications in cloud computing, distributed systems and secure e-mail forwarding. So far, the existing lattice-based IB-PRE schemes are designed on the general lattice and their security is based on the learning with errors (LWE) assumption. In this paper, we propose an IB-PRE scheme over NTRU lattices with the desirable properties of anonymity, unidirectionality, backward collusion safeness and multi-hop. Our IB-PRE scheme is provable secure under adaptive chosen-plaintext and adaptive chosen-identity attacks. And, in the random oracle model, the security of our scheme is based on the decisional Ring-LWE assumption. Besides, the key and ciphertext sizes of our IB-PRE scheme are short, only one or two ring elements, and our scheme could encrypt n bits in each encryption process.