Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm The question stems from the fact that foundations of crypto states:
suppose breaking an encryption scheme is NP-complete, then P != NP implies that this encryption is hard to break in the worst case, but does not rule out the possibility that it can be broken almost always.
How can this be true, if the encryption is NP-complete breaking should take super-polynomial time no?
The Merkle–Hellman knapsack cryptosystem (Wikipedia article) is the canonical example of this.  It was designed to rely on the difficulty of the subset sum problem, which is NP-complete.  However, while NP-complete means, under the P ≠ NP hypothesis, that there is no polynomial-time algorithm to guarantee a solution for every input, that doesn't mean the legitimate user can efficiently generate keys or ciphertexts for which all polynomial-time algorithms to decrypt ciphertexts or recover keys will fail with nonnegligible probability.  And it turns out that the knapsack cryptosystem is easily breakable.

Now, it is not always the case that cryptosystems with relations to NP-complete or NP-hard problems are practically breakable.  For example, the McEliece cryptosystem (Wikipedia article), whose decryption is related to the NP-hard problem of decoding general linear codes, has withstood scrutiny of decades, and modern parametrizations are not known to be breakable even with a quantum computer.

For more about P = NP and crypto, see also an earlier post I wrote on the usefulness of asymptotic cost analyses versus concrete cost analyses.  The brief summary is that even if P = NP, that fact may nevertheless have no practical consequences for cryptography.