| 引用本文： |
-
陈义杰,吕克伟,申培松,陈驰.子集和问题格基归约算法研究[J].信息安全学报,已采用 [点击复制]
- Chen Yijie,Lv Kewei,Shen Peisong,Chen Chi.A Study on Lattice Reduction Algorithm for the Subset Sum Problem[J].Journal of Cyber Security,Accept [点击复制]
|
|
| 摘要: |
| 子集和问题(Subset sum problem, SSP)是计算理论和密码学中的经典问题，其求解算法在许多领域应用广泛。子集和问题格基归约算法是基于格求解子集和问题的算法，其通过访问给定范数下最短向量问题(Shortest vector problem, SVP) oracle，对子集和问题求解。目前该类算法主要是围绕某些特殊情形的子集和问题开展的，求解一般情形下子集和问题的格基归约算法研究较少。本文证明，给定l_p范数下SVP ( SVPp ) oracle，可以多项式时间内求解n个正整数a_1,\ldots,a_n的子集和问题，其中n<2^{p-1}。这给出了子集和问题到SVPp的更精细归约。由此，本文给出一个新的基于SVPp oracle求解子集和问题的秩约减确定算法，它不需要对SSP的密度、正整数的分布等有条件约束，适用于一般情况下的子集和问题，且可以选择性的优先寻找包含指定某些a_i的解。另一方面，对任意指定a_i，若存在包含a_i的解，本文证明可通过调用一次SVPp oracle找到该解。进一步，我们将该方法拓展到模子集和问题，并得到了类似的结果。基于SVPp oracle，给出n(n<2^{p-1}-1)个正整数的模子集和问题的求解算法，并证明通过调用一次SVPp oracle即可找到包含指定a_i的一个解。本文归约一定程度上体现了SVP的困难性，帮助我们更好的认识SVP的复杂性。 |
| 关键词: 子集和问题 最短向量问题 格基归约 |
| DOI： |
| 投稿时间：2023-11-21修订日期：2024-03-28 |
| 基金项目:密码科学技术国家重点实验室开放课题 |
|
| A Study on Lattice Reduction Algorithm for the Subset Sum Problem |
|
Chen Yijie, Lv Kewei, Shen Peisong, Chen Chi
|
| (Institute of Information Engineering，Chinese Academy of Sciences) |
| Abstract: |
| The Subset Sum Problem (SSP) is a classical problem within the realms of computational theory and cryptography, with its solving algorithms being broadly applied across various fields. The lattice basis reduction algorithm for the subset sum problem, which relies on the lattice to solve the subset sum problem, constitutes a vital category of solution methodologies. These algorithms operate by interfacing with an oracle for the Shortest Vector Problem (SVP) within a specified norm. Currently, research on such algorithms mainly addresses special-case instances of the subset sum problem, with little exploration into algorithms for lattice basis reduction that can tackle the general version of the subset sum problem. This paper proves that for a set of n positive integers a_1,\ldots,a_n where n is less than 2^{p-1}, the subset sum problem can be solved in polynomial time using an SVPp oracle (SVP oracle under l_p norm). This represents a more refined reduction of the subset sum problem to the shortest vector problem. Building on this, the paper introduces a new deterministic rank-reduction algorithm based on the SVPp oracle to solve the subset sum problem without imposing conditions on the density, distribution, or other characteristics of positive integers, making it suitable for the general subset sum problem instances. The algorithm can also selectively prioritize finding solutions that contain certain specified elements a_i. On another note, for any specified integer a_i, the paper demonstrates that if a solution that includes a_i exists, it can be ascertained with a single invocation of the SVPp oracle. Moreover, we extend this approach to the modular subset sum problem. For the modular subset sum problem involving n positive integers where n is less than 2^{p-1}-1, the paper offers an algorithm predicated on the SVP oracle under l_p norm and proves that a solution including a specific a_i can be identified with just one call to the SVPp oracle. The reductions presented in this paper to some extent reflect the difficulty intrinsic to SVP, aiding in a better understanding of the complexity of the shortest vector problem. |
| Key words: Subset Sum Problem Shortest Vector Problem Lattice Reduction |
