Lattice-based Cryptology - Coursework Example

Running Head: TITLE OF THE WORK Title of the work Name Name of Instructor Subject Institution Date Abstract The study of lattices has been studied way back in the 19 century. They form an important basis in solving mathematical problems in encryption. In the sphere of cryptosystems, there is usually an underlying problem that proves to be difficult to solve. Very few studies have suggested a proof in solving these hard mathematical problems by breaking the cryptosystems. Some of the examples that exist include; the discrete logarithmic problem, integer factorization problem and the discrete logarithmic problem. Though there exist several difficult mathematical problems, which may be employed in the aspect of cryptography. The outstanding problems that this paper discusses are; the shortest vector problem and closest vector problems. The paper further discusses their application in cryptography. Moreover, the presence of gap phenomena is also discussed as concerned with the closest vector problem and shortest vector problem. Introduction Lattices at first were investigated by mathematicians like Gauss, Lagrange, and Minkowski [19]. Later on, a number of individuals have brought out the relationship of lattices in relation to computer science. Lattices are recognized as algorithm tools that aid to solve various problems. This has found a basis in the cryptanalysis and, from the computational point of view. In addition, the lattices have also been seen to possess unique properties. Lattice finds its application in the field of computer science, where there are considered class of optimization problems. They are termed as one of the powerful mathematical objects that are used in solving various polynomial factorizations over rational, computer science, Diophantine approximation and integer programming effectively. In this lattice discussion, the conjectured intractability would be focussed on the concentration of lattice based cryptosystems which are secured [12]. Currently they find their application on the potential basis of the cryptographic functions design. Lattices are divided into two classes namely; a subset sum problem whereby there exist a set of two equal for instance, S=K, it follows that a subset of one number whose sum is equal to k has to be found. This is mostly applicable in a knapsack problem (Barnard, 1993). Another subset entails finding the points in a vector space that are close to the vectors which are embedded in the lattice. At times it may entail, finding short vectors embedded in a lattice. This is elaborated in an example given in Ajtai and Dwork method [8] The lattice problem exhibited in the computational analysis include; CVP and SVP, which is the shortest vector problem. For instance, it may be required to get the shortest non zero of a lattice vector. Definition A lattice may be defined when we have a set of matrix that is ordered in the formb1, b2, ...b3] in a given n linear independent. The column vector assumes the form IRm. All the integral set linear combination gives the vector, L=L (B) :={ibi│ti=bi . This lattice is usually generalised by a base B. It takes a dimension of L: =n. For cases whereby n=m, it is defined as full dimensional lattice [10]. Having a lattice of sub≤L with a dim L sub=dim L, it gives a sub lattice of L. Therefore, the sub lattice of m defines the integer lattice. The study of the lattice which entails the (SVP) and (CVP), have found their interest way back for about a hundred years ago. They have been used in solving the intrinsic mathematics problems, cryptography, and also to the study of application of pure science. Studying lattices theoretically is referred to as the geometry of numbers. Lattice reduction method finds its application in determining the shortest or the closest lattice vectors. The usage of lattice reduction has found its application in various fields such as the cryptography, computer algebra, and applied mathematics in discrete mathematics. Lattice problems In the mathematical aspect of a lattice problem, a lattice is considered to be a set of points Rn, with the n taking a Euclidean space. In this case, we consider `L’ to be considered as a set of vectors and, it can therefore be represented as a linear combination of the elements having integer coefficients. When the value of n takes a value of at least 2, an infinitely base is exhibited. A cryptographic system may be generated with this mathematical problem. At times, sufficient information does not exist. This makes solving these problems very cumbersome. In trying to solve the lattice based models that may be employed, which include the; Closest vector problem (CVP) and the shortest vector problem (SVP). While trying to solve these problems, lattice basis reduction is employed which tries to ease solving procedures of CVP and SVP. The Lenstra, Lenstra, and LovasZ (LLL) algorithms tend give a good basis in the reduction algorithm of the Lattice based crypto systems. The scheme of fully homorphic encryption scheme was first invented by Craig Gentry of IBM with lattice based Cryptography [16]. Arbitrary depth circuits are supported by this scheme. Lattice cryptosystems are mainly based NP complete problems and, the security mostly relies on finding the solutions which could be approximate to lattice problems. Some of the encryption that exists includes the GGH encryption scheme. The Goldreich Goldwasser –Halevi is an asymmetric based cryptosystem in lattices. The scheme makes use of the CVP and believes that, it could be a hard problem. It was published in 1997 and, uses a one way function which depends on the lattice reduction [3]. It has also the digital signature scheme which was also published in 1997. Its proposal was done way back in 1995 that were based on a lattice, by solving the closest vector problem. It is with this analysis that gives the basis of algorithm NTRU sign signature There is also NTRU encrypt. It is a NTRU encryption algorithm which is alternative to the ECC and RSA. This depends on a given SVP in a given lattice. All the operations find themselves being truncated polynomial ring based on the objects with all the polynomials with convolution multiplication, having degree being at most N-1 and integer co efficient [8]. In addition, the NTRU sign is a digital signature algorithm based on the public key cryptography. This means that, the GGH signature scheme is in a 2N dimensional space, that involves mapping a message to a random point [5] It also follows that in the modulo reduction of the polynomials, various integers may be obtained from the reduction of modulo of the coefficients of various polynomials. For instance, if we tend to reduce the mod 16 to be -3ai Read More

For instance, it may be required to get the shortest non zero of a lattice vector. Definition A lattice may be defined when we have a set of matrix that is ordered in the formb1, b2, .b3] in a given n linear independent. The column vector assumes the form IRm. All the integral set linear combination gives the vector, L=L (B) :={ibi│ti=bi . This lattice is usually generalised by a base B. It takes a dimension of L: =n. For cases whereby n=m, it is defined as full dimensional lattice [10].

Having a lattice of sub≤L with a dim L sub=dim L, it gives a sub lattice of L. Therefore, the sub lattice of m defines the integer lattice. The study of the lattice which entails the (SVP) and (CVP), have found their interest way back for about a hundred years ago. They have been used in solving the intrinsic mathematics problems, cryptography, and also to the study of application of pure science. Studying lattices theoretically is referred to as the geometry of numbers. Lattice reduction method finds its application in determining the shortest or the closest lattice vectors.

The usage of lattice reduction has found its application in various fields such as the cryptography, computer algebra, and applied mathematics in discrete mathematics. Lattice problems In the mathematical aspect of a lattice problem, a lattice is considered to be a set of points Rn, with the n taking a Euclidean space. In this case, we consider `L’ to be considered as a set of vectors and, it can therefore be represented as a linear combination of the elements having integer coefficients. When the value of n takes a value of at least 2, an infinitely base is exhibited.

A cryptographic system may be generated with this mathematical problem. At times, sufficient information does not exist. This makes solving these problems very cumbersome. In trying to solve the lattice based models that may be employed, which include the; Closest vector problem (CVP) and the shortest vector problem (SVP). While trying to solve these problems, lattice basis reduction is employed which tries to ease solving procedures of CVP and SVP. The Lenstra, Lenstra, and LovasZ (LLL) algorithms tend give a good basis in the reduction algorithm of the Lattice based crypto systems.

The scheme of fully homorphic encryption scheme was first invented by Craig Gentry of IBM with lattice based Cryptography [16]. Arbitrary depth circuits are supported by this scheme. Lattice cryptosystems are mainly based NP complete problems and, the security mostly relies on finding the solutions which could be approximate to lattice problems. Some of the encryption that exists includes the GGH encryption scheme. The Goldreich Goldwasser –Halevi is an asymmetric based cryptosystem in lattices.

The scheme makes use of the CVP and believes that, it could be a hard problem. It was published in 1997 and, uses a one way function which depends on the lattice reduction [3]. It has also the digital signature scheme which was also published in 1997. Its proposal was done way back in 1995 that were based on a lattice, by solving the closest vector problem. It is with this analysis that gives the basis of algorithm NTRU sign signature There is also NTRU encrypt. It is a NTRU encryption algorithm which is alternative to the ECC and RSA.

This depends on a given SVP in a given lattice. All the operations find themselves being truncated polynomial ring based on the objects with all the polynomials with convolution multiplication, having degree being at most N-1 and integer co efficient [8]. In addition, the NTRU sign is a digital signature algorithm based on the public key cryptography. This means that, the GGH signature scheme is in a 2N dimensional space, that involves mapping a message to a random point [5] It also follows that in the modulo reduction of the polynomials, various integers may be obtained from the reduction of modulo of the coefficients of various polynomials.

For instance, if we tend to reduce the mod 16 to be -3ai

Read More