Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleToward a rigorous variation of Coppersmith
Author(s) Aurelie Bauer, Antoine Joux
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn 1996, Coppersmith introduced two lattice reduction based techniques to find small roots in polynomial equations. One technique works for modular univariate polynomials, the other for bivariate polynomials over the integers. Since then, these methods have been used in a huge variety of cryptanalytic applications. Some applications also use extensions of Coppersmith’s techniques on more variables. However, these extensions are heuristic methods. In the present paper, we present and analyze a new variation of Coppersmith’s algorithm on three variables over the integers. We also study the applicability of our method to short RSA exponents attacks. In addition to lattice reduction techniques, our method also uses Gröbner bases computations. Moreover, at least in principle, it can be generalized to four or more variables.
KeywordsLattice reduction, Coppersmith’s algorithms, Gröbner basis
URL http://link.springer.com/chapter/10.1007%2F978-3-540-72540-4_21
PublisherBerlin: Springer
Translation No
Refereed No