# One-way functions with respect to various resource bounds

Informally, one-way functions are defined with respect to PTIME algorithms. They are computable in polynomial time but not invertible in average-case polynomial time. The existence of such functions is an important open problem in theoretical computer science.

I'm interested in one-way functions (not necessarily for cryptographic applications) defined with respect to different resource bounds. Such resource bounds could be LOGSPACE or bounded nondeterminism.

Is there a candidate (natural) problem which is one-way with respect to LOGSPACE algorithms? Is there a candidate (natural) problem which is one-way with respect to nondeterministic linear time algorithms ($\text{NTIME(n)}$)?

I'm fine with worst-case hardness of invertiblity with respect to the above resource bounds.

• Have you seen eprint.iacr.org/2013/001.pdf ? The topic of this paper may or may not be exactly relevant to you, but the techniques in the paper (or perhaps even the citations) may lead to something useful. – Daniel Apon Sep 1 '13 at 10:01
• The abstract does not help but thanks for your help. – Mohammad Al-Turkistany Sep 1 '13 at 11:49
• Oh well -- I hope the new answer does though. :) – Daniel Apon Sep 1 '13 at 16:33
• Yep, It does :) – Mohammad Al-Turkistany Sep 1 '13 at 20:39

Regarding log-space: Several candidate one-way functions are computable in log-space or below (and are supposedly secure even against poly-time adversaries). You can find several pointers for example in the Cryptography in NC$^0$ paper.
The Impagliazzo-Naor candidate based on subset-sum: $f(a_1,...,a_n,S) := (a_1,..., a_n, \sum_{i \in S} a_i \mod 2^n)$.