Thursday September 21, 2017

Laurent Imbert (ECO team, LIRMM)
Randomized Mixed-Radix Scalar Multiplication
A006, 10:30
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).

Wednesday July 5, 2017

Chloe Martindale (Technical University of Eindhoven, Netherlands)
Isogeny graphs, modular polynomials, and point counting for higher genus curves.
A006, 10:30

Thursday November 10, 2016

Vincent Neiger (AriC team, LIP, ÉNS Lyon -- Univ. of Waterloo (ON, CA))
Fast computation of normal forms of polynomial matrices
A006, 10:30

Friday June 17, 2016

Cécile Pierrot (Almasty team, LIP6, UPMC, Paris)
Génération d'aléa public et Bitcoin
A006, 10:30
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.

Tuesday April 19, 2016

Karim Bigou (Équipe CAIRN, IRISA, Lannion)
Calcul modulaire en RNS pour des implantations de cryptographie à clef publique
A006, 15:00
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.

Monday November 23, 2015

Chenqi Mou (School of Mathematics and Systems Science, Beihang University, China)
Sparse FGLM algorithms for solving polynomial systems
B013, 14:00

Monday November 16, 2015

Frédéric Bihan (Université de Savoie Mont Blanc)
Polynomial systems with many positive solutions from bipartite triangulations
A006, 10:30
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.

Wednesday October 14, 2015

Jan Tuitman (Department of Mathematics, KU Leuven, Belgium)
Counting points on curves: the general case
B013, 10:30
transparents: pdf (208 kb)

Wednesday September 9, 2015

Roland Wen (Univ. of New South Wales, Sydney)
Engineering Cryptographic Applications: Leveraging Recent E-Voting Experiences in Australia to Build Failure-Critical Systems
A006, 10:30

Thursday February 5, 2015

Matthieu Rambaud (Télécom ParisTech)
Comment trouver de bons algorithmes de multiplication par interpolation ?
A006, 10:30
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.

Thursday November 20, 2014

Sebastian Kochinke (Universität Leipzig)
The Discrete Logarithm Problem on non-hyperelliptic Curves of Genus g > 3.
A006, 14:00

Thursday November 20, 2014

Enea Milio (LFANT team, Institut de Mathématiques de Bordeaux)
Calcul des polynômes modulaires en genre 2
A006, 10:30
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.

Monday November 17, 2014

Thomas Richard (CARAMEL team, LORIA)
Cofactorization strategies for NFS
B013, 14:00

Thursday October 23, 2014

Andrea Miele (LACAL, EPFL, Lausanne)
Post-sieving on GPUs
A006, 10:30
transparents: pdf (930 kb)

Thursday September 11, 2014

Christian Eder (Department of Mathematics, University of Kaiserslautern)
Computing Groebner Bases
B013, 10:30
transparents: pdf (7607 kb)

Thursday July 3, 2014

Nicholas Coxon (CARAMEL team, LORIA)
Nonlinear polynomials for NFS factorisation
B013, 10:30
transparents: pdf (596 kb)

Thursday June 19, 2014

Irene Márquez-Corbella (GRACE team, LIX, École Polytechnique)
Une attaque polynomiale du schéma de McEliece basé sur les codes géométriques
A006, 10:30
transparents: pdf (1036 kb)
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.

Thursday April 24, 2014

Guillaume Moroz (Vegas team, LORIA)
Évaluation et composition rapide de polynômes
A006, 10:30
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.

Thursday March 13, 2014

Pierre-Jean Spaenlehauer (CARAMEL team, LORIA)
A Newton-like iteration and algebraic methods for Structured Low-Rank Approximation
A006, 10:30

Wednesday February 26, 2014

Armand Lachand (Équipe Théorie des Nombres, IECL)
Quelques perspectives mathématiques sur la sélection polynomiale dans le crible algébrique NFS
A006, 10:30
Soit B ≥ 2. Un entier n est dit B-friable si son plus grand facteur premier, noté P+(n) satisfait P+(n) ≤ B. Soit FZ[X1, X2] une forme binaire. Dans cet exposé, on s'intéressera à l'étude asymptotique du cardinal
ΨF(1)(X, B) := |{ 1 ≤ x1, x2 ≤ X : gcd(x1, x2) = 1 et P+(F(x1, x2)) ≤ B }|.
On établira tout d'abord des formules asymptotiques pour Ψ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.

Thursday December 19, 2013

Luca De Feo (CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
Algorithms for Fp
A006, 10:30

Friday December 6, 2013

Cécile Pierrot (PolSys team, LIP6)
Crible Spécial sur Corps de Nombres (SNFS) – Application aux courbes elliptiques bien couplées.
A006, 13:00
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.

Thursday November 28, 2013

Clément Pernet (AriC team, LIP, ENS Lyon)
Calcul de formes echelonnées et des profils de rang
A006, 10:30
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.

Thursday November 7, 2013

Julia Pieltant (GRACE team, LIX, École Polytechnique)
Algorithme de type Chudnovsky pour la multiplication dans les extensions finies de Fq.
A006, 10:30
Lorsque l'on effectue le produit de deux éléments de Fqn, on distingue deux types d'opérations élémentaires dans Fq : 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 Fq qui dépendent chacun d'un des deux éléments de Fqn 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 Fqn sur Fq 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 Fqn sur Fq, uniformes en n.

Friday July 19, 2013

Bastien Vialla (LIRMM)
Un peu d'algèbre linéaire
A006, 14:00
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.

Wednesday July 17, 2013

Alice Pellet-Mary (CARAMEL team, LORIA)
Test rapide de cubicité modulaire
B013, 14:00
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.

Tuesday July 16, 2013

Svyatoslav Covanov (CARAMEL team, LORIA)
Implémentation efficace d'un algorithme de multiplication de grands nombres
A006, 15:00
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 2O(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 2 problèmes seront l'objet de la présentation.

Monday July 15, 2013

Hamza Jeljeli (CARAMEL team, LORIA)
RNS Arithmetic for Linear Algebra of FFS and NFS-DL algorithms
B013, 15:30

Tuesday May 28, 2013

Mourad Gouicem (PEQUAN team, LIP6)
Fractions continues et systèmes de numérations : applications à l'implémentation de fonctions élémentaires et à l'arithmétique modulaire
A006, 10:30
transparents: pdf (1269 kb)
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 ()nN modulo 1, avec α 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.

Friday April 5, 2013

François Morain (GRACE team, LIX)
ECM using number fields
B200, 13:30

Thursday March 28, 2013

Antoine Joux (CryptoExperts / CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
Logarithmes discrets dans les corps finis. Application en caractéristique "moyenne".
A006, 10:30
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.

Friday March 15, 2013

Adeline Langlois (AriC, LIP, ENS Lyon)
Classical Hardness of Learning with Errors
A006, 14:00

Friday February 22, 2013

Jérémy Parriaux (CRAN, Univ. de Lorraine)
Contrôle, synchronisation et chiffrement
A006, 13:30
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.

Wednesday February 13, 2013

Emmanuel Jeandel (Équipe CARTE, LORIA)
Quête du plus petit jeu de tuiles apériodique
A006, 10:30
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.

Thursday January 31, 2013

Maike Massierer (Mathematisches Institut, Universität Basel)
An Efficient Representation for the Trace Zero Variety
A006, 10:30

Thursday January 17, 2013

Pierre-Jean Spaenlehauer (ORCCA, University of Western Ontario)
Résolution de systèmes polynomiaux structurés et applications en Cryptologie
B013, 13:00
transparents: pdf (853 kb)
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(20.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).

Thursday December 20, 2012

Alin Bostan (Projet SpecFun, INRIA Saclay)
Computer algebra for the enumeration of lattice walks
A008, 14:00

Thursday December 20, 2012

Mohab Safey El Din (Projet PolSys, LIP6, UPMC-IUF-INRIA)
Computer Algebra Algorithms for Real Solving Polynomial Systems: the Role of Structures
A008, 10:30

Thursday November 29, 2012

Paul Zimmermann (Projet CARAMEL, LORIA)
Sélection polynomiale dans CADO-NFS
C005, 10:30
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).

Friday November 23, 2012

Alexandre Benoit (Lycée Alexandre Dumas, Saint Cloud)
Multiplication quasi-optimale d'opérateurs différentiels
A006, 10:30
transparents: pdf (422 kb)
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).

Thursday November 15, 2012

Christophe Petit (Crypto Group, Université Catholique de Louvain)
On polynomial systems arising from a Weil descent
A006, 14:00
transparents: pdf (713 kb)

Tuesday November 6, 2012

Hugo Labrande (ENS de Lyon)
Accélération de l'arithmétique des corps CM quartiques
A006, 14:00
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.

Thursday September 27, 2012

Laura Grigori (Projet Grand Large, INRIA Saclay-Île de France, LRI)
Recent advances in numerical linear algebra and communication avoiding algorithms
B013, 10:30

Friday July 20, 2012

Francisco Rodríguez-Henríquez (CINVESTAV, IPN, México)
Computing square roots over prime extension fields
A006, 10:30

Friday June 29, 2012

Răzvan Bărbulescu (Projet CARAMEL, LORIA)
Finding Optimal Formulae for Bilinear Maps
B013, 14:00

Friday June 29, 2012

Cyril Bouvier (Projet CARAMEL, LORIA)
Finding ECM-Friendly Curves through a Study of Galois Properties
A006, 10:00

Wednesday June 20, 2012

Aurore Guillevic (Équipe Crypto, ENS / Laboratoire Chiffre, Thales)
Familles de courbes hyperelliptiques de genre 2, calcul explicite de l'ordre de la jacobienne et constructions pour les couplages
A006, 10:30
transparents: pdf (656 kb)
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 Y2 = X5 + aX3 + bX définie sur un corps fini Fq admet un grand facteur premier. Son approche consiste à obtenir différents candidats pour la fonction zeta de la jacobienne sur Fq 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 Y2 = X6 + aX3 + 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 ρ environ 4 pour une méthode à la Cocks-Pinch et environ 3 pour une méthode à la Brezing-Weng.

Wednesday April 25, 2012

Olivier Levillain (ANSSI)
SSL/TLS: état des lieux et recommandations
A008, 10:30
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.

Tuesday April 3, 2012

Luc Sanselme (Lycée Henri Poincaré, Nancy)
Algorithmique des groupes en calcul quantique
A006, 14:00

Friday March 30, 2012

Jean-Charles Faugère (Projet PolSys, LIP6)
Gröbner Bases and Linear Algebra
A006, 10:30

Tuesday March 20, 2012

Peter Schwabe (Academia Sinica, Taiwan)
EdDSA signatures and Ed25519
A217, 15:00
transparents: pdf (1050 kb)

Wednesday March 14, 2012

Karim Khalfallah (ANSSI)
Les canaux auxiliaires, approche sous l'angle du rapport signal-à-bruit
A006, 10:30
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.

Wednesday March 7, 2012

Jérémie Detrey (Projet CARAMEL, LORIA)
Implémentation efficace de la recherche de formules pour applications bilinéaires
A006, 10:30
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.

Wednesday February 29, 2012

Marion Videau (Projets CARAMEL, LORIA)
Codes d'authentification de message (suite et fin)
A006, 10:30

Thursday February 2, 2012

Stéphane Glondu (Projets CASSIS/CARAMEL, LORIA)
Tutoriel Coq (suite et fin)
B013, 10:00

Friday January 20, 2012

Charles Bouillaguet (CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
Presumably hard problems in multivariate cryptography
A006, 10:30
transparents: pdf (2437 kb)

Wednesday November 30, 2011

Cyril Bouvier (Projet CARAMEL, LORIA)
ECM sur GPU
A006, 10:30

Friday October 28, 2011

Sorina Ionica (Projet CARAMEL, LORIA)
Pairing-based algorithms for Jacobians of genus 2 curves with maximal endomorphism ring
A006, 11:00

Thursday October 6, 2011

Paul Zimmermann (Projet CARAMEL, LORIA)
Short Division of Long Integers (with David Harvey)
A006, 10:30
transparents: pdf (1764 kb)

Thursday September 29, 2011

Diego F. Aranha (Universidade de Brasília)
Efficient Software Implementation of Binary Field Arithmetic Using Vector Instruction Sets
B011, 10:30
transparents: pdf (402 kb)

Wednesday July 13, 2011

Benoît Gaudel (Projet CARAMEL, LORIA)
Étude de stratégies de cofactorisation pour l'algorithme Function Field Sieve
A006, 10:30
transparents: pdf (657 kb)
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.

Thursday June 30, 2011

Cyril Bouvier (Projet CARAMEL, LORIA)
ECM sur GPU
B013, 10:00
transparents: pdf (371 kb)

Thursday June 9, 2011

Alain Couvreur (Projet COCQ, Institut de Mathématiques de Bordeaux)
Une nouvelle construction géométrique de codes sur de petits corps
B013, 10:30
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 F2. Une approche classique consiste à choisir un bon code défini sur une extension F2m de F2 et de le « descendre » sur F2 via une opération arithmétique classique (restriction, trace, etc...)
Si le code défini sur F2m est un code géométrique construit sur une courbe de genre 0 et judicieusement choisi, l'opération de restriction à F2 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 F2.

Tuesday June 7, 2011

Christophe Mouilleron (Projet Arénaire, LIP, ENS Lyon)
Génération de schémas d'évaluation avec contraintes pour des expressions arithmétiques
A006, 10:30
transparents: pdf (445 kb)
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é.

Monday May 30, 2011

Marion Videau (ANSSI)
Cryptanalyse d'ARMADILLO2
A217, 14:00

Monday May 30, 2011

Hamza Jeljeli (LACAL, EPFL, Lausanne)
RNS on Graphic Processing Units
A213, 09:30

Wednesday May 18, 2011

Benjamin Smith (Projet TANC, LIX, École Polytechnique)
Middlebrow Methods for Low-Degree Isogenies in Genus 2
A006, 10:30

Thursday May 5, 2011

Xavier Pujol (Projet Arénaire, LIP, ENS Lyon)
Analyse de BKZ
B013, 10:30
transparents: pdf (870 kb)
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 Õ(n3/k2) appels à une routine de HKZ-réduction, BKZk renvoie une base telle que la norme du premier vecteur est bornée par ≈ γkn/2(k-1) × det(L)1/n. Le principal outil de la preuve est l'analyse d'un système dynamique linéaire associé à cet algorithme.

Thursday April 21, 2011

Răzvan Bărbulescu (Projet CARAMEL, LORIA)
Améliorations au problème du logarithme discret dans Fp*
B013, 10:30
transparents: pdf (306 kb)

Thursday April 14, 2011

Alin Bostan (Projet ALGORITHMS, INRIA Paris-Rocquencourt)
Algébricité de la série génératrice complète des chemins de Gessel
B013, 10:30
transparents: pdf (249 kb)
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.

Wednesday March 30, 2011

Martin Albrecht (Projet SALSA, LIP6)
The M4RI & M4RIE libraries for linear algebra over GF(2) and small extensions
A006, 10:30
transparents: pdf (1881 kb)

Thursday February 17, 2011

Bogdan Pasca (Projet Arénaire, LIP, ENS Lyon)
FPGA-specific arithmetic pipeline design using FloPoCo
B013, 10:30
transparents: pdf (869 kb)

Thursday January 27, 2011

Christophe Arène (Institut de Mathématiques de Luminy)
Complétude des lois d'addition sur une variété abélienne
B013, 10:30
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.

Friday January 21, 2011

Frederik Vercauteren (ESAT/COSIC, KU Leuven)
Fully homomorphic encryption via ideals in number rings
A006, 10:30

Thursday January 20, 2011

Junfeng Fan (ESAT/COSIC, KU Leuven)
ECC on small devices
B013, 10:30

Thursday December 9, 2010

Sylvain Collange (Arénaire, LIP, ENS Lyon)
Enjeux de conception des architectures GPGPU : unités arithmétiques spécialisées et exploitation de la régularité
A006, 10:30
transparents: pdf (1216 kb)
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.

Thursday December 2, 2010

Guillaume Batog (VEGAS, LORIA)
Sur le type d'intersection de deux quadriques de P3(R)
A006, 10:30
... ou le problème des courbes de genre 1 sans point réel.

Thursday November 25, 2010

Vanessa Vitse (CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
Calcul de traces de l'algorithme F4 et application aux attaques par décomposition sur courbes elliptiques
A006, 10:30
transparents: pdf (1243 kb)
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.

Monday November 8, 2010

Mehdi Tibouchi (Équipe Cryptographie, Laboratoire d'Informatique de l'ENS)
Hachage vers les courbes elliptiques et hyperelliptiques
A006, 10:30
transparents: pdf (396 kb)
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.

Thursday November 4, 2010

Marcelo Kaihara (LACAL, EPFL, Lausanne)
Implementation of RSA 2048 on GPUs
A006, 10:30
transparents: pdf (2765 kb)

Thursday October 14, 2010

Louise Huot (Équipe SALSA, LIP6)
Étude des systèmes polynomiaux intervenant dans le calcul d'indice pour la résolution du problème du logarithme discret sur les courbes
B200, 14:00
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.

Friday July 30, 2010

Thomas Prest (Équipe CARAMEL, LORIA)
Sélection polynomiale pour le crible NFS
B013, 11:00
La sélection polynomiale est la première étape du crible NFS et consiste à trouver un couple de polynômes dans 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.

Thursday July 15, 2010

Peter Montgomery (Microsoft Research & CWI)
Attempting to Run NFS with Many Linear Homogeneous Polynomials
A213, 16:00

Thursday July 15, 2010

Julie Feltin (Équipe CARAMEL, LORIA)
Implantation de l'algorithme ECM sur GPU
A213, 14:00

Thursday June 17, 2010

Fabrice Rouillier (Projet SALSA, LIP6)
Quelques astuces pour résoudre les systèmes polynomiaux dépendant de 2 variables
A008, 10:30
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.

Thursday June 3, 2010

Xavier Goaoc (Projet VEGAS, LORIA)
Influence du bruit sur le nombre de points extrêmes
C005, 10:30
transparents: pdf (365 kb)
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 ε 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.

Friday May 28, 2010

Paul Zimmermann (Projet CARAMEL, LORIA)
1,82 ?
A006, 10:30
transparents: pdf (308 kb)
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).

Wednesday April 28, 2010

Francesco Sica (Department of Mathematics and Statistics, University of Calgary)
Une approche analytique au problème de la factorisation d'entiers
A006, 10:30
transparents: pdf (471 kb)
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(logc N)) pour tout c > 0.

Monday April 26, 2010

Jean-François Biasse (Projet TANC, LIX, École Polytechnique)
Calcul de groupe de classes d'idéaux de corps de nombres.
A006, 10:30
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.

Friday April 9, 2010

Mioara Joldeş (Projet Arénaire, LIP, ENS Lyon)
Chebyshev Interpolation Polynomial-based Tools for Rigorous Computing
A006, 10:30
transparents: pdf (690 kb)

Wednesday March 31, 2010

Peter Schwabe (Department of Mathematics and Computer Science, TU Eindhoven)
Breaking ECC2K-130
A006, 14:00
transparents: pdf (280 kb)

Friday March 26, 2010

Romain Cosset (Projet CARAMEL, LORIA)
Formules de Thomae et isogénies
A006, 10:00
transparents: pdf (392 kb)
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 y2 = 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.

Friday March 19, 2010

Luca De Feo (Projet TANC, LIX, École Polytechnique)
Isogeny computation in small characteristic
A006, 10:30

Friday March 5, 2010

Wouter Castryck (Department of Mathematics, KU Leuven)
The probability that a genus 2 curve has a Jacobian of prime order
A006, 10:00
transparents: pdf (744 kb)

Tuesday March 2, 2010

Osmanbey Uzunkol (KANT Group, Institute of Mathematics, TU Berlin)
Shimura's reciprocity law, Thetanullwerte and class invariants
A006, 10:30

Thursday February 11, 2010

Fabien Laguillaumie (Algorithmique, GREYC, Univ. Caen Basse-Normandie)
Factorisation des entiers N = pq2 et applications cryptographiques
A006, 10:30
transparents: pdf (537 kb)
Nous présentons un algorithme original de factorisation des entiers de la forme pq2 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

Monday February 1, 2010

Pascal Molin (Institut de Mathématiques de Bordeaux)
Intégration numérique rapide et prouvée — Application au calcul des périodes de courbes hyperelliptiques
A006, 10:30

Thursday December 10, 2009

Éric Brier (Ingenico)
Familles de courbes pour factorisation par ECM des nombres de Cunningham
A208, 10:30

Les nombres de Cunningham permettent de plonger des corps de nombres de petit degré dans Z/NZ. 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 Z/4Z × Z/4Z de torsion défini sur Q8) et de rang non nul ainsi qu'une famille avec le sous-groupe Z/6Z × Z/3Z de torsion défini sur Q3) et de rang non nul. Ces familles ont été utilisées pour factoriser 2972 + 1 et 21048 + 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.

Friday September 25, 2009

Iram Chelli (CACAO)
Fully Deterministic ECM
A006, 10:30
transparents: pdf (589 kb)

Wednesday September 23, 2009

Răzvan Bărbulescu (CACAO)
Familles de courbes elliptiques adaptées à la factorisation des entiers
B100, 10:30

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.

Thursday September 17, 2009

Tadanori Teruya (LCIS, University of Tsukuba, Japan)
Generating elliptic curves with endomorphisms suitable for fast pairing computation
A006, 10:00

Tuesday June 23, 2009

Andy Novocin (ANR LareDa, LIRMM, Montpellier)
Gradual Sub-Lattice Reduction and Applications
B011, 10:30

Monday May 18, 2009

Nicolas Guillermin (Centre d'électronique de l'armement (CELAR), DGA)
Architecture matérielle pour la cryptographie sur courbes elliptiques et RNS
C103, 16:00
transparents: pdf (1027 kb)

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.

Thursday April 30, 2009

Judy-anne Osborn (Australian National University)
On Hadamard's Maximal Determinant Problem
A006, 11:00
transparents: pdf (3142 kb)

Thursday March 26, 2009

Jérémie Detrey (CACAO)
Hardware Operators for Pairing-Based Cryptography – Part II: Because speed also matters –
A006, 10:30
transparents: pdf (684 kb)

Thursday February 26, 2009

Jean-Luc Beuchat (Tsukuba)
Hardware Operators for Pairing-Based Cryptography – Part I: Because size matters –
A208, 10:00
transparents: pdf (676 kb)

Thursday November 6, 2008

Nicolas Estibals (ENS Lyon)
Multiplieurs parallèles et pipelinés pour le calcul de couplage en caractéristiques 2 et 3
A006, 11:00
transparents: pdf (872 kb)

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.

Thursday October 16, 2008

Marc Mezzarobba (Projet Algo)
Suites et fonctions holonomes : évaluation numérique et calcul automatique de bornes
A006, 10:30

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.

Thursday June 26, 2008

Éric Schost (University of Western Ontario.)
Deformation techniques for triangular arithmetic
B200, 14:00

Friday May 23, 2008

Joerg Arndt (Australian National University)
arctan relations for computing pi.
A006, 10:00
transparents: pdf (89 kb)
http://www.jjj.de/arctan/arctanpage.html

Wednesday May 14, 2008

Joerg Arndt (Australian National University)
Tests d'irreducibilité de polynômes sur GF(2) sans pgcd.
A006, 14:00

Thursday April 10, 2008

Mathieu Cluzeau (INRIA Rocquencourt, équipe SECRET)
Reconnaissance d'un code linéaire en bloc
A006, 10:30

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.

Tuesday March 25, 2008

Nicolas Meloni (Université de Toulon)
Chaines d'additions différentielles et multiplication de point sur les courbes elliptiques
A006, 10:30

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.

Thursday February 14, 2008

Laurent Imbert (LIRMM)
Quelques systèmes de numération exotiques (et applications)
A006, 10:30

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.

Thursday February 7, 2008

Guillaume Melquiond (MSR-INRIA)
L'arithmétique flottante comme outil de preuve formelle
A006, 10:30

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.

Thursday January 31, 2008

Aurélie Bauer (Université de Versailles Saint-Quentin-en-Yvelines, Laboratoire PRISM,)
Vers une variante rigoureuse de l'algorithme de Coppersmith en trois variables.
A006, 10:30

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.

Thursday January 17, 2008

Nicolas Julien (Projet Marelle, INRIA Sophia Antipolis.)
Arithmétique réelle exacte certifiée
A006, 10:30

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.

Wednesday December 5, 2007

Christophe Doche
DBNS et cryptographie sur courbes elliptiques
A006, 10:30

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

Thursday November 29, 2007

Clément Pernet
Algèbre linéaire dense dans des petits corps finis: théorie et pratique.
B13, 10:30

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.

Thursday November 8, 2007

Thomas Sirvent
Schéma de diffusion efficace basé sur des attributs
A006, 10:30

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.

Monday June 18, 2007

Jean-Luc Beuchat
Arithmetic Operators for Pairing-Based Cryptography
B13, 10:30
transparents: pdf (625 kb)

Thursday June 14, 2007

Ley Wilson
Quaternion Algebras and Q-curves
B13, 10:30

Thursday June 7, 2007

Jeremie Detrey
Évaluation en virgule flottante de la fonction exponentielle sur FPGA
B13, 10:30

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.

Tuesday June 5, 2007

David Kohel (Université de Sydney et UHP-Nancy 1)
Complex multiplication and canonical lifts
B200, 14:00

Thursday April 26, 2007

David Lubicz
Relèvement canonique en caractéristique impaire.
B200, 10:30

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.

Tuesday April 17, 2007

Paul Zimmermann
Fast Multiplication over GF(2)[x]
B200, 14:00

Tuesday April 17, 2007

Richard Brent
A Multi-level Blocking Algorithm for Distinct-Degree Factorization of Polynomials over GF(2).
B200, 10:30

Thursday March 15, 2007

Ben Smith
Explicit isogenies of hyperelliptic Jacobians
B011, 10:30

Thursday March 8, 2007

Guillaume Hanrot
Problème du vecteur le plus court dans un réseau : analyse de l'algorithme de Kannan (travail commun avec D. Stehlé).
B011, 11:00

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 \`a une complexit\'e 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.

Thursday February 8, 2007

Guillaume Melquiond (Projet Arénaire, INRIA Rhône-alpes.)
De l'arithmétique d'intervalles à la certification de programmes
C010, 11:00

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.

Tuesday January 16, 2007

Sylvain Chevillard (orateur), Christoph Lauter (Projet Arénaire, INRIA Rhône-alpes.)
Une norme infinie certifiée pour la validation d'algorithmes numériques
B200, 14:45
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.

Tuesday January 16, 2007

Christoph Lauter (Projet Arénaire, INRIA Rhône-alpes.)
Automatisation du contrôle de précision et de la preuve pour les formats double-double et triple-double
B200, 14:00
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.

Tuesday January 16, 2007

Sylvain Chevillard (Projet Arénaire, INRIA Rhône-alpes.)
Approximation polynomiale de fonctions continues et nombres flottants
B200, 11:00

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 :

  1. on détermine sur quel intervalle on souhaitera évaluer la fonction ;
  2. on détermine avec quelle précision on souhaite connaître les valeurs de la fonction ;
  3. on cherche un approximant fournissant la précision requise sur l'intervalle choisi.
  4. 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.

Wednesday November 29, 2006

Cédric Lauradoux (Projet Codes, INRIA Rocquencourt.)
Synthèse des registres à décalage
A208, 09:00
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).

Tuesday October 10, 2006

Marcus Wagner (Technische Universität Berlin)
On Deuring correspondences of algebraic function fields
B200, 14:00

Friday April 14, 2006

Michael Quisquater
Cryptanalyse lineaire des algorithmes de chiffrement par bloc.
B200, 10:00
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.

Thursday April 6, 2006

Stef Graillat
Évaluation précise de polynômes en précision finie
B200, 10:00
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.

Monday March 27, 2006

Christopher Wolf
Division without Multiplication in Factor Rings
B200, 11:00

Thursday March 23, 2006

Benoît Daireaux
Analyse dynamique des algorithmes euclidiens
B200, 14:00
transparents: pdf (522 kb)
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.

Thursday March 16, 2006

Frederik Vercauteren
The Number Field Sieve in the Medium Prime Case
B200, 14:00
TBA

Thursday February 16, 2006

Thomas Plantard
Arithmétique modulaire pour la cryptographie.
A208, 10:00
transparents: pdf (966 kb)
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.

Thursday January 5, 2006

Marion Videau (Projet Codes, INRIA Rocquencourt.)
Propriétés cryptographiques des fonctions booléennes symétriques.
A208, 11:00
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.

Thursday November 24, 2005

Alexander Kruppa (Technische Universität München)
Optimising the enhanced standard continuation of P-1, P+1 and ECM
B200, 10:00

Wednesday November 23, 2005, groupe de travail

Sebastian Pauli (Technische Universität Berlin)
Construction Class Fields of Local Fields
B200, 10:00

Tuesday November 8, 2005, groupe de travail

Damien
titre à préciser
B200, 16:00
résumé à préciser

Thursday October 13, 2005

Andreas Enge (Projet Tanc, INRIA Futurs, LIX)
Sur le calcul de polynômes de classes par des approximations flottantes
B013, 16:00
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.

Thursday October 6, 2005

Florian Hess (Technische Universität Berlin)
Arithmétique sur des courbes générales
B200, 10:00

Thursday September 29, 2005, groupe de travail

Pierrick
On finit l'exposé d'il y a deux semaines.
B200, 11:00

Thursday September 29, 2005, groupe de travail

Paul
On finit l'exposé de la semaine dernière.
B200, 10:00

Thursday September 22, 2005, groupe de travail

Paul
Calcul de fonctions holonomes en O(M(n) log(n)3)
A006, 10:00

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) * 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).

Thursday September 15, 2005, groupe de travail

Pierrick
Fonctions thétas et formules efficaces pour loi de groupe en genre 2.
B200, 10:30

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.

Tuesday June 21, 2005

Benjamin Werner (Projet LogiCal, INRIA Futurs, LIX)
A propos de la preuve formelle du théorème des quatre couleurs
B13, 11:00

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.

Tuesday June 21, 2005

Roland Zumkeller (Projet LogiCal, INRIA Futurs, LIX)
Traitement d'inégalités réelles en Coq
B200, 14:00

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.

Friday June 3, 2005, groupe de travail

Julien Cochet
à préciser
B200, 11:00

Thursday April 14, 2005

Damien Vergnaud (LMNO, CNRS / Université de Caen.)
Sur le problème xyz-Diffie Hellman décisionnel.
A006, 16:00

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, ...)

Thursday April 7, 2005, groupe de travail

Jean-Yves Degos
Étude de l'article Basiri-Enge-Faugère-Gurel sur l'arithmétique des courbes C3,4
B200, 14:00

Wednesday March 23, 2005, groupe de travail

Paul
Étude de l'article de P. L. Montgomery intitulé "Five, Six, and Seven-Term Karatsuba-Like Formulae".
B200, 14:00

Thursday March 10, 2005, groupe de travail

Emmanuel
Étude des preuves d'OAEP et OAEP+
B200, 14:00

Thursday March 3, 2005

Régis Dupont (projet TANC, INRIA Futurs, LIX)
Theta constantes et moyenne de Borchardt, applications.
B11, 10:30

Sur le corps des complexes, une courbe de genre g est isomorphe à un tore à g trous, i.e., à un quotient de la forme Cg/(Zg.1⊕Zg.τ) où τ est une matrice g×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, …).

Dernière modification: Wed 20 Sep 2017 01:35:45 PM CEST
© 2006– membres du projet ; XHTML 1.0 valide, CSS valide