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.

Advertisements

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

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

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

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

  11. Note to self: remember this blog.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: