Description
Nous étudions le problème du calcul de racines e-èmes modulaires. Sous l'hypothèse de la disponibilité d'un oracle fournissant des racines e-èmes de la forme particulière $x_i + c$, nous montrons qu'il est plus facile de calculer des racines $e$-èmes que de factoriser le module $n$. Ici $c$ est fixé, et l'attaquant choisit les petits entiers $x_i$. L'attaque se décline en plusieurs variantes, selon les hypothèses exactes sur l'oracle, et selon les buts poursuivis, allant de la falsification sélective à la falsificaction universelle. La complexité obtenue est $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ dans les cas les plus significatifs, ce qui correspond à la complexité du {\sl special} number field sieve ({\sc snfs}).<br/> Ce travail étend les résultats existants sur la malléabilité du schéma de signature RSA, plus particulièrement au sujet des falsificactions affines. Ce problème particulier est polynomial lorsque le {\em padding} $c$ n'excède pas $n^{2/3}$, mais sa résolution dans le cas général était uniquement accessible via la factorisation.
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
-