Lattice-based cryptography

Lattice-based cryptography is the generic term for asymmetric cryptographic primitives based on lattices.

History

Lattices were first studied by mathematicians Joseph Louis Lagrange and Carl Friedrich Gauss. Lattices have been used recently in computer algorithms and in cryptanalysis. In 1996 Miklós Ajtai showed in a seminal result the use of lattices as a cryptography primitive.

Mathematical background

A lattice is a set of points in a n-dimensional space with a periodic structure. It forms a vector subspace of the vector space Rⁿ. A basis of a lattice is a set of linearly independent vectors. A lattice can have many different bases.

Mathematical problems are used to construct a cryptography system. These problems are usually hard to solve unless one has extra information. Mathematical problems based on lattices are the Shortest Vector Problem(SVP) and the Closest Vector Problem(CVP). SVP: Given a basis of a lattice, find the shortest vector in the lattice. CVP: Given a basis of a lattice and a vector not in the lattice, find the lattice vector with the least distance to the first vector. These problems are normally hard to solve. There are algorithms to solve these problems with a good basis.

Lattice basis reduction is a transformation of an integer lattice basis in order to find a basis with short, nearly orthogonal vectors. If one can compute such a lattice basis, the CVP and SVP problems are easy to solve. A good basis reduction algorithm is the LLL algorithm.

Lattice-based cryptosystems

Encryption

• GGH encryption scheme
• NTRUEncrypt

Signature

• GGH signature scheme
• NTRUSign

Hash function

• LASH-x ([1])

See also

• Lattice problems
• Learning with errors

Bibliography

• Oded Goldreich, Shafi Goldwasser, and Shai Halevi. "Public-key cryptosystems from lattice reduction problems". In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.
• Phong Q. Nguyen. "Cryptanalysis of the Goldreich–Goldwasser–Halevi cryptosystem from crypto ’97". In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.
• Chris Peikert, “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,” in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333–342, http://portal.acm.org/citation.cfm?id=1536414.1536461.
• Oded Regev. Lattice-based cryptography. In Advances in cryptology (CRYPTO), pages 131–141, 2006.