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

Atsushi TAKAYASU; Noboru KUNIHIRO

doi:10.1587/transfun.E100.A.50

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

Atsushi TAKAYASU, Noboru KUNIHIRO

Full Text Views

0

Share
Cite this

Summary :

In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=N^δ and Y=N^β, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<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 β. At first, we summarize the previous results for 0<β<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<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.1 pp.50-61

Publication Date: 2017/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E100.A.50

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Authors

Atsushi TAKAYASU
the University of Tokyo,National Institute of Industrial Science and Technology (AIST)
Noboru KUNIHIRO
the University of Tokyo

Keyword

LLL algorithm, Coppersmith's method, the small inverse problem, cryptanalysis, multi-prime RSA

Cite this

Copy

Atsushi TAKAYASU, Noboru KUNIHIRO, "General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA" in IEICE TRANSACTIONS on Fundamentals, vol. E100-A, no. 1, pp. 50-61, January 2017, doi: 10.1587/transfun.E100.A.50.
Abstract: In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=N^δ and Y=N^β, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<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 β. At first, we summarize the previous results for 0<β<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<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.50/_p

Copy

@ARTICLE{e100-a_1_50,
author={Atsushi TAKAYASU, Noboru KUNIHIRO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA},
year={2017},
volume={E100-A},
number={1},
pages={50-61},
abstract={In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=N^δ and Y=N^β, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<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 β. At first, we summarize the previous results for 0<β<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<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/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.},
keywords={},
doi={10.1587/transfun.E100.A.50},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 50
EP - 61
AU - Atsushi TAKAYASU
AU - Noboru KUNIHIRO
PY - 2017
DO - 10.1587/transfun.E100.A.50
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2017
AB - In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=N^δ and Y=N^β, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<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 β. At first, we summarize the previous results for 0<β<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<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/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.
ER -