- Rafael Fourquet, Université Paris 8 Saint-Denis, – Décodage par liste des codes de Reed-Muller binaires
Nous présenterons un algorithme déterministe de décodage par liste des codes de Reed-Muller. Jusqu’à la borne de Johnson, sa complexité est linéaire en la longueur du code (complexité optimale pour un algorithme déterministe). Il s’agit d’une généralisation à tous les ordres de l’algorithme « sums » pour l’ordre un de Kabatianski-Tavernier (qui peut être vu comme le déroulement non-exhaustif d’une transformée de Fourier rapide). A titre d’exemple, nous appliquerons l’algorithme au calcul du profil de non-linéarité d’une fonction booléenne.
- Nicolas Delfosse, Institut de mathématiques de Bordeaux, – Construction et performances des codes quantiques topologiques
Les codes topologiques sont des codes quantiques construits à partir de pavages de surfaces. Ces codes ont été introduits par Kitaev, qui a défini un code quantique en utilisant un pavage carré du tore. Après avoir rappelé la construction de Kitaev, nous verrons comment les paramètres du code quantique s’expriment géométriquement en fonction du pavage. Nous nous intéresserons aux codes de surfaces hyperboliques de Zémor, qui forment l’une des rares familles de codes LDPC quantiques de rendement constant dont la distance minimale est croissante. En utilisant des pavages hyperboliques 3-coloriés nous obtenons une nouvelle famille de codes topologiques. Nous verrons que ces codes couleur hyperboliques possèdent aussi un rendement constant et une distance croissante.
Nous nous intéresserons ensuite aux performances de ces codes sur le canal à effacement. Nous verrons que les codes construits à partir de pavages réguliers n’atteignent pas la capacité du canal. Ce résultat nous permet de mieux comprendre les propriétés nécessaires pour approcher la capacité du canal.
Enfin, nous appliquerons ce résultat à un problème combinatoire. En utilisant la ressemblance entre effacements quantiques pour les codes hyperboliques et phénomène de percolation, nous déterminons une borne sur le seuil de percolation d’une famille de graphes hyperboliques auto-duaux. Nous obtenons ainsi une borne en théorie de la percolation provenant de la théorie de l’information quantique.
Travail en commun avec Gilles Zémor.
- Charles Bouillaguet, Université de Versailles-Saint-Quentin-en-Yvelines, – Symbolic Methods for the Automatic Search of Attacks Against Some Block Ciphers
Résumé. The block cipher cryptanalyst usually faces the following problem: she may interact with a black box containing the block cipher instantiated with a secret random key, and her goal is, in most cases, to retrieve this secret key using less time than exhaustive search and asking less encryptions/decryptions to the black box than the whole codebook. Several researchers had previously observed that the Advanced Encryption Standard (AES), the most widespread block cipher, had a relatively simple algebraic description over the field with 256 elements, because of its byte-oriented design. However, this property has not been harnessed by cryptanalysts to this day. In particular the (tempting) approach consisting in writing down the equations describing the AES, and trying to solve them directly using off-the-shelf tools such as SAT-solvers, has systematically failed to provide any result. In this talk, I will present the results we obtained using a slightly different method. We have designed tools that take as input a system of AES-like equations, and that search for an efficient ad hoc solving procedure. The result of these tools is the source code of a solver that can only solve the input system, but which can in some cases be efficient (its complexity can be predicted accurately). This solver can then be compiled and run to find the actual solutions. Our tools, which « reason » from the equations describing the AES (or similar looking symmetric primitives) are intrinsically symbolic, and they are inspired by standard tools from the field of automated deduction, such as the DPLL algorithm for SAT, the Knuth-Bendix completion algorithm, or the resolution algorithm for first-order logic. These tools found, nearly automatically, the best known Low-Data-Complexity attacks on reduced versions of the AES, and the best known attack on the full versions of AES-derived primitives, such as the Message Authentication code Pelican-MAC, and the stream cipher LEX.
Résumé à venir
- Patrick Derbez, École normale supérieure, –Généralisation des attaques de Demirci et Selçuk
Résumé: En 2008, Demirci et Selçuk présentent de nouvelles attaques sur 7 tours d’AES-192 et d’AES-256 reposant pour l’essentiel sur la technique du meet-in-the-middle. Dans cet exposé nous montrerons que ces attaques appartiennent en fait à une classe plus générale d’attaques et que celles trouvées par Demirci et Selçuk n’étaient pas optimales. Nous discuterons également de la méthode utilisée pour exhauster cette nouvelle classe ainsi que des résultats obtenus.
