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 security of the Paillier Cryptosystem @cite_15 rests on the assumption (DCR), which is the assumption that there is no polynomial time algorithm that can distinguish the uniform distribution on @math th powers in @math from uniform elements in @math . Thus any algorithm that finds roots of @math would break the security of this cryptosystem. Because of its homomorphic properties, the Paillier Cryptosystem is a building block for many cryptographic protocols e.g. private searching on streaming data @cite_7 and private information retrieval @cite_10 @cite_22 .
@cite_15 @cite_10 @cite_22 @cite_7
2132172731 1574024822 1511913323
This paper investigates a novel computational problem, namely the Composite Residuosity Class Problem, and its applications to public-key cryptography. We propose a new trapdoor mechanism and derive from this technique three encryption schemes : a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to RSA. Our cryptosystems, based on usual modular arithmetics, are provably secure under appropriate assumptions in the standard model. We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8]. We propose a one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication Θ(klog2n+llogn), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocol for l-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.