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

### Like this:

Like Loading...

*Related*

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)}

By:

lucaon September 15, 2009at 10:20 pm

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

By:

Vinodon September 15, 2009at 10:37 pm

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

By:

noamon September 16, 2009at 3:34 am

noam, I think you mean:

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

By:

ryanwon September 16, 2009at 4:28 am

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!

By:

jonkatzon September 16, 2009at 7:13 am

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 🙂

By:

Edward A. Hirschon September 16, 2009at 7:37 am

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

By:

lucaon September 16, 2009at 12:22 pm

Edward, thanks for your comments.

I believe the Massey slides you are talking about are these. (Please correct me if I am wrong.)

According to this blog, the best current circuit lower bound (for arbitrary basis) is 5n-o(n).

By:

jonkatzon September 17, 2009at 5:37 pm

This is probably a stupid question but what is the difference between proving lower bound on the running time of any algorithm for a problem and circuit lower bounds? Don’t we know of a plenty of “optimal algorithms” for different problems which have superlinear running time?

By:

Anonymouson September 17, 2009at 6:33 pm

Jon, thanks for the reference; however, the Iwama et al. 5n-o(n) bound mentioned in the comment there is for (single output circuit in) AND-OR-NOT basis, and the blog says about some 4.5-o(n) bound without giving a reference and I believe it is for the same model. (Please let me know if I missed anything.)

By:

Edward A. Hirschon September 18, 2009at 2:35 am

Note to self: remember this blog.

By:

Jimon February 17, 2010at 5:11 am