Description
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.
Prochains exposés
-
Key Attack on the ACDGV Matrix Encryption Scheme
Orateur : Anmoal Porwal - Technical University of Munich
I will present our key-recovery attack on the ACDGV public-key encryption scheme proposed at ASIACRYPT 2024 by Aragon, Couvreur, Dyseryn, Gaborit, and Vinçotte. The secret key is a Gabidulin code hidden by appending random rows and columns and by left- and right-multiplication with invertible matrices. Our attack exploits the resulting algebraic structure to recover an equivalent secret key. It[…]-
Cryptography
-
Asymmetric primitive
-
-
Module Learning With Errors and Structured Extrapolated Dihedral Cosets
Orateur : Jinwei Zheng - Télécom Paris
The Module Learning With Errors (MLWE) problem is the fundamental hardness assumption underlying the key encapsulation and signature schemes ML-KEM and ML-DSA, which have been selected by NIST for post-quantum cryptography standardization. Understanding its quantum hardness is crucial for assessing the security of these standardized schemes. Inspired by the equivalence between LWE and[…]-
Cryptography
-