Welcome to the resource topic for 2010/221
Title:
Solving Generalized Small Inverse Problems
Authors: Noboru Kunihiro
Abstract:We introduce a ``generalized small inverse problem (GSIP)‘’ and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of f(x_0, x_1, \ldots , x_n)=x_0 h(x_1, \ldots , x_n)+C=0 (\bmod \; M) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f=0, which are systematically transformed from a lattice basis for solving h=0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in \log M in an explicit form. Since GSIPs include some RSA related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.
ePrint: https://eprint.iacr.org/2010/221
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .