Abstract
In view of the known difficulty in solving NP-hard problems, a natural question is whether there exist cryptosystems which are NP-hard to crack. In Section I we display two such systems which are based on the knapsack problem. However, the first one, which is highly "linear" has been shown by Lempel to be almost always easy to crack. This shows that NP-hardness of a cryptosystem is not enough. Also, it provides the only natural problem we know of, which is NP-hard and yet almost always easy to solve. The second system is a form of a "double knapsack" and so far has resisted the cryptanalysis efforts.
In Section 2 a Public-Key Crypto-System (PKCS) is defined, and evidence is given that no such system can be NP-hard to break. This relates to the work of Brassard, et al. [2, 11], but the definition of PKCS leads us to a different cracking problem, to which Brassard's technique still applies, after proper modification.
This paper is based on two research reports, written by the authors in July 1979. It was supported in part by the Army Research Office under Grant No. DAAG29-79-C-0054.
Part of this research was done while the author visited the E.E. Department-Systems, University of Southern California, Los Angeles, CA., U.S.A.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Diffie, W. and Hellman, M.E., "New Directions in Cryptography", IEEE Transactions on Information Theory, Vol. 22, 1976, pp. 644–654.
Brassard, G., Fortune, S., and Hopcroft, J., "A Note on Cryptography and NP ∩ CoNP-P", TR78-338, Dept. of Comp. Sci., Cornell University.
Karp, R.M., "Reducibility Among Combinatorial Problems", in R.E. Miller and J.W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85–104.
Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
Aho, A.V., Hopcroft, J.E. and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
Even, S., Graph Algorithms, Computer Science Press, 1979.
Lempel, A., "Cryptology in Transition", Computing Surveys, December 1979.
Cook, S.A., "The Complexity of Theorem Proving Procedures", Proceedings 3rd Am. ACM Symposium on Theory of Computing, ACM, 1971, pp. 151–158.
Rivest, R.L., Shamir, A., and Adleman, L., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Comm. ACM 21, February 1978, pp. 120–126.
Merkle, R., and Hellman, M., "Hiding Information and Signatures in Trapdoor Knapsack", IEEE Transactions on Information Theory. Vol. IT-24, September 1978, pp. 525–530.
Brassard, G., "A Note on the Complexity of Cryptography", IEEE Transactions on Information Theory. Vol. IT-25, March 1979, pp. 232–233.
Ginsburg, S., private communication.
Ullian, J.S., "Partial Algorithm Problems for Context Free Languages". Information and Control, Vol. 11, 1967, pp. 80–101.
Brassard, G., "Relativized Cryptography". Proceedings of 20th FOCS, Puerto Rico 1979.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1980 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Even, S., Yacobi, Y. (1980). Cryptocomplexity and NP-completeness. In: de Bakker, J., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 1980. Lecture Notes in Computer Science, vol 85. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10003-2_71
Download citation
DOI: https://doi.org/10.1007/3-540-10003-2_71
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-10003-4
Online ISBN: 978-3-540-39346-7
eBook Packages: Springer Book Archive