Prove complexity bound without reduction?

The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the complexity of the reduction itself).

In particular, I'm thinking about the fact that breaking RSA encryption is believed to be at least as difficult as factoring a composite number into primes, but nobody has ever figured out how to express prime factorization in terms of RSA decryption. My question is: if somebody wanted to go about proving that breaking RSA is at least as difficult as prime factorization without relying on reduction, what techniques might be available to them?

• While a proof may not need to involve a reduction, the very notion of hardness is usually defined in terms of reducibility. That being said, descriptive complexity theory may serve as an example for how one might prove class membership without a reduction. Feb 19 '18 at 1:34