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
2132172731 2018738738 198181672 2122170871
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. 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. Asymmetric searchable encryption allows searches to be carried over ciphertexts, through delegation, and by means of trapdoors issued by the owner of the data. Public Key Encryption with Keyword Search (PEKS) is a primitive with such functionality that provides delegation of exact-match searches. As it is important that ciphertexts preserve data privacy, it is also important that trapdoors do not expose the user’s search criteria. The difficulty of formalizing a security model for trapdoor privacy lies in the verification functionality, which gives the adversary the power of verifying if a trapdoor encodes a particular keyword. In this paper, we provide a broader view on what can be achieved regarding trapdoor privacy in asymmetric searchable encryption schemes, and bridge the gap between previous definitions, which give limited privacy guarantees in practice against search patterns. Since it is well-known that PEKS schemes can be trivially constructed from any Anonymous IBE scheme, we propose the security notion of Key Unlinkability for IBE, which leads to strong guarantees of trapdoor privacy in PEKS, and we construct a scheme that achieves this security notion. When outsourcing data to third-party servers, searchable encryption is an important enabling technique which simultaneously allows the data owner to keep his data in encrypted form and the third-party servers to search in the ciphertexts. Motivated by an encrypted email retrieval and archive scenario, we investigate asymmetric searchable encryption (ASE) schemes which support two special features, namely message recovery and flexible search authorization. With this new primitive, a data owner can keep his data encrypted under his public key and assign different search privileges to third-party servers. In the security model, we define the standard IND-CCA security against any outside attacker and define adapted ciphertext indistinguishability properties against inside attackers according to their functionalities. Moreover, we take into account the potential information leakage from trapdoors, and define two trapdoor security properties. Employing the bilinear property of pairings and a deliberately-designed double encryption technique, we present a provably secure instantiation of the primitive based on the DLIN and BDH assumptions in the random oracle model.