Comment by WCSTombs

Sorry, I don't think this is true. There is basically no useful proven lower bound on the complexity of breaking popular cryptosystems. The math is absolutely not understood. In fact, it is one of the most poorly understood areas of mathematics. Consider that breaking any classical cryptosystem is in the complexity class NP, since if an oracle gives you the decryption key, you can break it quickly. Well we can't even prove that NP != P, i.e., that there even exists a problem where having such an oracle gives you a real advantage. Actually, we can't even prove that PSPACE != P, which should be way easier than proving NP != P if it's true.