Darren New wrote:
> Kevin Wampler wrote:
>> commonly used encryption algorithms which are believed to be NP-hard to 
> 
> Diffie Hellman is based on discrete log. Isn't that NP?
> 

Yes, although not in the way that you mean.  It's trivially shown to be 
in NP in the sense that many things are in NP which are not NP-hard (for 
instance anything in P is also in NP).  Although that's a common 
misconception, both discrete log and integer factorization are not 
believed to be NP-hard problems.  Hence the worry that quantum computers 
would break these cryptographic methods despite the face that very few 
people believe that they'd be able to solve NP-complete problems in 
polynomial time.

Post a reply to this message