Sur des variantes algébriques du problème Learning With Errors

Lattice-based cryptography relies in great parts on the use of the Learning With Errors (LWE) problemas hardness foundation. This problem is at least as hard as standard worst-case lattice problems, but the primitives based on it usually have big key sizes and slow algorithms. Polynomial Learning With Errors (PLWE), dual Ring Learning With Errors (dual-RLWE) and primal Ring Learning WithErrors (primal-RLWE) are variants of LWE which make use of extra algebraic structures in order to fix the above drawbacks. The PLWE problem is parameterized by a polynomial f, while dual-RLWE andprimal-RLWE are 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 betweendual-RLWE, primal-RLWE and PLWE that incur limited parameter losses. These results could be interpretedas a strong evidence that these problems are qualitatively equivalent.Then we introduce a new algebraic variant of LWE, Middle-Product Learning With Errors (MP-LWE). We show that this problem is at least as hard as PLWE for many defining polynomials f. As a consequence,any cryptographic system based on MP-LWE remains secure as long as one of these PLWE 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.La cryptographie à base de réseaux euclidiens repose en grande partie sur l’utilisation du problème Learning With Errors (LWE) comme fondation de sécurité. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, mais les primitives cryptographiques qui l’utilisent sont inefficaces en termes de consommation en temps et en espace. Les problèmes Polynomial Learning WithErrors (PLWE), dual Ring Learning With Errors (dual-RLWE) et primal Ring Learning With Errors(primal-RLWE) sont trois variantes de LWE qui utilisent des structures algébriques supplémentaires afin de pallier les inconvénients ci-dessus. Le problème PLWE est paramétré par un polynôme f, alors que dual-RLWE et primal-RLWE sont définis à l’aide de l’anneau d’entiers d’un corps de nombres.Ces problèmes, dits algébriques, sont eux-mêmes au moins aussi difficiles que des problèmes standards portant sur les réseaux, mais, dans leur cas, les réseaux impliqués appartiennent à des classes restreintes.Dans cette thèse, nous nous intéressons aux liens entre les variantes algébriques de LWE.Tout d’abord, nous montrons que pour une vaste classe de polynômes de définition, il existe des réductions (non-uniformes) entre dual-RLWE, primal-RLWE et PLWE pour lesquelles l’amplification des paramètres peut être contrôlée. Ces résultats peuvent être interprétés comme une indication forte de l’équivalence calculatoire de ces problèmes.Ensuite, nous introduisons une nouvelle variante algébrique de LWE, Middle-Product Learning WithErrors (MP-LWE). On montre que ce problème est au moins aussi difficile que PLWE pour beaucoup de polynômes de définition f. Par conséquent, un système cryptographique reposant sur MP-LWE reste sûr aussi longtemps qu’une de ces instances de PLWE reste difficile à résoudre.Enfin, nous montrons la pertinence cryptographique de MP-LWE en proposant un protocole de chiffrement asymétrique et une signature digitale dont la sécurité repose sur la difficulté présumée de MP-LWE