Academic literature on the topic 'Cryptographie sur réseaux euclidiens'

Les réseaux Euclidiens sont un riche objet algébrique qui apparaît dans des contextes variés en mathématiques et en informatique. Cette thèse considère plusieurs aspects algorithmiques des réseaux. Le concept de réduction d'une base d'un réseau est étudié minutieusement : nous couvrons en particulier le spectre complet des compromis qualité-temps des algorithmes de réduction. D'une part, nous présentons et analysons des algorithmes rapides pour trouver une base assez courte (base LLL-réduite) d'un réseau donné arbitraire. D'autre part, nous proposons de nouvelles analyses pour des algorithmes (plus lents) permettant de calculer des bases très courtes (bases HKZ et BKZ-réduites). Cette étude des algorithmes de résolution efficace de problèmes portant sur les réseaux est complétée par une application constructive exploitant leur difficulté apparente. Nous proposons et analysons des schémas cryptographiques, dont la fonction de chiffrement NTRU, et les prouvons au moins aussi difficiles à casser que de résoudre des problèmes pires-cas bien spécifiés portant sur les réseaux.

La cryptographie reposant sur les réseaux euclidiens est l'un des axes principaux pour construire des primitives à clef publique post-quantiques. Dans cette thèse, nous discutons de la construction de signatures numériques et de leur implémentation. Nous commençons par décrire une transformation de type Fiat-Shamir qui à partir d'un schéma d'identification qui utilise de l'échantillonnage par rejets permet de construire une signature prouvée dans le modèle de l'oracle aléatoire. Ensuite, nous décrivons un schéma de chiffrement basé sur l'identité et nous prouvons sa sécurité dans le modèle standard. Un schéma de chiffrement basé sur l'identité correspond à un chiffrement à clef publique classique pour lequel la clef publique d'un utilisateur est simplement son identité, comme par exemple son adresse mail ou son numéro de sécurité sociale. Un utilisateur contacte ensuite un tiers de confiance pour récupérer une clef secrète associée à son identité. Dans notre construction, cette clef secrète consiste essentiellement en une signature de l'identité de l'utilisateur. Nous décrivons également cette construction de signature numérique associée à notre chiffrement basé sur l'identité. Pour finir, nous présentons des résultats d'implémentation de ces deux schémas et comment nous avons choisi des paramètres concrets
Lattice-based cryptography is one of the major line of research to build post-quantum public key primitives. In this thesis, we discuss about digital signatures constructions and their implementation. We first describe a Fiat-Shamir transformation from an identification scheme using rejection sampling to a digital signature secure in the random oracle model. Then we describe an identity-based encryption scheme and we prove its security in the standard model. An identity-based encryption scheme is like a classical public key where the public key is the identity of a user such as its email address or its social security number. A user contacts a third trusted party to get a secret key associated to its identity. In our construction, a secret key consists essentially in a signature of the identity of the user. We also describe this underlying digital signature scheme associated to our identity based encryption scheme. Finally, we present implementation results of these two schemes and how we choose concrete parameters

Les réseaux euclidiens ont été l'objet d'un fort engouement théorique de la part de la communauté des cryptographes ces dernières années. Ils semblent fournir un fondement plus solide, mais s'avèrent aussi plus souples. Cependant, les efforts en direction de la mise en pratique de cette cryptographie innovante restent limités: essentiellement restreints aux cryptosystèmes ingénieux mais précoces de la compagnie NRTU autour des années 2000. Cette thèses s'inscrit dans cette direction, en particulier pour le problème des signatures digitales. Nous présentons en premier lieu une nouvelle attaque sur le schéma de signature NTRUSign: depuis son apparition, la présence dans NTRUSign d'une fuite d'information laissait douter de sa sécurité pratique. Nos travaux présentent la première attaque pratique sur ce schéma malgré les contremesure: mises en place. Nous nous intéressons ensuite à une autre contremesure, l'échantillonnage Gaussien discret, elle prouvablement sure, mais jusqu'alors peu efficace. Nous proposons de nouveaux algorithmes adaptés et efficaces pour cette tache, avec et sans virgule flottante. Nous concluons cette these par la conception et l'implementation d'un nouveau schéma de signature, BLISS, en nous appuyant sur de nombreuses idées du domaine, et avec deux objectifs: la sécurité prouvable, et l'efficacité pratique. Nous introduisons l'utilisation de gaussiennes Bimodales, qui permet, de façon surprenante, de tirer avantage à la fois des progrès sur les signatures sans trappes, et de la génération de trappes a la façon de NTRU. Notre implementation Open-Source, s'avère se comparer favorablement aux primitives standardisées telles que RSA et ECDSA
Lattices have attracted a theoretical interest in the cryptographers' community those past years. They seem to offer a stronger foundation, but have also proved themselves very versatile. Nevertheless, efforts in the direction of the implementation and use of this innovative cryptography have remained very limited: essentially restricted to the ingenious yet premature cryptosystems of the NTRU company around the year 2000. This thesis joins this direction, in particular for the problems of digital signatures. We first present a new attack on the NTRUSign signature scheme: since its introduction, an information leakage has cast doubts about its practical security of that cryptosystem. Our work presents the first practical attack on that scheme despite the implementation of counterineasures. We then move our attention to an alternative countermeasure that is provably secure, yet not so efficient. We propose new algorithms that are adapted and efficient for this task, with or without usage of floating point. We conclude this thesis with the conception and implementation of a new signature scheme, BLISS, with two objectives: provable security and practical efficiency. We introduce the usage of Bimodal Gaussian, that surprisingly allow one to benefit ath the same time from progress on trapless signatures, and from an NTRU-like trap generation. Our implementation is Open-Source, and compete favorably with standardized primitives such as RSA or ECDSA

La cryptographie à base de réseaux euclidiens a généré un vif intérêt durant les deux dernièresdécennies grâce à des propriétés intéressantes, incluant une conjecture de résistance àl’ordinateur quantique, de fortes garanties de sécurité provenant d’hypothèses de difficulté sur lepire cas et la construction de schémas de chiffrement pleinement homomorphes. Cela dit, bienqu’elle soit cruciale à bon nombre de schémas à base de réseaux euclidiens, la génération debruit gaussien reste peu étudiée et continue de limiter l’efficacité de cette cryptographie nouvelle.Cette thèse s’attelle dans un premier temps à améliorer l’efficacité des générateurs de bruitgaussien pour les signatures hache-puis-signe à base de réseaux euclidiens. Nous proposons unnouvel algorithme non-centré, avec un compromis temps-mémoire flexible, aussi rapide que savariante centrée pour des tables pré-calculées de tailles acceptables en pratique. Nousemployons également la divergence de Rényi afin de réduire la précision nécessaire à la doubleprécision standard. Notre second propos tient à construire Falcon, un nouveau schéma designature hache-puis-signe, basé sur la méthode théorique de Gentry, Peikert et Vaikuntanathanpour les signatures à base de réseaux euclidiens. Nous instancions cette méthode sur les réseauxNTRU avec un nouvel algorithme de génération de trappes
Lattice-based cryptography has generated considerable interest in the last two decades due toattractive features, including conjectured security against quantum attacks, strong securityguarantees from worst-case hardness assumptions and constructions of fully homomorphicencryption schemes. On the other hand, even though it is a crucial part of many lattice-basedschemes, Gaussian sampling is still lagging and continues to limit the effectiveness of this newcryptography. The first goal of this thesis is to improve the efficiency of Gaussian sampling forlattice-based hash-and-sign signature schemes. We propose a non-centered algorithm, with aflexible time-memory tradeoff, as fast as its centered variant for practicable size of precomputedtables. We also use the Rényi divergence to bound the precision requirement to the standarddouble precision. Our second objective is to construct Falcon, a new hash-and-sign signaturescheme, based on the theoretical framework of Gentry, Peikert and Vaikuntanathan for latticebasedsignatures. We instantiate that framework over NTRU lattices with a new trapdoor sampler

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

La cryptographie reposant sur les réseaux Euclidiens est une branche récente de la cryptographie dans laquelle la sécurité des primitives repose sur la difficulté présumée de certains problèmes bien connus dans les réseaux Euclidiens. Le principe de ces preuves est de montrer que réussir une attaque contre une primitive est au moins aussi difficile que de résoudre un problème particulier, comme le problème Learning With Errors (LWE) ou le problème Small Integer Solution (SIS). En montrant que ces problèmes sont au moins aussi difficiles à résoudre qu'un problème difficile portant sur les réseaux, présumé insoluble en temps polynomial, on en conclu que les primitives construites sont sûres. Nous avons travaillé sur l'amélioration de la sécurité et des constructions de primitives cryptographiques. Nous avons étudié la difficulté des problèmes SIS et LWE et de leurs variantes structurées sur les anneaux d'entiers de corps cyclotomiques, et les modules libres sur ceux-ci. Nous avons montré d'une part qu'il existe une preuve de difficulté classique pour le problème LWE (la réduction existante de Regev en 2005 était quantique), d'autre part que les variantes sur les modules sont elles-aussi difficiles. Nous avons aussi proposé deux nouvelles variantes de signatures de groupe dont la sécurité repose sur SIS et LWE. L'une est la première reposant sur les réseaux et ayant une taille et une complexité poly-logarithmique en le nombre d'utilisateurs. La seconde construction permet de plus la révocation d'un membre du groupe. Enfin, nous avons amélioré la taille de certains paramètres dans le travail sur les applications multilinéaires cryptographiques de Garg, Gentry et Halevi
Lattice-based cryptography is a branch of cryptography exploiting the presumed hardness of some well-known problems on lattices. Its main advantages are its simplicity, efficiency, and apparent security against quantum computers. The principle of the security proofs in lattice-based cryptography is to show that attacking a given scheme is at least as hard as solving a particular problem, as the Learning with Errors problem (LWE) or the Small Integer Solution problem (SIS). Then, by showing that those two problems are at least as hard to solve than a hard problem on lattices, presumed polynomial time intractable, we conclude that the constructed scheme is secure.In this thesis, we improve the foundation of the security proofs and build new cryptographic schemes. We study the hardness of the SIS and LWE problems, and of some of their variants on integer rings of cyclotomic fields and on modules on those rings. We show that there is a classical hardness proof for the LWE problem (Regev's prior reduction was quantum), and that the module variants of SIS and LWE are also hard to solve. We also give two new lattice-based group signature schemes, with security based on SIS and LWE. One is the first lattice-based group signature with logarithmic signature size in the number of users. And the other construction allows another functionality, verifier-local revocation. Finally, we improve the size of some parameters in the work on cryptographic multilinear maps of Garg, Gentry and Halevi in 2013

L'algorithme quantique de Shor peut être utilisé pour résoudre le problème de factorisation de grands entiers et le logarithme discret dans certains groupes. La sécurité des protocols cryptographiques à clé publique les plus répandus dépend de l'hypothèse que ces problèmes mathématiques soient difficiles à résoudre. Un ordinateur quantique suffisamment puissant pourrait donc constituer une menace pour la confidentialité et l'authenticité de la communication numérique sécurisée. La cryptographie post-quantique est basée sur des problèmes mathématiques qui sont difficile à résoudre même pour les ordinateurs quantiques, tels que Learning with Errors (LWE) et ses variants RLWE et MLWE. Dans cette thèse, nous présentons et comparons des implantations sur FPGA des algorithmes de chiffrement à clé publique. Nous discutons des compromis entre la sécurité, le temps de calcul et le coût en surface. Les implantations sont parallélisées afin d'obtenir une accélération plus importante. En outre, nous discutons de la sécurité matérielle des implantations, et proposons des protections contre des attaques par canaux auxilliares. Nous considerons des contremesures de l'état de l'art, telles que le masquage et le blindage, et proposons des améliorations à ces algorithmes. Nous proposons également de nouvelles protections basées sur la représentation redondante des nombres et sur des permutations aléatoires des opérations de calcul. Toutes ces protections sont implantées sur FPGA dans le but de comparer leur coût en surface et le surcoût en temps de calcul
Shor's quantum algorithm can be used to efficiently solve the integer factorisation problem and the discrete logarithm in certain groups. The security of the most commonly used public key cryptographic protocols relies on the conjectured hardness of exactly these mathematical problems. A sufficiently large quantum computer could therefore pose a threat to the confidentiality and authenticity of secure digital communication. Post quantum cryptography relies on mathematical problems that are computationally hard for quantum computers, such as Learning with Errors (LWE) and its variants RLWE and MLWE. In this thesis, we present and compare FPGA implementations of LWE, RLWE and MLWE based public key encryption algorithms. We discuss various trade-offs between security, computation time and hardware cost. The implementations are parallelized in order to obtain maximal speed-up. We show that MLWE has the best performance in terms of computation time and area utilization, and can be parallelized more efficiently than RLWE. We also discuss hardware security and propose countermeasures against side channel attacks for RLWE. We consider countermeasures from the state of the art, such as masking and blinding, and propose improvements to these algorithms. Moreover, we propose new countermeasures based on redundant number representation and the random shuffling of operations. All countermeasures are implemented on FPGA to compare their cost and computation time overhead. Our proposed protection based on redundant number representation is particularly flexible, in the sens that it can be implemented for various degrees of protection at various costs

La cryptographie basée sur les réseaux est un domaine de recherche qui étudie la construction d'outils pour une communication sécurisée basée sur des problèmes de réseaux difficiles. La cryptographie basée sur les réseau est l'un des candidats les plus prometteurs pour la communication sécurisée post-quantique. Cette thèse étudie les algorithmes pour résoudre les problèmes de réseaux difficiles et leur application à l'évaluation de la sécurité des constructions cryptographiques. Dans la première partie, nous introduisons une nouvelle famille d'algorithmes de sieving appelé sieving cylindrique. Le sieving heuristique est actuellement l'approche la plus rapide pour résoudre les problèmes de réseau central, SVP et CVP. Nous montrons que le sieving cylindrique peut surpasser les algorithmes de sieving existants dans certains cas, à savoir qu'il est plus efficace pour résoudre SVP pour des réseaux avec un volume premier petit et pour résoudre le problème de vecteur le plus proche avec prétraitement (CVPP). Dans la deuxième partie de la thèse, nous améliorons l'attaque duale utilisée à l'origine pour estimer la sécurité du Fast Fully Homomorphic Encryption scheme over Torus (TFHE). Nous hybridons l'attaque duale avec la recherche de la partie de la clé secrète. Comme TFHE utilise des clés binaires, la partie recherche de l'attaque peut être effectuée efficacement en exploitant la structure récursive de l'espace de recherche. Nous comparons notre attaque avec d'autres techniques existantes pour résoudre LWE et montrons que le niveau de sécurité du schéma TFHE devrait être mis à jour par rapport à la nouvelle attaque
Lattice-based cryptography is a field of research that studies the construction of tools for secure communication based on hard lattice problems. Lattice-based cryptography is one of the most promising candidates for secure post-quantum communication. This thesis studies algorithms for solving hard lattice problems and their application to the evaluation of the security of cryptosystems. In the first part, we introduce a new family of lattice sieving algorithms called cylindrical sieving. Heuristic sieving is currently the fastest approach to solve central lattice problems: SVP and CVP. We show that cylindrical sieving can outperform existing sieving algorithms in some cases, namely, that it is more efficient for solving SVP for lattices with small prime volume and for solving the closest vector problem with preprocessing (CVPP). In the second part of the thesis, we improve the dual attack originally used to estimate the security of the Fast Fully Homomorphic Encryption scheme over Torus (TFHE). We hybridize the dual attack with the search for the secret key part. As TFHE uses binary keys, the search part of the attack can be performed efficiently by exploiting the recursive structure of the search space. We compare our attack with other existing techniques for solving LWE and show that the security level of the TFHE scheme should be updated according to the new attack

La transition vers la cryptographie post-quantique est une tâche considérable ayant suscité un nombre important de travaux ces dernières années. En parallèle, la cryptographie pour la protection de la vie privée, visant à pallier aux limitations inhérentes des mécanismes cryptographiques basiques dans ce domaine, a connu un véritable essor. Malgré le succès de chacune de ces branches prises individuellement, combiner les deux aspects de manière efficace s'avère extrêmement difficile. Le but de cette thèse de doctorat consiste alors à proposer de nouvelles constructions visant à garantir une protection efficace et post-quantique de la vie privée, et plus généralement des mécanismes d'authentification avancés. Dans ce but, nous nous consacrons tout d'abord à l'étude de l'une des hypothèses mathématiques fondamentales utilisées en cryptographie sur les réseaux Euclidiens: Module Learning With Errors. Nous prouvons que le problème ne devient pas significativement plus facile même en choisissant des distributions de secret et d'erreur plus courtes. Ensuite, nous proposons des optimisations des échantillonneurs d'antécédents utilisés par de nombreuses signatures avancées. Loin d'être limitées à ce cas d'usage, nous montrons que ces optimisations mènent à la conception de signatures standards efficaces. Enfin, à partir de ces contributions, nous concevons des algorithmes de signatures avec protocoles efficaces, un outil polyvalent utile à la construction d'applications avancées. Nous en montrons les capacités en proposant le premier mécanisme d'accréditation anonyme post-quantique, que nous implémentons afin de mettre en exergue son efficacité aussi bien théorique que pratique
The transition to post-quantum cryptography has been an enormous effort for cryptographers over the last decade. In the meantime, cryptography for the protection of privacy, aiming at addressing the limitations inherent to basic cryptographic mechanisms in this domain, has also attracted a lot of attention. Nevertheless, despite the success of both individual branches, combining both aspects along with practicality turns out to be very challenging. The goal of this thesis then lies in proposing new constructions for practical post-quantum privacy, and more generally advanced authentication mechanisms. To this end, we first focus on the lower level by studying one of the fundamental mathematical assumptions used in lattice-based cryptography: Module Learning With Errors. We show that it does not get significantly easier when stretching the secret and error distributions. We then turn to optimizing preimage samplers which are used in advanced signature designs. Far from being limited to this use case, we show that it also leads to efficient designs of regular signatures. Finally, we use some of the previous contributions to construct so-called signatures with efficient protocols, a versatile building block in countless advanced applications. We showcase it by giving the first post-quantum anonymous credentials, which we implement to demonstrate a theoretical and practical efficiency

Les thèmes abordés dans cette thèse se situent aux interfaces de la cryptographie, de l'algorithmique et de l'analyse des algorithmes. Ils se concentrent sur un domaine particulier, celui de la géométrie des nombres et plus particulièrement, celui delà réduction des réseaux euclidiens. Devant la difficulté d'une analyse exacte de l'algorithme LLL, nous avons proposé toute une classe de modèles simplifiés pour l'exécution de l'algorithme, du plus simple, déjà proposé par Madrisch et Vallée, au plus compliqué, qui correspond à l'algorithme LLL lui-même. Nous sommes revenus sur l'analyse du modèle le plus simple en adoptant le point de vue du chip firing game. Nous avons aussi cherché à modéliser, dans ce cadre de cfg, les principales entrées qui nous intéressaient, correspondant à des réseaux cryptographiques. Nous avons été conduits à trois familles des réseaux cryptographiques : les réseaux dit réseaux d'Ajtai qui donnent lieu à des tas ``tous très pleins'', les réseaux sac-à-dos ou réseaux NTRU, qui donnent lieu à des tas de sable ``avec un seul tas'' et enfin les réseaux de Coppersmith, qui donnent lieu à des tas de sable ``avec des trous''. Nous avons ensuite étudié un modèle moins simplifié d'exécution, mais sans aucun doute plus proche de la réalité. Nous avons effectué une analyse précise de ce modèle d'exécution: analyse totale pour le cas de la dimension 2, qui correspond à la dimension 3 dans le monde des réseaux, où l'analyse du véritable algorithme LLL est déjà mal comprise --analyse partielle en dimension générale. Enfin, nous avons fait des expérimentations afin de rechercher une validation expérimentale des hypothèses qui mènent aux modèles simplifiés
The topics addressed in this thesis belong to the interface between cryptography, algorithmics, and analysis of algorithms. They focus to a particular area, the geometry of numbers, in particular lattice reduction. Given the difficulty of an exact analysis of the LLL algorithm, we proposed a class of simplified models for the execution of the algorithm, ranging from the simplest one, already proposed by Madrisch and Vallée, to the most complex, which is the LLL algorithm itself. We first returned to the analysis of the simplest model and adopted there the perspective of the ``chip firing game''. From this perspective, we also described models for the different inputs of interest, corresponding to cryptographic systems. We were then led to three families of ``cryptographic lattices'': Ajtai's lattices give rise to sandpiles, whose piles are all ``full'' ; Knapsack or NTRU lattices give rise to sandpiles ``with only one pile''; finally Coppersmith's lattices give rise to sandpiles with ``holes''. Then we studied a model for the execution which was less simplified, but probably more realistic. We performed a detailed analysis of this model: a complete analysis in the two dimensional case, which corresponds to three-dimensional lattices, where the analysis of the exact LLL algorithm is not yet known, together with a partial analysis in general dimensions. Finally, we conducted experiments, in order to obtain an experimental validation of the assumptions that lead to simplified models