论文标题
解决一类硬子集问题：与分解技术的晶格攻击的整合
Tackling A Class of Hard Subset-Sum Problems: Integration of Lattice Attacks with Disaggregation Techniques
论文作者
论文摘要
子集问题属于NP类，并在复杂性理论和基于背包的密码系统中都起着重要作用，当所谓的密度接近一个时，文献中已证明这在文献中变得最困难。晶格攻击在文献中被认为是最有效的方法，即使未知变量的数量中等大小时，也有时会失败。在本文中，我们提出了一种模块化分解技术和简化的晶格公式，基于两个晶格攻击算法的设计。我们在分类技术中介绍了新的概念“跳跃点”，并得出不平等条件以识别出较高的跳跃点，这些跳跃点可以更容易截止不可避免的短整数解决方案。 Empirical tests have been conducted to show that integrating the disaggregation technique with lattice attacks can effectively raise success ratios to 100% for randomly generated problems with density one and of dimensions up to 100. Finally, statistical regressions are conducted to test significant features, thus revealing reasonable factors behind the empirical success of our algorithms and techniques proposed in this paper.
Subset-sum problems belong to the NP class and play an important role in both complexity theory and knapsack-based cryptosystems, which have been proved in the literature to become hardest when the so-called density approaches one. Lattice attacks, which are acknowledged in the literature as the most effective methods, fail occasionally even when the number of unknown variables is of medium size. In this paper we propose a modular disaggregation technique and a simplified lattice formulation based on which two lattice attack algorithms are further designed. We introduce the new concept "jump points" in our disaggregation technique, and derive inequality conditions to identify superior jump points which can more easily cut-off non-desirable short integer solutions. Empirical tests have been conducted to show that integrating the disaggregation technique with lattice attacks can effectively raise success ratios to 100% for randomly generated problems with density one and of dimensions up to 100. Finally, statistical regressions are conducted to test significant features, thus revealing reasonable factors behind the empirical success of our algorithms and techniques proposed in this paper.
