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.
The RSA function @math is assumed to be a one-way trapdoor permutation. Optimal Asymmetric Encryption Padding (OAEP) is a general method for taking a one-way trapdoor permutation and a random oracle @cite_9 , and creating a cryptosystem that achieves security against adaptive chosen ciphertext attacks (IND-CCA security).
@cite_9
2052267638
We argue that the random oracle model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol P is produced by first devising and proving correct a protocol P R for the random oracle model, and then replacing oracle accesses by the computation of an “appropriately chosen” function h . This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.