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
-
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
-
-
Post-Quantum Signatures from Symmetric-Key-Friendly Techniques: From MPC-in-the-Head to VOLE-in-the-Head
Orateur : Dung Bui - Northwestern University
The MPC-in-the-Head (MPCitH) paradigm turns a secure multiparty computation protocol into a zero-knowledge proof and, via Fiat–Shamir, into a signature scheme whose security relies only on symmetric-key primitives. The framework of Katz, Kolesnikov and Wang (KKW, CCS18), which moves most of the MPC work into a committed preprocessing phase that the verifier checks by opening all-but-one of the[…] -
Distinguishing and Attacking McEliece Cryptosystems Using GRS Codes with Higher-Weight Mask
Orateur : Michael Schaller - University of Zürich, Applied Algebra group
Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon (GRS) codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code.There have been successful attacks on some of those schemes with row and column weight between $1$[…] -
Nouveaux doctorants
Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)