[cantos]

Apparently it is very hard to prove results in average case complexity theory. We don't even know if computational problems that are hard on average assuming P!=NP exist, let alone actually designing a cryptosystem out of one.

[mjn]

There actually are a few "average-case complete" problems. The field was started with this 1986 paper: http://epubs.siam.org/doi/abs/10.1137/0215020

It's true that we don't seem to know how to build a cryptosystem out of them. Part of it is that a cryptosystem needs something stronger than average-case complete, a property more like every instance being hard (possibly excluding trivially easy instances that can be detected and filtered out).

[cantos]

Average-case complexity is a not a topic I know a lot about, and I can't easily get the paper itself, but what the abstract seems to say is that for some particular NP complete problem, if an efficient average case algorithm exists for that problem then efficient average case algorithms exist for all NP complete problems. There is no mention of showing that such an algorithm does not exist.

My reference is Impagliazzo's 1995 survey paper "A Personal View of Average-Case Complexity" where he lays out five possible worlds based on open problems in complexity theory. He calls the world where P!=NP but all NP problems are easy on average "Heuristica." This is still an open problem as far as I know.

On your second point I can say a bit more. Cryptosystems in general do not need all instances to be hard. With RSA for example, there are all kinds of weird attacks, like the modulus n can easily be factored if phi(n) or phi(phi(n)) are products of small primes. There is no need to filter out these cases because the probability of them occurring is so small. There are cryptosystems where an arbitrary instance of the problem is as hard as the average case. This was a notable selling point for lattice cryptosystems when they were first invented.

In the RSA case the probability of these corner case attacks decreases with the size of the instance. So for current parameters the probability is near zero. However, even if you only had a scheme where the probability didn't diminish with the instance size and there are attacks that you can't check for, you can still securely send messages. Say the probability that your key generation algorithm gives you an instance that is hard is 50% (or any constant). You can securely send messages with arbitrarily small probability of having your message decrypted by using multiple keys and breaking up your message with a secret sharing scheme (Shamir's for example) and encrypting each message share with each of the keys. The attacker, able to only get a constant number of decrypted message shares will not be able to get decrypt your message.