On Optimal Bounds of Small Inverse Problems and Approximate GCD Problems with Higher Degree
On Optimal Bounds of Small Inverse Problems and Approximate GCD Problems with Higher Degree
复制标题
DOI：
10.1007/978-3-642-33383-5_4
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
N. Kunihiro
中科院分区：
文献类型：
--
作者：
N. Kunihiro
我们证明了一个小的反问题和近似GCD问题的最优界之间的关系。首先，我们提出了一个基于格的方法来解决小的反问题，具有较高的程度。该问题是Boneh和Durfee对RSA密码系统的小秘密指数攻击的自然推广。他们将这种攻击简化为求解二元模方程：，其中A是给定的整数，而de是公共指数。证明了当n ≤N0.292时，该问题可以在多项式时间内求解.本文将Boneh-Durfee的结果推广到更一般的问题。对于次数为κ（≥ 1）的一元多项式h（y），integersCande，我们想找到二元模方程的所有小根：我们用X和Y表示根的上界。我们给出了一个求解该问题的算法，并证明了该问题可以在多项式时间内求解，如果|C|是足够小的，其中X =eγ，Y =eα。我们采用了类似的方法，解开线性化技术介绍了赫尔曼和梅，特别是评估的晶格体积。有趣的是，我们的算法并不排除C = 0的情况，这意味着我们的算法可以解决一元未知模方程，其中p是未知的。我们的算法达到了文献中的最佳界限。然后，我们证明了我们得到的界在类似Howgrave-Graham在CaLC 2001中讨论的意义下是自然的，并且在合理的假设下，我们证明了我们的界，包括Boneh-Durfee的界，是最优的。
We show a relation between optimal bounds of a small inverse problem and an approximate GCD problem. First, we present a lattice based method to solve small inverse problems with higher degree. The problem is a natural extension of small secret exponent attack on RSA cryptosystem introduced by Boneh and Durfee. They reduced this attack to solving a bivariate modular equation:, whereAis a given integer andeis a public exponent. They proved that the problem can be solved in polynomial time whend≤N0.292. In this paper, we extend the Boneh–Durfee’s result to more general problem. For a monic polynomialh(y) of degreeκ( ≥ 1), integersCande, we want to find all small roots of a bivariate modular equation:. We denote byXandYthe upper bound of roots. We present an algorithm for solving the problem and prove that the problem can be solved in polynomial time ifand |C| is small enough, whereX=eγandY=eα. We employ a similar approach as unravelled linearization technique introduced by Herrmann and May in especially evaluating the lattice volume. Interestingly, our algorithm does not rule out the case ofC= 0, which implies that our algorithm can solve a univariate unknown modular equation, wherepis unknown. Our algorithm achieves the best bound in the literature. Then, we show that our obtained bound isnaturalunder the similar sense of Howgrave-Graham’s discussion in CaLC2001 and we prove that our bound, including Boneh–Durfee’s bound, is optimal under the reasonable assumption.