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 auxiliary polynomials of the type he used that would allow finding roots of size @math for monic degree- @math polynomials modulo @math . Our results rule out the existence of polynomials of any degree and do not rely on lattice algorithms, thus eliminating the possibility of 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 @math unless @math has a very small prime factor.
We study the security of individual bits in an RSA encrypted message EN(x). We show that given EN(x), predicting any single bit in x with only a nonnegligible advantage over the trivial guessing strategy, is (through a polynomial-time reduction) as hard as breaking RSA. Moreover, we prove that blocks of O(log log N) bits of x are computationally indistinguishable from random bits. The results carry over to the Rabin encryption scheme.Considering the discrete exponentiation function gx modulo p, with probability 1 − o(1) over random choices of the prime p, the analog results are demonstrated. The results do not rely on group representation, and therefore applies to general cyclic groups as well. Finally, we prove that the bits of ax + b modulo p give hard core predicates for any one-way function f.All our results follow from a general result on the chosen multiplier hidden number problem: given an integer N, and access to an algorithm Px that on input a random a i ZN, returns a guess of the ith bit of ax mod N, recover x. We show that for any i, if Px has at least a nonnegligible advantage in predicting the ith bit, we either recover x, or, obtain a nontrivial factor of N in polynomial time. The result also extends to prove the results about simultaneous security of blocks of O(log log N) bits. The RSA and Rabin encryption functions are respectively defined as EN(x) = xe mod N and EN(x) = x2 mod N , where N is a product of two large random primes p , q and e is relatively prime to ? (N) . We present a simpler and tighter proof of the result of [ACGS] that the following problems are equivalent by probabilistic polynomial time reductions: (1) given EN(x) find x; (2) given EN(x) predict the least-significant bit of x with success probability 1 2 + 1 poly(n) , where N has n bits. The new proof consists of a more efficient algorithm for inverting the RSA Rabin function with the help of an oracle that predicts the least-significant bit of x . It yields provable security guarantees for RSA message bits and for the RSA random number generator for modules N of practical size. 