Description
Dans une première partie, nous présentons le problème en donnant une définition de la complexité bilinéaire de la multilication dans les corps finis. Puis nous exposons les résultats classiques concernant cette complexité, notamment l'algorithme originel de multiplication par interpolation sur des courbes algébriques dû à D.V. et G.V. Chudnovski.<br/> Ensuite, nous présenterons en un premier temps nos résultats théoriques sur la complexité bilinéaire, à savoir des versions modifiées de l'algorithme de D.V. et G.V. Chudnovski appliquées à des tours de corps de fonctions algébriques ayant de bonnes propriétés. On montrera alors les bornes de la complexité qui s'en déduisent. On présentera enfin une application effective de ces résultats, à savoir la construction effective d'un algorithme bilinéaire quasi-optimal de multilication dans certains corps finis par interpolation sur une courbe hyperelliptique.
Next sessions
-
Séminaire C2 à INRIA Paris
Emmanuel Thomé et Pierrick Gaudry Rachelle Heim Boissier Épiphane Nouetowa Dung Bui Plus d'infos sur https://seminaire-c2.inria.fr/ -
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Speaker : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-