Name
Abstract | ||
|---|---|---|
The subset sum problem is to decide whether or not the 0-l integer programming problem &Sgr;ni=l aixi = M, ∀I, xI = 0 or 1, has a solution, where the ai and M are given positive integers. This problem is NP-complete, and the difficulty of solving it is the basis of public-key cryptosystems of knapsack type. An algorithm is proposed that searches for a solution when given an instance of the subset sum problem. This algorithm always halts in polynomial time but does not always find a solution when one exists. It converts the problem to one of finding a particular short vector v in a lattice, and then uses a lattice basis reduction algorithm due to A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz to attempt to find v. The performance of the proposed algorithm is analyzed. Let the density d of a subset sum problem be defined by d = n/log2(maxi ai). Then for “almost all” problems of density d d n, it is proved that the lattice basis reduction algorithm locates v. Extensive computational tests of the algorithm suggest that it works for densities d dc(n), where dc(n) is a cutoff value that is substantially larger than 1/n. This method gives a polynomial time attack on knapsack public-key cryptosystems that can be expected to break them if they transmit information at rates below dc(n), as n → ∞. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1145/2455.2461 | Journal of the ACM (JACM) |
Keywords | Field | DocType |
particular short vector v,low-density subset sum problem,additional key words and phrases: knapsack public-key cryptosystem,lattice basis reduction algorithm,proposed algorithm,locates v,integer lattice,k. lenstra,subset sum problems,knapsack public-key cryptosystems,h. w. lenstra,knapsack type,l' algorithm,subset sum problem,0-l integer programming problem,testing,approximation algorithms,algorithm design and analysis,lattice basis reduction,public key cryptography,polynomial time,tin,lattices,polynomials,additives,zinc,linear programming,cryptography | Integer,Approximation algorithm,Discrete mathematics,Combinatorics,Subset sum problem,Polynomial,Linear programming,Knapsack problem,Time complexity,Mathematics,Lattice reduction | Journal |
Volume | Issue | ISSN |
32 | 1 | 0004-5411 |
Citations | PageRank | References |
129 | 29.20 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. C. Lagarias | 1 | 563 | 235.61 |
| A. M. Odlyzko | 2 | 414 | 183.74 |