Paper 2016/353

General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA

Atsushi Takayasu and Noboru Kunihiro

Abstract

In 1999, Boneh and Durfee introduced the {\em small inverse problem}, which solves the bivariate modular equation x(N+y)\equiv1 \pmod{e}. Absolute values of solutions for x and y are bounded above by X=N^{\delta} and Y=N^{\beta}, respectively. They solved the problem for \beta={1/2} in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when \delta<(7-2\sqrt{7})/6\approx{0.284}. In the same work, the bound was further improved to \delta<1-1/\sqrt{2}\approx{0.292}. Thus far, the small inverse problem has also been analyzed for an arbitrary \beta. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound \delta<1-\sqrt{\beta}. However, the algorithm works only when \beta\geq1/4. When 0<\beta<1/4, there have been several works where the authors claimed their results are the best. In this paper, we revisit the problem for an arbitrary \beta. At first, we summarize the previous results for 0<\beta<1/4. We reveal that there are some results that are not valid and show that Weger's algorithms provide the best bounds. Next, we propose an improved algorithm to solve the problem for 0<\beta<1/4. Our algorithm works when \delta<1-2(\sqrt{\beta(3+4 \beta)}-\beta)/3. Our algorithm construction is based on the combinations of Boneh and Durfee's two forms of lattices and it is more natural compared with previous works. For the cryptographic application, we introduce small secret exponent attacks on Multi-Prime RSA with small prime differences.