Error correction and reconciliation techniques for lattice-based key generation protocols

Au cours de la dernière décennie, le développement des ordinateurs quantiques a considérablement progressé, avec des investissements massifs de la part des grandes entreprises technologiques. On suppose qu'une fois que les ordinateurs quantiques à grande échelle seront construits, de nombreux systèmes cryptographiques à clé publique couramment utilisés ne seront plus sécurisés. Pour prévenir les attaques quantiques, les chercheurs travaillent déjà à la conception de protocoles cryptographiques post-quantiques, et le National Institute of Standards and Technology (NIST) des États-Unis organise un concours international pour sélectionner de nouvelles normes cryptographiques.Les constructions cryptographiques à base de réseaux euclidiens sont des candidats prometteurs car elles offrent de fortes garanties de sécurité théoriques et peuvent être mises en œuvre efficacement. L'une des primitives cryptographiques les plus largement utilisées basées sur des réseaux est le problème d'apprentissage avec erreurs, ou en anglais emph{Learning with errors} (LWE) introduit par Regev. Des travaux ultérieurs ont proposé des variantes structurées de LWE telles que Ring-LWE et Module-LWE, qui permettent une représentation plus compacte.Dans cette thèse, nous considérons deux candidats au défi du NIST basés sur les réseaux euclidiens pour les mécanismes d'encapsulation de clé (KEM) et proposons de nouvelles techniques de correction d'erreur et de réconciliation afin d'améliorer leur efficacité, leur sécurité, ainsi que leur fiabilité. Contrairement à certains travaux antérieurs sur la correction d'erreurs pour les protocoles basés sur les réseaux, nous proposons des bornes de probabilité d'erreur rigoureuses.Nous considérons d'abord FrodoKEM, un cryptosystème basé sur LWE, et introduisons un mécanisme de correction d'erreur pour améliorer ses performances. Notre encodeur mappe la clé secrète par bloc dans le réseau de Gosset à 8 dimensions E_8. Nous proposons trois ensembles de paramètres pour notre implémentation modifiée. La première implémentation surpasse FrodoKEM en termes de sécurité plausible ; la seconde permet de réduire la bande passante en divisant par deux le module, et la troisième permet d'augmenter la taille des clés.Le deuxième KEM que nous considérons est KyberKEM, qui est basé sur Module-LWE. Nous proposons une technique de réconciliation utilisant toujours le réseau euclidien E_8, et montrons que notre schéma peut surpasser KyberKEM en termes de sécurité avec une probabilité d'erreur comparable et des exigences de bande passante similaires. Nous étudions également l'utilisation de réseaux de dimension supérieure pour la réconciliation.In the last decade, there has been significant progress in the development of quantum computers, with massive investments by major tech companies. It is assumed that once large-scale quantum computers are built, many commonly used public key cryptosystems will no longer be secure. To prevent quantum attacks, researchers are already working on the design of post-quantum cryptographic protocols, and the US National Institute of Standards and Technology (NIST) is holding an international competition to select new cryptographic standards.Lattice-based cryptographic constructions are promising candidates because they offer strong theoretical security guarantees and can be implemented efficiently. One of the most widely used cryptographic primitives based on lattices is the Learning With Errors (LWE) problem introduced by Regev. Later works have proposed structured variants of LWE such as Ring-LWE and Module-LWE, which allow for a more compact representation.In this thesis, we consider two lattice-based NIST candidates for Key Encapsulation Mechanisms (KEMs) and propose new error correction and reconciliation techniques in order to improve their efficiency, their security, as well as their reliability.Unlike some previous works on error correction for lattice-based protocols, we provide rigorous error probability bounds.We first consider FrodoKEM, a lattice-based cryptosystem based on LWE, and introduce a modified error correction mechanism to improve its performance. Our encoder maps the secret key block-wise into a scaled version of the 8-dimensional Gosset lattice E_8. We propose three sets of parameters for our modified implementation. The first implementation outperforms FrodoKEM in terms of plausible security; the second allows to reduce the bandwidth by halving the modulus, and the third allows to increase key sizes.The second KEM we are considering is KyberKEM, which is based on Module-LWE. We propose a reconciliation technique using the lattice E_8, and show that our scheme can outperform KyberKEM in terms of security with comparable error probability and similar bandwidth requirements. We also investigate the use of higher dimensional lattices for reconciliation