Jeudi 4 Avril 2024
La percée récente sur l’attaque du cryptosystème SIKE a montré l’utilité d’étudier et bien comprendre les courbes de genre 2 dont la jacobienne est un produit de courbes elliptiques. Les travaux de Kani font ressortir plus généralement des autres objet dans l’espace de modules de surfaces abéliennes et l’utilisation d’un invariant introduit sur le complex par Humbert permet de donner un cadre unifié pour appréhender aussi bien les produit de courbes elliptiques, la théorie CM, et les variétés de Shimura. Nous rappellerons des éléments de cette théorie et montrerons une application à la détermination de premiers de mauvaise réduction de certaines variétés abéliennes dans la direction de produire une formule à la Gross-Zagier.
Lundi 11 Mars 2024
Le Générateur Sac à dos, proposé en 1985 par Rueppel et Massey est un générateur pseudo aléatoire (PRNG) qui combine un premier PRNG faible, le LFSR, et un problème dur, le problème de la somme de sous-ensemble, dérivé du problème de sac à dos. Ce générateur a été attaqué avec succès par Knellwolf et Meyer en 2011. Je discuterai ici d’une variante plus efficace de cette attaque et des différentes attaques que j’ai pu proposer avec Damien Vergnaud et Charles Bouillaguet contre des variantes de ce générateur.
Jeudi 15 Février 2024
Mardi 13 Février 2024
Jeudi 25 Janvier 2024
Les fonctions thêta sont des fonctions analytiques spéciales, de plusieurs variables complexes, qui sont fondamentales pour l’étude des courbes elliptiques et des variétés abéliennes. Pour des applications algorithmiques, il faut être capable d’évaluer ces fonctions thêta en un point à de grandes précisions. Dans mon exposé, je présenterai un nouvel algorithme d’évaluation des fonctions thêta (joint avec Noam Elkies) fondé sur la formule de duplication. Cet algorithme est uniformément quasi-linéaire en la précision, fonctionne en toute dimension, et son implantation dans FLINT 3.1 est très performante en pratique.
Jeudi 7 Décembre 2023
Jeudi 23 Novembre 2023
Jeudi 21 Septembre 2023
Jeudi 22 Juin 2023
Jeudi 11 Mai 2023
Jeudi 30 Mars 2023
Jeudi 26 Janvier 2023
Vendredi 13 Janvier 2023
Jeudi 15 Décembre 2022
Dans cette présentation, nous nous intéressons à l’utilisation de la programmation par contraintes (CP) pour la résolution de problèmes de cryptanalyse différentielle. Nous nous intéressons plus particulièrement aux problèmes de recherche de caractéristiques différentielles (à clés liées ou non) pour les algorithmes de chiffrement symétriques Rijndael, AES et Midori. Nous avons également modélisé des attaques boomerangs pour Rijndael et généralisé cette méthode aux schémas Feistel. Cette nouvelle modélisation a été expérimentée sur les chiffrements WARP, Twine et LBlock-s. Pour résoudre ces différents problèmes, nous avons proposé de nouvelles techniques combinant des solveurs SAT et CP. Nous avons également introduit une nouvelle contrainte globale permettant de propager plus efficacement un ensemble de contraintes XOR lors de la recherche de caractéristiques différentielles tronquées. Ces nouveaux modèles nous ont permis d’améliorer les performances de solutions existantes et de découvrir de nouveaux distingueurs pour WARP (23 tours), Twine (15 et 16 tours) ainsi que pour LBlock-s (16 tours). Nous avons également trouvé de nouvelles attaques sur Rijndael (9 tours avec la version 128-160, 12 tours avec les versions 128-224 et 160-256) et sur WARP (26 tours).
Lundi 21 Novembre 2022
Calculer explicitement des isogénies entre variétés abéliennes a de nombreuses applications en cryptographie et théorie des nombres. Ces calculs peuvent devenir très coûteux dès que l’on dépasse le cas des courbes elliptiques, i.e. à partir de la dimension 2. Dans cet exposé, je montrerai qu’approcher ce problème via la théorie analytique des fonctions thêta permet toutefois d’obtenir des algorithmes utilisables en pratique. Je présenterai un algorithme quasi-linéaire et certifié pour l’évaluation de fonctions thêta en toute dimension, fondé sur les idées de Dupont et Labrande–Thomé. Je décrirai ensuite son implémentation et quelques applications précédemment inaccessibles.
Jeudi 10 Novembre 2022
Jeudi 27 Octobre 2022
Jeudi 20 Octobre 2022
Vendredi 24 Juin 2022
Mercredi 8 Juin 2022
Mardi 3 Mai 2022
Mardi 5 Avril 2022
Vendredi 25 Février 2022
Jeudi 16 Décembre 2021
Mercredi 24 Novembre 2021
Mardi 29 Juin 2021
Cet exposé présentera l’algorithme de sac-à-dos développé pour l’identification de nouveaux polluants athmosphériques en chimie analytique.
Étant donné un spectre de masse obtenu par Election Ionisation (EI) sur un spectromètre de masse à temps de vol (time-of-flight mass spectrometer TOF-MS), nous avons développé un algorithme de sac-à-dos pour identifier les formules chimiques possibles correspondant à chaque masse mesurée. L’incertitude de mesure fait que chaque masse est en fait un intervalle, et le sac-à-dos procure bien plus qu’une seule solution. Dans un deuxième temps nous avons développé un estimateur de vraisemblance et un algorithme d’optimisation basé sur un pseudo-graphe de fragmentation. La démarche a été conçue grâce à un ensemble de 36 substances connues, notamment de type CFC, PFC et HFC, et validée sur un ensemble de 21 substances (18 HFC de l’amendement de Kigali du protocole de Montréal et 3 HFOs). Des dizaines de nouveaux polluants athmosphériques non répertoriés ont été détectés grâce à ce travail.
Travail en commun avec Myriam Guillevic, Climate Gases Group, EMPA, ETHZ, Dübendorf, Suisse. Preprint hal-03176025.
Vendredi 25 Juin 2021
Les humains ont déjà perdu la bataille contre les machines dans de nombreux domaines, tels que les jeux, en particulier échecs, go et poker. Mais qu’en est-il de la cryptographie ? L’intelligence artificielle peut elle, là aussi, battre les humains ? Dans cette présentation, nous discuterons cette question à travers de récents résultats sur les applications de l’intelligence artificielle à la cryptanalyse.
Lundi 14 Juin 2021
Mardi 13 Avril 2021
Mardi 30 Mars 2021
A ce jour, le crible algébrique (NFS) est l’algorithme le plus performant permettant de factoriser des entiers et de calculer des logarithmes discrets dans un corps fini ; deux problèmes dont la difficulté est la clé de la sécurité de nombreux cryptosystèmes. Sous quelques hypothèses heuristiques, la complexité de la variante la plus classique de NFS pour factoriser un entier $N$ est : $\exp( (64/9)^{1/3} (\log N) ^ (1/3) (\log\log N) ^ {2/3} (1+f(N)) )$ où $f$ est une fonction qui tend vers $0$ lorsque $N$ tend vers l’infini. Cette formule est bien souvent simplifiée en considérant que $f = 0$, ce en particulier par les instances qui s’appuient dessus pour estimer les tailles de clé de cryptosystèmes couramment utilisés.
L’objet de nos travaux est d’évaluer la pertinence de cette simplification. Pour ce faire, on étudie f et on obtient pour cette fonction un développement asymptotique sous la forme d’une série bivariée évaluée en $\frac{\log\log\log N}{\log\log N}$ et $\frac{1}{\log\log N}$ et dont les coefficients peuvent être algorithmiquement calculés de manière exacte. Or, le domaine de convergence de ladite série se situe au delà de $\exp(\exp(25))$, bien au delà des valeurs de $N$ pertinentes pour des estimations pratiques. Il convient donc d’être prudent lorsqu’on se base sur des estimations pratiques faites en remplaçant $f$ par $0$.
Travaux réalisés avec Pierre-Jean Spaenlehauer et Emmanuel Thomé.
Vendredi 12 Mars 2021
La sécurité des systèmes cryptographiques basés sur des courbes elliptiques est sous-tendue par la difficulté du problème du logarithme discret sur courbes elliptiques (ECDLP). Nous nous concentrons sur l’attaque de calcul d’index pour le cas des courbes elliptiques définies sur des extensions de corps finis de degré premier. Ainsi, la première phase du calcul d’index, phase de recherche de relations, consiste à résoudre des systèmes d’équations obtenus à partir de polynômes de Semaev, dont les zéros représentent des coordonnées de points. La résolution de ces systèmes répond au problème de décomposition de points. Il existe des nombreuses méthodes algébriques pour la résolution de ces systèmes, comme, par exemple, les techniques de bases de Gröbner, la famille d’algorithmes XL, la recherche exhaustive et les méthodes hybrides. En revanche, nous proposons une méthode de résolution utilisant un solveur SAT dédié.
Il s’agit d’un travail commun avec Sorina Ionica et Gilles Dequen.
Mardi 16 Février 2021
Mardi 9 Février 2021
Lundi 18 Janvier 2021
Jeudi 13 Février 2020
Jeudi 6 Février 2020
Lundi 27 Janvier 2020
Vendredi 17 Janvier 2020
Lundi 13 Janvier 2020
Jeudi 12 Décembre 2019
Jeudi 4 Juillet 2019
Mardi 4 Juin 2019
Vendredi 24 Mai 2019
Jeudi 23 Mai 2019
Mardi 14 Mai 2019
Mardi 2 Avril 2019
Jeudi 14 Février 2019
Jeudi 31 Janvier 2019
Lundi 28 Janvier 2019
Jeudi 13 Décembre 2018
Jeudi 29 Novembre 2018
Vendredi 7 Septembre 2018
Le comptage de points de courbes algébriques est une primitive essentielle en théorie des nombres, avec des applications en cryptographie, en géométrie arithmétique et pour les codes correcteurs. Dans cette thèse, nous nous intéressons plus particulièrement au cas de courbes hyperelliptiques définies sur des corps finis de grande caractéristique $p$. Dans ce cas de figure, les algorithmes dérivés de ceux de Schoof et Pila sont actuellement les plus adaptés car leur complexité est polynomiale en $\log p$. En revanche, la dépendance en le genre $g$ de la courbe est exponentielle et se fait cruellement sentir même pour $g=3$.
Nos contributions consistent principalement à obtenir de nouvelles bornes pour la dépendance en $g$ de l’exposant de $\log p$. Dans le cas de courbes hyperelliptiques, de précédents travaux donnaient une borne quasi-quadratique que nous avons pu ramener à linéaire, et même constante dans le cas très particuliers de familles de courbes dites à multiplication réelle (RM).
En genre 3, nous avons proposé un algorithme inspiré de ceux de Schoof et de Gaudry-Harley-Schost dont la complexité, en général prohibitive, devient très raisonnable dans le cas de courbes RM. Nous avons ainsi pu réaliser des expériences pratiques et compter les points d’une courbe hyperelliptique de genre 3 pour un $p$ de 64 bits.
Lundi 11 Juin 2018
Mardi 5 Juin 2018
Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau $R$ quelconque, le produit sur $R$[$X$] des polynômes $a_0 + a_1 X$ et $b_0$ + $b_1 X$, pour tous $a_0$, $a_1$, $b_0$ et $b_1$ dans $R$, peut être calculé en seulement trois et non pas quatre multiplications sur $R$: $(a_0 + a_1 X) (b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2$, avec les trois produits $m_0 = a_0b_0$, $m_1 = a_1b_1$, et $m_2 = (a_0 + a_1)(b_0 + b_1)$. De la même manière, l’algorithme de Strassen permet multiplier deux matrices $2n\times 2n$ en seulement sept produits de matrices $n\times n$.
Les deux exemples précédents tombent dans la catégorie des applications bilinéaires: des fonctions de la forme $\Phi: K^{m} \times K^{n} \rightarrow K^{l}$, pour un corps donné $K$, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire $\Phi$, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L’objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d’attaques ont été suivis.
Un premier aspect de cette thèse est l’étude du problème du calcul de la complexité bilinéaire sous l’angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur $\mathbb{F}_{2}$, pour le produit de polynômes modulo $X^{5}$ et le produit de matrices 3x2 par 2x3.
Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d’algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de $n$ bits en $O(n \log n 2^{O(\log^{*}n)})$, où $\log^{*}$ est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d’une conjecture de théorie des nombres est proposé, reposant sur la FFT et l’utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d’obtenir une estimation en $O(n \log n 4^{\log^{*}n})$).
Lundi 4 Juin 2018
Vendredi 1 Juin 2018
Jeudi 29 Mars 2018
Jeudi 1 Février 2018
Lundi 11 Décembre 2017
Mardi 7 Novembre 2017
Dans cette exposé, je souhaite présenter l’état de l’art sur l’énumération de points d’un réseau autant en théorie qu’en pratique, afin de repérer des applications potentielles pour les algorithmes de crible algébrique.
Il semble en effet que des algorithmes dédiés aient été developpés dans le contexte du Crible Algébrique pour les réseaux de petites dimensions (2 ou 3), parfois en sacrifiant de précieuses informations géométriques au profit d’une structure de données simplifiée. De plus, ces approches spécialisées semblent difficiles à généraliser à de plus grandes dimensions, ce qui serait pourtant nécessaire pour le logarithme discret en moyenne caractéristique.
L’exposé se veut didactique et interactif, afin d’identifier de nouveaux outils utiles au Crible Algébrique.
Jeudi 21 Septembre 2017
Depuis 1996 et les premiers travaux de Kocher sur le sujet, les développeurs d’algorithmes cryptographiques savent qu’ils doivent impérativement veiller à protéger leurs implémentations contre les attaques par canaux cachés. Ces attaques visent aussi bien les implémentations matérielles que logicielles et s’appliquent aux algorithmes symmétriques et asymétriques. Après un rapide tour d’horizon de ces attaques, je présenterai un nouvel algorithme de multiplication scalaire sur courbe elliptique concu pour résister à la plupart des attaques par observation pour un surcoût inférieur aux contremesures classiques (ou presque).
Mercredi 5 Juillet 2017
Jeudi 10 Novembre 2016
Vendredi 17 Juin 2016
La génération de nombres aléatoires publics et fiables est nécessaire à de nombreux protocoles de cryptographie. Il a notamment été suggéré de s’appuyer sur l’imprédictabilité inhérente des chaines de blocs pour bâtir une source publique d’aléa, comme un phare aléatoire, par exemple, comme nous le verrons dans cet exposé. C’est ici qu’interviennent les monnaies électroniques décentralisées, comme le Bitcoin. En effet l’entropie de la chaine du registre public sousjacent au Bitcoin a été utilisée pour créer des loteries, puis proposée par la suite pour d’autres applications variant de la rédaction de contrats intelligents à l’audit d’élections.
La malléabilité des chaines de blocs montre cependant qu’un adversaire peut manipuler ces nombres aléatoires, même si celui-ci est tenu par des contraintes financières étroites et qu’il ne dispose que d’une puissance de calcul limitée.
En passant, cette analyse propose une généralisation des mots de Dyck dont nous verrons ici une illustration, si nous avons le temps.
Il s’agit d’un travail commun avec Benjamin Wesolowski.
Mardi 19 Avril 2016
La représentation modulaire des nombres ou RNS (de l’anglais residue number system) permet de représenter les entiers en les découpant en morceaux indépendants grâce au théorème chinois des restes. Cette représentation est notamment utilisée pour accélérer les calculs sur les grands nombres en cryptographie asymétrique, et devient de plus en plus populaire pour cette application. Cet exposé présente dans un premier temps les idées directrices de l’utilisation du RNS pour la cryptographie et certaines de ses particularités. Ensuite, des propositions algorithmiques récentes seront présentées sur le calcul modulaire RNS et plus particulièrement sur la multiplication modulaire dans un contexte de cryptographie sur courbes elliptiques.
Lundi 23 Novembre 2015
Lundi 16 Novembre 2015
On utilise une version de la fameuse méthode Viro pour construire des systèmes polynomiaux avec beaucoup de solutions positives. On montre que si un polytope P entier admet une triangulation régulière unimodulaire et bipartite, alors il existe un système polynomial dont toutes les équations ont P comme polytope de Newton et dont toutes les solutions dans le tore complexe sont en fait contenues dans l’orthant positif (système maximalement positif). On exhibe plusieurs familles de polytopes connues admettant de telles triangulations. Tous ces nouveaux exemples vérifient une conjecture faite par l’orateur sur les systèmes maximalement positifs. Si le temps le permet, on discutera aussi d’une construction de systèmes avec beaucoup de solutions positives utilisant une triangulation du polytope cyclique. C’est un travail en commun avec Pierre-Jean Spaenlehauer, INRIA Nancy.
Mercredi 14 Octobre 2015
Mercredi 9 Septembre 2015
Jeudi 5 Février 2015
La méthode de Chudnovsky & Chudnovsky fournit, aujourd’hui, les meilleures bornes de complexité bilinéaire pour la multiplication dans les grandes extensions de corps finis. Elle repose sur l’interpolation sur les courbes algébriques. Lorsqu’on fixe une courbe, on peut espérer construire des algorithmes qui atteignent au mieux une certaine complexité (avec des exceptions). Il semble qu’on arrive souvent à atteindre ce seuil. Nous illustrerons une méthode explicite pour y arriver.
Jeudi 20 Novembre 2014
Jeudi 20 Novembre 2014
Nous nous proposons de décrire nos travaux de thèse sur le calcul des polynômes modulaires en genre 2. Ces polynômes dépendent des invariants d’Igusa, qui sont une généralisation de la fonction $j$ dans le genre 1, et permettent d’obtenir toutes les variétés abéliennes isogènes à une variété abélienne donnée. Dans un premier temps, nous reviendrons sur cette notion de polynôme en genre 1 et 2 et discuterons de leur calcul par une approche du type évaluation/interpolation. Dans un second temps, nous expliquerons comment généraliser ces polynômes à d’autres invariants et décrirons certaines de leurs propriétés, notamment le lien entre le dénominateur d’un coefficient du polynôme modulaire et les surfaces de Humbert.
Lundi 17 Novembre 2014
Jeudi 23 Octobre 2014
Jeudi 11 Septembre 2014
Jeudi 3 Juillet 2014
Jeudi 19 Juin 2014
L’idée d’utiliser la difficulté du décodage d’un code aléatoire comme primitive de cryptographie à clé publique à été introduite par McEliece en 1978. Le schéma de McEliece présente l’intérêt de résister aux attaques d’un hypothétique ordinateur quantique. De plus, ses vitesses de chiffrement et de déchiffrement sont bien meilleures que celles de schémas basés sur les problèmes de factorisation ou du logarithme discret. En contrepartie il présente l’inconvénient de nécessiter de très grandes tailles de clés.
La proposition originelle de McEliece repose sur l’utilisation des codes de Goppa binaires. Par la suite, d’autres familles de codes ont été proposées pour ce schéma de chiffrement dans le but de réduire la taille des clés. La principale exigence est d’avoir un algorithme de décodage rapide et corrigeant beaucoup d’erreurs. Par exemple (et cette liste est loin d’être exhaustive), les codes de Reed-Solomon généralisés, leur sous-codes et les codes Reed-Müller binaires. Tous ces systèmes sont soumis à des attaques en temps polynomial ou sous-exponentiel.
Les codes géométriques sont des codes d’évaluation de fonctions rationnelles sur des courbes algébriques. Leur bonne distance minimale ainsi que l’existence d’algorithmes de décodage efficace en fait d’intéressants candidats pour le schéma de McEliece, ce qui a motivé Janwa et Moreno à les proposer à des fins cryptographiques. Faure et Minder ont proposé une attaque structurelle de ce systèmes lorsque les codes proposés sont construit à partir de courbes de genre $g$ < 3. Leur approche rend toutefois très difficile toute extension au cas de courbes de genre supérieur. Dans cet exposé je présenterai une attaque polynomiale du schéma de McEliece basé sur les codes géometriques.
Jeudi 24 Avril 2014
L’évaluation d’un polynôme en une valeur peut se faire au moyen de différents schémas d’évaluation. Cet exposé présentera la bibliothèque fast_polynomial écrite en cython, interfacée pour sage et python. Cette implantation efficace d’évaluation de polynômes reprend et améliore en pratique les algorithmes rapides de type diviser pour régner. L’abstraction sous-jacente permet en outre de mêler facilement et efficacement différents schémas d’évaluation. La structure de donnée implantée maintient une faible utilisation mémoire et permet d’exploiter le parallélisme des architectures modernes. Je présenterai enfin les limitations et les améliorations possibles de la bibliothèque.
Jeudi 13 Mars 2014
Mercredi 26 Février 2014
Soit $B \geq 2$. Un entier $n$ est dit $B$-friable si son plus grand facteur premier, noté $P^{+}(n)$ satisfait $P^{+}(n) \leq B$. Soit $F \in \mathbb{Z}[X_1, X_2]$ une forme binaire. Dans cet exposé, on s’intéressera à l’étude asymptotique du cardinal $$ \Psi_{F}^{(1)}(X, B) = \left|{ 1 \leq x_1, x_2 \leq X\ :\ \gcd(x_1, x_2) = 1\ \text{et}\ P^{+}(F(x_1, x_2)) \leq B }\right|.$$ On établira tout d’abord des formules asymptotiques pour $\Psi_{F}^{(1)}(X, B)$ lorsque $F$ est de degré 3, dans une large région en $(X, B)$. Dans un second temps, on étudiera la dépendance en $F$ d’une telle quantité. Cette deuxième partie, directement liée à la phase de sélection polynomiale dans l’algorithme de factorisation NFS, est le fruit d’un travail en collaboration avec Razvan Barbulescu.
Jeudi 19 Décembre 2013
Vendredi 6 Décembre 2013
La sécurité des protocoles cryptographiques repose sur des problèmes difficiles et évolue en fonction des connaissances que l’on a sur ceux-ci. Cet exposé s’intéresse à l’un de ces problèmes de théorie des nombres : le problèmes du logarithme discret dans les corps finis.
L’objet de cet exposé est d’apporter un rapide aperçu des algorithmes actuels pour les corps de moyennes et grandes caractéristiques en vue d’étendre le crible spécial de corps de nombres (SNFS), qui ne portait, jusqu’ici, que sur des corps de cardinal premier. Notre SNFS s’étend sur tout le domaine d’exécution du crible de corps de nombres général (NFS), et en améliore la complexité asymptotique. Il permet le calcul de logarithmes discrets dans des corps finis dont la caractéristique admet une représentation creuse adéquate, ce qui autorise en particulier son application sur des corps finis issus de procédés de couplage.
Il s’agit d’un travail commun avec Antoine Joux.
Jeudi 28 Novembre 2013
Les applications en calcul exact, utilisent l’élimination de Gauss non seulement pour la résolution de systèmes réguliers, comme en calcul numérique, mais aussi, lorsque la matrice est singulière, pour calculer sa forme échelonnée. La structure en échelon, aussi appelée profil de rang en colonne, indique le premier sous-ensemble de vecteurs colonnes linéairement indépendants dans la matrice. Elle joue par exemple un rôle important dans le calcul de bases de Gröbner à partir de la matrice de Macaulay. Plus généralement nous définirons la matrice de profil de rang qui caractérise les profils de rangs ligne et colonne de toute sous-matrice dominante d’une matrice donnée.
La mise en oeuvre efficace de l’élimination de Gauss fait appel à de nombreuses variantes algorithmique concernant la découpe en blocs, le choix de permutation, la recherche des pivots ou l’ordonnancement des mises à jour. Nous présenterons des conditions suffisantes et le plus souvent nécessaires pour qu’un algorithme d’élimination puisse révéler les profils de rang en ligne, en colonnes ainsi que la matrice de profil de rang. En corollaire, nous présenterons deux nouveaux algorithmes, l’un récursif par découpe en quatre quadrant, l’autre itératif servant de cas de base, qui calculent une décomposition PLUQ révélant la matrice de profil de rang, de complexité sous-cubique, sensible au rang et en place.
La mise en oeuvre pour le calcul dans des petits corps finis améliore l’efficacité des implantations existantes et ouvre des perspectives nouvelles pour le parallélisme.
Jeudi 7 Novembre 2013
Lorsque l’on effectue le produit de deux éléments de $\mathbb{F}_{q^n}$, on distingue deux types d’opérations élémentaires dans $\mathbb{F}_{q}$ : les opérations scalaires (additions, multiplications par des constantes) comptabilisées par la complexité scalaire, et les opérations bilinéaires (multiplications de deux éléments de $\mathbb{F}_{q}$ qui dépendent chacun d’un des deux éléments de $\mathbb{F}_{q^n}$ dont on effectue le produit) comptabilisées par la complexité bilinéaire. Cette dernière notion de complexité est alors indépendante de la base de $\mathbb{F}_{q^n}$ sur $\mathbb{F}_{q}$ choisie.
L’algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky est actuellement le meilleur algorithme de multiplication connu en terme de complexité bilinéaire : il a permis d’établir que cette complexité est linéaire en le degré n de l’extension considérée, et en fournit désormais les meilleures bornes connues dans le cas d’extensions de degré grand relativement au cardinal du corps de base. On présentera donc cet algorithme ainsi que certaines de ses améliorations récentes, et on montrera comment il permet d’obtenir des bornes de complexité bilinéaire de la multiplication dans $\mathbb{F}_{q^n}$ sur $\mathbb{F}_{q}$, uniformes en $n$.
Vendredi 19 Juillet 2013
La résolution de systèmes linéaires creux intervient dans beaucoup de domaines. Un des algorithmes les plus utilisés est celui de Wiedemann. Après un bref rappel de l’algorithme de Wiedemann par blocs, nous introduirons des nouveaux types de blocs permettant d’améliorer la complexité et d’obtenir un meilleur parallélisme. Cependant, l’opération principale est le produit matrice vecteur, nous présenterons un format de stockage de la matrice qui permet d’obtenir de bonne performance sur CPU. Finalement nous arborderons des méthodes pour réordonner les éléments non nuls afin de les concentrer.
Mercredi 17 Juillet 2013
Il existe plusieurs algorithmes pour calculer le symbole de Jacobi en temps quasi linéaire. L’objectif de mon stage était d’adapter un de ces algorithmes (l’algorithme de Richard Brent et Paul Zimmermann) en un algorithme quasi linéaire pour calculer le symbole de résiduosité cubique, qui est l’analogue du symbole de Jacobi pour les cubes.
Mardi 16 Juillet 2013
Pendant près de 35 ans, l’algorithme le plus rapide qui était connu permettait de multiplier des grands nombres de taille $n$ en un temps $O(n\log n \log \log n)$. Il s’agissait de l’algorithme de Schönhage-Strassen. En 2007, Martin Fürer publie un article où il explicite un algorithme permettant d’obtenir une complexité en $O(n \log n 2^{O(\log^{*}n)})$. Un des problèmes théoriques est de savoir si on peut descendre à $O(n \log n \log^{*}n)$ voire $O(n \log n)$, sachant que la borne inférieure $O(n \log n)$ n’est à ce jour qu’une conjecture. Un problème plus pratique est de savoir comment implémenter l’algorithme de Fürer de sorte à concurrencer les implémentations actuelles de Schönhage-Strassen. Ces deux problèmes seront l’objet de la présentation.
Lundi 15 Juillet 2013
Mardi 28 Mai 2013
Durant la seconde moitié du 20ème siècle, les systèmes de numération basés sur les développements en fractions continues ont été utilisés pour démontrer des propriétés sur la répartition de la suite $(n\alpha)_{n\in\mathbb{N}}$ modulo 1, avec $\alpha$ réel. Dans cet exposé, nous allons utiliser certaines de ces propriétés pour deux applications.
La première application est la recherche de cas difficiles à arrondir de fonctions élémentaires. Plus particulièrement, nous nous intéresserons à l’algorithme de Lefèvre, son lien avec le théorème des trois longueurs, et son comportement divergent sur GPU. Nous proposerons ainsi un nouvel algorithme avec un flot de contrôle plus régulier permettant une accélération de 3.44x sur GPU par rapport au déploiement de l’algorithme de Lefèvre. Il s’agit d’un travail en collaboration avec Pierre Fortin et Stef Graillat.
La seconde application est l’arithmétique modulaire. Nous proposerons des algorithmes de multiplication et de division modulaires de complexité quadratique reposant sur l’écriture dans des bases issues de développements en fractions continues. Ces algorithmes se basent donc sur l’algorithme d’Euclide étendu et présentent l’avantage d’intégrer la réduction.
Vendredi 5 Avril 2013
Jeudi 28 Mars 2013
Cet exposé commencera par une introduction aux algorithmes génériques de calcul de logarithmes discrets. Ensuite, nous nous intéresserons aux algorithmes de calcul d’index dans le cas le plus simple : celui de la petite ou moyenne caractéristique. Après une présentation des algorithmes précédemment connus, nous montrerons comment une transformation simple de ces algorithmes permet une amélioration importante de la complexité asymptotique et conduit à de nouveaux records de calcul de logarithmes discrets.
Vendredi 15 Mars 2013
Vendredi 22 Février 2013
Cette exposé traite de la synchronisation de systèmes dynamiques dans une maître-esclave. Il s’agit d’un scénario typiquement rencontré en cryptographie. Une attention spécifique est portée sur l’autosynchronisation, comportement qui caractérise la synchronisation par le simple couplage maître-esclave et donc en l’absence de tout contrôle extérieur. Elle joue un rôle majeur dans les communications impliquant des chiffreurs par flot autosynchronisants. L’étude de l’autosynchronisation dans le contexte cryptographique s’appuie sur la théorie du contrôle. Un lien original entre l’autosynchronisation et le principe de chiffrement/déchiffrement en cryptographie est mis en évidence. Il fait appel à la propriété de platitude des systèmes dynamiques, un concept emprunté à l’automatique. On montre que les systèmes dynamiques plats définissent complètement l’ensemble des systèmes autosynchronisants et permettent d’élargir les structures existantes des chiffreurs autosynchronisants. La platitude est tout d’abord étudiée pour deux types de systèmes non linéaires : les systèmes linéaires commutés et à paramètres variants (LPV). La caractérisation des sorties plates s’appuie sur le concept de semigroupes nilpotents et un algorithme performant est proposé. Par la suite, l’autosynchronisation est étudiée dans le contexte booléen privilégié en cryptographie. On caractérise entièrement l’ensemble des fonctions booléennes autosynchronisantes. On montre qu’elle peuvent être classées en trois catégories et que jusque là, seule la première était connues et utilisée.
Mercredi 13 Février 2013
Un jeu de tuiles apériodique est une collection finie de pièces de puzzles qui permettent de couvrir le plan, mais pas de façon périodique. De tels jeux sont fondamentaux dans l’étude des pavages et on peut en général relier à chaque grand résultat de la théorie la découverte d’une nouvelle façon de créer un jeu apériodique.
Le plus petit connu contient 13 tuiles et a été inventé par Culik suivant une technique de Kari et utilise une propriété arithmétique très simple: Si on part d’un réel non nul et qu’on le multiplie par 2 ou divise par 3 un certain nombre de fois, on ne retombera jamais sur le réel initial.
Je vais présenter ici un programme que j’ai réalisé et qui prouve en temps humain qu’il faut au moins 10 tuiles pour réaliser un jeu apériodique. Le même programme peut sans doute montrer qu’il faut au moins 11 tuiles, mais on se heurte alors à deux difficultés: (a) le temps d’exécution commence à être inhumain (b) certains jeux à 10 tuiles ont l’air d’être apériodiques, et il faut montrer “à la main” qu’ils ne le sont pas.
Jeudi 31 Janvier 2013
Jeudi 17 Janvier 2013
Les systèmes polynomiaux multi-homogènes, déterminantiels et booléens jouent un rôle prépondérant dans plusieurs applications en Cryptologie, en Géométrie Réelle ou en Optimisation. Dans cet exposé, par des méthodes de calcul de bases de Gröbner et sous des hypothèses de généricité sur les coefficients de ces systèmes, je présente de nouvelles bornes de complexité asymptotique pour leur résolution :
- dans le cas déterminantiel et dans le cas bilinéaire, ces bornes permettent d’identifier des sous-familles de systèmes pour lesquelles la complexité de résolution est polynomiale en le nombre de solutions ;
- pour les systèmes quadratiques booléens, un nouvel algorithme de résolution est proposé. Pour un système de $n$ équations en $n$ variables, l’espérance de la complexité d’une variante probabiliste est $O(2^{0.792n})$, sous des hypothèses algébriques sur le système d’entrée. Ceci permet de résoudre exponentiellement plus rapidement que par recherche exhaustive.
L’obtention de ces bornes passe par une analyse de la structure algébrique des systèmes ; ceci conduit à des formules explicites pour la série de Hilbert générique des idéaux associés. Cette analyse sera illustrée par des applications en Cryptologie (cryptanalyse de MinRank, HFE et QUAD).
Travail commun avec Jean-Charles Faugère et Mohab Safey El Din (systèmes déterminantiels et multi-homogènes) et avec Magali Bardet, Jean-Charles Faugère et Bruno Salvy (systèmes booléens).
Jeudi 20 Décembre 2012
Jeudi 20 Décembre 2012
Jeudi 29 Novembre 2012
Pour la phase de sélection polynomiale, CADO-NFS utilise l’algorithme présenté par Kleinjung au workshop CADO en 2008. On décrira en détail cet algorithme, ainsi que les détails d’implantation dans CADO-NFS. Travail en commun avec Shi Bai (Australian National University) et Alain Filbois (SED Inria Nancy - Grand Est).
Vendredi 23 Novembre 2012
Le produit de polynômes et le produit de matrices sont deux des opérations les plus élémentaires en mathématiques ; l’étude de la complexité de ces calculs est au centre de l’informatique. Dans cet exposé, nous nous intéressons à la complexité de la multiplication d’opérateurs différentiels linéaires. Ces objets algébriques encodent les équations différentielles linéaires, et forment un anneau non commutatif qui partage de nombreuses propriétés avec l’anneau commutatif des polynômes usuels.
Pourtant, l’étude algorithmique des opérateurs différentiels linéaires est actuellement beaucoup moins avancée que dans le cas polynomial : la complexité de la multiplication a été abordée que récemment, mais pas complètement résolu. Le but de ce travail est de faire un pas pour combler cette lacune, et à résoudre une question ouverte posée par van der Hoeven.
Ce travail est commun avec Alin Bostan (INRIA) et Joris van der Hoeven (CNRS).
Jeudi 15 Novembre 2012
Mardi 6 Novembre 2012
Certains problèmes relatifs aux courbes hyperelliptiques de genre 2 sur les corps finis peuvent être résolus algorithmiquement en effectuant des calculs dans un certain corps de nombre associé à la courbe hyperelliptique. Le corps considéré est alors un corps CM quartique, c’est à dire une extension quadratique imaginaire d’un corps quadratique réel. Nous présenterons des algorithmes destinés spécifiquement à accélérer les calculs dans ces corps.
Jeudi 27 Septembre 2012
Vendredi 20 Juillet 2012
Vendredi 29 Juin 2012
Vendredi 29 Juin 2012
Mercredi 20 Juin 2012
L’utilisation des courbes elliptiques et hyperelliptiques en cryptographie nécessite de pouvoir calculer en un temps raisonnable l’ordre de la jacobienne de la courbe. T. Satoh proposa à Eurocrypt 2009 un algorithme polynomial pour vérifier si l’ordre de la jacobienne d’une courbe hyperelliptique de la forme $Y^{2} = X^{5} + aX^{3} + bX$ définie sur un corps fini $\mathbb{F}_{q}$ admet un grand facteur premier. Son approche consiste à obtenir différents candidats pour la fonction zeta de la jacobienne sur $\mathbb{F}_{q}$ en partant de la fonction zeta de la jacobienne sur une extension où la jacobienne se partage en deux courbes elliptiques. L’approche de T. Satoh se généralise pour obtenir l’expression exacte de la fonction zeta de jacobienne de courbes hyperelliptiques de genre 2 de la forme ci-dessus et $Y^{2} = X^{6} + aX^{3} + b$. Nous avons obtenu les expressions exactes des fonctions zeta par des résolutions successives d’équations de degré 2.
Les systèmes à bases de couplages utilisent des courbes elliptiques particulières présentant un petit degré de plongement par rapport à un grand sous-groupe d’ordre premier. Les formules explicites d’ordre des jacobiennes nous permettent de compléter les deux algorithmes de Freeman et Satoh pour générer des jacobiennes pour les couplages. Notre méthode utilise celles proposées pour construire des courbes elliptiques pour les couplages (la méthode de Cocks-Pinch et celle de Brezing-Weng).
Les formules exactes permettent de voir que les restrictions faites précédemment sur le degré de plongement sont valables pour une courbe elliptique et peuvent être réduites pour une jacobienne. Pour illuster notre méthode nous présentons des constructions intéressantes de paramètre $\rho$ environ 4 pour une méthode à la Cocks-Pinch et environ 3 pour une méthode à la Brezing-Weng.
Mercredi 25 Avril 2012
SSL/TLS est un protocole ayant pour but de créer un canal de communication authentifié, protégé en confidentialité et en intégrité. L’objectif initial de SSL/TLS était la sécurisation du protocole HTTP, mais son champ d’application s’est élargi depuis : protection d’autres services (SMTPS, LDAPS, etc.), création de réseaux privés virtuels (VPN), sécurisation de réseaux sans-fil (EAP-TLS).
Après un rapide historique des différentes versions de SSL/TLS et une description rapide du protocole, je présenterai un panorama des attaques connues, qu’elles portent sur le protocole en lui-même, les algorithmes cryptographiques, ou les certificats mis en oeuvre. Cette énumération des vulnérabilités de SSL/TLS permettra de déduire des recommandations pour une utilisation sécurisée de SSL/TLS.
Mardi 3 Avril 2012
Vendredi 30 Mars 2012
Mardi 20 Mars 2012
Mercredi 14 Mars 2012
La présentation portera sur la problématique générale des attaques sur les composants cryptos par observation de leurs canaux physiques (courant et champ électro-magnétique). L’accent sera porté sur l’approche par SNR ou rapport signal à bruit, une méthode permettant de quantifier la résistance d’une implémentation donnée inspirée de la théorie des communications numériques [Mangard $et al.$, 2004]. On montrera comment il est possible de déterminer un ordre de grandeur théorique du nombre de mesures nécessaires à casser une implémentation donnée.
On présentera ensuite les principales familles de contre-mesures existantes (la désynchronisation, le masquage, les technologies alternatives au CMOS) et leurs effets respectifs en terme de rapport signal-à-bruit. On présentera en passant deux solutions de masquage de l’algorithme AES, une logicielle par recalcul de la boîte S, l’autre matérielle reposant sur sa définition algébrique.
Mercredi 7 Mars 2012
Cet exposé a pour objectif de présenter quelques points intéressants de l’implémentation de l’algorithme de recherche exhaustive de formules pour le calcul d’applications bilinéaires présenté aux JAV 2012.
Mercredi 29 Février 2012
Jeudi 2 Février 2012
Vendredi 20 Janvier 2012
Mercredi 30 Novembre 2011
Vendredi 28 Octobre 2011
Jeudi 6 Octobre 2011
Jeudi 29 Septembre 2011
Mercredi 13 Juillet 2011
L’algorithme FFS, utilisé pour calculer le logarithme discret dans un corps fini, comporte une étape appelée cofactorisation. Il s’agit de traiter un grand nombre de couples de polynômes en testant leur friabilité et en les factorisant le cas échéant. Nous verrons comment l’entrée de cette étape a été modélisée et quelles stratégies ont été mises en place.
Jeudi 30 Juin 2011
Jeudi 9 Juin 2011
Nous rappellerons tout d’abord quelques rudiments de la théorie des codes correcteurs et des codes géométriques. Nous nous focaliserons ensuite sur le problème classique (et souvent difficile) de rechercher de bons codes de longueur $n$ à coefficients dans $\mathbb{F}_{2}$. Une approche classique consiste à choisir un bon code défini sur une extension $\mathbb{F}_{2^{m}}$ de $\mathbb{F}_{2}$ et de le « descendre » sur $\mathbb{F}_{2}$ via une opération arithmétique classique (restriction, trace, etc…)
Si le code défini sur $\mathbb{F}_{2^{m}$ est un code géométrique construit sur une courbe de genre 0 et judicieusement choisi, l’opération de restriction à $\mathbb{F}_{2}$ donne des codes bien meilleurs que dans le cas « générique ». Dans cet exposé, nous présenterons une généralisation de cette approche aux courbes de genre quelconque basée sur une utilisation l’opérateur de Cartier. Cette approche permet ainsi de construire d’intéressantes familles asymptotiquement bonnes de codes sur $\mathbb{F}_{2}$.
Mardi 7 Juin 2011
L’implantation d’une expression arithmétique donnée en machine soulève plusieurs questions, notamment quant à la vitesse et la précision des calculs en arithmétique approchée. L’outil CGPE (Code Generation for Polynomial Evaluation) a été conçu dans le but de trouver des schémas d’évaluation satisfaisants pour un polynôme approximant une fonction donnée. Ces schémas doivent être rapides sur des processeurs entiers de type VLIW, et suffisamment précis pour permettre d’en déduire l’arrondi correct, au sens du standard IEEE 754-2008, ou l’arrondi fidèle pour la fonction de départ.
Dans cet exposé, nous verrons comment les schémas d’évaluation sont définis et manipulés au sein de CGPE. Ensuite, je montrerai comment l’ajout de contraintes numériques permet d’accéler la recherche dans CGPE. Enfin, je parlerai de la généralisation de cette approche pour s’attaquer au problème de minimisation du nombre d’opérations d’un type donné.
Lundi 30 Mai 2011
Lundi 30 Mai 2011
Mercredi 18 Mai 2011
Jeudi 5 Mai 2011
La réduction forte de réseaux est la clé de la plupart des attaques contre les cryptosystèmes basés sur les réseaux. Entre la réduction HKZ, forte mais trop coûteuse, et la réduction LLL, plus faible mais rapide, existent plusieurs tentatives d’obtenir des compromis efficaces. Celle qui semble atteindre le meilleur rapport temps/qualité est la réduction BKZ, introduite par Schnorr et Euchner en 1991. Cependant, aucune borne de complexité raisonnable sur cet algorithme n’était connue jusqu’à maintenant. Nous prouvons qu’après $\widetilde{O}(n^{3}/k^{2})$ appels à une routine de HKZ-réduction, $\operatorname{BKZ}_{k}$ renvoie une base telle que la norme du premier vecteur est bornée par $\sim \gamma_{k}^{n/2(k-1)} \times \det(L)^{1/n}$. Le principal outil de la preuve est l’analyse d’un système dynamique linéaire associé à cet algorithme.
Jeudi 21 Avril 2011
Jeudi 14 Avril 2011
Nous montrerons que certaines questions de combinatoire énumérative peuvent être traitées de façon systématique en utilisant une approche de type « mathématiques expérimentales » guidée par des algorithmes modernes du calcul formel. Nous décrirons la découverte et la preuve assistées par ordinateur de l’algébricité de la série génératrice des chemins confinés au quart de plan et utilisant des pas de longueur un vers l’est, l’ouest, le sud-ouest, ou le nord-est.
Mercredi 30 Mars 2011
Jeudi 17 Février 2011
Jeudi 27 Janvier 2011
L’addition sur les courbes d’Edwards a apporté le premier exemple de loi d’addition qui puisse être définie, dans certains cas, quels que soient les points rationnels choisis. Cela a mené à considérer la notion de $k$-complétude pour les lois d’addition sur une variété abélienne $A$/$k$. Je présenterai les résultats obtenus avec David Kohel et Christophe Ritzenthaler. Nous montrons notamment la non existence d’une seule loi géométriquement complète et, si le groupe de Galois absolu de $k$ est infini, l’existence d’un plongement projectif de $A$ muni d’une loi d’addition $k$-complète.
Vendredi 21 Janvier 2011
Jeudi 20 Janvier 2011
Jeudi 9 Décembre 2010
Les processeurs graphiques (GPU) actuels sont des architectures parallèles qui offrent une importante puissance de calcul disponible à faible coût. Il est possible de détourner leur usage pour réaliser du calcul non graphique, donnant lieu au domaine du calcul généraliste sur processeur graphique (GPGPU).
Nous considérons d’une part des techniques logicielles pour tirer parti de l’ensemble des opérateurs arithmétiques spécifiques aux GPU dans le cadre du calcul scientifique, et d’autre part des adaptations matérielles aux GPU afin d’exécuter plus efficacement les applications généralistes.
En particulier, nous identifions la régularité comme une opportunité générale d’optimisation des architectures parallèles, et exposons son potentiel par la simulation d’une architecture GPU existante.
Nous considérons en particulier deux alternatives permettant d’exploiter cette régularité. D’une part, nous mettons au point un mécanisme matériel dynamique de dé-duplication des registres qui vise à améliorer l’efficacité énergétique des unités de calcul. D’autre part, nous présentons une analyse statique opérée à la compilation, qui permet de simplifier le matériel dédié au contrôle dans les GPU.
Jeudi 2 Décembre 2010
… ou le problème des courbes de genre 1 sans point réel.
Jeudi 25 Novembre 2010
Dans cet exposé, on présentera une variante de l’algorithme F4 pour le calcul de bases de Gröbner, permettant de résoudre plus rapidement des familles de systèmes polynomiaux ayant des expressions similaires. On donnera une illustration de l’efficacité de cette variante sur les problèmes de calculs d’indices sur courbes elliptiques, et plus particulièrement sur la courbe Oakley ‘Well Known Group’ 3 du standard IPSEC.
Lundi 8 Novembre 2010
Dans de nombreux protocoles cryptographiques, notamment à base de couplages, il est nécessaire de disposer de fonctions de hachage à valeur dans le groupe des points d’une courbe elliptique (ou plus généralement dans la jacobienne d’une courbe hyperelliptique). Nous expliquerons comment il est possible de construire de telles fonctions à partir de fonctions de hachage plus classiques (à valeur dans des chaînes de bits) d’une façon qui préserve la sécurité des protocoles considérés. L’étude de ces fonctions et les preuves de sécurité associées mettent en jeu des outils mathématiques variés, depuis des calculs élémentaires dans les corps finis jusqu’à des résultats plus sophistiqués sur les sommes d’exponentielles et les fonctions $L$ de courbes algébriques.
Jeudi 4 Novembre 2010
Jeudi 14 Octobre 2010
Travail efféctué lors d’un stage de Master 2 sous la direction de Jean-Charles Faugère et Guénaël Renault.
Dans la méthode de résolution du DLP sur une courbe elliptique par calcul d’indice (proposée par C. Diem et P. Gaudry indépendemment), une étape cruciale nécessite de décomposer des points sur cette courbe. Une méthode algébrique pour résoudre ce problème est de le modéliser sous forme de systèmes polynomiaux. Pour une courbe elliptique définie par une équation de Weierstrass, Diem et Gaudry modélisent le problème de décomposition d’un point à l’aide des polynômes de Semaev. Dans cet exposé, nous présenterons de nouvelles méthodes pour décrire ce problème sous forme de systèmes polynomiaux à partir de différentes représentations de courbes elliptiques. Nous mettrons en évidence des représentations de courbes telles que les systèmes polynomiaux obtenus ont une structure très particulière. Nous présenterons aussi les résultats pratiques pour la résolution des systèmes générés par chacunes des modélisations et représentations étudiées. Ces travaux permettent d’identifier les représentations qui apportent un gain sur la résolution du problème de décomposition d’un point.
Vendredi 30 Juillet 2010
La sélection polynomiale est la première étape du crible NFS et consiste à trouver un couple de polynômes dans $\mathbb{Z}$[$X$], irréductibles, ayant un résultant égal à $N$ le nombre à factoriser (ou à défaut, un petit multiple de $N$) et vérifiant certaines conditions sur la taille de leurs coefficients.
Tout d’abord je vous parlerai de la méthode de Peter Montgomery permettant de générer un couple de polynômes quadratiques « optimaux » pour le crible NFS.
Ensuite je vous exposerai différentes méthodes pouvant éventuellement mener à la génération de couples de polynômes de degré > 2.
Jeudi 15 Juillet 2010
Jeudi 15 Juillet 2010
Jeudi 17 Juin 2010
La résolution des systèmes algébriques en deux variables est l’opération principale, et donc la partie bloquante, pour de nombreux algorithmes pour l’étude des courbes planes, qu’il s’agisse d’un simple tracé ou d’un calcul complet de topologie.
Après un résumé sur les motivations du moment, particulièrement un nouvel algorithme de calcul de topologie de courbes, deux composants essentiels seront détaillés :
- l’approximation numérique certifiée des solutions réelles d’un polynôme en une variable avec une très grosse précision, essentielle pour une résolution « récursive » d’ensembles triangulaires ou de paramétrisations rationnelles des systèmes considérés ;
- un calcul dédié de paramétrisation rationnelle des solutions.
En conclusion on résumera les progrès induits par ces nouveaux composants sur les algorithmes pour l’étude des courbes planes présentés en introduction.
Jeudi 3 Juin 2010
L’enveloppe convexe d’une famille de points est le plus petit polygone les contenant. Il s’agit d’un objet naturel, largement étudié en géométrie algorithmique.
L’enveloppe convexe de $n$ points du plan a au plus $n$ sommets, ce qui se produit quand les points sont « en position convexe ». Imaginons maintenant que l’on parte d’une telle configuration – $n$ points en position convexe – et que l’on perturbe chaque point aléatoirement en le remplaçant par un point pris, par exemple, dans un disque de rayon $\epsilon$ centré en sa précédente position. Combien de points restent, en moyenne, sur l’enveloppe convexe ?
Dans cet exposé, je présenterai quelques résultats obtenus avec Dominique Attali (GIPSA - Grenoble) et Olivier Devillers (INRIA - Sophia Antipolis) sur cette question, qui correspond à l’analyse de la complexité « lissée » (au sens de Tang et Spielman) de l’enveloppe convexe. Je montrerai aussi comment les lois que l’on peut obtenir dans ce cadre modélisent assez finement les phénomènes d’arrondis sur des grilles régulières.
Lien vers l’article correspondant.
Vendredi 28 Mai 2010
On cherche à calculer une seconde décimale après la virgule de la constante de Masser-Gramain, qui est une généralisation en 2D de la constante d’Euler (travail en cours).
Mercredi 28 Avril 2010
J’exposerai une voie d’attaque possible pour factoriser un produit $N$ de deux entiers par des moyens analytiques. Les points essentiels de cette approche sont la définition d’une fonction arithmétique multiplicative (en fonction de $N$) et la théorie de la fonction zêta de Riemann, qui au moyen de son équation fonctionnelle permet d’isoler des termes principaux. En particulier, on arrive à devoir évaluer des séries multiples données par des fonctions analytiques. Certaines d’entre elles (les séries singulières mineures) ne posent pas de problème, mais je suis à la recherche d’un ingrédient (peut-être tiré du calcul numérique) pour évaluer les restantes (séries singulières majeures). En cas de succès, cela permettrait d’arriver à un algorithme déterministe avec un temps d’exécution prouvé vraisemblablement $O(\exp(\log^{c} N))$ pour tout $c>0$.
Lundi 26 Avril 2010
Le thème principal de l’exposé est le calcul de la structure du groupe de classes d’idéaux de l’ordre maximal d’un corps de nombres.
Les meilleurs algorithmes connus à ce jour pour résoudre ce problème sont sous-exponentiels par rapport au logarithme du discriminant de l’ordre maximal. Nous nous intéresserons aussi au calcul du régulateur et à la résolution du problème du logarithme discret et du test de principalité d’idéaux dans l’ordre maximal. En dimension 2, nous étudierons les stratégies basées sur le crible quadratique dûes à Jacobson et leurs améliorations pratiques. Pour les corps de dimension arbitraire, nous verrons comment diminuer la complexité de la résolution de ces problèmes dans une certaine classe de corps de nombres.
Vendredi 9 Avril 2010
Mercredi 31 Mars 2010
Vendredi 26 Mars 2010
Les courbes elliptiques, très utilisées en cryptographie à clé publique, se généralisent avec les variétés abéliennes. Un exemple important de variétés abéliennes est donné par les jacobiennes de courbes hyperelliptiques. Les fonctions thêta permettent de représenter les points d’une variété abélienne et fournissent les formules les plus rapides pour calculer dans les jacobiennes de courbe. Elles sont caractérisées par les thêta constantes correspondantes. Une question naturelle est d’obtenir des formules reliant une courbe sous forme de Weierstrass $y^2=f(x)$ et les thêta constantes correspondantes. Thomae a résolu ce problème pour le niveau (2, 2) : ses formules relient des puissances des thêta constantes aux racines de $f$.
J’expliquerai comment obtenir des formules pour les niveaux $(r,r)$. Il est alors possible d’en déduire les thêta constantes de niveau $r$. Cette dernière étape peut être utilisé pour « descendre de niveau sans prendre d’isogénie » ce qui permet de calculer des $r$-isogénies.
Vendredi 19 Mars 2010
Vendredi 5 Mars 2010
Mardi 2 Mars 2010
Jeudi 11 Février 2010
Nous présentons un algorithme original de factorisation des entiers de la forme $pq^2$ utilisant des résultats classiques sur les formes quadratiques et des techniques de recherche de petites racines de polynômes. Cet algorithme est déterministe et sa complexité (heuristique), en générale exponentielle, dépend essentiellement du régulateur du corps quadratique de discriminant $p$. Certains cryptosystèmes basés sur l’arithmétique des corps quadratiques fournissent des données permettant de rendre la complexité de notre algorithme polynomiale sur ces entrées et donc de retrouver la clé secrète en quelques secondes sur un PC standard.
Travail en commun avec G. Castagnos, A. Joux et P. Nguyen
Lundi 1 Février 2010
Jeudi 10 Décembre 2009
Les nombres de Cunningham permettent de plonger des corps de nombres de petit degré dans $\mathbb{Z}/N\mathbb{Z}$. Ceci nous permet de sortir des bornes données par le théorème de Mazur sur les torsions possibles des courbes elliptiques. Ensuite, nous exhibons une famille de courbes elliptiques avec le sous-groupe $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z}$ de torsion défini sur $\mathbb{Q}(\zeta_{8})$ et de rang non nul ainsi qu’une famille avec le sous-groupe $\mathbb{Z}/6\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$ de torsion défini sur $\mathbb{Q}(\zeta_{3})$ et de rang non nul. Ces familles ont été utilisées pour factoriser $2^{972} + 1$ et $2^{1048} + 1$. En chemin, nous donnons une représentation paramétrique des courbes avec un groupe de torsion tel que la courbe modulaire associée soit de genre 0 ou 1.
Vendredi 25 Septembre 2009
Mercredi 23 Septembre 2009
Dans la méthode des courbes elliptiques pour factoriser des entiers, on utilise en général des familles de courbes particulières qui permettent d’accélrer les calculs. La famille de Suyama est une de ces familles, dont l’efficacité est due à la présence d’un grand groupe de torsion. Nous proposons une démarche pour construire de nouvelles familles. En particulier, nous avons trouvé deux familles de courbes, chacune paramétrée par une courbe elliptique de rang 1, et offrant de meilleures propriétés que celles de Suyama.
Jeudi 17 Septembre 2009
Mardi 23 Juin 2009
Lundi 18 Mai 2009
Les architectures matérielles pour réaliser la cryptographie asymétrique sont intéressante pour de nombreux aspects (performance, embarcabilité, sécurité vis à vis des canaux auxiliaires…) et ont fait l’objet de recherches nombreuses ces dernières années. Dans cet exposé je propose une architecture utilisant les représentations RNS des nombres pour réaliser des multiplications scalaires sur courbes elliptiques quelconque définies sur GF(p). Cette architecture, simple et flexible, permet d’atteindre des temps de calculs très performants tout en restant raisonnables en terme d’encombrement.
Jeudi 30 Avril 2009
Jeudi 26 Mars 2009
Jeudi 26 Février 2009
Jeudi 6 Novembre 2008
La cryptographie sur courbes elliptiques et plus particulièrement à base de couplages a permis de développer un grand nombre de protocoles originaux. Le calcul d’un couplage est une opération non triviale et exigeante en ressources. Ces courbes sont définies sur des corps finis, ici de caractéristique 2 ou 3, et demandent ainsi une arithmétique spécifique à laquelle les processeurs généralistes ne sont pas adaptés. De ce fait il est intéressant d’étudier des opérateurs matériels pour les corps finis, et plus particulièrement la multiplication qui est l’un des goulots d’étranglement du calcul de couplage ($\eta_T$ pour notre cas). Afin d’obtenir des performances accrues, nous avons conçu une architecture basée sur un multiplieur parallèle et pipeliné. Nous étudions ici différents algorithmes de multiplication et leur implémentation sur FPGA. Cette approche nous a permis d’améliorer le temps de calcul d’un couplage et le produit temps-surface.
Jeudi 16 Octobre 2008
Une famille d’algorithmes dus (dans leur version générale) à David et Gregory Chudnovsky permet d’évaluer numériquement à grande précision — pour fixer les idées, mille ou dix mille décimales — les fonctions analytiques solutions d’équations différentielles linéaires à coefficients polynomiaux. Le point de départ est un algorithme efficace pour « dérouler » certaines suites récurrentes. Je présenterai ces différents algorithmes, devenus pour la plupart classiques, ainsi que quelques remarques sur leur complexité et leur implémentation.
Par ailleurs, je décrirai un procédé de calcul de bornes sur les suites satisfaisant des récurrences linéaires à coefficients polynomiaux. Dans le contexte des algorithmes précédents, celui-ci permet de contrôler finement le nombre de termes des développements de Taylor à prendre en compte pour garantir une certaine précision lors du prolongement analytique numérique. Il s’agit d’un travail en cours avec mon directeur de thèse Bruno Salvy.
Jeudi 26 Juin 2008
Vendredi 23 Mai 2008
http://www.jjj.de/arctan/arctanpage.html
Mercredi 14 Mai 2008
Jeudi 10 Avril 2008
Dans le cadre de l’étude de canaux dans un contexte non coopératif, nous nous intéressons à la reconstruction des codes correcteurs d’erreurs. Dans ce contexte, un observateur qui voudrait avoir connaissance d’informations échangées par des utilisateurs légitimes doit retrouver tous les paramètres de communication et de codage de canal afin de pouvoir décoder l’information circulant sur le canal. Du point de vue de l’attaquant, nous étudions les algorithmes permettant de retrouver sans connaissance a priori les paramètres du codeur de canal et plus particulièrement de codes en blocs linéaires. Nous verrons comment il est possible de retrouver la longueur et la synchronisation utilisée lors de la transmission et comment reconstruire le code en bloc utilisé. Du point de vue de la théorie de l’information, nous nous intéresserons aussi au problème de savoir combien de mots de codes bruités sont nécessaire à la reconstruction.
Mardi 25 Mars 2008
Depuis leur introduction au milieu des années 80, les courbes elliptiques sont devenues l’un des principaux outils de la cryptographie moderne. La principale opération (en termes de temps de calcul) de tout protocole utilisant les courbes elliptiques est la multiplication de point par un scalaire: le calcul de k*P=P+…+P, où k est un entier et P un point de la courbe. Afin d’effectuer cette opération de la manière la plus efficace possible, de nombreuses méthodes ont été proposées. Elles reposent, en général, sur l’algorithme dit “double-and-add” consistant à effectuer des séries de doublements entrecoupées d’additions, en fonction de la représentation binaire du scalaire k.
Dans cet exposé nous allons sortir des sentiers battus en nous intéressant à des méthodes de multiplication de point basées sur les chaînes d’additions différentielles. Celles-ci ont la particularités d’être principalement composées d’additions (au lieu de doublements), entrainant un plus grand nombre d’étapes de calcul, compensé par le fait qu’il est possible d’obtenir, sous certaines conditions, une addition plus efficace qu’un doublement. Nous verrons que cette approche apparait comme très prometteuse de prime abord, mais que certains problèmes (concernant la taille des chaînes notamment) restent à résoudre afin d’envisager une utilisation concrète.
Jeudi 14 Février 2008
Je présenterai un système de numération où les entiers sont représentés comme une somme de puissances combinées de 2 et de 3. Ce système, appellé “double-base number system”, permet dans certains cas d’accélérer la multiplication scalaire sur les courbes elliptiques. Je reviendrai très rapidement sur ces motivations avant de m’intéresser à des problèmes d’approximation diophantienne liés à ce système. Je présenterai un algorithme optimal pour de calculer l’entier de la forme 2^a3^b le plus proche d’un entier donne, basé sur un autre système de numération “exotique”, (peu) connu sous le nom de système d’Ostrowski. Dans une seconde partie, je m’intéresserai ensuite à des questions d’ordre combinatoire, en particulier à dénombrer le nombre de partitions {2,3}-aires chaînées.
Jeudi 7 Février 2008
Dans certains systèmes formels, les mécanismes de conversion et de réflexion permettent l’évaluation “rapide” de fonctions et l’utilisation de leur valeurs au sein de preuves. Ces mécanismes peuvent alors remplacer avantageusement l’approche déductive traditionnelle en substituant des calculs aux applications de théorème.
Afin d’adapter cette approche aux preuves manipulant des nombres réels, une bibliothèque d’arithmétique flottante a été développée pour l’assistant de preuves Coq. Elle fournit les opérateurs arithmétiques de base et quelques fonctions élémentaires, le tout en multi-précision et en base quelconque. Les calculs sont effectifs et réalisés au sein du formalisme de Coq.
Une bibliothèque d’arithmétique d’intervalles a été construite par dessus. En conjonction avec des méthodes de différentiation, elle offre à l’utilisateur des tactiques Coq permettant de prouver automatiquement des inégalités sur des expressions à valeurs réelles.
Jeudi 31 Janvier 2008
En 1996, Coppersmith introduit deux techniques basées sur la réduction de réseaux permettant de retrouver de petites racines d’équations polynomiales. Une de ces techiques s’applique au cas d’équations modulaires en une variable, l’autre concerne les équations entières à deux variables. Depuis, ces méthodes ont été utilisées dans de nombreuses applications cryptographiques. Pour certaines de ces applications, qui font intervenir plus de deux variables, des extensions des méthodes de Coppersmith ont été proposées. Malheureusement, ces méthodes sont heuristiques et ne permettent pas toujours de retrouver les racines recherchées quand le nombre de variables est supérieur à deux.
Dans cette présentation, nous proposons une nouvelle variante de l’algorithme de Coppersmith dans le cas d’équations entières faisant intervenir trois variables et nous étudions son applicabilité. Nous nous intéressons notamment à des attaques sur RSA dans le cas d’exposants petits. Cette méthode utilise non seulement la réduction de réseaux mais également le calcul de bases de Gröbner. En principe, elle peut être généralisée dans le cas de quatre variables ou plus.
Jeudi 17 Janvier 2008
La co-induction en Coq fournit un cadre de travail confortable pour décrire des algorithmes certifiés pour l’arithmétique réelle exacte.
La bibliothèque que nous décrivons s’inspire d’expériences précédentes utilisant des séquences infinies de chiffres redondants en base 2 et les généralise par l’utilisation de bases entières arbitraires.
L’objectif est de pouvoir utiliser les opérations rapides des entiers natifs et de fournir ainsi des calculs efficaces sur les nombres réels à l’interieur du système Coq.
Nous décrirons la représentation utilisée ainsi que quelques algorithmes, en particulier une technique de calcul des series entières convergentes.
Mercredi 5 Décembre 2007
Nous présentons le DBNS (Double-Base Number system) et ses applications la cryptographie, en particulier pour accélérer la multiplication scalaire sur courbes elliptiques. Après une brève introduction, nous détaillerons 2 applications pratiques :
- un algorithme de multiplication scalaire rapide pour des courbes génériques lorsque des précalculs sont autorisés. Ce travail repose sur le concept de DBNS étendu qui est une généralisation naturelle du DBNS.
- le premier algorithme de multiplication scalaire de complexité sous-linéaire. Cette méthode exploite une généralisation du DBNS aux courbes de Koblitz
Jeudi 29 Novembre 2007
Depuis l’introduction du produit matriciel de complexité sous-cubique, des algorithmes par bloc ont été conçus pour réduire la complexité de la plupart des problèmes classique d’algèbre linéaire à celle du produit de matrice: O(n^w). Cependant, jusqu’à récemment, le meilleur algorithme pour le calcul du polynôme caractéristique exigeait un nombre logarithmique de produit matriciels, impliquant une complexité de O(n^w log n) opérations dans le corps de base. Nous présenterons un nouvel algorithme probabiliste de type Las Vegas, calculant le polynôme caractéristique dans un corps suffisamment grand. Grâce à un nouveau type de réduction, il atteint la complexité O(n^w).
Les réductions au produit matriciel sont par ailleurs d’un grand intérêt pratique car elle permettent l’utilisation de noyaux efficaces pour cette opération (combinant optimisation de cache et produit sous-cubique). Nous présenterons ainsi les principes de la bibliothèque FFLAS-FFPACK pour l’algèbre linéaire dense dans un corps fini. En particulier, dans ce contexte, une implémentation du nouvel algorithme de calcul du polynôme caractéristique, permet d’améliorer radicalement les temps de calcul des meilleures implémentations précédentes.
Jeudi 8 Novembre 2007
Cet exposé correspond à un travail réalisé avec David Lubicz. Il présente un nouveau schéma de diffusion (broadcast) avec révocations éphémères (stateless receivers). Contrairement aux schémas traditionnels dans le même cadre (Complete Subtree, Subset Difference), l’émetteur utilise des attributs pour décrire l’ensemble des destinataires. Ainsi, lorsque l’émetteur souhaite révoquer une catégorie d’utilisateurs, il peut le faire en utilisant simplement l’attribut relatif à cette catégorie, et non en révoquant individuellement chacun des membres de la catégorie.
Dans les schémas existants à base d’attributs, le déchiffrement représente un coût calculatoire important pour les destinataires, par le calcul de nombreux couplages. Le schéma présenté utilise une approche différente, et permet de limiter le déchiffrement à essentiellement 3 couplages.
Lundi 18 Juin 2007
Jeudi 14 Juin 2007
Jeudi 7 Juin 2007
Jusqu’à présent, le consensus est que, dans les processeurs généralistes, les fonctions élémentaires en virgule flottante soient implémentées grâce à des algorithmes “micro-codés” –c’est-à-dire utilisant les opérations de base de l’unité flottante– et non par des opérateurs matériels dédiés. Ce choix s’explique par le surcoût important en silicium qu’auraient de tels opérateurs par rapport à l’utilisation somme toute restreinte de ces opérations.
Pour certaines applications spécifiques très calculatoires reposant lourdement sur ces fonctions, un tel choix peut s’avérer être un véritable handicap. Cependant, la capacité d’intégration des circuits FPGA (pour Field-Programmable Gate Arrays) est aujourd’hui suffisante pour les utiliser comme de véritables co-processeurs reconfigurables, permettant ainsi de “compléter” les unités de calcul des processeurs généralistes selon les besoins de chaque application.
Lors de cet exposé, après avoir brièvement présenté les FPGA et leur architecture générale, je détaillerai, à travers l’exemple de la fonction exponentielle, les diverses problématiques qui entrent en jeu lors de la conception et l’implémentation d’algorithmes dédiés au matériel. Je donnerai enfin les résultats obtenus qui, montrant un facteur d’accélération de l’ordre de 100 par rapport à un processeur généraliste, nous encouragent à poursuivre nos travaux dans cette direction.
Mardi 5 Juin 2007
Jeudi 26 Avril 2007
Dans cet exposé, nous expliquerons comment calculer effectivement des équations donnant un plongement projectif de l’espace des variétés abéliennes munies d’une certaine structure de niveau et caractériser dans cet espace les relevés canoniques. Nous donnerons des applications algorithmiques.
Mardi 17 Avril 2007
Mardi 17 Avril 2007
Jeudi 15 Mars 2007
Jeudi 8 Mars 2007
Le problème (SVP) de trouver un vecteur non nul le plus court d’un réseau de $\R^n$ de dimension $d$ est un problème très classique ; au cours des dix dernières années, de nombreux travaux ont montré des bornes inférieures sur la complexité de ce problème. Ces résultats sont à la base des arguments de sécurité d’un certain nombre de cryptosystèmes (Ajtai-Dwork, NTRU). Le meilleur algorithme pratique pour ce problème, dû à Kannan, consiste à énumérer des points dans un ellipsoïde. Son analyse consiste classiquement à borner le nombre de points par le volume, qui est à son tour estimé par le volume du pavé circonscrit, donnant une complexité de $\tilde{O}(d^{d/2(1+o(1))})$. Nous montrons qu’une analyse plus fine conduit à une complexité de $\tilde{O}(d^{d/(2e)(1+o(1))})$; ce résultat permet également d’améliorer la complexité des algorithmes de recherche du vecteur le plus proche (CVP), ou de calcul de bases “blocs-réduites” à la Schnorr.
Jeudi 8 Février 2007
Parce que les nombres manipulés en machine ont généralement un domaine et une précision limités, il est nécessaire de certifier soigneusement que les applications les utilisant se comportent correctement. Réaliser une telle certification à la main est un travail propice à de nombreuses erreurs. Les méthodes formelles permettent de garantir l’absence de ces erreurs, mais le processus de certification est alors long, fastidieux et généralement réservé à des spécialistes.
Le travail présenté dans cet exposé vise à rendre ces méthodes accessibles en automatisant leur application. L’approche adoptée s’appuie sur une arithmétique d’intervalles accompagnée d’une base de théorèmes sur les propriétés des arithmétiques approchées et d’un mécanisme de réécriture d’expressions permettant le calcul de bornes fines sur les erreurs d’arrondi.
Ce travail s’est concrétisé par le développement de l’outil Gappa d’aide à la certification. Il permet de vérifier les propriétés de codes numériques qui utilisent de l’arithmétique à virgule fixe ou à virgule flottante. Cette vérification s’accompagne de la génération d’une preuve formelle de ces propriétés utilisable par l’assistant de preuves Coq.
Gappa a été utilisé avec succès pour certifier la correction de fonctions dans les bibliothèques CRlibm, CGAL et FLIP par exemple.
Mardi 16 Janvier 2007
Le développement d’algorithmes numériques nécessite de borner certaines fonctions, en particulier les fonctions représentant une erreur d’approximation. Ce problème se réduit au calcul de la norme infinie de la fonction d’erreur. Par exemple, le développement de fonctions élémentaires, tant au niveau logiciel que matériel, utilise ce genre de calcul.
Il existe déjà des implémentations de la norme infinie fournissant une très bonne approximation de la valeur réelle de la norme. Cependant, il n’existe pas d’algorithme capable de fournir un résultat à la fois précis et sûr. On entend par sûr, un algorithme qui renvoie une valeur majorant la norme réelle et qui fournit par ailleurs un certificat prouvant la validité de cette majoration.
Nous proposons un algorithme de calcul de la norme infinie utilisant l’arithmétique d’intervalles. Cet algorithme est optimisé pour les fonctions correspondant à une erreur relative ou absolue, c’est-à-dire des fonctions numériquement très mal conditionnées du fait d’importantes cancellations. Notre algorithme peut aussi, dans une certaine mesure, travailler avec des fonctions numériquement instables à proximité de certains points où elles ne sont définies que par continuité.
Enfin, notre algorithme peut retenir l’arbre des calculs qu’il a effectués afin de produire une preuve de correction du résultat de son calcul.
Mardi 16 Janvier 2007
L’arrondi correct des fonctions élémentaires en double précision demande l’approximation de la fonction avant l’arrondi final à une précision d’environ 2^-120. Le format le plus précis dont l’implémentation est requise par la norme IEEE 754 est la double précision avec 53 bits de mantisse. Le téchniques traditionelles de type double-double ne suffisent donc pas. On s’intéressera alors en premier lieu au format triple-double et ses avantages devant un format multiprécision à base de calcul entier.
Ces avantages en terme de performance entraînent certains inconvénients. L’approche de preuve se base sur un ensemble de théorèmes – deux par opérateur triple-double – qui établissent un lien entre la précision de l’opérateur et une borne de chevauchement des composantes du triple-double ainsi qu’entre les bornes de chevauchement elles-même. L’instantiation de ces théorèmes paramétrés est tout de même fastidieuse ce qui provoque des erreurs dans la preuve du code produit.
On verra que l’évaluation de Horner de polynômes d’approximation d’une fonction variant peu dans un domaine donné est un problème très bien conditionné. D’une part, on peut exploiter ce bon comportement pour une utilisation mixte de code double, double-double et triple-double précision donnant de bonnes performances. D’autre part, le bon conditionnement permet d’automatiser le processus de développement du code pour l’évaluation en formats mixtes et de la preuve formelle de la borne d’erreur arithmétique.
L’automatisation accélère le processus de développement d’une fonction élémentaire non seulement en surmontant les quelques problèmes liés au format triple-double mais aussi en permettant d’essayer rapidement plusieurs moyens d’approcher une fonction donnée.
Les résultats montrés sont la combinaison fructueuse de plusieurs travaux, entre autre, l’implémentation et la preuve d’opérateurs triple-double, la maturité de leur exploitation, en particulier concernant leur preuve en Gappa, et l’implémentation d’une norme infinie suffisamment fiable.
Mardi 16 Janvier 2007
Pour calculer des valeurs approchées numériques des fonctions mathématiques usuelles, on remplace généralement la fonction par une autre, très proche et plus facile à calculer. Ainsi, l’élaboration d’un algorithme numérique pour évaluer la fonction suit généralement les étapes suivantes :
- on détermine sur quel intervalle on souhaitera évaluer la fonction ;
- on détermine avec quelle précision on souhaite connaître les valeurs de la fonction ;
- on cherche un approximant fournissant la précision requise sur l’intervalle choisi.
- on cherche un bon algorithme pour évaluer l’approximant.
Pour la troisième étape, on choisit généralement un polynôme (notamment parce que la quatrième étape a été très bien étudiée dans le cas où l’approximant est un polynôme et on sait la traiter de manière satisfaisante).
Les coefficients du polynôme doivent être stockés dans la mémoire de l’ordinateur et doivent donc être représentables sous forme de nombres flottants. Nous nous intéressons au problème de la recherche d’un très bon polynôme à coefficients représentables en machine, pour approcher une fonction continue. En utilisant la théorie des réseaux de points (et l’algorithme LLL de A. Lenstra, H. Lenstra et L. Lovasz) nous proposons un algorithme permettant d’obtenir un tel polynôme. Nous illustrerons les avantages et les défauts de l’algorithme sur un exemple complet.
Mercredi 29 Novembre 2006
Les registres à décalage sont des circuits très courants en électronique. Ils sont toujours associés à des circuits (combinatoires ou séquentiels) de rétroaction. Parmi tous ces circuits, les registres à décalage à rétroaction linéraire (Linear Feedback Shift Registers - LFSRs) sont les plus répandus. Ils sont présents dans tous les systèmes de communication pour le brassage des données, l’étalement de spectre, les chiffrements à flot ou la vérification matérielle (Built-in Self Test)… Malgré cette popularité, l’impact des propriétés des LFSRs n’a jamais été vraiment étudié en terme d’implantation. J’ai travaillé sur la synthèse des LFSRs sur les FPGA Xilinx Spartan2E en terme de surface, de chemin critique et de débit. L’étude des implantations haut débit est très importante pour la synthèse logicielle. Je décrirais les propriétés que l’on peut observer pour les deux types de synthèse. Pour conclure, je décrirais certain travaux en cours sur les registres à rétroaction non-lineaire comme les FCSRs (Feedback with Carry Shift Registers).
Mardi 10 Octobre 2006
Vendredi 14 Avril 2006
Les algorithmes de chiffrement par bloc sont abondamment utilises dans les communications modernes et assurent la confidentalite des donnees. Un algorithme de chiffrement par bloc est une permutation dependant d’un parametre appele cle secrete. Differentes methodes ont ete proposees pour mettre en defaut la securite de ces algorithmes. Parmi les methodes statistiques, on retrouve notamment la cryptanalyse lineaire et differentielle. Ces methodes se basent sur la recherche d’expressions simples appelees caracteristiques. Ces expressions sont probabilistes et donnent de l’information sur la cle secrete a partir de paires clair/chiffre. L’evaluation de l’efficacite de ces methodes permettent de mettre en evidence les proprietes algebriques auquelles les composantes de l’algorithme de chiffrement doivent satisfaire afin de rendre l’algorithme le plus resistant possible aux attaques connues.
Nous commencerons l’expose par une breve introduction a la cryptographie. Nous decrirons ensuite les reseaux de Feistel, une des classes importantes d’algorithmes de chiffrement par bloc dont le precedent standard americain DES fait partie. Nous poursuivrons l’expose en esquissant les principes de la cryptanalyse lineaire. En outre, nous presenterons une generalisation de cette methode developpee par Biryukov, De Canniere et moi-meme et publiee a la conference Crypto 2004. Nous terminerons par un bref rappel de theorie de Fourier et nous decrirons les criteres de conception induits par la cryptanalyse lineaire.
Jeudi 6 Avril 2006
L’algorithme le plus efficace d’un point de vue complexité pour l’évaluation d’un polynôme est l’algorithme de Horner. On sait de plus qu’il est inverse-stable. Néanmoins, l’évaluation polynomiale peut être extrêmement mal conditionnée ; c’est le cas par exemple lorsque l’on se situe près d’une racine multiple. Or évaluer un polynôme de manière précise peut être une tâche cruciale par exemple pour le critère d’arrêt des méthodes itératives de type Newton pour la recherche de zéros. Les solutions existantes utilisent toutes des bibliothèques multiprécisions qui permettent d’augmenter la précision des calculs mais souvent au prix d’un surcoût très élevé.
Nous proposons un algorithme de Horner compensé qui permet d’évaluer de façon précise et rapide un polynôme à coefficients flottants. La précision du résultat calculé est similaire à celle donnée en effectuant l’évaluation classique par le schéma de Horner avec une précision double de la précision courante. Notre algorithme est deux fois plus rapide que les implémentations existantes donnant la même précision pour le résultat. Nous présentons aussi un algorithme pour calculer en arithmétique flottante IEEE 754 une borne d’erreur certifiée. Par certifiée, on entend que la borne calculée majore effectivement l’erreur de l’évaluation par l’algorithme de Horner compensé. Des expérimentations avec des polynômes très mal conditionnés illustrent ces résultats théoriques. Nos algorithmes n’utilisent qu’une seule précision courante et sont portables si l’on suppose que l’arithmétique flottante est conforme au standard IEEE 754.
Lundi 27 Mars 2006
Jeudi 23 Mars 2006
Cet exposé traitera de l’analyse de la complexité moyenne (nombre d’itérations, complexité en bits) d’algorithmes de pgcd sur les entiers. Les premiers travaux dans ce domaine remontent aux années 70, avec les premières analyses de l’algorithme d’Euclide par Dixon et Heilbronn, puis les analyses de ses variantes par Knuth et Yao, Brent, Rieger. Depuis une dizaine d’année s’est développée autour des travaux de Brigitte Vallée une technique efficace d’analyse de tels algorithmes, l’analyse dynamique, basée sur une modélisation des algorithmes en systèmes dynamiques. L’avantage de cette méthode est qu’elle permet de remplacer l’étude analytique de séries génératrices (difficile dans ce contexte) par l’étude spectrale d’un opérateur de transfert, outil classique en théorie des systèmes dynamiques. Je présenterai donc cette méthode d’analyse que j’illustrerai par des résultats récents qu’elle a permis d’obtenir. Je parlerai dans un premier temps de l’analyse de l’algorithme d’Euclide interrompu : on étudie l’évolution des principales grandeurs (quotients, tailles des restes) au cours de l’exécution de l’algorithme. Cette étude permet en outre d’obtenir des résultats interessants sur les versions accélérées de l’algorithme d’Euclide (algorithmes de Lehmer-Euclide, Knuth-Schönhage). Puis je présenterai l’analyse en moyenne de l’algorithme LSB, mis au point et utilisé par Stehlé et Zimmermann dans leur algorithme rapide de calcul de pgcd. L’analyse de cet algorithme diffère des analyses classiques, puisqu’elle fait appel à des argument issus de la théorie de produits de matrices aléatoires. Les différents résultats présentés ici ont été obtenus en collaboration avec Brigitte Vallée, Véronique Maume-Deschamps et Loïck Lohte.
Jeudi 16 Mars 2006
TBA
Jeudi 16 Février 2006
Les protocoles de cryptographie à clé publique utilisent des opérateurs arithmétiques sur des corps (ECC) ou des anneaux (RSA). De nombreuses classes de moduli offrent des propriétés intéressantes pour effectuer cette arithmétique modulaire: les nombres de Mersenne, les pseudo nombres de Mersenne, les nombres de Mersenne généralisés… Dans ce contexte, nous proposons un nouveau système de représentation. Celui ci est adapté à l’arithmétique modulaire. Après analyse de ce système, nous proposons deux axes d’utilisation de ce système de représentation modulaire. Dans un premier temps, une nouvelle classe de moduli peut être créée à partir de ce système de représentation. Cette classe est à la fois efficace et suffisamment dense pour répondre aux contraintes d’utilisation des protocoles d’ECC. Dans un second temps et à partir de la théorie des réseaux euclidiens, nous présentons un théorème d’existence de représentation faiblement redondante dans ce système. C’est à partir de ce théorème que nous proposons différentes solutions à des problèmes classiques de l’ arithmétique modulaire, pour le protocole RSA entre autre.
Jeudi 5 Janvier 2006
Les fonctions booléennes symétriques sont les fonctions dont la valeur ne dépend que du poids du vecteur d’entrée. Ces fonctions peuvent être représentées plus simplement, que ce soit par leur forme algébrique normale ou leur vecteur des valeurs, que des fonctions booléennes générales — vecteurs de taille (n+1) contre des vecteurs de taille 2^n en général. En outre, ces fonctions ont une complexité en nombre de portes qui est linéaire en le nombre de variables d’entrées [Muller_Preparata75]. Ces qualités en font par exemple, des candidates potentielles comme fonctions de filtrage dans un chiffrement à flot. C’est pourquoi une étude systématique des propriétés cryptographiques de ces fonctions est nécessaire. Des résultats concernant la non-linéarité maximale des fonctions booléennes symétriques sont connus [Savicky 1994, Maitra-Sarkar 2002], ainsi que des familles infinies de fonctions symétriques sans correlation et résilientes [Gopalakrishnan-Hoffman-Stinson 1993, von zur Gathen-Roche 1997, Maitra-Sarkar 2003]. L’étude que nous présentons (travaux en commun avec Anne Canteaut) est basé sur un théorème qui établit un lien entre le degré algébrique des fonctions symétriques et la périodicité de leur vecteur des valeurs simplifié (vecteur des valeurs prises pour les différents poids des vecteurs d’entrée). Ce théorème nous a permis d’explorer de manière systématique différentes propriétés cryptographiques (non-linéarité, résilience, critère de propagation) et d’établir plusieurs nouveaux résultats pour ces fonctions. Par ailleurs, le calcul explicite du spectre de Walsh des fonctions booléennes symétriques de degré 2 et 3 a été réalisé, ainsi que la détermination de toutes les fonctions symétriques équilibrées de degré inférieur ou égal à 7, indépendamment du nombre de variables.
Jeudi 24 Novembre 2005
Mercredi 23 Novembre 2005
Mardi 8 Novembre 2005
résumé à préciser
Jeudi 13 Octobre 2005
Le calcul de polynômes de classe est l’étape principale dans la construction de courbes elliptiques par la méthode de la multiplication complexe. Ces courbes peuvent servir comme base de cryptosystèmes, dans les preuves de primalité ou pour tricher dans la chasse au record de factorisation avec ECM. Je donne la complexité des algorithmes usuels pour calculer ces polynômes, ainsi qu’un algorithme asymptotiquement optimal, mais pratiquement lent.
Jeudi 6 Octobre 2005
Jeudi 29 Septembre 2005
Jeudi 29 Septembre 2005
Jeudi 22 Septembre 2005
Une fonction holonome est une fonction dont les coefficients de Taylor vérifient une récurrence linéaire à coefficients polynomiaux, ou de manière équivalente qui vérifie une équation différentielle linéaire à coefficients polynomiaux. La méthode “binary splitting” permet d’évaluer une telle fonction en un entier ou un rationnel $x$ de taille bornée en $O(M(n)\log n)$, pour un résultat sur $n$ bits. Lorsque $x$ est un flottant de $n$ bits, cette méthode ne s’applique pas directement. Pour certaines fonctions comme l’exponentielle admettant une équation fonctionnelle, i.e. $\exp(a+b)=\exp(a)\cdot\exp(b)$, on peut obtenir un algorithme en $O(M(n)(\log n)^2)$. Dans le cas général (pas d’équation fonctionnelle), David et Gregory Chudnovsky ont montré en 1990 qu’on pouvait calculer une fonction holonome sur $n$ bits en $O(M(n) \log(n)^3)$
Jeudi 15 Septembre 2005
Dans cet exposé, je présenterai des formules pour calculer rapidement la multiplication scalaire dans la jacobienne d’une courbe de genre 2 sur un corps fini de caractéristique impaire. Cette opération est au cœur des cryptosystèmes à clef publique utilisant des courbes de genre 2 et son temps de calcul est directement relié au temps de signature, par exemple.
Ces formules sont du type «exponentiation de Montgomery», où l’on effectue à chaque étape une addition et un doublement. Elles sont donc bien adaptées aux environnements sensibles aux attaques « Side Channel&».
Les travaux précédents dans cette direction (Lange, Duquesne) partaient de l’algorithme de Cantor. Dans ce travail, nous avons une approche différente, puisque les formules dérivent directement de formules d’addition et de duplication de fonctions thétas.
Mardi 21 Juin 2005
En 1998 Thomas Hales a annoncé d’avoir prouvé la conjecture de Kepler. Sa preuve s’appuie sur des inégalités dans les nombre réels, qui sont vérifiées par des algorithmes d’optimisation. Ces méthodes se basent sur l’arithmétique d’intervalles avec certains raffinements: prise en compte de monotonies, considération du gradient etc. Une formalisation (encore partielle) de ces algorithmes est présentée. Elle se sert des nombres réels (représentés comme suites de Cauchy) comme bornes d’intervalles et évite ainsi les problèmes d’arrondi, indispensable pour le développement de preuves formelles. Le but ultime de ce travail est de prouver toutes les inégalités surgissant dans la preuve de Hales.
Mardi 21 Juin 2005
Je vais essayer de présenter quelques aspects de la récente preuve en Coq du théorème des quatre couleurs. En particulier de l’exploitation de résultats calculatoires à l’intérieur du raisonnement mathématique.
Vendredi 3 Juin 2005
Jeudi 14 Avril 2005
Les signatures numériques classiques ont la propriété, parfois indésirable, d’être universellement vérifiables par toute personne possédant la clé publique du signataire. Récemment, en collaboration avec F. Laguillaumie et P. Paillier, nous avons proposé des signatures dont la vérification ne peut s’effectuer sans interaction avec le signataire. La sécurité de ces signatures repose sur la difficulté présumée de la variante « xyz » du problème Diffie-Hellman classique. Dans cet exposé, nous présenterons le problème algorithmique dans son contexte cryptographique et nous donnerons des arguments en faveur de sa difficulté (sécurité générique, sécurité sur les bits, …)
Jeudi 7 Avril 2005
Mercredi 23 Mars 2005
Jeudi 10 Mars 2005
Jeudi 3 Mars 2005
Sur le corps des complexes, une courbe de genre $g$ est isomorphe à un tore à $g$ trous, i.e., à un quotient de la forme $\mathbb{C}^g/(\mathbb{Z}^g\oplus\mathbb Z^g\tau)$, où $\tau$ est une matrice $g\times g$ appelée matrice de Riemann.
Dans le cas du genre $g$=1, le calcul de $τ$ à partir de l’équation d’une courbe elliptique est l’une des applications classiques de la moyenne arithmético-géométrique (AGM), que l’on peut interpréter en considérant des fonctions appelées theta constantes.
Nous montrons comment tout ceci peut se transposer au genre supérieur en considérant une généralisation de l’AGM connue sous le nom de moyenne de Borchardt.
En particulier, nous donnons un algorithme permettant le calcul de matrices de Riemann en genre 2 en temps quasi-linéaire, algorithme particulièrement simple à implanter.
Nous montrons aussi comment ces techniques permettent d’évaluer rapidement des formes et fonctions modulaires, en genre 1 et en genre 2, et nous discutons des applications (constructions de courbes CM, calculs explicites d’isogénies, …).