Ideal lattice

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices.[1] 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.[2] These cryptosystems are provably secure under the assumption that the shortest vector problem (SVP) is hard in these ideal lattices.

  1. ^ Lyubashevsky, Vadim (2008). "Lattice-Based Identification Schemes Secure Under Active Attacks" (PDF). Public Key Cryptography – PKC 2008. Lecture Notes in Computer Science. Vol. 4939. pp. 162–179. doi:10.1007/978-3-540-78440-1_10. ISBN 978-3-540-78439-5.
  2. ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "On Ideal Lattices and Learning with Errors over Rings". In Gilbert, Henri (ed.). Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. CiteSeerX 10.1.1.297.6108. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.