Solving low-density multiple subset sum problems with SVP oracle

被引：7

作者：

Pan Yanbin ^{[1
]}

Zhang Feng ^{[1
]}

机构：

[1] Chinese Acad Sci, Acad Math & Syst Sci, NCMIS, Key Lab Math Mechanizat, Beijing 100190, Peoples R China

来源：

JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY | 2016年 / 29卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Lattice; low-density; multiple modular subset sum problem; multiple subset sum problem; LATTICE BASIS REDUCTION; ALGORITHMS; KNAPSACKS;

D O I：

10.1007/s11424-015-3324-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is well known that almost all subset sum problems with density less than 0.9408 center dot center dot center dot can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice. In this paper, the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution. Specially, for the single subset sum problem (k = 1), a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before. Moreover, some extended versions of the multiple subset sum problem are also considered.

引用

页码：228 / 242

页数：15

共 18 条

[1]

[Anonymous], 1990, Cryptology and Computational Number Theory, DOI 10.1090/psapm/042

[2]

[Anonymous], 1979, COMPUT INTRACTABILIT

[3]

Cohen H., 1996, A Course in Computational Algebraic Number Theory

[4]

Coster MJ, 1992, COMPUT COMPLEX, V2, P111