Paper 2016/869

Cryptographic applications of capacity theory: On the optimality of Coppersmith's method for univariate polynomials

Ted Chinburg, Brett Hemenway, Nadia Heninger, and Zachary Scherr

Abstract

We draw a new connection between Coppersmith's method for finding small solutions to polynomial congruences modulo integers and the capacity theory of adelic subsets of algebraic curves. Coppersmith's method uses lattice basis reduction to construct an auxiliary polynomial that vanishes at the desired solutions. Capacity theory provides a toolkit for proving when polynomials with certain boundedness properties do or do not exist. Using capacity theory, we prove that Coppersmith's bound for univariate polynomials is optimal in the sense that there are no auxiliary polynomials of the type he used that would allow finding roots of size $N^{1/d+\epsilon}$ for any monic degree-$d$ polynomial modulo $N$. Our results rule out the existence of polynomials of any degree and do not rely on lattice algorithms, thus eliminating the possibility of improvements for special cases or even superpolynomial-time improvements to Coppersmith's bound. We extend this result to constructions of auxiliary polynomials using binomial polynomials, and rule out the existence of any auxiliary polynomial of this form that would find solutions of size $N^{1/d+\epsilon}$ unless $N$ has a very small prime factor.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2016
Keywords
Coppersmith's methodlatticespolynomial congruencescapacity theoryRSA
Contact author(s)
ted @ math upenn edu
fbrett @ cis upenn edu
nadiah @ cis upenn edu
zscherr @ math upenn edu
History
2016-09-10: received
Short URL
https://ia.cr/2016/869
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/869,
      author = {Ted Chinburg and Brett Hemenway and Nadia Heninger and Zachary Scherr},
      title = {Cryptographic applications of capacity theory: On the optimality of Coppersmith's method for univariate polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2016/869},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/869}},
      url = {https://eprint.iacr.org/2016/869}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.