<p>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.</p>

<p>For super-fast crypto, you may want the one-way function to be computable in restricted models. Here a great <a href="http://www.wisdom.weizmann.ac.il/~bennyap/pubs/nc0-full.pdf">result</a> 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).</p>

CC BY-SA 2.5
2010-08-25T17:29:19.617Z
2010-08-25T17:29:19.617Z
Manu
<p>Let me start with traditional definition of one-way function (with polynomials): </p>

<p>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,</p>

<p>$Pr[f(A(f(x))) = f(x)] &lt; \frac{1}{p(n)}$</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-25T12:49:51.803Z
2010-08-25T13:11:54.790Z
2010-08-25T13:11:54.790Z
Grigory Yaroslavtsev
<p>For instance, A function that is computable but not invertable in log space, Is it one-way function?</p>

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

<cc.complexity-theory><space-bounded><one-way-function>
What are the different notions of one-way functions?
Mohammad Al-Turkistany
# What are the different notions of one-way functions?

(Asked by: username_0 on 2010-08-25)

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)

**Tags:** cc.complexity-theory, space-bounded, one-way-function


---

## 2 answers

### Answer by username_1 on 2010-08-25. Score: 7 | Accepted answer

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](http://www.wisdom.weizmann.ac.il/~bennyap/pubs/nc0-full.pdf) 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 by username_2 on 2010-08-25. Score: 5

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.


---

