Paper 2011/525
A Note on the Density of the Multiple Subset Sum Problems
Yanbin Pan and Feng Zhang
Abstract
It is well known that the general subset sum problem is NP-complete. However, almost all subset sum problems with density less than $0.9408\ldots$ can be solved in polynomial time with an oracle that can find the shortest vector in a special lattice. In this paper, we give a similar result for the multiple subset sum problems which has $k$ subset sum problems with the same solution. Some extended versions of the multiple subset sum problems are also considered. In addition, a modified lattice is involved to make the analysis much simpler than before.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- LatticeLow-DensityMultiple Subset Sum ProblemMultiple Modular Subset Sum Problem.
- Contact author(s)
- panyanbin @ amss ac cn
- History
- 2011-10-18: revised
- 2011-09-26: received
- See all versions
- Short URL
- https://ia.cr/2011/525
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/525, author = {Yanbin Pan and Feng Zhang}, title = {A Note on the Density of the Multiple Subset Sum Problems}, howpublished = {Cryptology {ePrint} Archive, Paper 2011/525}, year = {2011}, url = {https://eprint.iacr.org/2011/525} }