J. C. Lagarias
Abstract
The subset sum problem is to decide whether or not the 0-l integer programming problem Σ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 → ∞.
- 1 ADLEMAN, L.M. the 15th ACM SjmTposium on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New York, 1983, 402-412. Google Scholar
- 2 AFFLERBACH, U Minkowskische Reduktionsbedingungen fiir positiv definite quadratische Formen in 5 Variabeln. Monatsh. Math. 94 (1982), 1-8.Google Scholar
- 3 BRENT, R.P. A Fortran multiple-precision arithmetic package. ACM Trans. Math. Sofiw. 4, 1 (Mar. 1978), 57-70. Google Scholar
- 4 BRENTJES, A.J. Multi-dimensional continued fraction algorithms. Mathematical Centre Tract No. 145, Matematisch Centrum, Amsterdam, The Netherlands, 1981.Google Scholar
- 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.Google Scholar
- 6 DIETER, U.How to calculate shortest vectors in a lattice. Math. Comput. 29 (1975), 827-833.Google Scholar
- 7 FERGUSON, H. R. P., AND FORCADE, R. W.Multidimensional Euclidean algorithms. J. reine angew. Math. 344 (1982), 171-181.Google Scholar
- 8 GAREY, M.R., AND JOHNSON, D.S.Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman and Co., San Francisco, 1979. Google Scholar
- 9 KALTOFEN, E.On the complexity of finding short vectors in integer lattices. In Computer Algebra: Proceedings of EUROCAL '83, European Computer Algebra Conference, J. A. VanHulzen, Ed. Lecture Notes in Computer Science, vol. 162. Springer-Verlag, New York, 1983, pp. 236-244. Google Scholar
- 10 LAGARIAS, J.C.The computational complexity of simultaneous Diophantine approximation problems. SIAM J Comput. 14 (1985), to be published. Google Scholar
- 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.Google Scholar
- 12 LEMPEL, A. Cryptography in transition: A survey. Comput. Surv. 11 (1979), 285-304. Google Scholar
- 13 LENSTRA, A.K., I.ENSTRA, H.W., JR., AND LOVASZ, L.Factoring polynomials with rational coefficients. Math. Annalen 261 (1982), 515-534.Google Scholar
- 14 MAZO, J.E., AND ODLYZKO, A.M.Lattice points in high-dimensional spheres, paper in preparation.Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- 18 SHAMIR, A.Embedding cryptographic trapdoors in arbitrary knapsack systems. Inf. Proc. Lett. 17 (1983), 77-79.Google Scholar
- 19 WILF, H.S.Backtrack: An O( 1 ) expected time algorithm for the graph coloring problem. Inf. Proc. Lett. 18 (1984), 11'9-121.Google Scholar
Index Terms
- Solving low-density subset sum problems
Recommendations
Solving low density subset sum problems
SFCS '83: Proceedings of the 24th Annual Symposium on Foundations of Computer ScienceThe 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 ...
An improved low-density subset sum algorithm
EUROCRYPT'91: Proceedings of the 10th annual international conference on Theory and application of cryptographic techniquesThe general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on ...
Chosen-Ciphertext Security from Subset Sum
Proceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 9614We construct a public-key encryption PKE scheme whose security is polynomial-time equivalent to the hardness of the Subset Sum problem. Our scheme achieves the standard notion of indistinguishability against chosen-ciphertext attacks IND-CCA and can be ...
Reviews
Eugene D. Denman
This paper discusses the subset sum problem: :9I where a i and M are integers. This problem is NP-complete and is related to the public-key cryptosystem of the knapsack type. The authors propose a short vector lattice method (Algorithm SV) where a set of basis vector b i is constructed for an n+1 dimensional lattice L = L( a, M). A reduced basis is then computed using the L 3 algorithm of Lenstra, Lenstra, and Lova´sz [1]. The authors show that “almost all problems of densities d < 0.645 and d < 1/ n can be solved by the SV algorithm. The paper includes an analysis of the algorithm as well as some computational results. The paper should be of interest to researchers working on data encryption.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments