Solving low-density subset sum problems

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 < 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 < 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 → ∞.

REFERENCES

• 1: Leonard M. Adleman, On breaking generalized knapsack public key cryptosystems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.402-412, December 1983 [doi>10.1145/800061.808771]
• 2: AFFLERBACH, U Minkowskische Reduktionsbedingungen fiir positiv definite quadratische Formen in 5 Variabeln. Monatsh. Math. 94 (1982), 1-8.
• 3: Richard P. Brent, A Fortran Multiple-Precision Arithmetic Package, ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.57-70, March 1978 [doi>10.1145/355769.355775]
• 4: BRENTJES, A.J. Multi-dimensional continued fraction algorithms. Mathematical Centre Tract No. 145, Matematisch Centrum, Amsterdam, The Netherlands, 1981.
• 5: BRICKELL, E. Are most low density knapsacks solvable in polynomial time? In Proceedings of the 14th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1983. Congressus Numerantium, Vol. 39, 1983, pp. 145-156.
• 6: DIETER, U.How to calculate shortest vectors in a lattice. Math. Comput. 29 (1975), 827-833.
• 7: FERGUSON, H. R. P., AND FORCADE, R. W.Multidimensional Euclidean algorithms. J. reine angew. Math. 344 (1982), 171-181.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Erich Kaltofen, On the complexity of finding short vectors in integer lattices, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.236-244, March 28-30, 1983
• 10: J. C. Lagarias, The computational complexity of simultaneous diophantine approximation problems, SIAM Journal on Computing, v.14 n.1, p.196-209, Feb. 1985 [doi>10.1137/0214016]
• 11: LAGARIAS, J.C.Knapsack-type public key cryptosystems and Diophantine approximation, (Extended Abstract). In Advances in Cryptology, Proceedings of CRYPTO-83 (Santa Barbara, Aug.), D. Chaum, Ed. Plenum, New York, 1984, pp. 3-24.
• 12: Abraham Lempel, Cryptology in Transition, ACM Computing Surveys (CSUR), v.11 n.4, p.285-303, Dec. 1979 [doi>10.1145/356789.356792]
• 13: LENSTRA, A.K., I.ENSTRA, H.W., JR., AND LOVASZ, L.Factoring polynomials with rational coefficients. Math. Annalen 261 (1982), 515-534.
• 14: MAZO, J.E., AND ODLYZKO, A.M.Lattice points in high-dimensional spheres, paper in preparation.
• 15: MERKLE, R.C., AND HELLMAN, M.E.Hiding information and signatures in trap-door knapsacks. IEEE Trans. Inf. Theory IT-24 (1978), 525-530.
• 16: ODLYZKO, A.M.Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme. IEEE Trans. Inf. Theory IT-30, 4 (July I984), 584-601.
• 17: SHAMIR, A.A polynomial time algorithm for breaking the Merkle-Hellman cryptosystem. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 145-152.
• 18: SHAMIR, A.Embedding cryptographic trapdoors in arbitrary knapsack systems. Inf. Proc. Lett. 17 (1983), 77-79.
• 19: WILF, H.S.Backtrack: An O( 1 ) expected time algorithm for the graph coloring problem. Inf. Proc. Lett. 18 (1984), 11'9-121.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Design, Measurement, Performance, Security, Theory, Verification