What is a *one-way function*, intuitively a function that is easy to compute and hard to invert? Taking this intuitive idea to a formal definition has yield two quite different meanings, sometimes causing confusion.The first directly tries to translate the intuition. A function f is one-way if

- f is 1-1 (so an inverse is unique),
- f is length increasing (so the output of the inverse function is not too large),
- f is computable in polynomial time, and
- there is no polynomial-time computable g such that for all x, g(f(x))=x.

A function is r(n)-secure one-way if

- There is a function l(n)≥n such that f maps strings of length n to strings of length l(n),
- f is computable in polynomial time, and
- for all probabilistic polynomial-time algorithms A, the probability that f(A(f(x)))=f(x) is at most r(n) where the probability is taken over x chosen uniformly from the strings of length n and the random coins used by A.

At one point I tried using complexity-theoretic one-way functions and cryptographic one-way functions to distinguish the two, but this only caused confusion. So we have to live with the fact that we have these two definitions with the same name and we'll have to just use context to figure out which definition is appropriate. If you give a talk or write a paper about one-way functions, it never hurts to distinguish which version you are talking about.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 9/29/2003 04:21:30 PM

Powered by Blogger Pro