3 ms·
>Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial. Interestingly, that's the basis of the (now broke
by SilasX 10y ago
>Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial.
Interestingly, that's the basis of the (now broken) Knapsack cryptosystem -- your private key is an easy knapsack, and you convert it to the public key -- a hard knapsack -- via modular multiplication. You encode your message by your choice of which items from the hard knapsack to add to the sum, which becomes the ciphertext.
https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
- hackcasual 10y agoHave you checked out lattice based crypto? It's the spiritual successor to merkel-hellman, based on the hardness of subset sum. I've got a rough presentation from when I talked about it at a reading group: https://docs.google.com/presentation/d/1_kLJ7M_7HKrzN0auz0-zOLImqzhhX9TX8xrQA71zwNA/edit?usp=sharing https://docs.google.com/presentation/d/1_kLJ7M_7HKrzN0auz0-z...
- SilasX 10y agoInteresting! I didn't know they were related. Thanks!