Description
Soit S une suite d'éléments d'un groupe fini G noté multiplicativement ; le problème du sac à dos consiste à trouver une sous-suite de S dont le produit vaut un élément donné z de G. Des méthodes très efficaces pour le résoudre existent quand G=Z/nZ mais elles nous abandonnent lorsque l'on change de groupe : on peut en effet prouver qu'aucun algorithme générique (c'est-à-dire, en un sens, qui s'applique à tout groupe G) ne peut résoudre ce problème en moins de O(sqrt(#G)) opérations. Si une approche de type « pas de bébé, pas de géant » réussit avec pour complexité O(sqrt(#G)) en temps et en mémoire, il n'est pas évident de faire mieux. Dans un premier temps, cet exposé aura pour but d'expliquer comment adapter certaines idées de Pollard à ce contexte afin d'obtenir un algorithme en temps O(sqrt(#G)) et coût mémoire négligeable. Ensuite, nous présenterons certaines applications, notamment à la recherche d'isogénie entre deux courbes elliptiques.<br/> Ces travaux sont conjoints avec Andrew V. Sutherland.
Next sessions
-
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
-