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 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.