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,...,x_n) = x_0h(x_1,..., 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.
展开▼
机译：我们引入了一个“广义小逆问题（GSIP）”，并提出了一种解决该问题的算法。GSIP 的表述为为 n 变量多项式 h、非零整数 C 和 M 找到 f（x_0， x_1,...,x_n） = x_0h（x_1,..., x_n） + C = 0（mod M） 的小解。我们的算法基于基于晶格的Coppersmith技术。我们提供了一种求解 f = 0 的格基构造策略，该策略由求解 h = 0 的格基系统地转换而来。然后，我们推导一个上限，使得目标问题可以在对数 M 的多项式时间内以显式形式求解。由于GSIP包含一些与RSA相关的问题，因此我们的算法适用于它们。例如，Boneh 和 Durfee 的小键攻击会自动重新找到。
展开▼
