On algebraic variants of Learning With Errors

Sur des variantes algébriques du problème Learning With Errors 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.