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

*Ted Chinburg and Brett Hemenway and 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.

**Category / Keywords: **Coppersmith's method, lattices, polynomial congruences, capacity theory, RSA

**Original Publication**** (in the same form): **IACR-ASIACRYPT-2016

**Date: **received 6 Sep 2016, last revised 10 Sep 2016

**Contact author: **ted at math upenn edu, fbrett at cis upenn edu, nadiah at cis upenn edu, zscherr at math upenn edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20160910:154759 (All versions of this report)

**Short URL: **ia.cr/2016/869

[ Cryptology ePrint archive ]