Mathematical Background
A lattice L is a set of points in the n-dimensional Euclidean space Rn with a strong periodicity property. A basis of L is a set of vectors such that any element of L is uniquely represented as their linear combination with integer coefficients. When n is at least 2, each lattice has infinitely 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.
Read more about this topic: Lattice-based Cryptography
Famous quotes containing the words mathematical and/or background:
“As we speak of poetical beauty, so ought we to speak of mathematical beauty and medical beauty. But we do not do so; and that reason is that we know well what is the object of mathematics, and that it consists in proofs, and what is the object of medicine, and that it consists in healing. But we do not know in what grace consists, which is the object of poetry.”
—Blaise Pascal (1623–1662)
“They were more than hostile. In the first place, I was a south Georgian and I was looked upon as a fiscal conservative, and the Atlanta newspapers quite erroneously, because they didn’t know anything about me or my background here in Plains, decided that I was also a racial conservative.”
—Jimmy Carter (James Earl Carter, Jr.)