="Warren Smith" <warren.wds@gmail.com> 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).
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
Dhananjay S. Phatak pointed out to me (then I improved by consulting Joerg Arndt's book...) that the "Gray coding" problem is a provable (pitifully weak, but provable) example.
Funny you should mention this--coincidentally today I was recalling that long ago Whit Diffie mentioned something about proving the existence of trap door functions being one of the open problems in public key cryptography. Whit, are you lurking, and inclined to replace my vague amnesia with facts?