Warp wrote:
>   The vast majority of modern cryptography uses algorithms which have been
> proven to be NP, and their security relies on the assumption that P != NP.

Technically, I don't think this is true.  Symmetric cyphers aren't based on 
NP problems.  DH is based on discrete log which I think is NP, but RSA is 
based on an NP problem *with* a trap door, yes? Otherwise it would be hard 
for everyone.  I was pretty sure most of the algorithms involve something 
that *would* be NP if it weren't for trap doors, but again maybe I'm 
misremembering. This isn't really my domain.

>   (Of course there's still the possibility that a new discovered physical
> phenomenon can be used to solve NP problems fast with enormously massive
> parallelism or other weirdness.)

There's always that. It's only NP for Turing machines.

-- 
Darren New, San Diego CA, USA (PST)
    C# - a language whose greatest drawback
    is that its best implementation comes
    from a company that doesn't hate Microsoft.

Post a reply to this message