A favorite question of mine — not that I’ve worked on it, just that I think more people should be working on it — is whether we can prove the existence of a (very weak) one-way function . I’m interested in an unconditional result here, but I’m willing to weaken the conditions significantly:
- I only want the difficulty of inverting to be harder than the difficulty of computing (measured in terms of, say, gate complexity), I don’t care how much harder it is. (The inversion problem is not immediately well-defined if is not a permutation, but one can define things appropriately or restrict to that are permutations.)
- If it helps, we can look at hardness of inverting in the worst-case, rather than the average-case.
- Even a non-constructive proof would be interesting. We know, non-constructively, that there exist functions that are exponentially hard. To the best of my knowledge there is no analogous result stating that there exist functions harder to invert than to compute.
Seems like a natural question, no? Yet the only work on this topic of which I am aware are the following two papers:
- A paper by Hiltgen in Asiacrypt ’92 shows an explicit function which is (provably and unconditionally) about twice as hard to invert as to compute.
- Followup work by Hirsh and Nikolenko shows some form of (very weak) trapdoor function, which is easier to invert (by a constant factor) with trapdoor than without.
I’m especially surprised by the fact that there is no non-constructive existence proof. Note that such a proof would not necessarily settle any outstanding complexity questions (like P vs. NP), so there’s no inherent reason to think it’s impossible. My guess is that people just haven’t looked at it much.