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 Lindner 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.