Bien que relativement récente, la cryptographie à base de réseaux euclidiens s’est distinguée sur de nombreux points, que ce soit par la richesse des constructions qu’elle permet, par sa résistance supposée à l’avènement des ordinateursquantiques ou par la rapidité dont elle fait preuve lorsqu’instanciée sur certaines classes de réseaux. Un des outils les plus puissants de la cryptographie sur les réseaux est le Gaussian sampling. À très haut niveau, il permet de prouver qu’on connaît une base particulière d’un réseau, et ce sans dévoiler la moindre information sur cette base. Il permet de réaliser une grande variété de cryptosystèmes. De manière quelque peu surprenante, on dispose de peu d’instanciations pratiques de ces schémas cryptographiques, et les algorithmes permettant d’effectuer du Gaussian sampling sont peu étudiés. Le but de cette thèse est de combler le fossé qui existe entre la théorie et la pratique du Gaussian sampling. Dans un premier temps, nous étudions et améliorons les algorithmes existants, à la fois par une analyse statistique et une approche géométrique. Puis nous exploitons les structures sous-tendant de nombreuses classes de réseaux, ce qui nous permet d’appliquer à un algorithme de Gaussian sampling les idées de la transformée de Fourier rapide, passant ainsi d’une complexité quadratique à quasilinéaire. Enfin, nous utilisons le Gaussian sampling en pratique et instancions un schéma de signature et un schéma de chiffrement basé sur l’identité. Le premierfournit des signatures qui sont les plus compactes obtenues avec les réseaux à l’heure actuelle, et le deuxième permet de chiffrer et de déchiffrer à une vitesse près de mille fois supérieure à celle obtenue en utilisant un schéma à base de couplages sur les courbes elliptiques. / Although rather recent, lattice-based cryptography has stood out on numerous points, be it by the variety of constructions that it allows, by its expected resistance to quantum computers, of by its efficiency when instantiated on some classes of lattices. One of the most powerful tools of lattice-based cryptography is Gaussian sampling. At a high level, it allows to prove the knowledge of a particular lattice basis without disclosing any information about this basis. It allows to realize a wide array of cryptosystems. Somewhat surprisingly, few practical instantiations of such schemes are realized, and the algorithms which perform Gaussian sampling are seldom studied. The goal of this thesis is to fill the gap between the theory and practice of Gaussian sampling. First, we study and improve the existing algorithms, byboth a statistical analysis and a geometrical approach. We then exploit the structures underlying many classes of lattices and apply the ideas of the fast Fourier transform to a Gaussian sampler, allowing us to reach a quasilinearcomplexity instead of quadratic. Finally, we use Gaussian sampling in practice to instantiate a signature scheme and an identity-based encryption scheme. The first one yields signatures that are the most compact currently obtained in lattice-based cryptography, and the second one allows encryption and decryption that are about one thousand times faster than those obtained with a pairing-based counterpart on elliptic curves.

National Institute of Standards and Technology (NIST) is currently running a stan- dardization process for a post-quantum cryptography primitives. Depending on the al- gorithms building blocks these primitives can be divided into five categories. In the first part of this thesis we described all five categories and compared their characteristics. The most important aspect of the schemes for NIST is security against both classical and quantum adversaries. We chose one of the five categories (namely, we picked lattice- based cryptosystems) for further cryptanalysis. As we think that the security analysis of some of the second round candidates in the NIST standardization project is not suffi- ciently well described in their specification documents and some known attacks are not considered at all, we provide a unified security analysis of these schemes. We described two currently known attacks (primal and dual attacks) against lattice-based schemes, estimated cost of these attacks against the lattice-based candidates in the second round of the NIST standardization project and compared these values with the security claimed by these candidates. In most cases our estimations matches those published in the speci- fication documents and therefore we conclude that the security estimates claimed by the candidates are...

In response to the threat of a future, large-scale, quantum computer, the American National Institute of Standards and Technology (NIST) initiated a competition for designs of quantum-resistant cryptographic primitives. In 2022, the lattice-based Module-Learning With Errors (M-LWE) scheme Kyber emerged as the winner to be standardized. The standardization procedure and development of secure implementations call for thorough evaluation and research. One of the main threats to implementations of cryptographic algorithms today is Side-Channel Analysis (SCA), which is the topic of this thesis. Previous work has presented successful power-based attacks on implementations of lattice cryptography protected by masking and even masking combined with shuffling. Shuffling makes SCA harder as the order of independent instructions is randomized, reducing the correlation between operations and power consumption. This randomization is commonly implemented by shuffling the order of the indexes used to iterate over a loop, using the modern Fisher-Yates algorithm. This work describes a new attack that defeats the shuffling countermeasure by first attacking the generation of the index permutation itself. The attack first recovers the positions of the first and last indexes, 0 and 255, and then rotates the encrypted messages using a ciphertext malleability applicable to many ring-based LWE schemes to shift two bits into the known positions from which they can be recovered. This procedure is repeated to recover full messages in 128 rotations. The attack is tested and evaluated on masked and shuffled implementations of Kyber as well as Saber, another similar finalist of the NIST competition which is based on the Module-Learning With Rounding (M-LWR) problem. Compared to the previous attack on masked and shuffled Saber, which required 61,680 traces, the 4,608 needed for this attack demonstrates a 13-fold improvement. / Som svar på hotet från en framtida, storskalig kvantdator initierade amerikanska National Institute of Standards and Technology (NIST) en tävling för design av kvantsäker kryptografi. Den gitter-baserade Module-Learning With Errors algoritmen Kyber valdes 2022 till vinnare och därmed till att standardiseras. Standardiseringsprocessen och utvecklingen av säkra implementationer manar till utvärderingar och forskning. Ett av de primära hoten mot implementationer av kryptografiska algoritmer är sidokanalsanalys, vilket är fokus i detta arbete. Tidigare attacker har genom effektanalys demonsterat lyckade attacker på implementationer av gitter-baserade algoritmer skyddade genom maskering samt maskering och slumpad ordning av operationer. Slumpad ordning av oberoende operationer gör sidokanalsanalys svårare då korrelationen till effektförbrukningen minskar. Denna slumpordning brukar vanligtiv implementeras genom att slumpmässigt permutera, med den moderna implementationen av Fisher-Yates, de index som används i en kodslinga. I detta arbete presenteras en ny attack som till först extraherar positionen av det första och det sista indexen, 0 och 255, innan de två motsvarande meddelandebitarna extraheras. Bitarna i meddelandet roteras till de kända positionerna med en metod för skiffertextmanipulation som är vanlig bland ring-baserade LWE-designer. Denna process upprepas 128 gånger för att få fram hela meddelandet. Attacken has testats och utvärderats på implementationer, skyddade genom maskering kombinerad med slumpad operationsordning, av både Kyber och en liknande NIST-finalist, Saber. Jämfört med den tidigare attacken på Saber med samma skyddsåtgärder minskar den nya metoden det antal mätningar som krävs från 61,608 till 4,608, vilket motsvarar en 13-falding förbättring.

Le premier protocole cryptographique basé sur les codes correcteurs d'erreurs a été proposé en 1978 par Robert McEliece. La cryptographie basée sur les codes est dite post-quantique car il n'existe pas à l'heure actuelle d'algorithme capable d'attaquer ce type de protocoles en temps polynomial, même en utilisant un ordinateur quantique, contrairement aux protocoles basés sur des problèmes de théorie des nombres. Toutefois, la sécurité du cryptosystème de McEliece ne repose pas uniquement sur des problèmes mathématiques. L'implantation, logicielle ou matérielle, a également un rôle très important pour sa sécurité et l'étude de celle-ci face aux attaques par canaux auxiliaires/cachés n'a débuté qu'en 2008. Des améliorations sont encore possibles. Dans cette thèse, nous proposons de nouvelles attaques sur le déchiffrement du cryptosystème de McEliece, utilisé avec les codes de Goppa classiques, ainsi que des contre-mesures correspondantes. Les attaques proposées sont des analyses de temps d'exécution ou de consommation d'énergie. Les contre-mesures associées reposent sur des propriétés mathématiques et algorithmiques. Nous montrons qu'il est essentiel de sécuriser l'algorithme de déchiffrement en le considérant dans son ensemble et non pas seulement étape par étape / The first cryptographic protocol based on error-correcting codes was proposed in 1978 by Robert McEliece. Cryptography based on codes is called post-quantum because until now, no algorithm able to attack this kind of protocols in polynomial time, even using a quantum computer, has been proposed. This is in contrast with protocols based on number theory problems like factorization of large numbers, for which efficient Shor's algorithm can be used on quantum computers. Nevertheless, the McEliece cryptosystem security is based not only on mathematical problems. Implementation (in software or hardware) is also very important for its security. Study of side-channel attacks against the McEliece cryptosystem have begun in 2008. Improvements can still be done. In this thesis, we propose new attacks against decryption in the McEliece cryptosystem, used with classical Goppa codes, including corresponding countermeasures. Proposed attacks are based on evaluation of execution time of the algorithm or its power consumption analysis. Associate countermeasures are based on mathematical and algorithmic properties of the underlying algorithm. We show that it is necessary to secure the decryption algorithm by considering it as a whole and not only step by step