Le prochain sémininaire CCA se déroulera le vendredi 12 juin à TélécomParisTech (46, rue Barrault) en amphithéâtre Emeraude.
- 10h00 : Johan Nielsen, LIX, INRIA Saclay-Ile de France, and somehow UVSQ – Power Decoding Reed-Solomon Codes Up to the Johnson Radius
Résumé : Power decoding, also known as « decoding using virtual interleaving » is a simple technique for decoding Reed-Solomon codes up to the Sudan radius. It is based on the classical approach of solving a « key equation » involving a special polynomial whose roots reveal the error positions. Since the inception of Power decoding, it has been an open question if it is possible to incorporate « multiplicities »: the parameter allowing the Guruswami-Sudan algorithm (G-S) to decode up to the Johnson radius.
In this talk I will describe how this can be done, and show how one can solve the resulting equations in an efficient manner using lattice basis reduction. This gives a new, simple decoding algorithm with the same decoding radius and speed as the G-S algorithm, but which does not need the additional root-finding step of the G-S. It has the drawback that it is a partial bounded-distance decoding algorithm, as it will fail for a few received words.
- 11h15 : Gilles Zémor, IMB, Université de Bordeaux – Combinatoire additive et théorie des codes
Résumé: un des objectifs de la combinatoire additive est de caractériser les parties S d’éléments d’un groupe telles que S+S soit de petite cardinalité. Le théorème de Vosper affirme en particulier que les ensembles d’entiers modulo p de plus petites sommes de parties ne peuvent qu’être des progressions arithmétiques, quelques cas dégénérés mis à part. Nous nous intéressons à la transposition de ces résultats dans des algèbres, notamment à la caractérisation d’espaces vectoriels S dont le carré S^2 engendre un espace vectoriel de petite dimension. Des transpositions du théorème de Vosper nous permettront d’affirmer que de tels espaces doivent admettre des bases d’éléments en progression géométrique. Des bornes de codage dans des espaces de formes quadratiques jouent un rôle crucial dans l’obtention d’une variante du théorème de Vosper dans les extensions de corps. Nous obtiendront également que sous quelques conditions, les codes de Reed-Solomon sont les seuls codes qui minimisent la dimension du produit de Schur de deux codes.
Travaux communs avec Christine Bachoc, Oriol Serra, et avec Diego Mirandola.
- 14h15 : Cédric Lauradoux, – Projet Privatics, INRIA Rhône-Alpes, Exploitations concrètes des mauvaises utilisations des fonctions de hachage
Résumé : L’avènement de SHA-3 pourrait laisser penser que tous les problèmes opérationnels liés aux fonctions de hachage sont résolus. Ce n’est malheureusement pas la cas car les propriétés des fonctions de hachage cryptographiques sont mal comprises. Les impacts de cette mauvaise compréhension vont de la re-identification (Gravatar,Navizon) au déni de service algorithmique. Pour illustrer les erreurs que l’on peut rencontrer, je présenterais 2 exemples: les problèmes de secondes pré-images et de saturation des filtres de Bloom et pour conclure l’utilisation de SHA-256 dans Google Safe Browsing.
- 15h30 : Christina Boura, Prism, Université de Versailles-Saint Quentin en Yvelines – Improving impossible differential cryptanalysis
Résumé : Impossible differential cryptanalysis is a powerful attack against block ciphers introduced independently by Knudsen and Biham et al. The idea of these attacks is to exploit differentials that have zero probability to occur in order to eliminate some key candidates. These attacks, even if extensively used, remain not fully understood because of their high technicality. We show in this talk how to derive general formulas for evaluating the data, time and memory complexity of this kind of cryptanalysis and we propose then several new techniques for optimizing these attacks. Finally, we show applications of these techniques for numerous block ciphers, such as the AES, CRYPTON, ARIA, CLEFIA, Camellia, LBlock and the SIMON family of ciphers. These attacks improve all previous impossible differential attacks and lead in some cases to the best known cryptanalysis against these ciphers.
This is a joint work with Virginie Lallemand, Maria Naya-Plasencia and Valentin Suder.
