Welcome to the resource topic for 2016/353
Title:
General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA
Authors: Atsushi Takayasu, 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.
ePrint: https://eprint.iacr.org/2016/353
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 .