In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.
Ideal lattices also form the basis for quantum computer attack resistant cryptography based on the Ring Learning with Errors. These cryptosystems are provably secure under the assumption that the shortest vector problem (SVP) is hard in these ideal lattices.
Introduction In general terms, ideal lattices are lattices corresponding to ideals in rings of the form for some irreducible polynomial of degree . All of the definitions of ideal lattices from prior work are instances of the following general notion: let be a ring whose additive group is isomorphic to (i.e., it is a free -module of rank ), and let be an additive isomorphism mapping to some lattice in an -dimensional real vector space (e.g., ). The family of ideal lattices for the ring under the embedding is the set of all lattices , where is an ideal in
Definition
Notation Let be a monic polynomial of degree , and consider the quotient ring .
Using the standard set of representatives , and identification of polynomials with vectors, the quotient ring is isomorphic (as an additive group) to the integer lattice , and any ideal defines a corresponding integer sublattice .
An ideal lattice is an integer lattice such that for some monic polynomial of degree and ideal .
Related properties It turns out that the relevant properties of for the resulting function to be collision resistant are: should be irreducible. the ring norm is not much bigger than for any polynomial , in a quantitative sense.
The first property implies that every ideal of the ring defines a full-rank lattice in and plays a fundamental role in proofs.
Lemma: Every ideal of , where is a monic, irreducible integer polynomial of degree , is isomorphic to a full-rank lattice in .
Ding and LindnerJintai Ding and Richard Lindner. Identifying Ideal Lattices. In Cryptology ePrint Archive, Report 2007/322, 2007. gave evidence that distinguishing ideal lattices from general ones can be done in polynomial time and showed that in practice randomly chosen lattices are never ideal. They only considered the case where the lattice has full rank, i.e. the basis consists of linear independent vectors. This is not a fundamental restriction because Lyubashevsky and Micciancio have shown that if a lattice is ideal with respect to an irreducible monic polynomial, then it has full rank, as given in the above lemma.
Algorithm: Identifying ideal lattices with full rank bases
Data: A full-rank basis Result: true and , if spans an ideal lattice with respect to , otherwise false.
Transform into HNF Calculate , , and Calculate the product if only the last column of P is non-zero then set to equal this column else return false if for then use CRT to find and else return false if then return true, else return false
where the matrix M is
Using this algorithm, it can be seen that many lattices are not ideal lattices. For example, let and , then
is ideal, but
is not. with is an example given by Lyubashevsky and Micciancio.
Performing the algorithm on it and referring to the basis as B, matrix B is already in Hermite Normal Form so the first step is not needed. The determinant is , the adjugate matrix
and finally, the product is
At this point the algorithm stops, because all but the last column of have to be zero if would span an ideal lattice.
Use in cryptography Micciancio introduced the class of structured cyclic lattices, which correspond to ideals in polynomial rings , and presented the first provably secure one-way function based on the worst-case hardness of the restriction of Poly(n)-SVP to cyclic lattices. (The problem γ-SVP consists in computing a non-zero vector of a given lattice, whose norm is no more than γ times larger than the norm of a shortest non-zero lattice vector.) At the same time, thanks to its algebraic structure, this one-way function enjoys high efficiency comparable to the NTRU scheme evaluation time and storage cost). Subsequently, Lyubashevsky and Micciancio and independently Peikert and Rosen showed how to modify Micciancio's function to construct an efficient and provably secure collision resistant hash function. For this, they introduced the more general class of ideal lattices, which correspond to ideals in polynomial rings . The collision resistance relies on the hardness of the restriction of Poly(n)-SVP to ideal lattices (called Poly(n)-Ideal-SVP). The average-case collision-finding problem is a natural computational problem called Ideal-SIS, which has been shown to be as hard as the worst-case instances of Ideal-SVP. Provably secure efficient signature schemes from ideal lattices have also been proposed, but constructing efficient provably secure public key encryption from ideal lattices was an interesting open problem.
The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding and provided a state of the art description of a quantum resistant key exchange using Ring LWE. The paper appeared in 2012 after a provisional patent application was filed in 2012. In 2014, Peikert presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional signal for rounding in Ding's construction is also utilized. A digital signature using the same concepts was done several years earlier by Vadim Lyubashevsky in, "Lattice Signatures Without Trapdoors." Together, the work of Peikert and Lyubashevsky provide a suite of Ring-LWE based quantum attack resistant algorithms with the same security reductions.
Efficient collision resistant hash functions The main usefulness of the ideal lattices in cryptography stems from the fact that very efficient and practical collision resistant hash functions can be built based on the hardness of finding an approximate shortest vector in such lattices. Independently constructed collision resistant hash functions by Peikert and Rosen, as well as Lyubashevsky and Micciancio, based on ideal lattices (a generalization of cyclic lattices), and provided a fast and practical implementation. These results paved the way for other efficient cryptographic constructions including identification schemes and signatures.
Lyubashevsky and Micciancio gave constructions of efficient collision resistant hash functions that can be proven secure based on worst case hardness of the shortest vector problem for ideal lattices. They defined hash function families as: Given a ring , where is a monic, irreducible polynomial of degree and is an integer of order roughly , generate random elements , where is a constant. The ordered -tuple determines the hash function. It will map elements in , where is a strategically chosen subset of , to . For an element , the hash is . Here the size of the key (the hash function) is , and the operation can be done in time by using the Fast Fourier Transform (FFT) , for appropriate choice of the polynomial . Since is a constant, hashing requires time . They proved that the hash function family is collision resistant by showing that if there is a polynomial-time algorithm that succeeds with non-negligible probability in finding such that , for a randomly chosen hash function , then a certain problem called the “shortest vector problem” is solvable in polynomial time for every ideal of the ring .
Based on the work of Lyubashevsky and Micciancio in 2006, Micciancio and Regev defined the following algorithm of hash functions based on ideal lattices:
Parameters: Integers with , and vector f . Key: vectors chosen independently and uniformly at random in . Hash function: given by .
Here are parameters, f is a vector in and is a block-matrix with structured blocks .
Finding short vectors in on the average (even with just inverse polynomial probability) is as hard as solving various lattice problems (such as approximate SVP and SIVP) in the worst case over ideal lattices, provided the vector f satisfies the following two properties: For any two unit vectors u, v, the vector [F∗u]v has small (say, polynomial in , typically norm. The polynomial is irreducible over the integers, i.e., it does not factor into the product of integer polynomials of smaller degree.
The first property is satisfied by the vector corresponding to circulant matrices, because all the coordinates of [F∗u]v are bounded by 1, and hence . However, the polynomial corresponding to is not irreducible because it factors into , and this is why collisions can be efficiently found. So, is not a good choice to get collision resistant hash functions, but many other choices are possible. For example, some choices of f for which both properties are satisfied (and therefore, result in collision resistant hash functions with worst-case security guarantees) are where is prime, and for equal to a power of 2.
Digital signatures Digital signatures schemes are among the most important cryptographic primitives. They can be obtained by using the one-way functions based on the worst-case hardness of lattice problems. However, they are impractical. A number of new digital signature schemes based on learning with errors, ring learning with errors and trapdoor lattices have been developed since the learning with errors problem was applied in a cryptographic context.
Their direct construction of digital signatures based on the complexity of approximating the shortest vector in ideal (e.g., cyclic) lattices. The scheme of Lyubashevsky and Micciancio has worst-case security guarantees based on ideal lattices and it is the most asymptotically efficient construction known to date, yielding signature generation and verification algorithms that run in almost linear time.
One of the main open problems that was raised by their work is constructing a one-time signature with similar efficiency, but based on a weaker hardness assumption. For instance, it would be great to provide a one-time signature with security based on the hardness of approximating the Shortest Vector Problem (SVP) (in ideal lattices) to within a factor of .
Their construction is based on a standard transformation from one-time signatures (i.e. signatures that allow to securely sign a single message) to general signature schemes, together with a novel construction of a lattice based one-time signature whose security is ultimately based on the worst-case hardness of approximating the shortest vector in all lattices corresponding to ideals in the ring for any irreducible polynomial .
Key-Generation Algorithm: Input: , irreducible polynomial of degree . Set , , For all positive , let the sets and be defined as: such that such that Choose uniformly random Pick a uniformly random string If then Set else Set to the position of the first 1 in the string end if Pick independently and uniformly at random from and respectively Signing Key: . Verification Key:
Signing Algorithm:
Input: Message such that ; signing key
Output:
Verification Algorithm:
Input: Message ; signature ; verification key
Output: “ACCEPT”, if and
“REJECT”, otherwise.
The SWIFFT hash function