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

what about hash functions? length increasing (non-decreasing) criteria rules those out, but they're still important to cryptographers via same intuition and then some

ReplyDeleteThey have some similar properties as one-way functions with some extra conditions. If you want to go into depth on cryptographic functions, I suggest Oded Goldreich's foundations.

ReplyDelete