Solving low-density subset sum problems
- 1 January 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (1), 229-246
- https://doi.org/10.1145/2455.2461
Abstract
The subset sum problem is to decide whether or not the 0-l integer programming problem Σ n i=l a i x i = M , ∀I , x I = 0 or 1, has a solution, where the a i 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 /log 2 (max i a i ). Then for “almost all” problems of density d < 0.645, the vector v we searched for is the shortest nonzero vector in the lattice. For “almost all” problems of density d < 1/ 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 < d c ( n ), where d c ( 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 d c ( n ), as n → ∞.Keywords
This publication has 10 references indexed in Scilit:
- The Computational Complexity of Simultaneous Diophantine Approximation ProblemsSIAM Journal on Computing, 1985
- Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature schemeIEEE Transactions on Information Theory, 1984
- Embedding cryptographic trapdoors in arbitrary knapsack systemsInformation Processing Letters, 1983
- On the complexity of finding short vectors in integer latticesLecture Notes in Computer Science, 1983
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- Minkowskische Reduktionsbedingungen für positiv definite quadratische Formen in 5 VariablenMonatshefte für Mathematik, 1982
- Cryptology in TransitionACM Computing Surveys, 1979
- Hiding information and signatures in trapdoor knapsacksIEEE Transactions on Information Theory, 1978
- A Fortran Multiple-Precision Arithmetic PackageACM Transactions on Mathematical Software, 1978
- How to calculate shortest vectors in a latticeMathematics of Computation, 1975