Darren New wrote:
>>> 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). 
> 
> Well, obviously that's what I meant. I just wasn't being pedantic.

I figured, I commented on it more for the benefit of other people who 
might be following along and who are less familiar with the area :)


> So, no, I don't know of any crypto algorithms that depend on p!=np.

I wonder why this is.  It seems like it would be (relatively) 
straightforward to construct an encryption method which would be NO-hard 
to crack, so there must be a reason why this doesn't seem to be done. 
Perhaps instances of NP-hard problems tend to be much harder to analyze 
and predict the properties of, and thus it's easier to get an encryption 
algorithm which is susceptible to attacks in practice, despite the 
appearance of stronger theoretical guarantees.

Post a reply to this message