624 résultats

  • Un nouvel algortithme itératif rapide pour le PGCD de deux entiers

    • 19 mars 2004

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Sidi Mohamed Sedeljmaci

    Nous présentons un nouvel algorithme itératif pour le PGCD de deux entiers ou deux polynômes. Il est base sur une procédure itérative de type half-GCD qui évite la répétition d'appels récursifs. On procède progressivement a partir des bits de poids les plus forts. Quoique la complexité reste en $O(n \log2 n \log \log n$ pour deux entiers de $n$ bits, comme l'algorithme fameux de Schonhage, notre[…]
  • Algorithme probabiliste d'Ajtai, Kumar et Sivakumar de recherche du plus court vecteur dans un réseau

    • 12 mars 2004

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Damien Stehlé - INRIA Lorraine - ENS

    Nous présenterons l'algorithme d'Ajtai, Kumar et Sivakumar pour résoudre le problème du plus court vecteur d'un réseau Euclidien. Ce problème a été prouvé NP-dur sous des réductions randomisées par Ajtai en 1996. Cet algorithme, présenté à STOC 2001, a une complexité probabiliste $2^O(n)$ en temps et en espace. Il bat donc la précédente borne de complexité ($n^{O(n)}$), qui correspond à l[…]
  • Schémas de codage étendu pour canaux "wire-tap" et applications à l'identification biométrique

    • 05 mars 2004

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Gilles Zémor - ENST

    Un mécanisme traditionnel de mise en gage (commitment) consiste à publier $y=f(b)$ où $f$ est une fonction à sens unique et $b$ est un vecteur binaire destiné à rester caché jusqu'à ce qu'il soit révélé. La vérification que $f(b)=y$ empêche de révéler un vecteur différent de celui sur lequel on s'est engagé. Le problème d'une mise en gage {\em floue} (fuzzy commitment) se pose lorsqu'on souhaite[…]
  • Courbes a sécurité réduite en cryptographie hyperelliptique

    • 27 février 2004

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Nicolas Thériault - Université de Toronto

    Au cours des dernières années, les courbes hyperelliptiques se sont imposées comme une bonne alternative aux courbes elliptiques pour la cryptographie a clé publique. Il est donc important de développer une bonne évaluation de la sécurité des cryptosystèmes qui en découlent.<br/> Dans cet expose, nous présentons certains développements récents pour deux types d'attaques contre le problème du log[…]
  • Autour d'un algorithme de calcul de sommes de Kloosterman (d'après un travail de N.Tsuzuki)

    • 06 février 2004

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Gweltaz Chatel - Université de Rennes

    Dans une optique voisine de celle ayant mené Lauder et Wan à leur algorithme de comptage de points, on regardera l'interprètation cohomologique des sommes de Kloosterman, et ce dans le langage de la cohomologie rigide. Cela nous amènera à construire et considérer un F-isocristal dit de Bessel. Par nature, sa matrice de Frobenius vérifie une équation différentielle. En tirant parti du fait que,[…]
  • Sécurité informatique, de la vérification formelle de protocoles cryptographiques à la détection d'intrusions en temps réel

    • 30 janvier 2004

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Jean Goubeault-Larrecq - ENS Cachan

    Le but de cet exposé est de présenter très grossièrement deux aspects de la recherche en sécurité menée au LSV (laboratoire spécification et vérification, ENS Cachan et CNRS UMR 8643) et dans le projet INRIA SECSI.<br/> Un premier aspect est la vérification automatique de protocoles cryptographiques. L'idée est au départ de vérifier qu'un protocole est sûr sous des hypothèses simplificatrices[…]