Darren New <dne### [at] sanrrcom> wrote:
> I imagine it can be done. I just don't imagine it's easy to come up with a 
> system like that, nor that it's easy to prove a mathematical problem is easy 
> with the key and NP-hard without.

  One thing is certain: Creating a truly secure encryption system based on
an NP-hard algorithm is far from trivial. For example, all of these are
based on known NP-hard problems, yet can be cracked in a matter of weeks
with some hundreds of computers:

http://en.wikipedia.org/wiki/McEliece_cryptosystem
http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
http://en.wikipedia.org/wiki/Naccache%E2%80%93Stern_knapsack_cryptosystem

  It seems that research on "future-proof" encryption systems which cannot
be cracked quickly even by a quantum computer is a hot topic of research,
and cryptosystems based on NP-hard problems is one line of study, but it's
actually surprisingly hard to come up with an actual cryptosystem which
cannot be cracked even with regular computers (much less quantum computers).

-- 
                                                          - Warp

Post a reply to this message