On Wed, Feb 13, 2013 at 8:47 PM, Warren Smith <warren.wds@gmail.com> wrote:
Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y).
For example, if F maps (a,b,c) to (b^a mod c, b, c) where gcd(b,c)=1, then many people think/hope that Finverse is a lot harder than F ("discrete logarithm problem").
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
The problem is that what you'd really like is an example where F can be computed in polyomial time, but Finverse cannot. But if F is in P, then Finverse is in NP, so proving that any F has this property is at least as hard as proving that P != NP. Andy