<p>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 <a href="http://www.cs.technion.ac.il/~yuvali/pubs/AIK04.ps">Cryptography in NC$^0$</a> paper.</p>

<p>Two specific examples include:</p>

<p>Integer multiplication (there are some subtleties for standard OWF, but if you only care about worst-case this is enough)</p>

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

CC BY-SA 3.0
2013-09-01T20:06:11.040Z
Thanks Emanuele. This answers the Logspace case. Just for completeness, Could you list some of those functions in your answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-09-01T23:14:34.617Z
I've added two examples.
Manu
CC BY-SA 3.0
2013-09-02T13:35:27.903Z
Thanks a lot Emanuele. Is there an insight that explains the hardness of inverting those functions (by LOGSPACE algorithms)?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-09-01T15:04:41.593Z
2013-09-01T23:14:19.757Z
2013-09-01T23:14:19.757Z
Manu
<p>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.</p>

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

<blockquote>
  <p>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)}$)?</p>
</blockquote>

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

CC BY-SA 3.0
2013-09-01T10:01:09.307Z
Have you seen http://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
CC BY-SA 3.0
2013-09-01T11:49:35.580Z
The abstract does not help but thanks for your help.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-09-01T16:33:37.760Z
Oh well -- I hope the new answer does though. :)
Daniel Apon
CC BY-SA 3.0
2013-09-01T20:39:18.960Z
Yep, It does :)
Mohammad Al-Turkistany
<cc.complexity-theory><one-way-function>
One-way functions with respect to various resource bounds
Mohammad Al-Turkistany
# One-way functions with respect to various resource bounds

(Asked by: username_0 on 2013-08-30)

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.

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

> **Comments:**
> **username_1**: Have you seen http://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.  
> **username_0**: The abstract does not help but thanks for your help.  
> **username_1**: Oh well -- I hope the new answer does though. :)  
> **username_0**: Yep, It does :)  

---

## 1 answers

### Answer by username_2 on 2013-09-01. Score: 11 | Accepted answer

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$](http://www.cs.technion.ac.il/~yuvali/pubs/AIK04.ps) paper.

Two specific examples include:

Integer multiplication (there are some subtleties for standard OWF, but if you only care about worst-case this is enough)

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

> **Comments:**
> **username_0**: Thanks Emanuele. This answers the Logspace case. Just for completeness, Could you list some of those functions in your answer.  
> **username_2**: I've added two examples.  
> **username_0**: Thanks a lot Emanuele. Is there an insight that explains the hardness of inverting those functions (by LOGSPACE algorithms)?  

---

