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 Z [ x ] / ⟨ f ⟩ {\displaystyle \mathbb {Z} [x]/\langle f\rangle } for some irreducible polynomial f {\displaystyle f} of degree n {\displaystyle n} . All of the definitions of ideal lattices from prior work are instances of the following general notion: let R {\displaystyle R} be a ring whose additive group is isomorphic to Z n {\displaystyle \mathbb {Z} ^{n}} (i.e., it is a free Z {\displaystyle \mathbb {Z} } -module of rank n {\displaystyle n} ), and let σ {\displaystyle \sigma } be an additive isomorphism mapping R {\displaystyle R} to some lattice σ ( R ) {\displaystyle \sigma (R)} in an n {\displaystyle n} -dimensional real vector space (e.g., R n {\displaystyle \mathbb {R} ^{n}} ). The family of ideal lattices for the ring R {\displaystyle R} under the embedding σ {\displaystyle \sigma } is the set of all lattices σ ( I ) {\displaystyle \sigma (I)} , where I {\displaystyle I} is an ideal in R . {\displaystyle R.}
Definition
Notation Let f ∈ Z [ x ] {\displaystyle f\in \mathbb {Z} [x]} be a monic polynomial of degree n {\displaystyle n} , and consider the quotient ring Z [ x ] / ⟨ f ⟩ {\displaystyle \mathbb {Z} [x]/\langle f\rangle } . Using the standard set of representatives { ( g mod f ) : g ∈ Z [ x ] } {\displaystyle \lbrace (g{\bmod {f}}):g\in \mathbb {Z} [x]\rbrace } , and identification of polynomials with vectors, the quotient ring Z [ x ] / ⟨ f ⟩ {\displaystyle \mathbb {Z} [x]/\langle f\rangle } is isomorphic (as an additive group) to the integer lattice Z n {\displaystyle \mathbb {Z} ^{n}} , and any ideal I ⊆ Z [ x ] / ⟨ f ⟩ {\displaystyle I\subseteq \mathbb {Z} [x]/\langle f\rangle } defines a corresponding integer sublattice L ( I ) ⊆ Z n {\displaystyle {\mathcal {L}}(I)\subseteq \mathbb {Z} ^{n}} . An ideal lattice is an integer lattice L ( B ) ⊆ Z n {\displaystyle {\mathcal {L}}(B)\subseteq \mathbb {Z} ^{n}} such that B = { g mod f : g ∈ I } {\displaystyle B=\lbrace g{\bmod {f}}:g\in I\rbrace } for some monic polynomial f {\displaystyle f} of degree n {\displaystyle n} and ideal I ⊆ Z [ x ] / ⟨ f ⟩ {\displaystyle I\subseteq \mathbb {Z} [x]/\langle f\rangle } .
Related properties It turns out that the relevant properties of f {\displaystyle f} for the resulting function to be collision resistant are:
… excerpt ends here. Continue reading the full article.
