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

1 Answer 1

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

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.