Hiding information and signatures in trapdoor knapsacks
- 1 September 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 24 (5) , 525-530
- https://doi.org/10.1109/tit.1978.1055927
Abstract
The knapsack problem is an NP-complete combinatorial problem that is strongly believed to be computationally difficult to solve in general. Specific instances of this problem that appear very difficult to solve unless one possesses "trapdoor information" used in the design of the problem are demonstrated. Because only the designer can easily solve problems, others can send him information hidden in the solution to the problems without fear that an eavesdropper will be able to extract the information. This approach differs from usual cryptographic systems in that a secret key is not needed. Conversely, only the designer can generate signatures for messages, but anyone can easily check their authenticity.Keywords
This publication has 10 references indexed in Scilit:
- Secure communications over insecure channelsCommunications of the ACM, 1978
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)IEEE Transactions on Information Theory, 1978
- Fast approximation algorithms for knapsack problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- New directions in cryptographyIEEE Transactions on Information Theory, 1976
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975
- A high security log-in procedureCommunications of the ACM, 1974
- A user authentication scheme not requiring secrecy in the computerCommunications of the ACM, 1974
- Computing Partitions with Applications to the Knapsack ProblemJournal of the ACM, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972