Paper 2016/353
General Bounds for Small Inverse Problems and Its Applications to MultiPrime 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<(72\sqrt{7})/6\approx{0.284}. In the same work, the bound was further improved to \delta<11/\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<12(\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 MultiPrime RSA with small prime differences.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Minor revision. ICISC 2014
 Contact author(s)
 atakayasu @ it k utokyo ac jp
 History
 20160406: received
 Short URL
 https://ia.cr/2016/353
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/353, author = {Atsushi Takayasu and Noboru Kunihiro}, title = {General Bounds for Small Inverse Problems and Its Applications to MultiPrime {RSA}}, howpublished = {Cryptology ePrint Archive, Paper 2016/353}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/353}}, url = {https://eprint.iacr.org/2016/353} }