What are the different notions of one-way functions?

Question

For instance, A function that is computable but not invertable in log space, Is it one-way function?

What are the known definitions of one-way functions? (especially the ones that do not invoke polynomials)

Answer 1

Usually one-way functions are used for crypto, and so you want that no efficient adversary can invert the function. Identifying efficient adversaries with randomized polynomial-time, you get the typical notion of security which talks of randomized poly-time machines. But of course you can think of different security notions.

For super-fast crypto, you may want the one-way function to be computable in restricted models. Here a great result by Applebaum, Ishai, and Kushilevitz shows that a poly-time computable OWF implies a OWF where each output bit depends on just O(1) input bits (which is arguably one of the simplest computational models you can think of).

Answer 2

Let me start with traditional definition of one-way function (with polynomials):

A function '$f: {0, 1}^* \rightarrow {0, 1}^*$' is one-way if f can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm A,

$Pr[f(A(f(x))) = f(x)] < \frac{1}{p(n)}$

for every polynomial p(n) and sufficiently large n, assuming that x is chosen from the uniform distribution on ${0, 1}^n$ and the randomness of A.