> Many attempts have been made to construct public-key encryption systems based on problems known to be NPC, but it always seems that adding the necessary trap-

> Many attempts have been made to construct public-key encryption systems based on problems known to be NPC, but it always seems that adding the necessary trap-door reduces the difficulty of the problem to sub-NPC. RSA and Diffie-Hellman-Merkle-Williamson key negotiation rely on the difficulty of factoring and discrete logarithms respectively, but these are known (or believed - not sure of the current state) to be sub-NPC. A clarification here is that these rely upon the existence of one way functions, of which discrete logarithms and factoring are conjectured to be in. A proof of the existence of one way functions is actually a slightly stronger result than P!=NP (as it relates to languages with only a single accepting state rather than many. The name of the class escapes me and Complexity Zoo is unresponsive at the moment)