International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Solving Generalized Small Inverse Problems

Noboru Kunihiro
Search ePrint
Search Google
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.
  title={Solving Generalized Small Inverse Problems},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / cryptanalysis, lattice techniques, RSA},
  note={This is a full version of ACISP2010 paper. 14721 received 19 Apr 2010, last revised 21 Apr 2010},
  author={Noboru Kunihiro},