Hiding information and signatures in trapdoor knapsacks

TLDR

The knapsack problem is NP‑complete and generally hard, and this approach exploits it without requiring a secret key. Instances that are hard without trapdoor information let the designer embed hidden data in solutions and generate signatures, while others can send such hidden data and anyone can verify the signatures.

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.