- 10 juin 2010 – Charles Bouillaguet (ENS) : Nouveaux algorithmes pour l’équivalence simultanée de formes quadratiques (aka. « le problème IP »).
| Résumé : Il est bien connu que toute forme quadratique réelle est équivalente à une forme « diagonale », et la matrice de passage est facile à calculer. Une extension très naturelle du problème est la suivante : étant donné deux paires de formes quadratiques simultanément équivalentes, peut-on retrouver la matrice de passage ? La difficulté calculatoire de ce problème a rendu possible son utilisation directe en cryptographie, par exemple pour construire un schéma d’authentification à clef publique (Patarin96). La difficulté calculatoire d’une généralisation de ce problème sous-tend également la difficulté de retrouver la clef secrète dans un certain nombre de schémas de chiffrement ou de signature reposant sur l’utilisation de polynomes quadratiques multivariés, tels que C^*, HM, SFLASH, TTS et ses variantes, TRMS, l-IC, Square, etc. Ces schémas ont tous été cassés, la plupart du temps par des algorithmes ad hoc qui résolvaient les instances particulières offertes par les schémas considérés du problème général de l’équivalence simultanée de formes quadratiques.
Dans cet exposé, je présente de nouveaux algorithmes pour résoudre le problème dans le cas le plus général.Ces techniques permettent de casser en quelques minutes le schéma d’authentification proposé par Patarin en 1996. Elles démontrent également qu’il est possible de résoudre les instances les plus dures avec une complexité égale à la racine carrée des techniques connues auparavant. Cela signifie en pratique qu’il est vain de faire reposer la sécurité d’un cryptosystème sur la difficulté du « problème IP », ainsi que Patarin l’avait nommé initialement. L’analyse de ces nouveaux algorithmes n’est pas triviale, et mêle des résultats classiques d’algèbre linéaire sur la dimension du commutant d’un endomorphisme, la complexité du calcul des bases de Gröbner, ainsi la distributions d’arbres non-orientés aléatoires. |
- 17 mai 2010 – Igor Shparlinski (Macquarie University, Australie – ENS, Chaire France Telecom) : Playing Hide and Seek in Finite Fields: Hidden Number Problem and Its Applications.
| Abstract :We describe several recent results on the hidden number problem introduced by Boneh and Venkatesan in 1996. The method is based on a rather surprising, yet powerful, combination of two famous number theoretic techniques: bounds of exponential sums and lattice reduction algorithms.This combination has led to a number of cryptographic applications, helping to make rigorous several heuristic approaches. It provides a two edge sword which can be used both to prove certain security results and also to design rather powerful attacks.
The examples of the first group include results about the bit security of the Diffie-Hellman key exchange system, of the Shamir message passing scheme and of the XTR and LUC cryptosystems. The examples of the second group include attacks on the Digital Signature Algorithm and its modifications which are provably insecure under certain conditions. |
- 8 avril 2010 – Gaëtan Bisson (LORIA de Nancy – TU/e d’Eindhoven) : Courbes elliptiques : sécurité et isogénies.
| Résumé : Les cryptosystèmes basés sur le problème du logarithme discret de courbes elliptiques offrent de nombreux attraits, tant théoriques que pratiques. Leur sécurité est entre autres liée aux isogénies, applications qui transfèrent ce problème d’une courbe à une autre (et permettent ainsi de transporter à la première courbe ses éventuelles faiblesses sur la seconde). Nous expliquerons la structure de graphe que forment ces isogénies, montrerons comment on peut la calculer et y déterminer l’emplacement d’une courbe, de sorte à évaluer le coût de transférer son problème du logarithme discret vers celui d’une autre courbe. Enfin, si le temps le permet, nous évoquerons comment ces travaux, fortement liés à la structure d’« anneau d’endomorphismes », se généralisent aux courbes hyperelliptiques de genre supérieur. |
- 25 mars 2010 – Nadia El Mrabet (GREYC) : Attaque DPA contre l’algorithmede Miller
| Résumé : Les couplages ont permis la simplification de protocoles existants et la création de protocoles originaux, par exemple la cryptographie basée sur l’identité. Durant un protocole basé sur l’identité, l’utilisateur calcule un couplage entre une entrée secrète et une entrée publique. Nous pouvons alors appliquer des attaques à canaux cachés pour tenter de retrouver ce secret. Nous nous intéressons dans cet exposé à l’attaque différentielle par analyse de courant (acronyme DPA) menée contre l’algorithme de Miller, étape centrale du calcul des couplages de Weil, de Tate, Ate et twisted Ate. |
- 17 mars 2010 – Céline Chevalier (Telecom ParisTech) : Smooth Projective Hashing for Conditionally Extractable Commitments
| Abstract : The notion of smooth projective hash functions was proposed by Cramer and Shoup and can be seen as special type of zero-knowledge proof system for a language. Though originally used as a means to build efficient chosen-ciphertext secure public-key encryption schemes, some variations of the Cramer-Shoup smooth projective hash functions also found applications in several other contexts, such as password-based authenticated key exchange and oblivious transfer. In this paper, we first address the problem of building smooth projective hash functions for more complex languages. More precisely, we show how to build such functions for languages that can be described in terms of disjunctions and conjunctions of simpler languages for which smooth projective hash functions are known to exist. Next, we illustrate how the use of smooth projective hash functions with more complex languages can be efficiently associated to extractable commitment schemes and avoid the need for zero-knowledge proofs. Finally, we explain how to apply these results to provide more efficient solutions to two well-known cryptographic problems: a public-key certification which guarantees the knowledge of the private key by the user without random oracles or zero-knowledge proofs and adaptive security for password-based authenticated key exchange protocols in the universal composability framework with erasures. |
- 11 mars 2010 – Nicolas Gama (GREYC, Ensicaen) – Resolution exacte du SVP par Extreme pruning
| Résumé : Le problème du plus court vecteur (SVP), et aussi celui du plus proche vecteur (CVP) d’un réseau euclidien sont deux problèmes NP-difficiles, et sur lesquels la sécurité de nombreux cryptosystemes se réduit instantanément. Dans cet exposé, nous étudions des methodes probabilistes pour résoudre exactement et en pratique ces problèmes (principalement des algorithmes de crible). On connait depuis quelques années des algorithmes simplement exponentiels probabilistes en temps et en memoire qui résolvent ces problèmes. Cependant, dans les dimensions qui nous interessent: entre 90 et 150, ces methodes ne sont pas forcément les plus rapides, et sont actuellement difficilement parallélisables. Dans cet exposé, nous étudions plutot des algorithmes en 2^O(n^2) qui s’avèrent en pratique bien plus rapides. Ce sont des variantes de l’algorithme de recherche exhaustive de Schnorr-Euchner, dans lequel l’arbre de recherche exhaustive a été élagué de très près, de sorte qu’il ne reste qu’une partie infinitésimale de l’arbre initial. Nous montrons que la probabilité que le plus court vecteur appartienne toujours à l’arbre élagué diminue bien moins rapidement que la taille de l’arbre, ce qui représente un compromis temps-de-calcul/probabilité de succès plus que favorable. Par ailleurs, nous montrons comment une randomisation des entrées permet de compenser la faible probabilité de succès intrinsèque de l’algorithme sus-mentionné, et de de résoudre le SVP et le CVP dans n’importe quel réseau, et ce en utilisant une approche incroyablement parallelisable. |
- 4 février 2010 – Malika Izabachène (PRiSM,UVSQ) : Anonymity in cryptographic protocols
| Abstract : Firstly, we present a state-of-the-art of the techniques used for the design of anonymous protocols. Then, we focus on identity-based encryption, a primitive that simplifies certificates’ management and give a new definition of anonymity in this setting. We also consider anonymous schemes with revocable anonymity, while preventing subliminal channel attacks. we propose an efficient scheme and prove its security in a model that we introduce. Finally, we address anonymity in Passord-Based Key-Exchange (PAKE) protocols, where a user wants to establish a common session key with a server. We consider security of PAKE protocols in the two- or three-player setting, enhancing adversarial behaviors while keeping the user’s identity private, which precisely consists in an application of our new definition of anonymity. |
- 14 janvier 2010 – Peter Birkner (PRiSM,UVSQ) : Edwards Curves and the ECM Factorisation Method
| Abstract : The ECM method, introduced about 20 years ago by Lenstra, is one of the best algorithms for factoring integers. This method employs elliptic curves, usually in Montgomery form, to find a factor of a given integer. The recently introduced Edwards and Twisted Edwards curves offer very efficient arithmetic and can improve the speed of the ECM algorithm. We give a brief overview of the ECM method and Edwards curves, and show how to construct Edwards curves which are suitable for ECM, that is, Edwards curves with large torsion and positive rank over Q. |
- 10 décembre 2009 – Bastien Vayssière (PRISM,UVSQ) : Recherche de collisions de fonctions de hachage en utilisant des chemins différentiels
| Résumé : J’expliquerai le contexte de cette cryptanalyse : les fonctions de hachage, quelques propriétés exigées pour les fonctions de hachage, une attaque générique utilisant le paradoxe des anniversaires, les principes de la cryptanalyse différentielle. Ensuite, je décrirai les méthodes avec des chemins différentiels qui ont marqué la dernière décennie. Je concluerai avec un bilan des complexités d’attaques de ce type et éventuellement collisions trouvées, pour MD5, SHA-1, SHA-256 et SHA-512, expliquant pourquoi il y a actuellement une compétition pour un nouveau standard, SHA-3. |
- 26 novembre 2009 – Emmanuel Volte (PRISM,UVSQ) : Le point sur les attaques rectangles
| Résumé : Les études sur la sécurité des schémas de Feistel déséquilibrés et expansifs ont mis en évidence des attaques génériques dites « rectangles ». Ce sont des attaques différentielles multi-points. Je vais décrire ces attaques à l’aide d’une nouvelle notation très synthétique et expliquer pourquoi certaines attaques ne peuvent pas fonctionner. On retrouve parmi les contraintes un problème mathématique assez intéressant dont je parlerai. La compréhension de ces contraintes m’a permis récemment de générer automatiquement toutes les attaques (dans des cas particuliers) et de voir jusqu’à quel tour ces attaques génériques pouvaient marcher. Pour l’anectode, mes résultats ont renforcé (trop tard) la sécurité de CRUNCH ! |
- 19 novembre 2009 – Sorina Ionica (PRISM,UVSQ) : Etude de volcans d’isogénies (2ème partie)
- novembre 2009 – Sorina Ionica (PRISM,UVSQ) : Etude de volcans d’isogénies (1ère partie)
| Résumé : Les volcans d’isogénies sont des graphes dont les noeuds sont des courbes elliptiques et les arêtes sont des isogénies entre les courbes. Dans un premier temps, nous expliquerons comment ces structures peuvent être utilisées pour calculer l’anneau d’endomorphismes d’une courbe elliptique. Nous présenterons ensuite quelques algorithmes récents qui utilisent les volcans d’isogénies pour le calcul du polynôme de Hilbert et des polynômes modulaires. Enfin, nous donnons une méthode qui permet, partant d’un noeud donné, de choisir une direction pour « voyager » sur le volcan. Nous montrerons que notre méthode permet une optimisation des algorithmes qui calculent le polynôme de Hilbert ou des polynômes modulaires. |
- 22 octobre 2009 – Anja Becker (PRISM,UVSQ) : The knapsack problem
| Abstract : We will take a look at an alternative mathematical problem that can be used to define cryptosystems (in comparison to RSA, ElGamal, ECDLP). We will pack a backpack and discover the knapsack problem as the starting point for the Merkle-Hellman cipher and others. We will then crack the system, observe the weak points and state the security requirements to prevent these attacks. |
- 15 octobre 2009 – Vanessa Vitse (PRISM,UVSQ) : Application à la résolution du problème du log discret sur E(\F_q^n)
| Résumé : J’expliquerai l’algorithme de Gaudry et Diem permettant de faire du calcul d’index sur E(\F_q^n) pour n>2 et présenterai une variante développée par Antoine Joux et moi-même. |
- 8 octobre 2009 – Vanessa Vitse (PRISM,UVSQ) : Résolution de systèmes polynomiaux multivariés à l’aide de bases de Gröbner
| Résumé : Après avoir présenté l’intérêt principal de ces bases, j’expliquerai comment les calculer en détaillant l’algorithme de Buchberger et ses deux principaux critères. J’introduirai ensuite les améliorations apportées par les algorithmes F4 et F5 de Faugère et développerai un exemple de calcul. |
Séminaires CRYPTO 2009-2010