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.
Prochains exposés
-
Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
Orateur : Mathias Boucher - Université de Rennes
The Dihedral Coset Problem (DCP), also known as the hidden shift problem, plays a fundamental role in post-quantum public-key cryptography, since the Learning-With-Error problem reduces to DCP. The “Simon meets Kuperberg” quantum algorithm by Bonnetain and Naya-Plasencia solves the DCP in quasi-polynomial time when the modulus is a power of two. We provide a generalization of this algorithm for[…] -
Adelic reduction of module lattices
Orateur : Henry Bambury - DGA-MI et Inria Rennes
We give a strict generalisation of the LLL algorithm over number fields, based on the reduction theory of $GL(n)$ over the adele ring of a number field. Our algorithm is free of heuristics, with rigorous bounds on output quality and complexity. -- based on joint work with Seungki Kim, Changmin Lee and Phong Nguyen ---
Cryptography
-
-
European Cyber Week: atelier cryptographie post-quantique
Dans la continuité des éditions 2021, 2022 et 2024, la DGA — en partenariat avec CREACH LABS et avec le soutien de l'ANSSI, de l'IRISA, de l'IRMAR et du Pôle d'Excellence Cyber — organise la 4e édition de l'atelier consacré à la cryptographie post-quantique dans le cadre de l'European Cyber Week 2026. Attention, il faut s'inscrire (gratuitement) au préalable — s'inscrire à la conférence Les[…] -
Post-quantum day of the cryptography seminar
A scientific day devoted to post-quantum cryptography, held in the wake of the European Cyber Week, with talks more technical than those presented at the ECW.Confirmed speakers:- Melissa Azouaoui- Thomas Pornin- Gustavo Banegas- Alice Pellet-Mary- Nadim Kobeissi -
Chiffrement homomorphe à l'aide des groupes après Nuida
Orateur : 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
-