Lattice based cryptography
- 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 . 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
Encryption
* GGH encryption scheme
* NTRUEncrypt
Signature
* GGH signature scheme
* NTRUSign
Hash function
* [http://www.cs.bris.ac.uk/~page/research/lash.html LASH-x] ( [http://eprint.iacr.org/2007/430.pdf 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.
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
