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
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
-
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}, url = {https://eprint.iacr.org/2016/869} }