Cryptology ePrint Archive: Report 2010/221

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