Lattice-based cryptography

Lattice based Cryptography is the generic term for asymmetric cryptographic primitives based on lattice.

History

Lattice have first been discovered by mathematicans Lagrange and Gauss. Lattice have been used laterly in computer algorithms and in cryptanalysis. In 1996 Atjai showed in a seminal result the use of lattices as a cryptography primitive.

Mathematical Background

A lattice (group) is a set of points in a n-dimensional space with a periodic structure. It forms a sub vector space of the vector space $R^{n}$ . A basis of a lattice is a set of linear independened vectors. A lattice can have two diffrent basis.

Mathematical problems are used to construct a cryptography system. These problems are usually hard to solve unless you have extra informations. Mathematical problems based on lattice 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 normaly hard to solve. There are algorithms to solve this 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 mathematical problemsets would be solved. A good basis reduction algorithm is the LLL algorithm.

Lattice based Cryptosystems

Encryption

Signature

Hash function

|LASHx (|broken)

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.
Oded Regev. Lattice-based cryptography. In Advances in cryptology (CRYPTO), pages 131–141, 2006.