Lattice based cryptography
Encyclopedia
Lattice-based cryptography is the generic term for asymmetric cryptographic primitive
s based on lattices
.
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.
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.
. Many of them are quite efficient, and some even compete with the best known alternatives; they are typically quite simple to implement; and are all believed to be secure against attacks using conventional or quantum computers.
In terms of security, lattice-based cryptographic constructions can be divided into two types. The first includes practical proposals, which are typically very efficient, but often lack a supporting proof of security. The second type admits strong provable security guarantees based on the worst-case hardness of lattice problems, but only a few of them are sufficiently efficient to be used in practice.
The importance of the worst-case security guarantee is twofold. First, it assures us that attacks on the cryptographic construction are likely to be effective only for small choices of parameters and not asymptotically. In other words, it assures us that there are no fundamental flaws in the design of our cryptographic construction. In fact, in some cases, the worst-case security guarantee can even guide us in making design decisions. Second, in principle the worst-case security guarantee can help us in choosing concrete parameters for the cryptosystem, although in practice this leads to what seems like overly conservative estimates and one often sets the parameters based on the best known attacks.
for typical approximation factors, because of their periodic structure, and because the Fourier transform
, which is usually exploited in quantum algorithms, is tightly related to the notion of lattice duality.
Attempts to solve lattice problems by quantum algorithms have been made since Shor’s
discovery of the quantum factoring algorithm in the mid-1990s, but have so far met with little success if any at all.
Cryptographic primitive
Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build computer security systems. These routines include, but are not limited to, one-way hash functions and encryption functions.- Rationale :...
s based on lattices
Lattice (group)
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 can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
.
History
Lattices were first studied by mathematicians Joseph Louis LagrangeJoseph Louis Lagrange
Joseph-Louis Lagrange , born Giuseppe Lodovico Lagrangia, was a mathematician and astronomer, who was born in Turin, Piedmont, lived part of his life in Prussia and part in France, making significant contributions to all fields of analysis, to number theory, and to classical and celestial mechanics...
and Carl Friedrich Gauss
Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...
. Lattices have been used recently in computer algorithms and in cryptanalysis. In 1996, Miklós Ajtai
Miklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
showed in a seminal result the use of lattices as a cryptography primitive.
Mathematical background
A latticeLattice (group)
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 can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
L is a set of points in the n-dimensional Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
Rn with a strong periodicity property. A basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
of L is a set of vectors such that any element of L is uniquely represented as their linear combination
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
with integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
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
Lattice problems
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...
are usually hard to solve unless one has extra information. Mathematical problems based on lattices are the Shortest Vector Problem
Lattice problems
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...
(SVP) and the Closest Vector Problem
Lattice problems
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...
(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
Lattice reduction
In mathematics, the goal of lattice basis reduction is given an integer lattice basis as input, to find a basis with short, nearly orthogonal vectors. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.-Nearly...
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
Lenstra–Lenstra–Lovász lattice basis reduction algorithm
The LLL-reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982, see...
algorithm.
Lattice-based cryptosystems
In 2009, Craig Gentry using lattice-based cryptography showed the first fully homomorphic encryption scheme as announced by IBM on June 25. His scheme supports evaluations of arbitrary depth circuits.Hash function
- LASH-x (broken, see Cryptanalysis)
Security issues
Lattice-based cryptographic constructions hold a great promise for post-quantum cryptographyPost-quantum cryptography
Post-quantum cryptography refers to research on cryptographic primitives that are not breakable using quantum computers...
. Many of them are quite efficient, and some even compete with the best known alternatives; they are typically quite simple to implement; and are all believed to be secure against attacks using conventional or quantum computers.
In terms of security, lattice-based cryptographic constructions can be divided into two types. The first includes practical proposals, which are typically very efficient, but often lack a supporting proof of security. The second type admits strong provable security guarantees based on the worst-case hardness of lattice problems, but only a few of them are sufficiently efficient to be used in practice.
Worst-case hardness
Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with some small non-negligible probability) is provably at least as hard as solving several lattice problems (approximately, within polynomial factors) in the worst case. In other words, breaking the cryptographic construction implies an efficient algorithm for solving any instance of some underlying lattice problem. In most cases, the underlying problem is that of approximating lattice problems such as SVP to within polynomial factors, which is conjectured to be a hard problem. Such a strong security guarantee is one of the distinguishing features of lattice-based cryptography.The importance of the worst-case security guarantee is twofold. First, it assures us that attacks on the cryptographic construction are likely to be effective only for small choices of parameters and not asymptotically. In other words, it assures us that there are no fundamental flaws in the design of our cryptographic construction. In fact, in some cases, the worst-case security guarantee can even guide us in making design decisions. Second, in principle the worst-case security guarantee can help us in choosing concrete parameters for the cryptosystem, although in practice this leads to what seems like overly conservative estimates and one often sets the parameters based on the best known attacks.
Quantum and lattices
Lattice problems are typically quite hard. The best known algorithms either run in exponential time, or provide quite bad approximation ratios. The field of lattice-based cryptography has been developed based on the assumption that lattice problems are hard. There are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best known classical (i.e., non-quantum) algorithms. This is despite the fact that lattice problems seem like a natural candidate to attempt to solve using quantum algorithms: because they are believed not to be NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
for typical approximation factors, because of their periodic structure, and because the Fourier transform
Fourier transform
In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
, which is usually exploited in quantum algorithms, is tightly related to the notion of lattice duality.
Attempts to solve lattice problems by quantum algorithms have been made since Shor’s
Shor's algorithm
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...
discovery of the quantum factoring algorithm in the mid-1990s, but have so far met with little success if any at all.