Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors
Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors
复制标题
DOI：
10.1007/978-3-642-39059-3_9
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Atsushi Takayasu;N. Kunihiro
中科院分区：
文献类型：
--
作者：
Atsushi Takayasu;N. Kunihiro
在CaLC 2001上，Howgrave-Graham提出了多项式时间算法，用于求解单变量线性方程，模取已知复合整数的未知因子，即所谓的部分近似公因数问题。到目前为止，在密码分析的背景下，已经考虑了该问题的两种多元推广形式。第一种是联立模单变量线性方程，其多项式时间算法由Cohn和Heninger在ANTS 2012上提出。第二种是模多元线性方程，其多项式时间算法是由Herrmann和May在Asiacrypt 2008上提出的。这两种算法都涵盖了单变量情况下的Howgrave-Graham算法。另一方面，在根界的渐近情况下，这两个多元问题也变得与Howgrave-Graham问题相同。然而，在这种情况下，以前的算法并没有涵盖Howgrave-Graham算法。在本文中，我们介绍了考虑根界大小的自然算法构造策略。我们算出了在构造格时多项式的选择。我们的算法优于所有已知的解决多元方程的攻击，并且可以推广到任意数量的变量的情况。我们的算法为一些与RSA密码系统相关的应用实现了更好的密码分析边界。
At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.