The Brave New World of Bodacious Assumptions in Cryptography (2010) [pdf]
ams.org
ams.org
For example, RSA is based on the integer factoring problem, but they are not equivalent. Vanilla RSA does not offer what they call "chosen-ciphertext security"; in fact, a careful plaintext padding scheme† is needed to approximate this property.
PKCS#1v1.5 padding is not that scheme††: it formats the plaintext with a fixed leading byte (or two). This puts implementers in a tricky spot - what do you do if you decrypt a message and the prefix is wrong? If your answer was "throw an error", then congratulations! You've completely compromised the security of RSA.
They reference this attack briefly on page two of the linked article; grep for "Bleichenbacher". For more information, you can find Bleichenbacher's description of his padding oracle attack on PKCS#1 here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19..... I'll go further and say that implementing this attack is fun and enlightening - it's well worth your time.
† The scheme I'm alluding to is OAEP, but even it has implementation pitfalls that can sometimes be exploited.
†† But it is (bafflingly) the default padding scheme in every RSA library I can think of.
It is very important to remember that there is really next to no theoretical basis for the existence of cryptography at all. It's completely an applied field.
Likewise, if someone builds a physical architecture that solves prohibitively impractical cryptographic problems easily through a different means (e.g. quantum computing) then if it is cheap, nobody will care about the theoretical strength of the algorithm on classical computers.
The point is simply that there are assumed-hard problems and cryptographic constructions based on them. If there is wiggle room between these things (as in RSA), it can severely undermine the strength of the system.
This is why proofs are valuable: if you can prove the cryptographic construct is reducible to the underlying problem†, you can focus your attention on the problem. I feel much better worrying about the practicality of quantum computers than whether there's a plaintext recovery attack that runs in a million queries.
† This isn't a panacea, unfortunately, as side channels are still a concern. Also: conformance of implementation to what has been proven.
There's still no problem useful for public key encryption with a provable lower bound on solution work effort. Public-key encryption started with the knapsack problem, which turned out to have an efficient solution. Factoring is assumed to be hard because much mathematical effort has gone into studying factoring with only limited published success. It's not like there's a provable lower bound for it.
The only thing we really know works is a one-time pad, and even that can be screwed up by operational errors. A "one-time pad" used twice is easy to break. It's worth reconsidering one-time pads; in the era of the 64GB flash drive for $30, you could have enough one time pad for a thousand hours of voice calls on one USB stick.