Séminaires

Nous organisons régulièrement un séminaire dédié à la cryptographie et à la sécurité informatique. Ce séminaire, ouvert à tous, a généralement lieu le lundi matin de 11h à 12h en salle 301 du bâtiment Descartes. 

Pour intervenir dans celui-ci, en présentant vos recherches ou vos développements industriels, veuillez contacter Luca De Feo. La liste des séminaires des années précédentes est disponible ici.

 

2011-2012

  • 2 avril 2012 - Maike Massierer - Elisa Gorla (Universität Basel).
  • 12, 19 ou 26 mars - Luca De Feo et Jérôme Plût (PRiSM) - Fun with isogenies and trees.
  • 5 mars 2012 - Emmanuel Volte (Doctorant PRiSM) - ZK with Rubik's Cubes. Résumé: Since the invention of the Rubik's cube by Ernö Rubik in 1974,  similar puzzles have been produced, with various number of faces or stickers. We can use these toys to define several problems in computer science, such as go from one state of the puzzle to another one. In this talk, we will classify some of these problems based on the classic Rubik's cube or on generalized Rubik's Cube. And we will see how we can use them in Zero Knowledge Authentication with a public key in order to achieve a given complexity against the best known attacks (for example 280 computations). The efficiency of these schemes, and their possible connection with
    NP-complete problems will also be discussed.
  • 6 février 2012 - Guillaume Quintin (Doctorant LIX) - On Generalized Reed-Solomon Codes Over Commutative and Noncommutative Rings.
    Résumé: In this talk we will study generalized Reed-Solomon codes over commutative, non commutative rings and show that the classical Welch-Berlekamp and Guruswami-Sudan decoding algorithms still hold in this context and we investigate their complexities. Under some hypothesis, the study of noncommutative Reed-Solomon codes over finite rings leads to the fact that GRS code over commutative rings have better parameters than their noncommutative counterparts. Also GRS codes over finite fields have better parameters than their commutative rings counterparts. But we will also show that given a unique decoding algorithm for a GRS code over a finite field, there exists a unique decoding algorithm for a GRS code over a Galois ring with a better asymptotic complexity. Moreover we will introduce new unique- and list-decoding algorithms designed to work when the base ring is for example a Galois ring or the ring of square matrices over a Galois ring.
  • 7 décembre 2011 - Cécile Gonçalves (Doctorante LIX) - Un algorithme à la Kedlaya pour compter les points de revêtements cycliques de la droite projective.
    Résumé : Le comptage de points de la jacobienne d'une courbe est un problème intervenant naturellement en théorie des nombres et en cryptographie. L'algorithme proposé par Kedlaya en 2001 est l'un des premiers à être pratiquable en genre supérieur à 2 : c'est un algorithme qui permet de compter les points d'une courbe hyperelliptique et qui est polynomial en le genre.  Dans cet exposé, nous présenterons un algorithme à la Kedlaya de comptage de points d'un revêtement cyclique de la droite projective, qui résulte en fait d'une extension de l'algorithme proposé par P. Gaudry et N. Gürel pour les courbes superelliptiques.

  • 30 novembre 2011 - Aurore Guillevic (Doctorante Thalès - ENS) - Familles de courbes hyperelliptiques de genre 2, calcul de l'ordre de la jacobienne et constructions pour les couplages. [transparents] 
    Résumé : L'utilisation des courbes elliptiques et hyperelliptiques en cryptographie nécessite de pouvoir calculer en un temps raisonnable l'ordre de la courbe elliptique et dans le cas hyperelliptique, de la jacobienne de la courbe. T. Satoh proposa à Eurocrypt 2009 un algorithme polynomial pour vérifier si l'ordre de la jacobienne d'une courbe hyperelliptique de la forme Y^2 = X^5 + aX^3 + bX définie sur un corps fini Fq admet un grand facteur premier. Son approche consiste à obtenir différents candidats pour la fonction zeta de la jacobienne sur Fq en partant de l'expression de la fonction zeta sur une extension où la jacobienne se départage en deux courbes elliptiques. L'approche de T. Satoh se généralise pour obtenir l'expression exacte de la fonction zeta de la jacobienne de courbes hyperelliptiques de genre 2 de la forme ci-dessus et de la forme Y^2 = X^6 + aX^3 + b. Nous avons obtenus les coefficients exacts des fonctions zeta par des calculs successifs (un peu techniques) de résolution d'équations de degré 2. 
    Les systèmes à bases de couplages utilisent des courbes elliptiques particulières présentant un petit degré de plongement par rapport à un grand sous-groupe d'ordre premier. Les formules explicites d'ordre des jacobiennes des deux familles de courbes hyperelliptiques ci-dessus permettent de construire des jacobiennes ayant les propriétés voulues pour une utilisation en cryptographie à base de couplages. Pour cela nous avons étendu les méthodes existantes dans le cas elliptique, à savoir la méthode de Cocks-Pinch et la méthode cyclotomique (ou de Brezing-Weng). Pour illustrer la faisabilité de notre méthode nous donnons quelques exemples pour un degré de plongement entre 5 et 35. La mesure de l'efficacité rho = 2 log p / log r est comprise entre 2.25 et 4. 
    Travail en collaboration avec Damien Vergnaud.

  • 23 novembre 2011 - Nicolas Estibals (Doctorant équipe CARAMEL - INRIA Nancy Grand-Est) - Implémentation matérielle de l'arithmétique de corps de caractéristique 2 et 3[transparents]
    Résumé : La cryptographie sur courbes elliptiques et hyperelliptiques, et plus spécialement celle reposant sur les couplages, demande d'effectuer des calculs dans des corps finis de petites caractéristiques.  Dès lors, développer des opérateurs matériels pour effectuer les opérations arithmétiques sur ces corps est un problème intéressant, que ce soit dans un but de performances (ces opérations sont mal supportées par les processeurs généralistes) ou pour obtenir des accélérateurs spécifiques pour les calculs cryptographiques.
    Durant cet exposé, nous examinerons la représentation des éléments de corps finis de petites caractéristiques et la réalisation d'opérations sur ceux-ci afin de décrire un coprocesseur arithmétique pour corps finis.  Parmi ces opérations, la plus coûteuse est la multiplication. C'est pourquoi nous montrerons différents algorithmes pour effectuer le produit et discuterons des différents compromis performance/consommation de ressources obtenus lors de l'implémentation matérielle de ceux-ci.
    Travail en collaboration avec Jean-Luc Beuchat (LCIS, Université de Tsukuba, Japon) et  Jérémie Detrey (Équipe-projet CARAMEL, INRIA Nancy Grand-Est).

  • 16 novembre 2011 - Cristian Calude (University of Auckland) - Is quantum randomness pseudo-randomness? [transparents]
    Abstract: This talk will present recent theoretical and experimental results
    contrasting quantum randomness with software-generated randomness.

  • 9 novembre 2011 - Louise Huot (doctorante LIP6) - Utilisation des symétries pour la résolution du problème de décomposition de points. [transparents]
    Résumé : Pour résoudre le DLP sur les courbes elliptiques définies sur un corps fini non premier K : extension de degré n de k, P. Gaudry a introduit un nouvel algorithme reposant sur le principe général du calcul d'indice. Une étape cruciale de cet algorithme nécessite de décomposer des points de la courbe E(K) selon une base de facteurs. C'est à dire, étant donné un point fixé R de E(K) trouver n points Pi, 1 ≤ i ≤ n, de la base de facteurs F ⊂ E(K) tels que R = P1 ⊕ ... ⊕ Pn (1). Une méthode de résolution algébrique de ce problème consiste à modéliser l'équation (1) sous forme d'un système polynomial et de le résoudre. À cette fin, Semaev introduit les polynômes de sommation qui projettent le problème de décomposition de points sur l'axe des abscisses. L'application d'une restriction de Weil de K à k sur un tel polynôme de sommation engendre un système à coefficients dans k à n équations et n inconnues, dont la résolution est équivalente à celle du problème de décomposition de point. Le coût de la résolution de ces systèmes est exponentiel en n et elle devient rapidement impossible. Il est donc nécessaire d'optimiser la résolution de ces systèmes. Un moyen est d'utiliser les symétries du problème de décomposition de points. Une symétrie naturelle de ce problème, lié à la commutativité de la loi de groupe sur les points de la courbe, est l'action du groupe symétrique Sn. Dans cet exposé, nous mettrons en évidence des symétries supplémentaires. Nous étudierons en particulier deux représentations de courbes − les courbes d'Edwards et les intersections de Jacobi − dont les symétries se propagent sur les polynômes de sommation. Pour ces représentations, nous verrons également comment elles permettent de simplifier les systèmes polynomiaux à résoudre. Finalement nous présenterons quelques résultats pratiques montrant le gain apporté par l'utilisation des symétries.
    Travail en collaboration avec Jean-Charles Faugère, Pierrick Gaudry et Guénaël Renault.

  • 12 octobre 2011 et 2 novembre 2011 - Jacques Patarin 
    Quelques généralisations transfinies du Théorème d'incomplétude de Gödel
    Résumé : Que se passe-t-il dans les théorèmes d'incomplétude si l'on dispose d'ordinateurs "transfinis" c'est-à-dire capables de faire une infinité de calculs en 1 seconde ? Par infinité de calculs on désigne ici une quantité de calculs inférieure ou égale à alpha, et avec une mémoire inférieure ou égale à alpha, où alpha est un cardinal infini fixé, par exemple alpha égal aleph zero (le dénombrable) ou bien alpha égal le continu (le cardinal de l'ensemble des nombres réels). Ceci sera le sujet de notre exposé, où nous verrons qu'en fait à peu près tous les célèbres théorèmes d'incomplétude ou de limitation se généralisent dans ce cadre.
    Mercredi 12 octobre : présentation du théorème classique de Gödel et de résultats classiques de limitation sur les ordinateurs standards.
    Mercredi 2 novembre : généralisation au transfini, et, si on a le temps, discussion sur ce qui se passe sur les classes (au lieu des ensembles).

  • 6 octobre 2011 - horaire exceptionnel jeudi après-midi 15h 
    Dimitar Jechtev (Post-doctoral LACAL -EPFL) - Hardness of Computing Individual Bits for Pairing-based One-way Functions
    Abstract: We prove that if one can predict any of the bits of the input to a classical pairing-based one-way function with non-negligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem (FAPI-1/FAPI-2). The latter has implications for the security of various pairing-based schemes such as the identity-based encryption scheme of Boneh--Franklin, Hess' identity-based signature scheme, as well as Joux's three-party one-round key agreement protocol. Moreover, if one can solve FAPI-1 and FAPI-2 in polynomial time then one can solve the Computational Diffie--Hellman problem (CDH) in polynomial time. Our result implies that all the bits of the pairing-based one-way function are hard--to--compute, assuming that CDH is hard. Our argument uses a list-decoding technique via discrete Fourier transforms due to Akavia--Goldwasser--Safra. 
    This is joint work with Alexandre Duc.

  • 28 septembre 2011 - Jérôme Plût (Post-doctorant CRYPTO- UVSQ) - Modularité de familles de courbes elliptiques.
    Résumé : Je présenterai des extensions du modèle quartique de Jacobi représentant des familles plus larges de courbes elliptiques, au prix de surcoûts dans les opérations d'addition. Ces formules d'additions sont unifiées sur un grand sous-groupe des points de ces courbes. Je donnerai également une caractérisation de ces familles de courbes par l'action du Frobenius sur les points de torsion, ce qui permet d'en obtenir un comptage asymptotique de façon particulièrement directe. Enfin, je montrerai comment cette caractérisation est une conséquence de la modularité de certaines familles de courbes elliptiques.

 Imprimer  E-mail

DMC Firewall is a Joomla Security extension!