On the existence (and non-existence) of reductions in cryptography

[Amitabh Saxena]

Suppose I have computational problems A and B which both seem to be
hard but problem A appears to be harder than problem B. For
instance, I can reduce B to A using an oracle but not the other way
round. Is there any way to prove this for sure (say by constructing a
decisional problem C using A and B and than proving that if A reduces
to B than C is easy)

I wanted to know if there are any mathematical tool (eg. like random
oracle model) to prove that some problem is provably NOT as hard as
other problem.

Essentially, I want to prove the "opposite" of what normally the random
oracle model is used for (to prove that a given problem is as hard as
some other problem).

I would appreciate if someone can point me in the right direction on
how to prove that one problem is definitely EASIER than the other,
although both of them are computationally hard.

[David Wagner]

Post by Amitabh Saxena
Suppose I have computational problems A and B which both seem to be
hard but problem A appears to be harder than problem B. For
instance, I can reduce B to A using an oracle but not the other way
round. Is there any way to prove this for sure

Yes. Prove that if there exists any scheme solving problem A, then there
exists a scheme that solves problem A and doesn't solve problem B. This
is known as a "separation"; there are tons of papers in the cryptographic
literature that provide not only implications (via a reduction) but also
separations (by proving a theorem of the form I listed above).