13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel Apon Sep 1 '13 at 10:01
  • $\begingroup$ The abstract does not help but thanks for your help. $\endgroup$ – Mohammad Al-Turkistany Sep 1 '13 at 11:49
  • $\begingroup$ Oh well -- I hope the new answer does though. :) $\endgroup$ – Daniel Apon Sep 1 '13 at 16:33
  • $\begingroup$ Yep, It does :) $\endgroup$ – Mohammad Al-Turkistany Sep 1 '13 at 20:39
11
$\begingroup$

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.

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

$\endgroup$
  • $\begingroup$ Thanks Emanuele. This answers the Logspace case. Just for completeness, Could you list some of those functions in your answer. $\endgroup$ – Mohammad Al-Turkistany Sep 1 '13 at 20:06
  • $\begingroup$ I've added two examples. $\endgroup$ – Manu Sep 1 '13 at 23:14
  • $\begingroup$ Thanks a lot Emanuele. Is there an insight that explains the hardness of inverting those functions (by LOGSPACE algorithms)? $\endgroup$ – Mohammad Al-Turkistany Sep 2 '13 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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