# What are the different notions of one-way functions?

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)

## 2 Answers

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

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.