[aparent]

What do mean by this? I don't think complexity classes give any provable security to asymmetric cryptography. It cannot be proven that the difficulty of breaking any of the currently used (or known?) asymmetric key cryptography is not in P (It can't even be proven to be NP-complete).

[charrisku]

This.

[wolfgke]

Asymmetric crypto clearly is in NPcomplete. What one can not prove yet is that some crypto system is in NPcomplete \ P (since this would imply P != NP).

[aparent]

> Asymmetric crypto clearly is in NPcomplete

To be in NP-complete a problem must both be in NP and every problem in NP must have a polynomial time reduction to it. This means that NP-complete is fully contained in NP and in fact smaller if P!=NP.

For example P is contained in NP and if P!=NP then no problems in P are in NP-complete.

[wolfgke]

Sorry, I was typing NPcomplete and meant NP. :-(