Paper 2010/221 Original: eprint.iacr.org/2010/221 ↗
Solving Generalized Small Inverse Problems
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_0, x_1, \ldots , x_n)=x_0 h(x_1, \ldots , x_n)+C=0 (\bmod \; 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 are 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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2010-04-28: last updated
- 2010-04-28: published
- Short URL
- https://ia.cr/2010/221
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2010/221,
author = {Noboru Kunihiro},
title = {Solving Generalized Small Inverse Problems},
howpublished = {Cryptology {ePrint} Archive, Paper 2010/221},
year = {2010},
url = {https://eprint.iacr.org/2010/221}
}