-

Cette thèse est consacrée à la modélisation et l'optimisation non convexe basées sur la programmation DC et DCA pour certaines classes de problèmes issus de deux domaines importants : le Data Mining et la Cryptologie. Il s'agit des problèmes d'optimisation non convexe de très grande dimension pour lesquels la recherche des bonnes méthodes de résolution est toujours d'actualité. Notre travail s'appuie principalement sur la programmation DC et DCA. Cette démarche est motivée par la robustesse et la performance de la programmation DC et DCA, leur adaptation aux structures des problèmes traités et leur capacité de résoudre des problèmes de grande dimension. La thèse est divisée en trois parties. Dans la première partie intitulée Méthodologie nous présentons des outils théoriques servant des références aux autres. Le premier chapitre concerne la programmation DC et DCA tandis que le deuxième porte sur les algorithmes génétiques. Dans la deuxième partie nous développons la programmation DC et DCA pour la résolution de deux classes de problèmes en Data Mining. Dans le chapitre quatre, nous considérons le modèle de la classification floue FCM et développons la programmation DC et DCA pour sa résolution. Plusieurs formulations DC correspondants aux différentes décompositions DC sont proposées. Notre travail en classification hiérarchique (chapitre cinq) est motivé par une de ses applications intéressante et très importantes, à savoir la communication multicast. C'est un problème non convexe, non différentiable de très grande dimension pour lequel nous avons reformulé sous la forme des trois programmes DC différents et développé les DCA correspondants. La troisième partie porte sur la Cryptologie. Le premier concerne la construction des fonctions booléennes équilibrées de haut degré de non-linéarité - un des problèmes cruciaux en Cryptographie. Plusieurs versions de combinaison de deux approches - DCA et les algorithmes génétiques (AG) sont étudiées dans le but d'exploiter simultanément l'efficacité de chaque approche. Le deuxième travail concerne des techniques de cryptanalyse d'un schéma d'identification basé sur les deux problèmes ''Perceptron'' (PP) et ''Perceptron Permuté'' (PPP). Nous proposons une méthode de résolution des deux problèmes PP et PPP par DCA et une méthode de coupes dans le dernier chapitre / This thesis is dedicated to non-convex modeling and the optimization based on the DC programming and DCA for certain classes of problems of two important domains : the Data Mining and the Cryptology. They are non-convex optimization problems of very large dimensions for which the research of good solution methods is always of actuality. Our work is based mainly on the DC programming and DCA that have been successfully applied in various fields of applied sciences, including machine learning. It is motivated and justified by the robustness and the good performance of DC programming and DCA in comparison with the existing methods. This thesis is devised in three parties. The first part, entitling Methodology, serves as a reference for other chapters. The first chapter concerns the programming of DC and DCA while the second chapter describes the genetic algorithms. In the second part, we develop the DC and DCA programming to solve two classes of problems in Data Mining. In the chapter four, we take consideration into the model of classification FCM and develop the programming DC and DCA for their resolution. Many formulations DC in correspondence to different decompositions DC are proposed. Our work in hierarchic classification (chapter 5) is motivated by one of its interesting and very important applications, known as muliticast communication. It's a non-convex, non differentiable, non-convex problem in a very big dimension with which we have reformulated in the forms of 3 different DC programs and developed the DCA relative. The 3rd part focuses on the Cryptology. The 1st chapter is the construction of stable boonlean functions with high degree of non-linearity - one of the crucial problems of Cryptography. Many versions of combination of 2 approaches, DCA and Genetic Algorithms (GA) are studied in the purpose of exploiting simultaneously the efficacy of each approach. The secondrd work is about the techinics of cryptanalyse of a identification scheme based on two problems Perceptron (PP) and Perceptron Permuted. We propose a method of resolving two problems PP and PPA by DCA and a cutting plan method in the last chapter

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

-

Block ciphers are widely used building blocks for secure communication systems; their purpose is to ensure confidentiality of the data exchanged through such systems, while achieving high performance. In this context, a variety of aspects must be taken into account. Primarily, they must be secure. The security of a block cipher is usually assessed by testing its resistance against known attacks. However as attacks may exist that are currently unknown, generic security proofs are also tried to be obtained. On the other hand, another attack methodology is also worth considering. Contrary to the others, it aims at the implementation of the algorithm rather than the cipher itself. It is known as side-channel analysis. Finally, performance of a block cipher in terms of throughput is very important as well. More than any other cryptographic primitive, block ciphers allow a tradeoff to be made between security and performance. In this thesis, contributions are given regarding these various topics. In the first part of the thesis, we deal with two particular types of attacks, namely the square attack and key schedule cryptanalysis. We also consider security proofs in the so-called Luby-Rackoff model, which deals with adversaries having unbounded computation capabilities. More precisely, we are interested in the Misty structure, when the round functions are assumed to be involutions. The second part of the thesis is devoted to design and implementation aspects. First, we present a fault attack on substitution-permutation networks, which requires as few as two faulty ciphertexts to retrieve the key. We also study the security of DeKaRT, which is an algorithm intended to protect smart cards against probing attacks. Finally we present the design of ICEBERG, a block cipher deliberately oriented towards good performance in hardware, and give an adequate analysis of its security.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La cryptographie à base de réseaux euclidiens est un domaine prometteur pour la construction de primitives cryptographiques post-quantiques. Un problème fondamental, lié aux réseaux, est le problème du plus court vecteur (ou SVP, pour Shortest Vector Problem). Ce problème est supposé être difficile à résoudre même avec un ordinateur quantique. Afin d’améliorer l’efficacité des protocoles cryptographiques, on peut utiliser des réseaux structurés, comme par exemple des réseaux idéaux ou des réseaux modules (qui sont une généralisation des réseaux idéaux). La sécurité de la plupart des schémas utilisant des réseaux structurés dépend de la difficulté du problème SVP dans des réseaux modules, mais un petit nombre de schémas peuvent également être impactés par SVP dans des réseaux idéaux. La principale construction pouvant être impactée par SVP dans des réseaux idéaux est la fonction multilinéaire GGH13. Cette fonction multilinéaire est principalement utilisée aujourd’hui pour construire des obfuscateurs de programmes, c’est-à-dire des fonctions qui prennent en entrée le code d’un programme et renvoie le code d’un programme équivalent (calculant la même fonction), mais qui doit cacher la façon dont le programme fonctionne.Dans cette thèse, nous nous intéressons dans un premier temps au problème SVP dans les réseaux idéaux et modules. Nous présentons un premier algorithme qui, après un pre-calcul exponentiel, permet de trouver des vecteurs courts dans des réseaux idéaux plus rapidement que le meilleur algorithme connu pour des réseaux arbitraires. Nous présentons ensuite un algorithme pour les réseaux modules de rang 2, également plus efficace que le meilleur algorithme connu pour des réseaux arbitraires, à condition d’avoir accès à un oracle résolvant le problème du plus proche vecteur dans un réseau fixé. Le pré-calcul exponentiel et l’oracle pour le problème du plus proche vecteurs rendent ces deux algorithmes inutilisables en pratique.Dans un second temps, nous nous intéressons à la fonction GGH13 ainsi qu’aux obfuscateurs qui l’utilisent. Nous étudions d’abord l’impact des attaques statistiques sur la fonction GGH13 et ses variantes. Nous nous intéressons ensuite à la sécurité des obfuscateurs utilisant la fonction GGH13 et proposons une attaque quantique contre plusieurs de ces obfuscateurs. Cette attaque quantique utilise entre autres un algorithme calculant un vecteur court dans un réseau idéal dépendant d’un paramètre secret de la fonction GGH13. / Lattice-based cryptography is a promising area for constructing cryptographic primitives that are plausibly secure even in the presence of quantum computers. A fundamental problem related to lattices is the shortest vector problem (or SVP), which asks to find a shortest non-zero vector in a lattice. This problem is believed to be intractable, even quantumly. Structured lattices, for example ideal lattices or module lattices (the latter being a generalization of the former), are often used to improve the efficiency of lattice-based primitives. The security of most of the schemes based on structured lattices is related to SVP in module lattices, and a very small number of schemes can also be impacted by SVP in ideal lattices.In this thesis, we first focus on the problem of finding short vectors in ideal and module lattices.We propose an algorithm which, after some exponential pre-computation, performs better on ideal lattices than the best known algorithm for arbitrary lattices. We also present an algorithm to find short vectors in rank 2 modules, provided that we have access to some oracle solving the closest vector problem in a fixed lattice. The exponential pre-processing time and the oracle call make these two algorithms unusable in practice.The main scheme whose security might be impacted by SVP in ideal lattices is the GGH13multilinear map. This protocol is mainly used today to construct program obfuscators, which should render the code of a program unintelligible, while preserving its functionality. In a second part of this thesis, we focus on the GGH13 map and its application to obfuscation. We first study the impact of statistical attacks on the GGH13 map and on its variants. We then study the security of obfuscators based on the GGH13 map and propose a quantum attack against multiple such obfuscators. This quantum attack uses as a subroutine an algorithm to find a short vector in an ideal lattice related to a secret element of the GGH13 map.

Etablir un canal garantissant l'authentification de façon efficace requiert l'utilisation de nombreux outils cryptographiques. Dans ce mémoire, nous nous intéressons à la sécurité de plusieurs d'entre eux, présents à différentes étapes dans le protocole de mise en place du canal. Dans un premier temps, nous abordons l'analyse de deux protocoles qui, mis bout à bout, assurent la mise en place d'un canal authentifié, confidentiel et intègre : un algorithme d'échange de clefs authentifié et un algorithme de chiffrement authentifié. Le premier algorithme permet de générer des clefs en alliant plusieurs moyens d'authentification (biométrie, mot de passe, carte à puce). Le second est un algorithme normalisé appelé CCM. Dans un second temps, nous nous intéressons plus particulièrement à la phase d'extraction de clefs, étape charnière entre l'échange de clefs et son utilisation pour établir un canal sécurisé. Nous présentons une méthode simple pour extraire une clef symétrique d'un élément Diffie-Hellman, puis nous analysons l'utilisation d'HMAC comme fonction d'extraction de clefs. Dans un troisième temps, nous concentrons notre attention sur les fonctions de hachage, très utilisées à plusieurs niveaux du protocole. Plus précisément, nous analysons la sécurité d'un mode opératoire basé sur un algorithme de chiffrement par bloc dont on fixe la clef, puis, nous examinons des modes opératoires qui cherchent à garantir une sécurité en seconde préimage optimale.

La cryptographie multivariée peut être définie comme la cryptographie à clé publique basée sur la difficulté de résoudre des systèmes polynomiaux à plusieurs variables. Bien que la recherche de tels schémas soit apparue dès le début des années 80, elle s'est surtout développée depuis une dizaine d'années, et a conduit à plusieurs propositions jugées promet-teuses, telles que le cryptosystème HFE et le schéma de signature SFLASH. Les shémas multivariés se posent ainsi en alternative possible aux schémas traditionnels basés sur des problèmes de théorie des nombres, et constituent des solutions efficaces pour l'implantation des fonctionnalités de la cryptographie à clé publique. Lors d'Eurocrypt 2005, Fouque, Granboulan et Stern ont proposé une nouvelle approche cryptanalytique pour les schémas multivariés basée sur l'étude d'invariants liés à la différentielle, et ont démontré la pertinence de cette approche par la cryptanalyse du schéma PMI proposé par Ding. Au cours de cette thèse, nous avons développé l'approche différentielle proposée par Fouque et al. dans deux directions. La première consiste en un traitement combinatoire des invariants dimensionnels de la différentielle. Ceci nous a permis de montrer qu'une clé publique HFE pouvait être distinguée d'un système quadratique aléatoire en temps quasipolynomial. Une seconde application de cette même approche nous a permis de cryptanalyser une variation de HFE proposée par Ding et Schmidt à PKC 2005. Le second développement de la thèse est la découverte d'invariants fonctionnels de la différentielle et nous a permis de montrer la faiblesse du schéma SFLASH.

Le chiffrement est sûrement une primitive fondamentale parmi les fonctions cryptogra- phiques. Cela rend possible à deux parties, d'ordinaire appelées Alice et Bob, de commu- niquer au travers d'un canal non sécurisé en permettant qu'un adversaire, Eve, ne puisse pas comprendre leur communication. Il pourrait sembler assez facile d'identifier les contraintes nécessaires pour le design d'un " bon " schéma de chiffrement. Il s'avère en réalité que la définition d'un modèle de sécurité rigoureux n'est pas trivial. Ceci dépend fortement du contexte. La sécurité même dépend du contexte. Ce document s'ouvre avec un chapitre d'introduction à la cryptographie à clé publique. Nous décrirons ensuite comment la sécurité d'une telle primitive est évaluée en définissant de façon rigoureuse un attaquant, en particulier cela signifie fixer son but et les moyens dont il dispose. La suite de ce document s'organise autour de deux parties. La première partie concerne l'anonymat révocable. Nous obtenons et présentons deux schémas pour garantir l'anonymat pour l'envoyeur d'un message chiffré mais avec la possibilité pour un troisième acteur de confiance, si le cas le nécessite, de révéler l'identité de l'envoyeur. Cette primitive a été appliquée dans les contextes du chiffrement à clé publique et du chiffrement broadcast. Dans la deuxième partie, nous nous dédions à l'étude et à l'amélioration d'un schéma de chiffrement à clé publique dont l'original est dû à Goldwasser et Micali. Notre travail généralise leur schéma en fournissant une famille de schémas de chiffrement. Notre travail est motivé par la recherche de l'amélioration de l'efficacité (en termes de bande passante) du schéma original, afin de pouvoir chiffrer des messages plus longs dans un chiffré de la même taille.