Solving Generalized Small Inverse Problems

Noboru KUNIHIRO

doi:10.1587/transfun.E94.A.1274

Solving Generalized Small Inverse Problems

Noboru KUNIHIRO

Full Text Views

0

Cite this

Summary :

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₀, x₁, ..., x_n)=x₀ h(x₁, ..., x_n)+C=0 (mod ; 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 is 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.6 pp.1274-1284

Publication Date: 2011/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E94.A.1274

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Noboru KUNIHIRO, "Solving Generalized Small Inverse Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E94-A, no. 6, pp. 1274-1284, June 2011, doi: 10.1587/transfun.E94.A.1274.
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₀, x₁, ..., x_n)=x₀ h(x₁, ..., x_n)+C=0 (mod ; 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 is 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.1274/_p

Copy

@ARTICLE{e94-a_6_1274,
author={Noboru KUNIHIRO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Solving Generalized Small Inverse Problems},
year={2011},
volume={E94-A},
number={6},
pages={1274-1284},
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₀, x₁, ..., x_n)=x₀ h(x₁, ..., x_n)+C=0 (mod ; 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 is 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.},
keywords={},
doi={10.1587/transfun.E94.A.1274},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Solving Generalized Small Inverse Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1274
EP - 1284
AU - Noboru KUNIHIRO
PY - 2011
DO - 10.1587/transfun.E94.A.1274
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2011
AB - 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₀, x₁, ..., x_n)=x₀ h(x₁, ..., x_n)+C=0 (mod ; 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 is 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.
ER -