- 16 juin 2011 – Peter Schwabe (National Taiwan University) : How to use the negation map in the Pollard rho method
| Abstract: Pollard’s rho method is the best known algorithm to solve the discrete logarithm problem (DLP) in generic prime-order groups. The algorithm algorithm requires a pseudo-random iteration function. Most implementations of the algorithm sacrifice some randomness for efficiency and use so-called additive walks. For elliptic-curve groups another textbook optimization consists in making use of efficiently computable endomorphisms, most importantly negation. This optimization gives a theoretical factor-sqrt(2) speedup but when combined with additive walks leads to the problem of so-called fruitless cycles. In July 2009 Bos, Kaihara, Kleinjung, Lenstra, and Montgomery announced breaking a DLP on a 112-bit elliptic curve, this is still the largest elliptic-curve DLP for which a solution has been publicly announced. The computations did not make use of the negation map, the reason given by the authors is that dealing with fruitless cycles would have been too expensive in the SIMD environment they chose to carry out the computations. In my talk I will explain the parallel version of Pollard’s rho algorithm with the above-mentioned textbook optimizations. Then I will describe why the theoretical speedups are not trivially achievable in practice. Finally I will present results of joint research with Daniel J. Bernstein and Tanja Lange that show how the theoretical sqrt(2) speedup from using the negation map can be achieved in practice in exactly the SIMD computing environment that was used to solve the 112-bit elliptic-curve DLP. |
- 9 juin 2011 – Jean-Gabriel Kammerer (DGA – IRMAR) : Deterministic parameterizations of plane curves.
| Abstract: Much attention has been focused recently on the problem of computing points on a given elliptic curve over a finite field in deterministic polynomial time. This problem arises in a very natural manner in many cryptographic protocols when one wants to hash messages into the group of points of an elliptic curve. Hashing into finite fields being easy, the main step is to encode a field element into an elliptic curve. The difficulty is to deterministically find a field element x such that some polynomial in x is a square.
In this presentation, we will quickly review the encodings proposed by Icart in 2009 then K. Lercier and Renault on the one hand, Farashahi on the other hand in 2010. We will then explain how the geometry of the nine flex tangents to a cubic closely relates to these parameterizations. |
- 12 mai 2011 – Luca de Feo (IRMAR) : Algorithmes rapides pour le calcul d’isogénies explicites
| Résumé : Une isogénie est un morphisme de variétés abeliennes qui préserve la structure de groupe. Calculer des isogénies entre courbes elliptiques, oui, mais quoi et comment ? Si dans le contexte du bon vieil algorithme SEA le problème est bien défini et relativement bien compris, la cryptographie moderne pose des nouveaux problèmes qui nécessitent des réponses… rapides !
Dans cet exposé nous allons passer en revue les différentes définitions du problème du « calcul d’isogénies », avec leurs motivations respectives. Nous allons ensuite présenter le zoo d’algorithmes de calcul d’isogénies, puis nous allons entrer dans les détails de certaines variantes et améliorations, en quête de la complexité optimale. Ceci nous amenera à introduire des outils avancés du calcul formel, tels la transposition d’algorithmes et l’arithmétique des tours d’Artin-Schreier. Nous allons conclure avec une présentation des implantation logicielles et des questions ouvertes. |
- 6 mai 2011 – Céline Chevalier (LSV – ENS Cachan) : Composition of Password-based protocols
| Abstract: In this talk, we investigate in the symbolic model the composition of protocols that share a common secret. This situation arises when users employ the same password on different services. More precisely we study whether resistance against guessing attacks composes when the same password is used. As already done in [DKR08], we model guessing attacks using a common definition based on static equivalence in a cryptographic process calculus close to the applied pi calculus. Resistance against guessing attacks composes in the presence of a passive attacker. However, composition does not preserve resistance against guessing attacks for an active attacker. We therefore propose a simple syntactic criterion under which we show this composition to hold. Finally, we present a protocol transformation that ensures this syntactic criterion and preserves resistance against guessing attacks. |
- 5 mai 2011 – Benoît Gérard (post-doctorant UCL) : Shannon Entropy: a generic tool for analysing attacks
| Abstract: Cryptanalysis can be viewed as a communication problem. Indeed, a plaintext X is encrypted using a key K to obtain a ciphertext Y. The attacker’s goal is to recover information on X knowing Y or recovering information on K knowing (X,Y). The maximum information he can extract from the observations he made is quantified by the mutual information between these variables: I(K;(X,Y)) for key recovery, I(X;Y) otherwise. Information theory has been used to prove the unconditional security of the one-time-pad algorithm for instance. In that case, it is easy to show that I(X;Y)=0.
Shannon entropy metrics may also be used for a first analysis of a cryptanalysis. In 2009, entropy has been used both for unifying the analysis of side-channel attacks and for analysing multiple linear cryptanalysis leading to promising results. This presentation is focused on block cipher cryptanalysis for which many interesting results can be obtained. In that case, entropy is not directly computable but can be tightly approximated using a simple bound on mutual information. First, we will introduce Shannon entropy and mutual information. Then, we will focus on the mutual information decomposition bound that is the cornerstone of the derivation of an estimate for entropy. Finally, we will present and discuss the results obtained applying this bound to some examples of cryptanalysis. |
- 5 mai 2011 – Stéphane Manuel (ATER – ESIAG Paris 12) : SHA-1, toujours en course ?
| Résumé : Suite aux attaques publiées en 2005 puis 2006 et 2007, la fonction de hachage cryptographique SHA-1 est considérée comme cassée par l’ensemble de la communauté cryptographique. En 2008, le NIST publiait le document FIPS 180-3 et organisait une compétition internationale pour l’élection d’un nouveau standard de hachage. Cette compétition a eu pour effet de créer un certain désintéressement pour l’étude de cette fonction. Cependant, il s’avère que SHA-1 est toujours incluse dans le nouveau document (draft FIPS 180-4), soumis à commentaire par le NIST, qui vise à préciser les algorithmes standard de hachage sûr (SHS). Il en résulte que l’étude de la fonction SHA-1 continue de présenter un réel intérêt pratique. Nous nous proposons dans cet exposé de revenir sur l’historique des attaques par collision contre la fonction SHA-1. Puis, nous présenterons nos derniers résultats concernant le comportement des collisions locales qui constituent un des points clés des cryptanalyses de SHA-1. |
- 4 mai 2011 – Anja Becker (UVSQ) : Improved Generic Algorithms for Hard Knapsacks – Joint work with Jean-Sébastien Coron, and Antoine Joux.
| Abstract : At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of density close to 1 in time O^~(2^0.337n) and memory O^~(2^0.256n), thereby improving a 30-year old algorithm by Shamir and Schroeppel. Our new technique allows us to get an algorithm with running time down to O^~(2^0.291n).
The knapsack instance is divided in two halves with possible overlap, as in the Howgrave-Graham–Joux algorithm, but the set of possible coefficients is extended from 0,1 to -1,0,+1. This means that a coefficient -1 in the first half can be compensated with a coefficient +1 in the second half, resulting in an coefficient 0 of the golden solution. To reveal the golden solution, we therefore search for one decomposition (out of many) of the solution by solving two knapsacks. Adding (a few) -1 coefficients brings an additional degree of freedom that enables to again decrease the running time. To explain the idea, we will have a look at a practical example. |
- 4 mai 2011 – Gaëtan Leurent (Université Luxembourg) : Analysis of some SHA-3 candidates
| Abstract : Hash functions are essential primitives in modern cryptography, used in many protocols and standards. Due to attacks on most widely used hash functions, the SHA-3 competition was launched by NIST in 2008 to select a new hash function for standardisation. This ongoing effort is focusing the attention of many people in the symmetric crypto community, from designers to cryptanalysts.
In this talk we will describe two recent attacks on second-round SHA-3 candidates. The first attack is based on a cancellation property of some generalized Feistel schemes, and leads to a pseudo-preimage attack on the full compression function of SHAvite3-512. The same ideas can be used to attack reduced versions of Lesamnta, and also to target some generalized Feistel schemes in a block cipher setting. The second attack is a near-collision attack on the full compression function of Blue Midnight Wish (BMW). We describe some tools for the analysis of systems of additions and xors used in the attack, and which can be useful for the analysis of other ARX designs. |
- 28 avril 2011 – Pierre-Jean Spaenlehauer (INRIA/UPMC/LIP6) : Cryptanalyse algébrique du Algebraic Surface Cryptosystem.
| Résumé : Dans cet exposé, nous présentons une attaque sur le système de chiffrement asymétrique ASC (Algebraic Surface Cryptosystem). La sécurité de ce cryptosystème repose sur la difficulté d’un problème inhabituel en cryptographie multivariée : chercher une section de faible degré dans une surface algébrique. Cette construction permet notamment d’obtenir des tailles de clés très petites. En utilisant des méthodes algébriques (décomposition d’idéaux, calcul de bases de Gröbner,…), nous proposons une attaque permettant de retrouver le message clair en temps polynomial en tous les paramètres de sécurité et quasi-linéaire en la taille de la clé secrète. Pour les paramètres de sécurité proposés par les auteurs d’ASC, cette attaque permet de retrouver le clair en 0.05 secondes. De plus, l’attaque est plus rapide que l’algorithme de déchiffrement pour une large plage de paramètres.
Travail commun avec Jean-Charles Faugère. |
- 10 mars 2011 – Naomi Benger (UVSQ) : Tools for Pairing-Based Cryptography (PBC).
| Abstract : PBC is fundamentally different to most other Public-Key Cryptography. For RSA, or schemes based on the discrete logarithm problem (both in the finite field and in the group of points on an elliptic curve), an efficient implementation can be written which works well for any level of security. Of course an implementation specially tailored for, and hard-wired to, a particular level of security will perform somewhat better, but not spectacularly so. For PBC an efficient implementation at the 80-bit level of security will be completely different from an implementation at the 128-bit level and very little code will be reusable between the two implementations. The development and maintenance of good quality pairing code becomes difficult and there is a compelling case for the development of a cryptographic compiler which can generate good quality code for each case.
I will present some of the tools developed to contribute to the construction of such a compiler. |
- 20 janvier 2011 – Reynald Lercier (DGA – IRMAR) : Arithmétique p-adique rapide pour le comptage de points sur courbe (hyper)elliptique
| Résumé : En 2002, Mestre a proposé un algorithme remarquable pour déterminer le nombre de points de courbes (hyper)elliptiques définies sur GF(2^n). Nous passerons en revue dans cet exposé les nombreuses améliorations qui ont suivies, dues à Satoh-Skjernaa-Taguchi, Gaudry, Kim et al., Lercier-Lubicz, Harley, etc… et qui ont permis de faire décroître la complexité de O(n^(3+o(1))) à O(n^(2+o(1))). Nous nous intéresserons plus particulièrement au choix de bases pour les extensions p-adiques non ramifiées utilisées dans ces algorithmes, que nous comparerons avec les bases normales elliptiques introduites par Couveignes et Lercier en 2009. |
- 12 janvier 2011 – Damien Robert (INRIA – Bordeaux) : Computing isogenies and applications in cryptography
| Abstract : Elliptic curves provide an efficient public-key cryptosystem. An important tool in the study of elliptic curves is Vélu’s formulas which allow to compute explicit isogenies between them. In this talk, I will explain how to generalize Vélu’s formulas to abelian varieties (this is a joint work with Romain Cosset and David Lubicz). I will then describe AVIsogenies, a full open source implementation of isogenies computation between Jacobians of genus 2 curves. The interest for cryptography is that genus 2 curves allow to work over fields of half the size for the same security as with elliptic curves.
The talk will be in French, but the slides in English. |
- 18 novembre 2010 – Vivien Dubois (DGA) : Le degré de régularité des systèmes HFE.
| Résumé: HFE est un cryptosystème à clé publique introduit par Patarin en 1996. Une clé publique HFE est un système de polynômes quadratiques à plusieurs variables sur un petit corps fini. Ce système de polynômes admet une structure cachée, qui permet au destinataire de trouver une solution pour tout choix des constantes.
Il est maintenant bien connu que résoudre un système HFE nécessite un degré de recombinaison algébrique (le degré de régularité) plus bas que pour des systèmes aléatoires. Les travaux de Faugère, Joux, Granboulan et Stern ont identifié les raisons de cette propriété, et des estimations théoriques ont été fournies pour les systèmes sur GF2. Dans cet exposé, nous montrerons comment prouver et généraliser ces résultats pour n’importe quel corps fini. Travail joint avec Nicolas Gama. |
- 14 octobre 2010 – Mehdi Tibouchi (ENS) : Hachage vers les courbes elliptiques et hyperelliptiques.
| Résumé : Dans de nombreux protocoles cryptographiques, notamment à base de couplages, il est nécessaire de disposer de fonctions de hachage à valeur dans le groupe des points d’une courbe elliptique (ou plus généralement dans la jacobienne d’une courbe hyperelliptique). Nous expliquerons comment il est possible de construire de telles fonctions à partir de fonctions de hachage plus classiques (à valeur dans des chaînes de bits) d’une façon qui préserve la sécurité des protocoles considérés. L’étude de ces fonctions et les preuves de sécurité associées mettent en jeu des outils mathématiques variés, depuis des calculs élémentaires dans les corps finis jusqu’à des résultats plus sophistiqués sur les sommes d’exponentielles et les fonctions L de courbes algébriques. |