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.
Next sessions
-
Polytopes in the Fiat-Shamir with Aborts Paradigm
Speaker : Hugo Beguinet - ENS Paris / Thales
The Fiat-Shamir with Aborts paradigm (FSwA) uses rejection sampling to remove a secret’s dependency on a given source distribution. Recent results revealed that unlike the uniform distribution in the hypercube, both the continuous Gaussian and the uniform distribution within the hypersphere minimise the rejection rate and the size of the proof of knowledge. However, in practice both these[…]-
Cryptography
-
Asymmetric primitive
-
Mode and protocol
-
-
Post-quantum Group-based Cryptography
Speaker : Delaram Kahrobaei - The City University of New York