511 results
-
Un nouvel algortithme itératif rapide pour le PGCD de deux entiers
Speaker : 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[…] -
Algebraic attacks and design of block ciphers, stream ciphers, and multivariate public key schemes
Speaker : Nicolas Courtois - Schlumberger
Following the famous 1949 paper of Shannon, breaking a "good" cipher should require: "as much work as solving a system of simultaneous equations in a large number of unknowns of a complex type". For most practical cryptosystems, the problem of recovering the key can indeed can be seen as solving a huge system of binary nonlinear equations. In general, solving such a problem is[…] -
Algorithme probabiliste d'Ajtai, Kumar et Sivakumar de recherche du plus court vecteur dans un réseau
Speaker : 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[…] -
Schémas de codage étendu pour canaux "wire-tap" et applications à l'identification biométrique
Speaker : 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[…] -
Courbes a sécurité réduite en cryptographie hyperelliptique
Speaker : 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[…] -
Autour d'un algorithme de calcul de sommes de Kloosterman (d'après un travail de N.Tsuzuki)
Speaker : 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[…]