Instructions

Une page wiki pour chaque sujet (liées dans la liste des sujets ci-dessous) a été préparée. La page contiens déjà les références qui vous seront utiles et une liste de points qui devront être traités.
Sentez-vous libre de créer des pages supplémentaires (il est par exemple naturel de créer une page par concept), mais n'oubliez pas de vous mentionner comme rédacteur et de les lier à la page de résumé correspondante.
Vous pouvez également librement inclure des liens vers les pages du wiki rédigées par vos collègues lorsque des notions étudiées précédemment apparaissent. Il s'agit de créer une ressource pédagogique sur le sujet du séminaire.

Conseils pratiques:

Vous pouvez rédiger des équation en LateX, en les entourant des symboles "\ [" et "\ ]" (en supprimant l'espace entre les deux caractères). Exemple: \( (a + b)^2 = a^2 + 2ab + b^2 \).
Pour un titre de section faîtes précéder le titre par "=".
Faîtes précéder chaque élément d'une liste par "*" ou "#".
Une référence sur le language de formatage utilisé sur ce wiki.
Si vous trouvez des références utiles ajoutez-les à la bibliographie au bas de la page correspondante.

Liste des sujets

Première partie: courbes elliptiques

Sujet 1: Rappels sur la théorie des nombres et sur les corps finis Il s'agit de rappeler quelques faits basiques, en particulier sur la théories des corps finis, qui seront utiles lors de l'étude des courbes elliptiques.

Sujet 2: Le modèle de Weierstrass Le modèle de Weierstrass représentent les courbes elliptiques sous la forme de solutions d'une certaine équation polynomiale en deux variables.

Sujet 3: L'invariant J L'invariant \(J\) permet, sur les corps algébriquement clos, d'identifier les équations de Weierstrass "équivalentes", dans le sens que leur solutions diffèrent par un redimensionnement homogène des variables.

Sujet 4: Loi de groupe sur les courbes elliptiques I Les courbes elliptiques sont des groupes abéliens. Ce sujet a pour but de définir la loi de groupe et de donner quelques exemples.

Sujet 5: Loi de groupe sur les courbes elliptiques II Ce sujet explore la structure des groupes abéliens correspondant aux courbes elliptiques rationelles, réelles et complexes.

Sujet 6: Méthodes efficaces pour calculer la loi de groupe Les applications en cryptographie requièrent fréquemment calculer l'addition de points dont les coordonnées sont des entiers très grands. Heureusement, des méthodes efficaces pour faire ces calculs existent, en utilisant des coordonnées différentes de celles du modèle de Weierstrass. De même, la multiplications de points par de grands entiers peut se calculer efficacement par doublement successifs.

Sujet 7: Diviseurs I Ce sujet a pour but d'introduire la notion de diviseur et leur relations aux fonctions sur les courbes elliptiques.

Sujet 8: Diviseurs II Dans ce sujet, nous prouverons les propriétés élémentaires des diviseurs associés aux fonctions sur les courbes elliptiques.

Sujet 9: Diviseurs III Ce sujet est un exemple détaillé de calcul de la fonction associée à un diviseur.

Sujet 10: Couplage de Weil I Le couplage de Weil est un homomorphisme envoyant le produit de deux copies d'un sous-groupes d'un groupe elliptique vers un groupe cyclique. Il permet de nombreuse applications cryptographiques intéressantes. Nous définirons le couplage de Weil après avoir brièvement décrit la structure des sous-groupes de torsion des courbes elliptiques.

Sujet 11: Couplage de Weil II Dans ce sujet, nous prouverons quelques propriétés du couplage de Weil.

Sujet 12: L'algorithme de Miller L'algorithme de Miller est un algorithme efficace pour le calcul du couplage de Weil.

Sujet 13: Le couplage de Tate-Lichtenbaum Le couplage the Tate-Lichtenbaum requiert pour être défini des conditions moins strictes que le couplage de Weil.

Sujet 14: Courbes elliptiques sur les corps finis I: structure Nous étudierons la structure générale des groupes de courbes elliptiques sur des corps finis, et donnerons des exemples d'ordre peu élevé.

Sujet 15: Courbes elliptiques sur les corps finis II: comptage de points Nous présenterons un algorithme pour calculer le nombre d'éléments dans les groupes de courbes elliptiques sur des corps finis.

Sujet 16: Le problème du logarithme discret et attaques I Le problème du logarithme discret un problème "à sens unique", c'est-à-dire difficile à résoudre mais facile à vérifier, qui est à la base de nombreuses applications cryptographiques. Dans ce contexte, il est particulièrement important de comprendre les attaques possibles, c'est-à-dire les situations dans lesquelles un algorithms efficace existe pour résoudre le problème. Dans ce sujet, nous définirons le problème du logarithme discret et étudierons un premier type d'attaque. Les deux sujets suivants présenterons d'autres attaques.

Sujet 17: Le problème du logarithme discret et attaques II Voir Sujet 16.

Sujet 18: Le problème du logarithme discret et attaques III Voir Sujet 16.

Deuxième partie: cryptographie

Sujet 19: Bases de cryptographie Ce sujet a pour but de présenter différents protocoles cryptographiques. Il ne présente pas de difficulté mathématique, mais requiert quelques recherches bibliographiques.

Sujet 20: Echange de clés de Diffie-Hellman Le protocole d'échange de clés de Diffie-Hellman utilise le problème du logarithme discret pour permettre à deux personnes de créer une clé secrète commune, qui peut ensuite être utilisée pour un chiffrement symétrique. Nous en profiterons pour introduire les problèmes de Diffie-Hellman calculatoires et décisionels, que nous retrouverons dans des sujets suivants.

Sujet 21: Fonctions de hachage Les fonctions de hachage permette d'extraire d'un ensemble de données une "signature" effectivement unique, et sont un ingrédient important de nombreux algorithmes cryptographiques.

Sujet 22: Cryptosystème de ElGamal Le cryptosystème de ElGamal fournit une incarnation relativement simple des protocoles de chiffrement à clé publique et de signature, en utilisant la difficulté du problème de Diffie-Hellman.

Sujet 23: Chiffrement homomorphe Certains cryptosystèmes ont la propriété d'être homomorphes, c'est-à-dire que certaines opérations mathématiques peuvent être effectuées indifféremment avant et après le chiffrement. Le cryptosystème de ElGamal est en particulier homomorphe par rapport à l'addition..

Sujet 24: Elliptic curve digital signature algorithm (ECDSA) et ECIES Le DSA est un protocole de signature standardisé basé sur le problème du logarithme discret. Le ECDSA est la version utilisant une courbe elliptique au lieu d'un groupe cyclique. Le ECIES est le protocole de chiffrement correspondant.

Sujet 25: Signatures de Schnorr Le protocole de signature de Schnorr permet naturellement l'agrégation de signatures: Etant donné un ensemble de signatures sur un même message, il est possible de combiner les signatures en une unique signature qui n'est valide que si toutes les signatures sont valides. Naïvement, les signatures de Schnorr permettent également l'agrégation de clés: étant donné un groupe de clés privées, il est possible de créer une clé publique pour laquelle il n'est possible de créer une signature valide que si les possesseurs des clés privées coopèrent. Ce schéma est néanmoins vulnérable par l'attaque de la clé malhonnête.

Sujet 26: Signatures de Boneh-Lynn-Shacham Les signatures BLS partages les bonnes propriétés des signatures de Schnorr, mais permettent l'agrégation de clés de manière sécurisée, ainsi que l'implémentation efficace de signatures à seuil (voir le prochain sujet). Elles utilisent de manière cruciale le couplage de Weil de la courbe elliptique sous-jacente.

Sujet 27: Signatures à seuil, signatures à sous-groupe responsable Les signatures à seuil sont des protocoles de signature tels que la création d'une signature nécessite la coopération de plusieurs entités. Pour une signature à sous-groupe responsable, il est possible de spécifier exactement quels sous-groupes de signataires sont capable de produire une signature valide.

Sujet 28: Mise en gage La mise en gage est un protocole cryptographique qui est l'analogue au fait de placer une valeur secrète dans une boîte fermée a clef. Un acteur fait un choix en s'engageant publiquement, sans toutefois révéler son choix. Il peut plus tard révéler son choix et fournir une clé prouvant que son choix est bien celui pour lequel il s'était engagé précédemment. La mise en gage de Pedersen est une mise en gage utilisant le problème du logarithme discret et ayant des propriétés intéressantes.

Sujet 29: Preuves à divulgation nulle de connaissances Une preuve à divulgation nulle de connaissance est un protocole cryptographique permettant à un acteur de prouver à un autre qu'il connaît la solution d'un problème, sans rien révéler de la solution.

Sujet 30: zk-SNARKs I: Programmation arithmétique quadratique Les zk-SNARKs (zero knowledge succint argument of knowledge) sont des preuves à divulgation nulle de connaissance "universelles", dans le sens qu'elles peuvent s'adapter à n'importe quel problème NP-difficile. (Comme ces "preuves" peuvent être brisées par un adversaire disposant d'une puissance de calcul illimitée, on parle plutôt d'"argument de connaissance"). Ce premier exposé présente la programmation arithmétique quadratique, un problème de factorisation de polynôme NP-difficile complet utilisé par la classe de zk-SNARKs que nous allons étudier.

Sujet 31: zk-SNARKs II: Préparation de l'argument de connaissance Voir Sujet 30. Ce sujet présente les hypothèses cryptographiques sous-tendant les zk-SNARKs et la structure d'un zk-SNARK.

Sujet 32: zk-SNARKs III: Vérification de l'argument de connaissance Voir Sujet 30. Ce sujet présente la procédure de vérification d'un zk-SNARK.

Sujet 33: L'attaque quantique de Shor I: calcul quantique Les applications cryptographiques actuelles reposent sur le fait que le problème du logarithme discret, tout comme le problème de la factorisation des nombres premiers, est difficile, dans le sens que l'on conjecture qu'il n'est pas possible de les résoudre en un temps polynomial dans la taille du problème. Cette conjecture est fausse dans le domaine du calcul quantique, rendant toute la cryptographie actuelle vulnérable à un hypothétique ordinateur quantique. Le but de ce sujet et des trois suivant est de présenter l'algorithme de Shor, une solution efficace au problème du logarithme discret utilisant le calcul quantique. Ce premier sujet a pour but de poser les bases du calcul quantique.

Sujet 34: L'attaque quantique de Shor II: stratégie Voir Sujet 33. Nous étudierons la généralisation de l'algorithme de Shor par Boneh-Lipton, valable pour les courbes elliptiques. Dans ce sujet, nous présenterons les deux résultats clés sans preuve, et montrerons comment ils permettent de résoudre le problème du logarithme discret.

Sujet 35: L'attaque quantique de Shor III: preuve Voir Sujets 33 et 34. Dans ce sujet et le suivant, nous étudierons la preuve du premier résultat clé, à savoir le fait qu'il existe un algorithme quantique permettant de retrouver la structure linéaire cachée d'une fonction en un temps polynomial.

Sujet 36: L'attaque quantique de Shor IV: preuve Voir Sujet 35.