BEGIN:VCALENDAR
CALSCALE:GREGORIAN
VERSION:2.0
X-WR-TIMEZONE:Europe/Paris
METHOD:PUBLISH
PRODID:-//LIP6//www.lip6.fr//FR
X-WR-CALNAME;VALUE=TEXT:Séminaire LIP6
X-LIC-LOCATION:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
DTSTART:19810329T020000
TZNAME:GMT+02:00
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
DTSTART:19961027T030000
TZNAME:GMT+01:00
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:Thèse Mickaël HAMDAD :
ORGANIZER;CN=Mickaël HAMDAD:MAILTO:Mickael.Hamdad@lip6.fr
DESCRIPTION:La sécurité de nombreux cryptosystèmes basés sur les 
 codes correcteurs repose sur la difficulté du problème suivant : é
 tant donnés une matrice H, un vecteur s et un entier w, trouver un v
 ecteur e comportant au plus w coordonnées non nulles et vérifiant H
 e = s. Ce dernier se nomme problème de décodage par syndrome. L’o
 bjectif principal de cette thèse est de proposer de nouveaux algorit
 hmes pour le résoudre et d’affiner l’analyse de ceux existants.
  De nombreux algorithmes de décodage utilisent de façon cruciale un
 e sous-routine qui résout le problème des plus proches voisins. Dan
 s un premier temps, nous étudions les méthodes de résolution de ce
  problème. En particulier, nous analysons l’algorithme de May–Oz
 erov pour le problème des plus proches voisins afin de le comparer
  à un algorithme plus classique appelé méthode des projections. Po
 ur cela, nous établissons de nouvelles bornes sur la complexité de 
 ces deux algorithmes qui prennent en compte les facteurs constants et
  polynomiaux. Ces résultats montrent que l’algorithme de May–Oze
 rov est galactique : bien que sa complexité possède un meilleur exp
 osant asymptotique que la méthode des projections, il ne devient plu
 s efficace que pour des instances de taille hors de portée en pratiq
 ue. Nous montrons ainsi qu’utiliser la méthode des projections dan
 s les algorithmes de décodage par ensemble d’information est le me
 illeur des deux choix.
  Dans un second temps, nous étudions le prob
 lème de décodage par syndrome quasi-abélien, sur lequel repose la 
 sécurité de plusieurs générateurs de corrélations pseudo-aléato
 ires. Nous réduisons ce problème à un problème d’interpolation 
 de polynômes multivariés creux sur de petits corps finis. Nous dév
 eloppons ensuite de nouveaux algorithmes pour résoudre ce problème 
 d’interpolation. D’une part des méthodes simples inspirées d’
 une idée de Richard Zippel, d’autre part une méthode plus avancé
 e basée sur un plongement dans le corps des nombres complexes et sur
  l’acquisition comprimée. Ces algorithmes permettent d’obtenir d
 es attaques pratiques contre plusieurs jeux de paramètres proposés 
 pour le problème de décodage par syndrome quasi-abélien. En partic
 ulier, pour les paramètres agressifs du protocole F4OLEAGE, notre im
 plémentation distingue la sortie du générateur de l’aléatoire a
 vec un avantage supérieur à 60 % et récupère l’ensemble des pol
 ynômes secrets avec une probabilité supérieure à 13 %.
DTSTAMP:20260805T171739Z
DTSTART;TZID=Europe/Paris:20260926T100000
DURATION:PT2H
URL;VALUE=URI:https://www.lip6.fr/actualite/personnes-fiche.php?ident=D2592
UID:LIP6/SEM/D2592
LOCATION:Campus Pierre et Marie Curie, salle Jacques Pitrat (25-26/10
 5)
GEO:48.847047;2.354619
END:VEVENT
END:VCALENDAR