- 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.
Clement.Pernet-03-02-2012 (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.
Christophe.Ritzenthaler-03-02-2012 (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.
