**Solving Generalized Small Inverse Problems**

*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.

**Category / Keywords: **public-key cryptography / cryptanalysis, lattice techniques, RSA

**Publication Info: **This is a full version of ACISP2010 paper.

**Date: **received 19 Apr 2010, last revised 21 Apr 2010

**Contact author: **kunihiro at k u-tokyo ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20100428:134327 (All versions of this report)

**Short URL: **ia.cr/2010/221

[ Cryptology ePrint archive ]