> In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound.

Actually, integer factorization already has subexponential-time algorithms, such as the General Number Field Sieve (GNFS).