Programme séminaire

How to improve information set decoding exploiting that $1+1=0$ over $mathbb{F}_2$

Le 14 février 2012 à 14:00 - Salle 106 à Jidé
Orateur : Anja Becker (doctorante à l'université de Versailles)
Thème : Cryptographie - Public : Plutôt mathématique

At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of n elements and density close to 1 in time O(2^{0.337n}) and memory O(2^{0.256n}). This improved a 30-year old algorithm by Shamir and Schroeppel of running time O(2^{0.5n}) and memory requirement O(2^{0.25n}). In this talk we will present the following: Using the simple observation that the solution to the knapsack problem, a binary vector, can be represented by two overlapping vectors with coefficients in {-1,0,1}, we can obtain a better algorithm of running time O(2^{0.291n}).
Furthermore, this technique can be applied to improve information set decoding attacking linear codes such as used in McEliece public key encryption. We can improve recent results on half-distance decoding such as Ball-collision decoding and May-Meurer-Thomae--ISD of asymptotic time complexity O(2^{0.056n}) and O(2^{0.054n}), respectively. Previous attempts split the solution vector in disjoint parts. We search the solution as decomposition of two overlapping vectors which permits to reduce the running time to $O(2^{0.049n}) in the asymptotic case.
The talk is based on the publications:
a joined work with Jean-S\'ebastien Coron, Antoine Joux, Alexander Meurer and Alexander May

 

Indifférentiabilité du schéma de Feistel et modèles de sécurité idéalisés

Le 21 février 2012 à 14:00 - Salle 106 à Jidé
Orateur : Yannick Seurin (expert crypto à l'ANSSI)
Thème : Cryptographie - Public : Plutôt mathématique

Le schéma de Feistel permet d'obtenir une permutation efficacement inversible à partir d'un certain nombre de fonctions de tour. Il est utilisé dans de nombreux algorithmes de chiffrement par blocs, notamment DES. Un résultat classique de Luby et Rackoff affirme que 4 tours de cette construction sont nécessaires et suffisants pour obtenir une permutation fortement aléatoire (i.e. indistinguable d'une permutation aléatoire inversible) à partir de fonctions de tour pseudoaléatoires (secrètes). Dans cet exposé, nous nous intéresserons au cas où les fonctions de tour sont publiques et aléatoires (elles constituent alors un "oracle aléatoire"). Le cadre théorique pour formaliser ce problème est celui de l'indifférentiabilité. Nous verrons que pour un nombre suffisant de tours (le minimum démontré à l'heure actuelle étant de 14), le schéma de Feistel se comporte comme une permutation aléatoire inversible même quand les fonctions de tour sont publiques. Nous expliquerons pourquoi cela implique en particulier que le modèle de l'oracle aléatoire et celui du chiffrement idéal (deux modèles de sécurité "idéalisés") sont équivalents.