Lattice-based cryptography relies in great parts on the use of the Learning With Errors (LWE) problem as hardness foundation. This problem is at least as hard as standard worstcase
lattice problems, but the primitives based on it usually have big key sizes and slow algorithms. Polynomial/(dual/primal) Ring-LWE are variants of LWE which make use of extra algebraic structures in order to fix the above drawbacks. Polynomial-LWE is parameterized by a polynomial f , while (dual/primal) Ring-LWE is defined using the ring of integers of a number field. These problems, which we call algebraic, also enjoy reductions from worst-case lattice problems, but in their case, the lattices involved belong to diverse restricted classes.
In this thesis, we study relationships between algebraic variants of LWE. We first show that for many defining polynomials, there exist (non-uniform) reductions between
dual Ring-LWE, primal Ring-LWE and Polynomial-LWE that incur limited parameter losses. These results could be interpreted as a strong evidence that these problems are qualitatively equivalent.
Then we introduce a new algebraic variant of LWE, Middle-Product Learning With Errors (MPLWE). We show that this problem is at least as hard as Polynomial-LWE for many defining polynomials f. As a consequence, any cryptographic system based on MP-LWE remains secure as long as one of these Polynomial-LWE instances remains hard to solve.
Finally, we illustrate the cryptographic relevance of MP-LWE by building a public-key encryption scheme and a digital signature scheme that are proved secure under the MP-LWE hardness assumption.
Gratuit
Disciplines