They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient.
Ideal lattices also form the basis for quantum computer attack resistant cryptography based on the Ring Learning with Errors.
[2] These cryptosystems are provably secure under the assumption that the shortest vector problem (SVP) is hard in these ideal lattices.
This is not a fundamental restriction because Lyubashevsky and Micciancio have shown that if a lattice is ideal with respect to an irreducible monic polynomial, then it has full rank, as given in the above lemma.
Algorithm: Identifying ideal lattices with full rank bases Data: A full-rank basis
[5] Performing the algorithm on it and referring to the basis as B, matrix B is already in Hermite Normal Form so the first step is not needed.
Micciancio[6] introduced the class of structured cyclic lattices, which correspond to ideals in polynomial rings
, and presented the first provably secure one-way function based on the worst-case hardness of the restriction of Poly(n)-SVP to cyclic lattices.
At the same time, thanks to its algebraic structure, this one-way function enjoys high efficiency comparable to the NTRU scheme
"[11] Together, the work of Peikert and Lyubashevsky provide a suite of Ring-LWE based quantum attack resistant algorithms with the same security reductions.
[3] These results paved the way for other efficient cryptographic constructions including identification schemes and signatures.
Lyubashevsky and Micciancio[5] gave constructions of efficient collision resistant hash functions that can be proven secure based on worst case hardness of the shortest vector problem for ideal lattices.
They proved that the hash function family is collision resistant by showing that if there is a polynomial-time algorithm that succeeds with non-negligible probability in finding
on the average (even with just inverse polynomial probability) is as hard as solving various lattice problems (such as approximate SVP and SIVP) in the worst case over ideal lattices, provided the vector f satisfies the following two properties: The first property is satisfied by the vector
For example, some choices of f for which both properties are satisfied (and therefore, result in collision resistant hash functions with worst-case security guarantees) are Digital signatures schemes are among the most important cryptographic primitives.
They can be obtained by using the one-way functions based on the worst-case hardness of lattice problems.
Their direct construction of digital signatures based on the complexity of approximating the shortest vector in ideal (e.g., cyclic) lattices.
[8] The scheme of Lyubashevsky and Micciancio[8] has worst-case security guarantees based on ideal lattices and it is the most asymptotically efficient construction known to date, yielding signature generation and verification algorithms that run in almost linear time.
[12] One of the main open problems that was raised by their work is constructing a one-time signature with similar efficiency, but based on a weaker hardness assumption.
For instance, it would be great to provide a one-time signature with security based on the hardness of approximating the Shortest Vector Problem (SVP) (in ideal lattices) to within a factor of
Analogously to standard LWE, the goal of the attacker is to distinguish arbitrarily many (independent) ‘random noisy ring equations’ from truly uniform ones.
In 2013, Guneysu, Lyubashevsky, and Poppleman proposed a digital signature scheme based on the Ring Learning with Errors problem.
[14] In 2014, Peikert presented a Ring Learning with Errors Key Exchange (RLWE-KEX) in his paper, "Lattice Cryptography for the Internet.
[15] Stehle, Steinfeld, Tanaka and Xagawa[16] defined a structured variant of LWE problem (Ideal-LWE) to describe an efficient public key encryption scheme based on the worst case hardness of the approximate SVP in ideal lattices.
This is the first CPA-secure public key encryption scheme whose security relies on the hardness of the worst-case instances of
Most of the cryptosystems based on general lattices rely on the average-case hardness of the Learning with errors (LWE).
They needed to introduce some techniques to circumvent two main difficulties that arise from the restriction to ideal lattices.
Firstly, the previous cryptosystems based on unstructured lattices all make use of Regev's worst-case to average-case classical reduction from Bounded Distance Decoding problem (BDD) to LWE (this is the classical step in the quantum reduction from SVP to LWE).
Because they did not obtain the hardness of the decisional variant, they used a generic hardcore function to derive pseudorandom bits for encryption.
In 2009, Gentry[19] proposed the first solution to the problem of constructing a fully homomorphic encryption scheme.