On the cryptocomplexity of knapsack systems

ABSTRACT

A recent trend in cryptographic systems is to base their encryption/decryption functions on NP-complete problems, and in particular on the knapsack problem. To analyze the security of these systems, we need a complexity theory which is less worst-case oriented and which takes into account the extra conditions imposed on the problems to make them cryptographically useful. In this paper we consider the two classes of one-to-one and onto knapsack systems, analyze the complexity of recognizing them and of solving their instances, introduce a new complexity measure (median complexity), and show that this complexity is inversely proportional to the density of the knapsack system. The tradeoff result is based on a fast probabilistic knapsack solving algorithm which is applicable only to one-to-one systems, and it indicates that knapsack-based cryptographic systems in which one can both encrypt and sign messages are relatively insecure. We end the paper with new results about the security of some specific knapsack systems.

REFERENCES

• 1: B. Arazi, private communication.
• 2: J. Cassels, "An Introduction to Diophantine Approximation", Cambridge University Press, 1965.
• 3: W. Diffie and M. Hellman, "New Directions in Cryptography", IEEE Trans. Information Theory, November 1976.
• 4: W. Feller, "An Introduction to Probability Theory and Its Applications", John Wiley & Sons, 1968.
• 5: Ellis Horowitz , Sartaj Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM (JACM), v.21 n.2, p.277-292, April 1974 [doi>10.1145/321812.321823]
• 6: R. Karp, "Reducibility Among Combinatorial Problems", in "Complexity of Computer Computations" (ed. R. Miller and J. Thatcher), Plenum Press, 1972.
• 7: Abraham Lempel, Cryptology in Transition, ACM Computing Surveys (CSUR), v.11 n.4, p.285-303, Dec. 1979 [doi>10.1145/356789.356792]
• 8: W. LeVeque, "Fundamentals of Number Theory", Addison-Wesley, 1977.
• 9: R. Merkle and M. Hellman, "Hiding Information and Receipts in Trap Door Knapsacks", IEEE Trans. Information Theory, September 1978.
• 10: M. Rabin, "Digitalized Signatures and Public Key Functions As Intractable as Factorization", to appear in CACM.
• 11: 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]
• 12: A. Shamir, "A Fast Signature Scheme", MIT/LCS/TM-107, July 1978.
• 13: L. Stockmeyer, "The Polynomial-Time Hierarchy", TCS, October 1976.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Management, Security, Theory