Description
En 1996, Coppersmith introduit deux techniques basées sur la réduction de réseaux permettant de retrouver de petites racines d'équations polynomiales. Une de ces techiques s'applique au cas d'équations modulaires en une variable, l'autre concerne les équations entières à deux variables. Depuis, ces méthodes ont été utilisées dans de nombreuses applications cryptographiques. Pour certaines de ces applications, qui font intervenir plus de deux variables, des extensions des méthodes de Coppersmith ont été proposées. Malheureusement, ces méthodes sont heuristiques et ne permettent pas toujours de retrouver les racines recherchées quand le nombre de variables est supérieur à deux. Dans cette présentation, nous proposons une nouvelle variante de l'algorithme de Coppersmith dans le cas d'équations entières faisant intervenir trois variables et nous étudions son applicabilité. Nous nous intéressons notamment à des attaques sur RSA dans le cas d'exposants petits. Cette méthode utilise non seulement la réduction de réseaux mais également le calcul de bases de Gröbner. En principe, elle peut être généralisée dans le cas de quatre variables ou plus.
Prochains exposés
-
Polytopes in the Fiat-Shamir with Aborts Paradigm
Orateur : 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[…]-
Cryptographie
-
Primitive asymétrique
-
Mode et protocole
-
-
Post-quantum Group-based Cryptography
Orateur : Delaram Kahrobaei - The City University of New York