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