Séminaire CCA (Codage, Cryptologie, Algorithmes)

• 10h00-11h00 : Clément Pernet, Université Joseph Fourier,- Adaptive decoding for evaluation/interpolation codes

Résumé : We will present recent work on CRT (Chinese Remainder Theorem) and more generally codes based on an evaluation-interpolation scheme that include the better known Reed-Solomon codes. It was motivated in the study of algorithm based fault tolerance (ABFT) applied to parallel exact linear algebra.In this area, Chinese Remainder Theorem is used to split computations over integers or rational numbers into several computations over finite rings, allowing a simple parallelization. CRT codes enable the use of Chinese Remainder reconstruction with errors in some of the residues, provided that some amount of redundant information has been computed. We will first introduce a more general error model allowing to derive tighter bounds on the error correction capacities of such codes. Then we will describe two adaptations of the usual unique decoding algorithm (based on the extended euclidean algorithm), making the correction capacity adaptive. Several termination criteria allow to efficiently use these codes without knowing their parameters, and use the maximal amount of redundancy available for correction. Furthermore they make it possible to adapt fault tolerance in algorithms with early termination. We will lastly present some recent insights on the application of these adaptive decoding to a problem in computer algebra: interpolation of sparse polynomials with errors.

Transparents (format pdf)

• 11h15-12h15 : Christophe Guyeux, Université de Franche-Comté,-Quelques avancées pour une approche topologique en sécurité informatique

Résumé : Nous nous intéressons à la possibilité de concevoir des machines de Turing au comportement imprévisible et désordonné. Le cadre théorique de cette étude est la topologie mathématique, avec de possibles ramifications dans les domaines de la complexité et de la théorie de la mesure. Les applications visées ont trait à la sécurité informatique et aux simulations numériques de phénomènes chaotiques. Cette conception et cette étude sont possibles en tenant compte des points suivants : de telles machines sont des processus itératifs, diverses distances naturelles sont envisageables, on peut donc étudier topologiquement le comportement de ces systèmes dynamiques. Nous nous focalisons en particulier sur les propriétés suivantes : régularité, transitivité, expansivité, sensibilité, mélange topologique, instabilité, entropies topologique et métrique, exposant de Lyapounov, etc.

Cette approche théorique prouve rigoureusement qu'il est possible d'obtenir du chaos sur machine, et ce de manière exacte et mathématiquement correcte. D'autre part, ce modèle nous donne la marche à suivre concrètement pour préserver intégralement toutes ces propriétés lors d'implémentations : l'espace sur lequel itérer est le produit cartésien entre les états finis de la machine et l'ensemble infini des rubans possibles. Ainsi, on doit itérer sur des vecteurs de bits, et prendre à chaque itérée une nouvelle entrée, si l'on veut se prémunir des cas dégénérés, et notamment éviter de boucler systématiquement. La situation idéale correspond aux traitements de flux audio ou vidéo.

Nous avons commencé par appliquer nos réflexions à des situations concrètes. Notre approche consiste à utiliser des algorithmes prouvés sûrs par la communauté, et à réaliser un traitement dessus de sorte que le nouvel objet a ses propriétés de sécurité préservées, et possède en sus de nouvelles propriétés de désordre topologique. Ainsi, nous avons détaillé comment réaliser un post-traitement sur une fonction de hachage de sorte que ses propriétés de résistance aux collisions et à la première préimage soient préservées tout en possédant de nouvelles propriétés reliées au caractère imprédictible de la valeur hachée 1,2. Dans le même esprit, nous avons proposé une approche pour mixer deux générateurs de nombres pseudo-aléatoires avec une fonction dont la suite récurrente est chaotique, de sorte que le nouveau générateur reste rapide, devienne parallélisable, possède une kyrielle de propriétés de désordre topologique tout en préservant des propriétés telles que l'uniforme distribution 3. De telles preuves s'appuient notamment sur la théorie des graphes et les chaînes de Markov. Ce générateur passe avec succès les tests DieHARD, NIST et TestU01, même quand les PRNGs fournis en entrée n'en sont pas capables. Enfin, dans le domaine de la dissimulation d'informations, nous avons proposé des schéma de tatouage et de stéganographie prouvés stégo-sûrs, et ayant de bonnes propriétés topologiques. Nous avons relié ces propriétés à des classes d'attaques jusqu'alors impossibles à étudier 4,5.

1 Jacques M. Bahi and Christophe Guyeux. Topological chaos and chaotic iterations, application to hash functions. In IJCNN’10, IEEE Int. Joint Conference on Neural Networks, pages 1–7, Barcelona, Spain, July 2010. Best paper award. (Conférence de rang A)

2 Christophe Guyeux et Jacques M. Bahi. A Topological Study of Chaotic Iterations. Application to Hash Functions. In Computational Intelligence for Privacy and Security (CIPS). Springer. Accepted paper, to appear.

3 Jacques M. Bahi, Jean-François Couchot, Christophe Guyeux, Adrien Richard. Chaotic discrete dynamical systems: why getting strongly connected iteration graph and how. In FCT’11, 18th Int. Symposium on fundamentals of computational theory. August 2011, Oslo, Norway. (rang A)

4 Jacques Bahi and Christophe Guyeux. A new chaos-based watermarking algorithm. In SECRYPT’10, Int. conf. on security and cryptography, pages 455–458, Athens, Greece, July 2010. SciTePress.

5 Nicolas Friot, Christophe Guyeux, et Jacques M. Bahi. Chaotic iterations for steganography - Stego-security and chaos-security. In SECRYPT’11, Int. conf. on security and cryptography, pages ***-***, Spain, July 2011.

• 14h15-15h15 : Christophe Ritzenthaler, Université de Marseille - Invariants et courbes hyperelliptiques : aspects géométriques, arithmétiques et algorithmiques

Travail en commun avec Reynald Lercier.

Résumé : De nombreuses questions géométriques ou arithmétiques sur les courbes hyperelliptiques peuvent être étudiées grâce aux invariants des formes binaires. S'il est relativement standard de calculer un système générateur de ces derniers, il est par contre nettement plus difficile de retrouver une forme binaire d'invariants donnés. En particulier la résolution par les bases de Gröbner est hors de portée des ordinateurs actuels dans le cas générique. Nous montrerons comment palier à ce problème par l'utilisation de la notion de covariants et de la méthode de Mestre. Nous compléterons ces résultats en étudiant si la courbe peut être construite sur son corps des modules.

Transparents (format pdf)

• 15h30-16h30 : Gohar Kyureghyan, Université de Magdebourg, - Permutation Polynomials over Finite Fields: Proof Techniques

Résumé : Permutation polynomials describe the bijective mappings on finite fields and play an important role in both theoretical and practical aspects of finite fields. For example, mappings used for applications in Coding Theory or Cryptology are often required to be bijective in order to ensure a unique decoding/decryption or to provide a good resistance against several attacks.

There are very few known explicit families of permutation polynomials, because lack of efficient methods for proving that a given polynomial defines a permutation on infinite many finite fields.

In the talk we will present some of known classes of permutation polynomials and give the key ideas used for proving them.

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

Transparents (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.

Transparents (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.

Transparents (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.

Transparents (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.

Transparents (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.

Transparents (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.

Transparents (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.

Transparents (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.

Transparents (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.

Transparents (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)