• Christine Bachoc (Université de Bordeaux) – Codes binaires, distances multivariées et programmation semidéfinie positive.

RESUME : C’est un problème classique en théorie des codes de déterminer le nombre maximum de mots qu’un code binaire ayant une distance minimale donnée peut avoir. La meilleure borne supérieure connue pour ce nombre est obtenue par la valeur optimale d’un programme linéaire, et est due à Philippe Delsarte (1973). Un certain nombre de généralisations de la distance de Hamming sous la forme de fonctions de $k\geq 3$ mots binaires ont été étudiées en théorie des codes, notamment en >relation avec la notion de décodage en liste. Nous présenterons un certain nombre de ces fonctions, et montrerons comment la programmation semidéfinie positive combinée avec de l’analyse harmonique du groupe des symétries de l’espace de Hamming peut permettre de donner des bornes analogues à celle de Delsarte, en exploitant des idées issues de l’optimisation combinatoire.

Christine.Bachoc-08-01-2010 (format pdf)

  • Anne Canteaut (INRIA Paris-Rocquencourt) – Modes opératoires pour les fonctions de hachage itératives

RESUME : Dans une fonction de hachage itérative, le choix du mode opératoire est essentiel car il influence à la fois sa sécurité et ses performances. La notion d’indifférentiabilité, introduite par Maurer, Renner et Holenstein en 2004, est particulièrement adaptée au cas des fonctions de hachage. Elle a par exemple été appliquée à certaines variantes de la construction de Merkle-Damgard et à la construction éponge, ce qui permet de déterminer le nombre de requêtes à la fonction de compression nécessaires pour différentier la fonction de hachage d’un oracle aléatoire. Nous verrons comment ces preuves peuvent tre généralisées et adaptées par exemple au nouveau mode opératoire utilisé dans Shabal, notre candidat à la compétition SHA-3. Dans ce cas, l’indifférentiabilité est mme préservée (dans une certaine limite) si la famille de permutations paramétrées utilisée ne se comporte pas comme un chiffrement par blocs idéal, mais possède certains distingueurs.
L’intérêt majeur de ce mode est donc qu’il permet d’atteindre de meilleures performances que les constructions classiques, notamment parce qu’il autorise l’utilisation de permutations paramétrées plus rapides que celles employées habituellement.
Ceci résulte d’un travail commun avec les membres de l’équipe de Shabal : http://www.shabal.com

Anne.Canteaut-08-01-2010 (format pdf)

  • Alain Couvreur (INRIA Saclay) – Codes géométriques sur les surfaces et leurs duaux, difficultés et points forts

RESUME : Si la théorie des codes sur les courbes a été étudiée de façon approfondie par une communauté aussi large qu’éclectique de mathématiciens, le cas des variétés de dimension supérieure n’a pas bénéficié du même succès. Une des explications de l’intérêt moindre porté sur ces codes est que leur étude est nettement plus complexe. En effet, certains problèmes tels que l’approximation des paramètres ou la description du code dual se résolvent très simplement pour les codes sur les courbes et deviennent extrêmement difficiles lorsque l’on travaille sur des variétés de dimension supérieure.
Dans cet exposé, nous présenterons une nouvelle construction de codes correcteurs d’erreurs à partir de $2$-formes différentielles sur des surfaces algébriques. Cette construction, bien que théoriquement et techniquement plus complexe, s’avère être une extension naturelle aux surfaces de la construction des codes géométriques « $C_{\Omega}$ » de Goppa bien connus dans le cas des courbes. De façon surprenante l’orthogonalité entre codes fonctionnels et différentiels – toujours vraie dans le cas des courbes – ne s’étend pas aux cas des surfaces. En général, le dual d’un code fonctionnel sur une surface ne se réalise pas comme code fonctionnel ou différentiel sur cette même surface. Cette dernière observation fait de la théorie des codes sur les surfaces une théorie en un sens plus riche que la théorie analogue sur les courbes puisque pour une surface donnée on peut construire « deux fois plus de codes », les codes fonctionnels et leurs duaux étant de type différent.
Nous terminerons cet exposé en présentant un procédé d’estimation de la distance minimale de l’orthogonal $C_L^{\bot}$ d’un code fonctionnel sur une surface. Cette méthode de minoration mêle théorèmes de Bertini et théorie de l’intersection.

Alain.Couvreur-08-01-2010 (format pdf)

  • Nicolas Gama (Université de Caen) – Réduction de réseau, la boîte à outils du cryptanalyste

RESUME : Depuis 1982, la réduction de réseau est un des principaux outils en cryptanalyse, et plus récemment, en cryptographie. Plus particulièrement, l’algorithme LLL et ses variantes par bloc permettent d’approcher des problèmes NP-durs tels le plus court vecteur (SVP) ou le plus proche vecteur (CVP) dans des réseaux euclidiens. La sécutité de certains cryptosystèmes se traduit naturellement en des problèmes de réseaux (Merkle Hellman, NTRU, LWE, GPV). De par la richesse de l’echelle de complexité des approximations du SVP, certains de ces cryptosystèmes sont totalement cassés, alors que d’autres possèdent au contraire une preuve de sécurité reposant sur une difficulté dans le pire cas.
Les réseaux permettent ont aussi des applications indirectes sur la factorisation de polynomes à coefficients rationnels (inconditionnellement en temps polynomial, il s’agit de la toute première application de LLL), et aussi sur la factorisation entière lorsque l’on connaît une information supplémentaire concernant un de ses diviseurs: comme par exemple un nombre s’exprimant comme un « petit » rationnel modulo un diviseurs. Ce principe, basé sur une variante de la methode de Coppersmith, a permis par le passé de factoriser en temps polynomial des nombres de la forme pq^r avec r grand, il a eu cette année de très lourdes conséquences sur toutes les instances du cryptosystème Nice, et pourrait aussi avoir de légères répercussions sur NTRU.

Nicolas.Gama-08-01-2010 (format pdf)