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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2011/525}},
      url = {https://eprint.iacr.org/2011/525}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.