The Factoring Cryptopocalypse
daemonology.net
daemonology.net
For what it's worth, Tom Ritter recently posted his notes on de-anonymizing alt.anonymous.messages[1], something widely believed to be very anonymous and very secure. It's an interesting read and shows why you not only need the crypto to be sound, but the implementation and your own use of it to be right too.
From a theory point of view, breaking a crypto-system typically means something like being able to do the following fast (i.e., in polynomial time): Given two plaintexts and a ciphertext which is the encryption of one of those two plaintexts, decide which of the plaintexts it is. Of course you could flip a coin, so the essential condition is that your success probability must be larger than 1/2.
So to show that a crypto-system is secure, you have to show that the problem of breaking it cannot be solved in polynomial time. We simply do not know how to show that any useful problem cannot be solved in polynomial time (we do know that P != EXPTIME, but we don't know any problems in EXPTIME that would be useful for cryptography). Hence the lack of provable security.
Intuitively, NP-hard problems are believed to be harder than factorization and discrete log. And so it should be easier to prove that an NP-hard problem is not in P.
What you are referring to is the opposite direction of the implication, which is very relevant in a discussion of why people have failed to find faster algorithms for integer factorization. However, the question I replied to is essentially why people have failed to prove that integer factorization (and discrete log) are hard problems.
Edit: After re-reading my previous comment, perhaps this clarifies it best: Integer factorization and discrete log are probably less hard than NP-hard problems. However, the meta-problem "prove that integer factorization or discrete log is really, unconditionally hard" is at least as difficult as the meta-problem "prove P != NP".
1. At the base, we need a one-way function [1], something that's easy to compute in one direction but hard to reverse. For example, it is believed to be much easier to multiply two large primes than to factor the result back into the original two primes. However so far nobody has come up with a way of proving that a function is one-way for any plausible definition. This is often, in the popular press, thought to be the P=NP question, but that would only prove the negative: if P=NP, then there are no one-way functions (for a certain definition). But even if P!=NP were proven, it is still not necessarily the case that there are one-way functions. In particular, NP-complete problems are not automatically one-way functions, because that is only a worst-case hardness notion, and cryptosystems that are only unbreakable in the worst case for the attacker are not so useful [2] (and indeed none of the major cryptosystems currently used rely on NP-complete problems).
In short, the seemingly hard problems that have had practical cryptosystems built out of them, such as integer factorization (closed related to the RSA problem) and the discrete logarithm problem on elliptic curves (ECC) only seem hard, but are not proven hard in any rigorous sense. This is an interesting outstanding question mathematically, because it would be nice if we understood either why these are hard and be able to prove them hard for some definition, or else to discover why they in fact aren't.
2. At the practical level, it's hard to produce a security proof that takes into account an attack completely outside the conception of the original framework. For example, early security proofs were completely oblivious to the problem of side-channel attacks, since they were proving the security of certain mathematical procedures, in a framework that did not countenance things like "your mathematical procedure might be run on an EC2 instance where your attacker can also get a VM and collect some (noisy) data about what it's doing". This is arguably a quite different question from whether the fundamental cryptosystem's approach is flawed, but this kind of consideration is the source of many practical attacks.
You might wonder if something closer to Merkle's approach could be improved to produce a larger gap, but the answer turns out to be no: http://www.boazbarak.org/Papers/merkle.pdf
"While he was at Bell Labs, Shannon proved that the cryptographic one-time pad is unbreakable in his classified research that was later published in October 1949" - http://en.wikipedia.org/wiki/Claude_Shannon
They can also be made to decrypt to any plaintext string
However, OTP does not scale to more than two or three people, they don't work at all on very large messages as the key has to be as large as the message and they have authentication issues. For two people sending small messages, one-time pads are ideal and if the pads are created, used and destroyed correctly, the encryption is, indeed, unbreakable.
Modern symmetric ciphers solve the "you need to securely exchange as much key material as you wish to send data" using mathematical formulas to stretch key material. Asymmetric ciphers use mathematical formulas to fix "you need a secure way to exchange keys."
Unfortunately, the math can't be probably secure, only believed secure and proved insecure.
With cell phones so widespread, I wondered why someone doesn't write a one time pad app. People could share gigabyte-sized pads via trusted wireless or a cable if they prefer.
If lots of people adopted one-time pads it might hinder NSA et al but this would be akin to trying to convince people to wear masks whenever they are in public to hinder monitoring with CCTV.