Table of contents

  • This session has been presented June 10, 2011.

Description

  • Speaker

    Louise Huot - LIP6

Récemment Diem et Gaudry ont introduit indépendemment une méthode de résolution du DLP sur les courbes elliptiques définies sur un corps fini non premier K, de degré d'extension n > 1 sur le corps de base k. Cet algorithme repose 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, 0 < i < n+1, de la base de facteurs F (sous ensemble fixé de E(K)) tels que R = P1 + ... + Pn. Une méthode de résolution algébrique de ce problème consiste à modéliser cette somme 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 -- pour lesquelles ces nouvelles 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.

Next sessions

  • Chiffrement homomorphe à l'aide des groupes après Nuida

    • November 27, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Pierre Guillot - Ravel Technologies/Université de strasbourg

    Nuida et d'autres ont montré comment on peut obtenir un protocole de chiffrement pleinement homomorphe si l'on sait chiffrer les éléments d'un groupe G convenable, tout en sachant faire l'opération de G "en homomorphe". Les exemples étaient jusqu'à présent limités au chiffrement d'un bit à la fois, avec beaucoup d'opérations à effectuer pour "simuler" les portes logiques usuelles. Je vais[…]
    • Cryptography

  • Post-Quantum Signatures from Symmetric-Key-Friendly Techniques: From MPC-in-the-Head to VOLE-in-the-Head

    • December 04, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Dung Bui - Northwestern University

    The MPC-in-the-Head (MPCitH) paradigm turns a secure multiparty computation protocol into a zero-knowledge proof and, via Fiat–Shamir, into a signature scheme whose security relies only on symmetric-key primitives. The framework of Katz, Kolesnikov and Wang (KKW, CCS18), which moves most of the MPC work into a committed preprocessing phase that the verifier checks by opening all-but-one of the[…]
  • Distinguishing and Attacking McEliece Cryptosystems Using GRS Codes with Higher-Weight Mask

    • December 11, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Michael Schaller - University of Zürich, Applied Algebra group

    Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon (GRS) codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code.There have been successful attacks on some of those schemes with row and column weight between $1$[…]
  • Nouveaux doctorants

    • January 08, 2027 (13:45 - 14:45)

    • Salle Guernesey à l'ISTIC

    Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)
Show previous sessions