Lattice based cryptography

Lattice based cryptography

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


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 different 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

* GGH encryption scheme
* NTRUEncrypt

* GGH signature scheme
* NTRUSign

Hash function
* [ LASH-x] ( [ broken] )


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

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Lattice problem — In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice based cryptosystems. For applications in such cryptosystems,… …   Wikipedia

  • Lattice (group) — A lattice in the Euclidean plane. In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn …   Wikipedia

  • Optical lattice — Simulation of an optical lattice potential. An optical lattice is formed by the interference of counter propagating laser beams, creating a spatially periodic polarization pattern. The resulting periodic potential may trap neutral atoms via the… …   Wikipedia

  • NTRU — is an asymmetric (public/private key) cryptosystem. It has two characteristics that make it interesting as an alternative to RSA and Elliptic Curve Cryptography; speed and quantum computing resistance. There are two NTRU based algorithms:… …   Wikipedia

  • NTRUEncrypt — (аббревиатура Nth degree TRUncated polynomial ring или Number Theorists aRe Us)  это криптографическая система с открытым ключом, ранее называвшаяся NTRU. Криптосистема NTRUEncrypt, основанная на решётчатой криптосистеме (англ.),… …   Википедия

  • NTRUEncrypt — The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is a lattice based alternative to RSA and ECC and is based on the shortest vector problem in a lattice (i.e. is not breakable using quantum computers).… …   Wikipedia

  • IEEE P1363 — is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public key cryptography. It includes specifications for: Traditional public key cryptography (IEEE Std 1363 2000 and 1363a 2004) Lattice based public key… …   Wikipedia

  • NTRUSign — NTRUSign, also known as the NTRU Signature Algorithm, is a public key cryptography digital signature algorithm based on the GGH signature scheme. It was first presented at the rump session of Asiacrypt 2001 and published in peer reviewed form at… …   Wikipedia

  • Gitter (Mathematik) — Ausschnitt eines Gitters. Die blauen Punkte gehören zum Gitter. In der Mathematik sind Gitter in gewissem Sinne regelmäßige Mengen. Sie finden u. a. Anwendung in der Gruppentheorie, der Geometrie und bei Approximationsfragestellungen. Die… …   Deutsch Wikipedia

  • Algebraic torus — In mathematics, an algebraic torus is a type of commutative affine algebraic group. These groups were named by analogy with the theory of tori in Lie group theory (see maximal torus). The theory of tori is in some sense opposite to that of… …   Wikipedia