Description
Depuis les travaux d'Adleman, DeMarrais et Huang il y a plus d'une décennie, il est bien connu que le problème du logarithme discret dans une courbe de grand genre sur un corps fini est plus simple à résoudre que dans une courbe elliptique de la même taille. Si L(\alpha, c) = e^{(c + o (1)) (g \log q)^{\alpha} (\log (g \log q))^{1 - \alpha}} désigne la fonction sous-exponentielle par rapport au genre g de la courbe et au cardinal q de son corps de définition, les algorithmes de logarithme discret pour les courbes de grand genre ont une complexité de L(1/2, c). Ceci est à comparer aux courbes elliptiques d'un côté, pour lesquelles seulement des algorithmes exponentiels existent sauf dans quelques cas particuliers; et au cas des corps finis, pour lesquels le crible des corps de nombres ou des corps de fonctions mène à un algorithme plus rapide en L(1/3, c).<br/> Je présente le premier algorithme sous-exponentiel avec un exposant \alpha < 1/2 pour attaquer le problème du logarithme discret dans une certaine classe de courbes algébriques. Ces courbes sont caractérisées par un degré relativement bas par rapport à leur genre. Dans le meilleur des cas, l'algorithme atteint une complexité de L(1/3, c) pour calculer la structure du groupe jacobien et L(1/3 + epsilon, o(1)) pour le logarithme proprement dit.
Next sessions
-
Verification of Rust Cryptographic Implementations with Aeneas
Speaker : Aymeric Fromherz - Inria
From secure communications to online banking, cryptography is the cornerstone of most modern secure applications. Unfortunately, cryptographic design and implementation is notoriously error-prone, with a long history of design flaws, implementation bugs, and high-profile attacks. To address this issue, several projects proposed the use of formal verification techniques to statically ensure the[…] -
On the average hardness of SIVP for module lattices of fixed rank
Speaker : Radu Toma - Sorbonne Université
In joint work with Koen de Boer, Aurel Page, and Benjamin Wesolowski, we study the hardness of the approximate Shortest Independent Vectors Problem (SIVP) for random module lattices. We use here a natural notion of randomness as defined originally by Siegel through Haar measures. By proving a reduction, we show it is essentially as hard as the problem for arbitrary instances. While this was[…] -
Endomorphisms via Splittings
Speaker : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-