CryptoDB
Solving Generalized Small Inverse Problems
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2010-23122,
title={Solving Generalized Small Inverse Problems},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / cryptanalysis, lattice techniques, RSA},
url={http://eprint.iacr.org/2010/221},
note={This is a full version of ACISP2010 paper. kunihiro@k.u-tokyo.ac.jp 14721 received 19 Apr 2010, last revised 21 Apr 2010},
author={Noboru Kunihiro},
year=2010
}