On breaking generalized knapsack public key cryptosystems

ABSTRACT

In this paper new methods, generalizing those of Shamir, are presented for attacking generalizations of the basic system. It is shown how these methods may be applied to the Graham-Shamir public-key crypto-system [2], and the iterated Merkle-Hellman public-key cryptosystem. We are unable to present a rigorous proof that the attacks presented here are effective. However, in the case of the Graham-Shamir system, the methods have been implemented and have performed well in tests. The method of attack uses recent results of Lenstra, Lenstra, and Lovasz [5]. The cryptanalytic problem is treated as a lattice problem rather than a linear programming one as in Shamir's result.

REFERENCES

• 1: W. Diffie, and N. Hellman, New Directions in Cryptography, IEEE Trans: Information Theory, IT-22-6, November, 1976.
• 2: A. Lempel, Cyrptology in Transition: A Survey, Program 134-45-90, Discrete Mathematics Department, Digital Techniques Laboratory, Sperry Research Center (1978).
• 3: Lagarias, J., Knapsack-Type Public Key Cryptosystems and Dcophantine Approximation, (abstract).
• 4: J. Lagarias, The Computational Complexity of Simultaneous Dcophantine Approximation Problems, Proceedings 23rd Foundations of Computer Science Conference (1982) pg. 32.
• 5: A.K. Lenstra, H.W. Lenstra, Jr., and L. Lovasz, Factoring Polynomials with Rational Coefficients, Report 82-05, Mathematics Institute, University of Amsterdam, March 1982.
• 6: K.L. Manders and L. Adleman, NP-Complete Decision Problems for Binary Quadratics, J. Computer and Systems Science 16 (1978), 168-184.
• 7: R. Merkle, N. Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, IT-24-5, September, 1978.
• 8: A. Shamir, A Polynomial Time Algorithm for Breaking Merkle-Hellman Cryptosystems, Proceedings 23rd Foundations of Computer Science Conference (1982).
• 9: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory