Is it possible to use the knapsack problem for digital signatures? What I am imagining is something like the Merkle–Hellman knapsack cryptosystem, but used for digital signing, rather than encryption. It seems that the knapsack problem is well suited to the task of demonstrating authenticity, but I can't quite figure out how it might be done.
Asked
Active
Viewed 426 times
1
-
Is this for fun or for an actual product? If the latter, don't. Use a standardized digital signature (RSA, DSA, etc). Instances of knapsack crypto have been broken over the years (including Merkel-Hellman). Not saying it would be impossible to do. If you just want to do it for fun, I think the original Merkle-Hellman paper describes signatures. – mikeazo Jan 14 '14 at 16:05
-
Thanks, I'll check out that paper. This is just for fun. Some friends of mine and I want to implement a cryptocurrency (based on block chain, like Bitcoin) which is simple enough to perform transactions by hand. Then we'd play Minecraft, doing all item trades through the cryptocurrency. The goal would be something like collect the most resources, either by gathering them in game, trading for them, or cheating the currency system to swindle your way to the top, the only rules being no calculators or computers. – Void Star Jan 14 '14 at 22:39
-
Sort of like Monopoly with hacking, cheating, and the ability to slay other players in game. – Void Star Jan 14 '14 at 22:42