A note on the bivariate Coppersmith theorem (Q2377067): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00145-012-9121-x / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2093762739 / rank
 
Normal rank

Revision as of 02:03, 20 March 2024

scientific article
Language Label Description Also known as
English
A note on the bivariate Coppersmith theorem
scientific article

    Statements

    A note on the bivariate Coppersmith theorem (English)
    0 references
    0 references
    0 references
    0 references
    27 June 2013
    0 references
    In this note the authors provide a proof of a result of \textit{D. Coppersmith} [J. Cryptology 10, No. 4, 233--260 (1997; Zbl 0912.11056)], whose original proof they claim to be incomplete. That result, Corollary 2 of the Coppersmith's paper and quoted here as Corollary 1, assures that we can efficiently compute all the roots \((x_0,y_0)\), with \(x_0,y_0\) bounded, of an irreducible bivariate polynomial \(p(x,y)\) defined over the integers. Such a result is related with an attack to a particular instance of the RSA cryptosystem. The note also points out that the gap in the paper of Coppersmith also exists in other papers inspired by it, in particular in two papers of the first author of the present note, and that the solution proposed here ``applies to those other papers as well''. The engaged proof of Corollary 1 is given in the Section 2 of the Note (Lemmas 1 and 2).
    0 references
    Copppersmith's theorem
    0 references
    bivariate polynomials
    0 references
    small roots
    0 references

    Identifiers