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
Knapsack problemComputer scienceKey (lock)CryptographyTheoretical computer scienceComputer securityAlgorithm
Affiliated Institutions
Related Publications
Solving large knapsack problems with a genetic algorithm
This paper develops a new approach to finding solutions to the subset sum problem. The subset sum problem is an important NP-complete problem in computer science which has appli...
An orthogonal genetic algorithm for multimedia multicast routing
Many multimedia communication applications require a source to send multimedia information to multiple destinations through a communication network. To support these application...
Quantum cryptography using any two nonorthogonal states
Quantum techniques for key distribution---the classically impossible task of distributing secret information over an insecure channel whose transmissions are subject to inspecti...
Privacy Amplification by Public Discussion
In this paper, we investigate how the use of a channel with perfect authenticity but no privacy can be used to repair the defects of a channel with imperfect privacy but no auth...
A method for obtaining digital signatures and public-key cryptosystems
An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two import...
Publication Info
- Year
- 1978
- Type
- article
- Volume
- 24
- Issue
- 5
- Pages
- 525-530
- Citations
- 805
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
805
OpenAlex
Cite This
Ralph C. Merkle,
Martin E. Hellman
(1978).
Hiding information and signatures in trapdoor knapsacks.
IEEE Transactions on Information Theory
, 24
(5)
, 525-530.
https://doi.org/10.1109/tit.1978.1055927
Identifiers
- DOI
- 10.1109/tit.1978.1055927