Paper Info
Title
Solving low density subset sum problems
Abstract
The subset sum problem is to decide whether or not the 0-1 integer programming problem Σi=1n aixi = M; all 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. We propose an algorithm which when given an instance of the subset sum problem searches for a solution. 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. Lovász to attempt to find v. We analyze the performance of the proposed algorithm. 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 ≪ .645 the vector v we are searching for is the shortest nonzero vector in the lattice. We prove that for "almost all" problems of density d ≪ 1/n 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
1983
10.1109/SFCS.1983.70
Tucson, AZ, USA
Keywords
DocType
ISSN
One-Bit Disclosures,trapdoor pseudo-random number generator,provably secure protocol,low density subset sum,new technique
Conference
0272-5428
ISBN
Citations 
PageRank 
0-8186-0508-1
9
2.57
References 
Authors
0
2
Name
Order
Citations
PageRank
J. C. Lagarias1563235.61
A. M. Odlyzko2414183.74