Posted by: jonkatz | September 15, 2009

## Do there exist (very weak) one-way functions?

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 $f$. I’m interested in an unconditional result here, but I’m willing to weaken the conditions significantly:

• I only want the difficulty of inverting $f$ to be harder than the difficulty of computing $f$ (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 $f$ is not a permutation, but one can define things appropriately or restrict to $f$ that are permutations.)
• If it helps, we can look at hardness of inverting $f$ 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:

1. 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.
2. 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.

## Responses

1. Even a very weak non-constructive result would settle a major complexity-theoretic open question.

Suppose Circuit-SAT is solvable by linear-size circuits. Then every function f() computable with t(n) gates can be inverted by an inverter that uses O(t(n)) gates.

Even a superlinear gap between complexity of evaluation and inversion would translate into a superlinear circuit lower bound for Circuit-SAT.

Proving a superlinear circuit lower bound for a problem in NP remains a major open question. For that matter, we don’t know how to prove a superlinear circuit lower bound for any problem in NE, the class of problems solvable by non-deterministic turing machines in time 2^{O(n)}

2. If you measure hardness in terms of circuit-depth, then it is easy to come up with such functions. Here is a (I assume well-known) function that is computable in NC0, but hard to invert by any AC0 circuit on the average (it is even a permutation):

f(x1,..,xn) = (x1, x1\xor x2, …, x_{n-1}\xor x_n)

Inverting it (even, computing x_n from the output) is as hard as computing parity of n bits.

-Vinod

3. There is also a result (I forgot the author and reference) of a function in NC0 that is P-hard to invert.

4. noam, I think you mean:

Johan Håstad: One-Way Permutations in NC0. Inf. Process. Lett. 26(3): 153-155 (1987)

5. Luca – you are right. But the trivial reduction shows that (if Curcuit-SAT has linear-size circuits then) every function f() computable with t(n) gates can be inverted by an inverter that uses O(n \cdot t(n)) gates, no? So one could hope for a function taking time n to compute and time n^{3/2} to invert.

Vinod – I had seen this example before, but thanks for reminding me of it.

Noam, Ryan – thanks for the reference!

6. Dear Jonathan and everyone,

It is not hard to see that most functions are *not at all* one-way, that is, the complexity of computing and the complexity of inverting are within a constant factor of each other (see slides of John Massey’s talk available on the net somewhere). Thus, there is not much hope for a non-constructive proof (at least, for a proof for a randomly selected function).

For proving a much better factor than two (say, five 🙂 ) for “one-way” functions, one needs to prove a very good circuit lower bound, and I am not aware of such bounds (though N.Blum gave [in 80s] a 3n-o(n) bound for predicates, it only translates to 4n-o(n) for n-bit functions; I am not aware of any improvements).

–Edward
P.S. My name is spelled with sCh 🙂

7. Even a superlinear lower bound for the *search* version of circuit-SAT would be new (right?), and if you work with the search version you don’t lose the factor of n