• Carlos Aguilar, Université de Limoges, – De l’utilisation du produit tensoriel pour le chiffrement complètement homomorphe

Résumé : Très récemment d’importantes avancées ont été réalisées en cryptographie au niveau des systèmes de chiffrement homomorphe, outils permettant de réaliser des calculs sur des données chiffrées sans passer par les données en clair. L’obtention de ces outils, souvent décrits comme le Graal de la cryptographie, a été un des problèmes ouverts les plus importants de la cryptographie depuis trente ans.

Dans cet exposé nous montrons comment l’utilisation de primitives cryptographiques basées sur des problèmes autres que ceux de la théorie des nombres a permis de débloquer ce problème en présentant rapidement les grandes constructions et en se focalisant ensuite sur l’utilisation du produit tensoriel.

• Sylvain Duquesne, Université de Rennes 1,- Représentation RNS des nombres et calcul de couplages

Résumé : Dans cet exposé, Je présenterai rapidement le système de représentation des nombres basé sur le théorème des restes chinois (RNS) et je montrerai comment et pourquoi il est bien adapté au calcul de couplages, en particulier pour les grands degrés d’extension comme pour les courbes BN et pour les implémentations matérielles (FPGA dans notre cas).

• Elodie Leducq, Université Paris 7, – Rayon de recouvrement des codes de Reed-Muller généralisés

Résumé : Le rayon de recouvrement des codes de Reed-Muller a surtout été étudié pour les codes de Reed-Muller binaires. Dans cet exposé, nous nous proposons d’étendre certains résultats aux codes de Reed-Muller généralisés. Plus, précisément nous en donnerons un encadrement qui permet de le calculer pour un nombre pair de variables. Dans le cas d’un nombre impair de variable, nous améliorerons cet encadrement pour un corps à trois éléments.

• Christophe Petit, Université Catholique de Louvain, –On polynomial systems arising from a Weil descent

Résumé : Polynomial systems of equations appearing in cryptography tend to have special structures that simplify their resolution. In this talk, we discuss a class of polynomial systems arising after deploying a ultivariate polynomial equation over an extension field into a system of polynomial equations over the ground prime field (a technique commonly called Weil descent). We provide theoretical and perimental evidence that the degrees of regularity of these systems are very low, in fact only slightly larger than the maximal degrees of the equations. We then discuss cryptographic applications of particular instances of) these systems to the hidden field equation (HFE) cryptosystem, to the factorization problem in SL(2,2^n) and to the elliptic curve discrete logarithm over binary fields. In particular, e show (under a classical heuristic assumption in algebraic cryptanalysis) that an elliptic curve index calculus algorithm due to Claus Diem has subexponential time complexity (2^{c\,n^{2/3}\log n})\) over the binary field GF(2^n), where c is a constant smaller than 7/3.

Based on joint work with Jean-Charles Faugère, Ludovic Perret, Jean-Jacques Quisquater and Guénaël Renault.

• Thierry Berger (Université de Limoges) – Une approche globale des automates algébriques (LFSR, FCSR, AFSR…). Application au design des générateurs pseudo-aléatoires

Résumé : Les automates LFSR et FCSR sont des automates qui calculent le développement selon les puissances croissantes de fractions rationnelles. Dans le cas LFSR, il s’agit de quotients de polynômes binaires (ou à coefficients dans un corps fini), dans le cas FCSR, il s’agit du développement 2-adique de quotients d’entiers. La principale différence entre LFSR et FCSR est la propagation de retenues, ce qui rend les automates FCSR non-linéaires au sens de la GF(2)-linéarité. Cette propriété a permis de les utiliser efficacement pour construire une famille de générateurs pseudo-aléatoires pour le chiffrement à flot (F-FCSR).

Dans cet exposé, nous présentons les propriétés de base des LFSR et des FCSR, le fonctionnement des générateurs F-FCSR et l’attaque de Hell et Johansson sur les F-FCSR basés sur des automates FCSR en mode Galois.

Cette attaque nous a poussé à adopter une approche matricielle pour la construction d’automates FCSR. Cette approche nous a permis de contrecarrer l’attaque précédente et de construire ainsi des automates plus performants simultanément en hardware et software.

Cette approche matricielle peut se généraliser à des anneaux munis d’une topologie I-adique relativement à un élément p particulier. Ceci permet de construire des automates appelés AFSR (Algebraic Feedback Shift Register). Nous donnerons plusieurs exemples d’applications, aussi bien dans le cas classique GF(2)[x] que dans certains anneaux non euclidiens.

Thierry.Berger-27-05-2011 (format pdf)

• Delphine Boucher (Université de Rennes 1) – Autour des codes définis sur des anneaux de polynômes tordus

Résumé : Dans cet exposé, après avoir fait un bref rappel sur les codes d’évaluation et les codes « q-cycliques » inventés par Gabidulin en 1985, on introduit la classe des codes tordus modules. Ces codes sont définis sur des anneaux de polynômes non commutatifs F[x,theta] où F est un corps fini et la multiplication est régie par la règle x*a=theta(a)*x pour a dans F. On s’intéressera en particulier à donner une matrice génératrice et une matrice de contrôle pour ces codes et on construira des codes tordus auto-duaux.

Delphine.Boucher-27-05-2011 (format pdf)

• Benoît Gérard (Université Catholique de Louvain)– L’entropie de Shannon : un outil générique pour analyser les attaques statistiques

Résumé : L’entropie de Shannon: un outil générique pour analyser les attaques statistiques.

Les liens étroits qu’entretiennent cryptographie et théorie de l’information sont connus depuis la fondation de cette dernière par Claude Shannon en 1948. Dès 1949, il applique sa théorie de la communication à la science du secret et depuis, la théorie de l’information a été principalement employée dans le cadre de la cryptographie à sécurité prouvée.

En 2009, on retrouve la notion d’entropie pour quantifier la force d’une attaque dans deux cadres assez différents: les attaques par canaux auxiliaires et la cryptanalyse linéaire multiple. L’objectif recherché dans le cadres des attaques par canaux auxiliaires est de pouvoir comparer, avec une métrique unique, différentes attaques (ou différentes implémentations). Dans le cadre de l’analyse de la cryptanalyse linéaire multiple, le but est de contourner la difficulté due à l’aspect multidimensionnel de l’attaque.

Nous nous intéresserons à ce dernier point: l’utilisation de la théorie de l’information pour l’analyse des cryptanalyses statistiques. Nous verrons sur plusieurs exemples que cette technique permet, de façon relativement simple, d’obtenir des résultats intéressants.

Benoit.Gerard-27-05-2011 (format pdf)

• Eleonora Guerrini (Université de Caen)–Deux problèmes difficiles dans les graphes et leurs applications

Résumé : Dans cet exposé nous allons introduire deux problèmes difficiles dans les graphes: la recherche d’un code identifiant et la recherche d’un noyau, et nous discuterons des applications possibles. Un code identifiant est un sous ensemble structuré de sommets d’un graphe et nous verrons comment utiliser cet objet pour détecter une panne dans un réseau d’ordinateurs. L’existence d’un tel code est garantie pour tout graphe à voisinages disjoints, mais il est difficile de trouver des bornes sur sa taille minimale. Nous verrons des solutions pour résoudre cette question. Un noyau est un sous-ensemble de sommets à la fois stable et dominant. Le problème de savoir si un graphe possède un noyau est un problème NP-complet. Nous montrerons d’une part comment utiliser cette propriété en cryptographie (on cache un noyau dans un graphe aléatoire). D’autre part, nous proposerons des algorithmes qui recherchent un noyau et étudierons leur complexité afin de déterminer comment construire des instances difficiles.

Eleonora.Guerrini-27-05-2011 (format pdf)

• Sorina Ionica (Ecole Polytechnique)– Couplages, volcans d’isogénies et calcul de l’anneau d’endomorphismes d’une courbe elliptique

Résumé : En 1996, D. Kohel propose un premier algorithme pour le calcul de l’anneau d’endomorphismes d’une courbe elliptique. Sa méthode repose, entre autres, sur un algorithme de parcours en profondeur du graphe d’isogénies (ce qu’on appelle un volcan). Les méthodes existantes a nos jours pour déterminer l’anneau d’endomorphismes utilisent des algorithmes de parcours de graphes d’isogénies. J’expliquerai l’algorithme de Kohel et je montrerai, en utilisant des résultats de ma thèse, que l’on peut calculer l’anneau d’endomorphismes sans avoir a parcourir les volcans d’isogénies et juste en calculant un petit nombre de couplages. Cela est possible lorsque la factorisation du conducteur de l’anneau d’endomorphismes contient que des facteurs premiers de taille pas très grande. Néanmoins, cette méthode a l’avantage d’éviter les calculs coûteux d’isogénies, en les remplaçant par un calcul rapide de couplage.

Sorina.Ionica-27-05-2011 (format pdf)

• Oded Regev (CNRS, ENS, Paris, and Tel Aviv University) – Learning with Errors over Rings

Based on joint work with Vadim Lyubashevsky and Chris Peikert.

RESUME :The « learning with errors » (LWE) problem is to distinguish randomlinear equations, which have been perturbed by a small amount ofnoise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications.

Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. After a short introduction to the area, we will discuss recent work on making LWE and its applications truly efficient by exploiting extra algebraic structure. Namely, we will define the ring-LWE problem, and prove that it too enjoys very strong hardness guarantees. We will mention some recent cryptographic applications in this line of work. Oded.Regev-21-01-2011 (format pdf)

• Marine Minier (INSA Lyon) – Quelques propriétés intégrales de Rijndael, LANE et Groestl

RESUME : Derrière ces étranges noms se cachent tout d’abord un chiffrement par blocs ou plutôt plusieurs versions d’un même chiffrement « Rijndael » dont la version pour des blocs de 128 bits est devenue le dernier standard de chiffrement américain l’AES en 2001. Quant à LANE et Groestl, il s’agit de deux candidats de la phase 1 de l’appel du NIST à la compétition SHA3 afin de standardiser une nouvelle fonction de hachage.

Nous nous intéresserons, dans cet exposé, à une forme d’attaques particulière contre ces algorithmes appelée cryptanalyse intégrale. Cette attaque a été introduite en 1997 par Lars Knudsen contre le chiffrement SQUARE puis ensuite formalisée en 2002 par David Wagner et Lars Knudsen. Il s’agit ici de faire prendre à un mot particulier du bloc à chiffrer toutes les valeurs possibles, les autres mots étant constants, afin d’observer après un certain nombre de tours de chiffrement des sommes de mots à 0. Ce type de propriétés, au même titre que les propriétés différentielles ou linéaires, permet de construire des relations statistiques ayant de grandes chances de se produire entre les entrées et les sorties d’un chiffrement limité à un nombre particulier de tours. On peut alors distinguer les sorties d’un chiffrement d’une suite aléatoire. Marine.Minier-21-01-2011 (format pdf)

• Tony Ezome (Université de Toulouse) – Les nombres premiers : recherche et intérêt

RESUME : Le théorème fondamental de l’arithmétique stipule que tout entier se décompose, de manière unique à l’ordre près des facteurs, en produit de nombres premiers. Mais en pratique la factorisation des grands entiers est un problème difficile. La preuve de primalité est à la base du processus de factorisation d’un entier. Et aujourd’hui, la cryptographie symétrique utilise les nombres premiers pour chiffrer les messages. On peut le voir dans la construction de grands entiers difficilement factorisables réalisée par les cryptosystèmes RSA. D’autre part, on se sert des nombres premiers en cryptographie asymétrique pour fixer un corps de base $F_p$, considérer des courbes elliptiques $E/F_p$ définies sur ce corps de base et profiter de la difficulté du problème du logarithme discret dans le groupe des points de $E$ pour produire des cryptosystèmes d’une grande robustesse. La conception de critères de primalité et des algorithmes qui en découlent a donc toute son importance.

Dans cet exposé nous reviendrons sur les tests de primalité Miller-Rabin (probabiliste et très efficace en pratique), AKS (déterministe utilisant les extensions cyclotomiques, mais lent nn pratique) et ECPP (probabiliste et très puissant, il fournit un certificat de primalité) avant de présenter un nouveau critère de primalité : le critère AKS elliptique. Il s’agit d’une amélioration du test AKS qui utilise les courbes elliptiques. Tony.Ezome-21-01-2011 (format pdf). Une version longue est disponible.

• Thomas Fuhr (ANSSI)– Cryptanalyse de fonctions de hachage : RadioGatun et Hamsi-256

RESUME : Les fonctions de hachage cryptographiques constituent un domaine dans lequel de nombreux développements sont apparus ces dernières années, tant du point de vue de la conception que du point de vue des attaques. Les techniques liées à la cryptanalyse différentielle ont mis à mal les standards de hachage existants. Cela a conduit le NIST à organiser la compétition SHA-3, dont l’objectif est la définition d’une nouvelle norme en matière de hachage.

Dans cet exposé nous nous intéressons à la cryptanalyse des fonctions de hachage, et à son évolution au cours des dernières années. La compétition SHA-3 requiert une capacité à évaluer la sécurité d’un nombre conséquent de fonctions de hachage en l’espace de 3 ans. De nombreux travaux récents mettent donc en lumière des vulnérabilités pas toujours directement exploitables de fonctions de hachage. De nouvelles techniques de cryptanalyse sont également apparues. Nous évoquerons particulièrement deux attaques contre des fonctions de hachage dont la fonction de compression est de bas degré algebrique. La première est une attaque en recherche de collisions sur RadioGatun, dont une partie des principes de conceptions ont conduit à la définition du candidat SHA-3 Keccak. Nous décrirons également une attaque en recherche de secondes préimages sur la fonction Hamsi-256, basée sur l’étude de ses propriétés algébriques. Thomas.Furr-21-01-2011 (format pdf)

• Gary McGuire (University College Dublin)-« Further results on divisibility of Kloosterman Sums over Finite Fields »

Travaux commun avec Richard Moloney, Faruk Gologlu

RESUME : Kloosterman sums, their values and distribution of values, have several connections to coding theory, cryptography, bent functions, and aspects of number theory (see Dillon, Lachaud-Wolfmann for example). The value 0 has particular interest. A characterization of zeros of Kloosterman sums over binary and ternary fields appears to be difficult to find. Authors such as Lisonek, Helleseth, Zinoviev, Charpin, have recently focused on characterizations of Kloosterman sums that are divisible by certain powers of 2 and 3. We will first give an introduction to the topic, and then present some recent results that characterize Kloosterman sums modulo higher powers of 2 and 3.

Présentation annulée et reportée sine die.

• Damien Vergnaud (ENS) – Systèmes de preuve Groth-Sahai et applications

Travaux en commun avec O. Blazy, G. Fuchsbauer, M. Izabachène, A. Jambert, B. Libert, D. Pointcheval & H. Sibert.

RESUME : Les preuves à divulgation nulle de connaissance sont des protocoles qui permettent à un utilisateur de prouver qu’un énoncé mathématique est vrai sans toutefois révéler une autre information que la véracité de l’énoncé. Une telle preuve est dite non-interactive si elle se compose d’un seul message. Ces preuves ont permis de développer un grand nombre d’applications en cryptographie mais qui sont rarement utilisées en pratique, car les constructions obtenues sont le plus souvent inefficaces. Une ligne récente de travaux, initiée par Groth, Ostrovsky et Sahai, a permis de réaliser des systèmes de preuve beaucoup plus performants pour certains types d’énoncés. Ces systèmes, basés sur les applications bilinéaires, permettent par exemple de prouver de façon efficace qu’un message a été signé sans révéler le message (ou la signature) ou de prouver qu’un texte chiffré possède certaines propriétés sans révéler le message clair.

Cet exposé donnera un aperçu de la construction de ces preuves et discutera ensuite certaines applications récentes développées dans le cadre du projet ANR PACE.

Damien.Vergnaud-22-10-2010 (format pdf)

• Hugues Randriam (Telecom ParisTech) – Construction de systèmes (2,1)-séparants battant la borne probabiliste

RESUME : Les systèmes séparants sont des objets combinatoires dont l’étude a commencé au début des années 1960. Ils ont été réintroduits plus récemment au sein de la communauté cryptographique en relation avec le problème du traçage de traîtres ; dans ce contexte, les codes (t,1)-séparants sont aussi appelés « t-frameproof codes ».

Dans cet exposé on améliore un résultat de Xing en donnant une construction de codes algébro-géométriques t-frameproof sur un alphabet q-aire (q grand) dont le rendement asymptotique est le meilleur connu à ce jour.

Au moyen d’une concaténation, ceci permet de construire de bons codes t-frameproof *binaires*. Un cas particulièrement intéressant est celui où t=2 ; il s’agit là d’un pur problème de combinatoire extrémale, pour lequel on obtient ainsi une construction battant la borne probabiliste. Cette question était restée ouverte depuis une trentaine d’années.

Hugues.Randriam-22-10-2010 (format pdf)

• François-Xavier Standaert (Université Catholique de Louvain)– « Recent results about side-channel attacks and countermeasures »

RESUME : Traditionally, cryptographic algorithms provide security against an adversary who has only black box access to cryptographic devices. That is, the only thing the adversary can do is to query the cryptographic algorithm on inputs of its choice and analyze the responses, which are always computed according to the correct original secret information. However, such a model does not always correspond to the realities of physical implementations. During the last decade, significant attention has been paid to the physical security evaluation of cryptographic devices. In particular, it has been demonstrated that actual attackers may be much more powerful than what is captured by the black box model. For example, they can actually get a side-channel information, based on the device’s physical computational steps. As a consequence, some kind of obfuscation is required to protect integrated circuits from these physical attacks. This is especially important for small embedded devices (e.g. smart card, RFIDs, sensor networks, …) that can typically be under an adversary’s control for a short period of time. This implies new theoretical concerns (how to exactly model and evaluate these physical threats) and practical ones (how to prevent them). In this talk, I will discuss different results in the area of side-channel attacks, with a particular focus on formal tools that can be used to evaluate physical security on a fair basis. Starting from an introductive view of the field, I will describe some well known attacks and countermeasures, present a framework for the analysis of side-channel key-recovery from Eurocrypt 2009, with some of its applications, and finally discuss the connection of this framework with recent works in leakage-resilient cryptography.

Francois-Xavier.Standaert-22-10-2010 (format pdf)

• Delphine Boucher (Université de Rennes 1) – Autour des codes définis sur des anneaux de polynômes tordus

Travail en commun avec W. Geiselmann et F. Ulmer.

RESUME : Les codes tordus sont définis dans des anneaux (non commutatifs) de polynômes tordus sur un corps fini Fq noté Fq[X,theta] où theta est un automorphisme de Fq et la multiplication est régie par la règle X a = theta(a) X pour a dans Fq. Les codes ‘idéaux’ theta-cycliques sont obtenus comme des idéaux à gauche de l’anneau quotient Fq[X,theta]/(X^n-1) où n est un multiple de l’ordre de l’automorphisme theta. On peut généraliser cette construction en considérant des quotients Fq[X,theta]/(f) où f est un polynôme central de Fq[X,theta] (on parle alors de codes ‘ideaux’ theta-centraux) mais aussi en considérant des modules à gauche des modules quotients Fq[X,theta]/(f) où f est un polynôme quelconque de Fq[X,theta]. On parlera alors de codes ‘modules’ tordus. Dans cet exposé, après avoir défini les codes tordus, on s’intéressera plus particulièrement à la caractérisation des codes tordus auto-duaux et à leur construction sur F4 pour les produits scalaires euclidiens et hermitiens.

Exposé annulé

• Pierrick Gaudry (LORIA) – Factorisation d’entiers et RSA768

RESUME : En janvier dernier, la factorisation de RSA-768 a été annoncée. Après avoir rappelé quelques éléments généraux sur la factorisation d’entiers, nous expliquerons avec un peu plus de détails l’algorithme du crible algébrique qui est utilisé pour factoriser les modules RSA. Nous détaillerons ensuite comment cet algorithme a été mis en oeuvre dans le cas de RSA-768. Il aura fallu environ 2 ans et demi et la collaboration des équipes de l’EPFL, du CWI, de NTT et de notre équipe nancéienne pour venir à bout de ce calcul.

Pierrick.Gaudry-18-06-2010 (format pdf)

• Didier Alquié (DGA) – « Branch Number » d’un automate linéaire et codes convolutifs récursifs systématiques

Travail commun avec Franck Landelle.

RESUME : Dans ce travail nous proposons un nouveau cadre pour estimer le biais linéaire d’un générateur pseudo aléatoire. Nous définissons le « branch number » d’un automate intermédiaire défini sur un corps fini GF(q) comme le nombre de boîtes actives liées aux entrées et sorties. Cette valeur est utile pour évaluer le biais linéaire global du générateur. Nous montrons qu’elle peut être reliée à la distance libre d’un code convolutif sur GF(q) convenablement défini, et que les codes optimaux par rapport à cette distance conduisent à une borne inférieure – fine – sur le « branch number ». En conséquence, l’utilisation de notre proposition spécifique comme partie d’un générateur pseudo aléatoire permet de fournir une borne supérieure « prouvée » du biais global.

Didier.Alquie-18-06-2010 (format pdf)

• Christophe Chabot (Université de Rennes 1)– Codes quasi-cycliques et polynômes à coefficients matriciels

RESUME : Nous nous intéressons ici à la généralisation de résultats connus sur les suites récurrentes linéaires classiques aux suites récurrentes linéaires ayant un polynôme caractéristique à coefficients matriciels. Nous montrerons qu’il est possible de construire des codes quasi-cycliques à partir de telles suites (par analogie avec la construction de codes cycliques à partir de suites récurrentes linéaires classiques). Nous obtiendrons alors la notion de code quasi-cyclique annulé par un polynôme à coefficients matriciels. Finalement nous construirons des codes quasi-cycliques auto-duaux Euclidiens et Hermitiens qui dans la plupart des cas atteignent les bornes connues pour les distances minimales.

Christophe.Chabot-18-06-2010 (format pdf)

• Ben Smith (INRIA Saclay) – Another look at genus 2 curves

RESUME : After the success of elliptic curves in Discrete Logarithm- and Pairing-based cryptography, researchers have turned towards hyperelliptic curves as an immediate and convenient generalization, motivated by improved efficiency. While higher-genus hyperelliptic curves have been shown to be compromised from a security point of view, curves of genus 2 remain a subject of active research. From the point of view of algebraic geometry, curves of genus 2 and their Jacobians are essentially more complicated than elliptic curves: algorithmically, this presents us with both opportunities and obstacles. In this talk, we will investigate some parallels and differences in cryptosystems based on elliptic curves and curves of genus 2. In particular, we will show how to use explicit Real Multiplication structures to increase cryptosystem efficiency and accelerate point counting algorithms.

(pas de transparents, exposé fait un tableau)

• Caroline Fontaine (CNRS-LabSTICC/Telecom Bretagne) – Codes de Tardös et Fingerprinting

RESUME : Lorsqu’un document multimedia est distribué, par exemple dans un système de vidéo à la demande, il peut être intéressant pour le distributeur de tracer les copies distribuées aux utilisateurs. Ainsi, s’il s’avère que le document distribué a été utilisé de manière non légitime par un ou plusieurs utilisateurs, le distributeur souhaite pouvoir identifier au moins un de ces utilisateurs malhonnêtes. Pour cela, il insère dans les documents distribués des identifiants, différents pour chaque utilisateur, voire chaque transaction. Ces identifiants sont les mots d’un code, dit code traçant, et cette insertion s’effectue par tatouage, de manière imperceptible et robuste. Le problème se corse lorsque une coallition d’utilisateurs se forme pour forger un nouveau document, mêlant alors les identifiants, voire en créant de nouveaux par exemple en moyennant pixel à pixel les images de plusieurs vidéos pour générer une vidéo piratée. Pour que le distributeur ait une chance de tracer au moins un des utilisateurs pirates, il faut que les identifiants insérés présentent une certaine structure, permettant de remonter à eux malgré des mélanges ; il faut par ailleurs également que la technique d’insertion soit en adéquation avec le type de code traçant choisi. De nombreuses recherches ont exploré l’utilisation de codes correcteurs comme codes traçants, mais ceux-ci se sont avérés très lourds à utiliser dans la pratique, car pour être efficaces ils devaient être très longs, et définis sur de gros alphabets. En 2003 G. Tardos, statisticien, a proposé une famille de codes qui a révolutionné le domaine. Ses codes sont en effet optimaux en terme de longueur, très faciles à implémenter et efficaces pour tracer les pirates. Nous commencerons dans cet exposé par présenter la problématique et rappeler l’historique des études menées sur les codes traçants, avant d’en arriver aux codes de Tardos. Après une présentation détaillée de ces codes, nous ferons le point sur la compréhension et la maîtrise que la communauté en a aujourd’hui, et présenterons les résultats que nous avons récemment obtenus quant à leur amélioration, sans oublier les perspectives et problèmes ouverts.

Caroline.Fontaine-02-04-2010 (format pdf)

Une démonstration a été faite, et Caroline Fontaine propose ce lien pédagogique.

• Maximilien Gadouleau (Université de Reims)– Codage réseau linéaire et affine

RESUME : Le codage réseau est un nouveau protocole de transmission de données à travers un réseau qui permet aux noeuds intermédiaires de combiner les paquets qu’ils reçoivent. En particulier, le codage réseau linéaire, où des combinaisons linéaires sont effectuées, offre un plus haut débit et une plus forte robustesse aux variations de topologie que le routage traditionnel. Le codage réseau linéaire peut être modélisé comme la transmission de sous-espaces vectoriels, permettant ainsi une correction non-cohérente de pertes ou d’injections de paquets. Dans cet exposé, nous montrons que le codage réseau en général peut s’exprimer comme la transmission de flats de matroïdes. Grâce à cette généralisation, nous proposons ensuite un nouveau protocole, appelé codage réseau affine, où des sous-espaces affines sont transmis. Nous montrons alors que le codage réseau affine a un plus haut rendement que le codage réseau linéaire. Nous donnons enfin une classe de codes correcteurs d’erreurs quasi-optimaux pour le codage réseau affine, démontrant ainsi que les avantages de ce protocole sont préservés lorsque les paquets sont protégés.

Maximilien.Gadouleau-02-04-2010 (format pdf)

• Christophe Chabot (Université de Rennes 1) – Codes quasi-cycliques et polynômes à coefficients matriciels

RESUME : Nous nous intéressons ici à la généralisation de résultats connus sur les suites récurrentes linéaires classiques aux suites récurrentes linéaires ayant un polynôme caractéristique à coefficients matriciels. Nous montrerons qu’il est possible de construire des codes quasi-cycliques à partir de telles suites (par analogie avec la construction de codes cycliques à partir de suites récurrentes linéaires classiques). Nous obtiendrons alors la notion de code quasi-cyclique annulé par un polynôme à coefficients matriciels. Finalement nous construirons des codes quasi-cycliques auto-duaux Euclidiens et Hermitiens qui dans la plupart des cas atteignent les bornes connues pour les distances minimales.

(exposé annulé et reporté au 18 juin)

• 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)